2016年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題A卷

1、2016年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題（A卷）*學(xué)科、專業(yè)名稱：計算機科學(xué)與技術(shù)、軟件工程研究方向：計算機系統(tǒng)結(jié)構(gòu)081201，計算機軟件與理論081202，計算機應(yīng)用技術(shù)081203，軟件工程083500，計算機技術(shù)(專業(yè)學(xué)位) 085211，軟件工程(專業(yè)學(xué)位) 085212考試科目名稱及代碼：數(shù)據(jù)結(jié)構(gòu)830考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。 一、 單項選擇題(每題2分，共30分) 1. 在線索化二叉樹中，T所指結(jié)點沒有左子樹的充要條件是（ ）。 A. T-> lchild=NULL B. T->ltag=1 C. t->ltag=

2、1且t-> lchild =Null D. 以上都不對2. 一個帶有頭結(jié)點的單鏈表為空的判定條件是 ( )。A. head = NULL B. head->next = NULLC. head->next = head D. head != NULL3. 線性鏈表不具有的特點是（ ）。A. 隨機訪問 B. 不必預(yù)估所需存儲空間大小C. 插入與刪除時不必移動元素 D. 所需空間與線性表長度成正比4. 在下面的排序方法中，穩(wěn)定的是（ ）。 A. 希爾排序 B. 堆排序 C. 插入排序 D. 快速排序5.設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（ ）輔助記錄空間。AO(1) B

3、. O(n) C. O(nlog2n) D. O(n2)6. 數(shù)組A的每個元素占5個字節(jié)，將其按行優(yōu)先次序存儲。假設(shè)A11元素的存儲地址為1000，則元素A，的存儲地址為( )。 A. 1140B. 1145 C. 1120 D. 11257. 高度為n的完全二叉樹的結(jié)點數(shù)至少為（ ）。A. 2n-1 B. 2n-1+1 C. 2n D. 2n+18. 設(shè)有一個無向圖G=（V，E）和G=（V，E），如果G為G的生成樹，則下面不正確的說法是（ ）。AG為G 的子圖 BG為G 的連通分量CG為G的極小連通子圖且V=V DG為G的一個無環(huán)子圖9. 在有向圖的鄰接表存儲結(jié)構(gòu)中，頂點V在表結(jié)點中出現(xiàn)的次

4、數(shù)是（ ）。A. 頂點V的度 B. 頂點V的出度 C. 頂點V的入度 D. 依附于頂點V的邊數(shù)10. 關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中( )。A最短的回路 B從源點到匯點的最短路徑C最長的回路 D從源點到匯點的最長路徑考試科目： 數(shù)據(jù)結(jié)構(gòu) 共 5 頁，第 1 頁11. 一個有n個結(jié)點的無向圖最多有（ ）條邊。A. n B. n-1 C. n(n-1) D. n(n-1)/212. 對某個無向圖的鄰接矩陣來說，( )。A第i行上的非零元素個數(shù)和第i列的非零元素個數(shù)一定相等B矩陣中的非零元素個數(shù)等于圖中的邊數(shù)C第i行上，第i列上非零元素總數(shù)等于頂點vi的度數(shù)D矩陣中非全零行的行數(shù)等于圖中的頂點數(shù)13. 平

5、衡二叉樹的平均查找長度是 ( )。 A. O(n2） B. O(nlog2n） C. O(n） D. O(log2n）14. 下列哪種排序需要的附加存儲開銷最大( )。 A. 快速排序 B. 堆排序 C. 歸并排序 D. 插入 排序 15. 設(shè)一數(shù)列的順序為1,2,3,4,5,6, 通過棧操作可以得到（ ）的輸出序列。 A. 3,2,5,6,4,1 B. 1,5,4,6,2,3 C. 6,4,3,2,5,1 D. 3,5,6,2,4,1二填空題(每空2分，共20分)1. 在一個長度為n的順序表中刪除第i個元素時，需向前移動 個元素。2. 設(shè)數(shù)組Data0.m作為循環(huán)隊列SQ的存儲空間，fron

6、t為隊頭指針，rear為隊尾指針則執(zhí)行出隊操作時front指針的值應(yīng)更新為 front= 。3. 在單鏈表中，若要刪除指針p所指結(jié)點的后一結(jié)點，則需要執(zhí)行下列語句：（設(shè)q為指針 變量）q=p->next; ； 。4. 在有n個結(jié)點的二叉鏈表中，值為NULL的鏈域的個數(shù)為 。5. 二叉樹中度為0的結(jié)點數(shù)為30，度為1的結(jié)點數(shù)為30，總結(jié)點數(shù)為 。6. 在堆排序的過程中，對任一分支結(jié)點進行篩選運算的時間復(fù)雜度為 ，整個堆排序過程的時間復(fù)雜度為 。7. 對于n個記錄（假設(shè)每個記錄含d個關(guān)鍵字）進行鏈?zhǔn)交鶖?shù)排序，總共需要進行 趟分配和收集。8. 設(shè)有向圖G中有向邊的集合E=<1，2>

7、，<2，3>，<1，4>，<4，2>，<4，3>，則該圖的一種拓撲序列為 。三判斷題（每題1分，共10分，正確的選t，錯誤的選f）1. 在n個頂點的無向圖中，若邊數(shù)>n-1，則該圖必是連通圖。 （ ）2. 具有n個結(jié)點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的（ ）3. 使用散列法存儲時，哈希表的大小可隨意選取，通常取10的倍數(shù)。（ ）4. 向一個二叉排序樹插入新的結(jié)點時，新插入的結(jié)點總是葉子結(jié)點（ ）5. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ）6. 普里姆(Prim)算法相對于克魯斯卡爾(Kruskal)算法更適合求一個稀疏圖G的最小

8、生成樹。（ ）7. 向二叉排序樹中插入一個新結(jié)點，需要比較的次數(shù)可能大于此二叉樹的高度h。（ ）8. 向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹高度為原樹的高度加1。（ ）9. 無向圖的鄰接矩陣一定是對稱陣。 ( )10. 對小根堆進行層次遍歷可以得到一個有序序列。（ ）考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5 頁，第 2 頁四. 簡答題（45分）1. 已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，求解下列問題：(1) 畫出此二叉樹。（4分）(2) 將該二叉樹轉(zhuǎn)換成森林。（4分）2. 設(shè)有一組關(guān)鍵字（71,23,73,14,55,89,33,43

9、,48）,采用哈希函數(shù)：H(key)=key %10，采用開放地址的二次探測再散列方法解決沖突，試在散列地址空間中對該關(guān)鍵字序列(按從左到右的次序)構(gòu)造哈希表，并計算在查找概率相等的前提下，成功查找的平均查找長度。（7分）3. 設(shè)有一組初始記錄關(guān)鍵字為(3,1,4,6,8,2,5)，要求構(gòu)造一棵平衡二叉樹，并給出構(gòu)造過程。（5分）4. 對圖1所示的無向加權(quán)圖完成下列要求： （1）寫出它的鄰接表；（5分）（2）按克魯斯卡爾（Kruskal）算法求其最小生成樹，并給出其過程。（6分）（3）給出從頂點a開始的深度優(yōu)先搜索序列和深度優(yōu)先生成樹。（4分） 圖 15. 已知序列(142,543,123,6

10、5,453,879,572,434,111,242,811,102)。(1) 采用希爾排序?qū)υ撔蛄凶魃蚺判颍埥o出第一趟排序的結(jié)果（初始步長為7）。（5分）(2) 采用堆排序?qū)υ撔蛄凶魃蚺判颍埥o出初始堆以及第一趟排序的結(jié)果。（5分）五算法填空，（每空2分,共20分）1. 下面算法實現(xiàn)對一個不帶頭結(jié)點的單鏈表L進行就地（不增加額外存儲空間）逆置。請在_處填上適當(dāng)內(nèi)容，使其成為一個完整算法。typedef int DataType;typedef struct DataType data; struct Node *next;Node;typedef Node * LinkList;考試科目

11、： 數(shù)據(jù)結(jié)構(gòu) 共5 頁，第 3 頁LinkList Reverse(LinkList L)LinkList p, q;if (!L) return; /鏈表為空返回 p=L->next; q=L->next; L->next=NULL;while(q)q=q->next; (1) (2) p=q; return L; 2. 下面是一個采用二叉鏈表存儲結(jié)構(gòu), 中序遍歷線索二叉樹T的算法。 Visit是對結(jié)點操作的應(yīng)用函數(shù)。請在_處填上適當(dāng)內(nèi)容，使其成為一個完整算法。/*二叉樹的二叉線索存儲表示*/Typedef enum PointerTagLink, Thread; t

12、ypedef struct BiThrNode TelemType data;struct BiThrNode *lchild, *rchild;PointerTag LTag, RTag; BiThrNode, *BiThrTree;Status InOrderTraverse_Thr(BiThrTree T, Status(* Visit)(TelemType e)BiThrNode *p;p= (3) while(p!=T) /空樹或遍歷結(jié)束時p=T while(p->LTag=Link) (4) if(!Visit(p->data) return ERROR; while

13、(p->RTag=Thread && (5) (6) Visit（p->data）； (7) return OK;考試科目： 數(shù)據(jù)結(jié)構(gòu) 共5 頁，第 4 頁3. 下面是一個利用遞歸對二叉排序樹進行查找的算法。請在_處填上適當(dāng)內(nèi)容，使其成為一個完整算法。 typedef struct BTreeNode TelemType data;struct BTreeNode *lchild, *rchild; BTreeNode;bool Find(BTreeNode* T, TelemType& item) if( (8) )return FALSE; /查找失敗else if (item=T->data) /查找成功return TRUE;else if(item<T->data)return Find( (9) , item );else return Find( (10) , item )