2016年廣東暨南大學數(shù)據(jù)結構考研真題

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

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

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

4、 D. 依附于頂點V的邊數(shù)10. 關鍵路徑是事件結點網(wǎng)絡中( )。A最短的回路 B從源點到匯點的最短路徑C最長的回路 D從源點到匯點的最長路徑11. 一個有n個結點的無向圖最多有（ ）條邊。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. 平衡二叉樹的平均查找長度是 ( )。 A. O(n2） B. O(nlog2n） C. O(n） D. O(log

5、2n）14. 下列哪種排序需要的附加存儲開銷最大( )。 A. 快速排序 B. 堆排序 C. 歸并排序 D. 插入 排序 15. 設一數(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ù)組Data0.m作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針則執(zhí)行出隊操作時front指針的值應更新為 front= 。3. 在單鏈表中，若

6、要刪除指針p所指結點的后一結點，則需要執(zhí)行下列語句：（設q為指針 變量）q=p-next; ； 。4. 在有n個結點的二叉鏈表中，值為NULL的鏈域的個數(shù)為 。5. 二叉樹中度為0的結點數(shù)為30，度為1的結點數(shù)為30，總結點數(shù)為 。6. 在堆排序的過程中，對任一分支結點進行篩選運算的時間復雜度為 ，整個堆排序過程的時間復雜度為 。7. 對于n個記錄（假設每個記錄含d個關鍵字）進行鏈式基數(shù)排序，總共需要進行 趟分配和收集。8. 設有向圖G中有向邊的集合E=，則該圖的一種拓撲序列為 。三判斷題（每題1分，共10分，正確的選t，錯誤的選f）1. 在n個頂點的無向圖中，若邊數(shù)n-1，則該圖必是連通圖。

7、 （ ）2. 具有n個結點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的（ ）3. 使用散列法存儲時，哈希表的大小可隨意選取，通常取10的倍數(shù)。（ ）4. 向一個二叉排序樹插入新的結點時，新插入的結點總是葉子結點（ ）5. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ）6. 普里姆(Prim)算法相對于克魯斯卡爾(Kruskal)算法更適合求一個稀疏圖G的最小生成樹。（ ）7. 向二叉排序樹中插入一個新結點，需要比較的次數(shù)可能大于此二叉樹的高度h。（ ）8. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹高度為原樹的高度加1。（ ）9. 無向圖的鄰接矩陣一定是對稱陣。 ( )10. 對

8、小根堆進行層次遍歷可以得到一個有序序列。（ ）四. 簡答題（45分）1. 已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，求解下列問題：(1) 畫出此二叉樹。（4分）(2) 將該二叉樹轉換成森林。（4分）2. 設有一組關鍵字（71,23,73,14,55,89,33,43,48）,采用哈希函數(shù)：H(key)=key %10，采用開放地址的二次探測再散列方法解決沖突，試在散列地址空間中對該關鍵字序列(按從左到右的次序)構造哈希表，并計算在查找概率相等的前提下，成功查找的平均查找長度。（7分）3. 設有一組初始記錄關鍵字為(3,1,4,6,8,2,5)，要求

9、構造一棵平衡二叉樹，并給出構造過程。（5分）4. 對圖1所示的無向加權圖完成下列要求： （1）寫出它的鄰接表；（5分）（2）按克魯斯卡爾（Kruskal）算法求其最小生成樹，并給出其過程。（6分）（3）給出從頂點a開始的深度優(yōu)先搜索序列和深度優(yōu)先生成樹。（4分） 圖 15. 已知序列(142,543,123,65,453,879,572,434,111,242,811,102)。(1) 采用希爾排序?qū)υ撔蛄凶魃蚺判颍埥o出第一趟排序的結果（初始步長為7）。（5分）(2) 采用堆排序?qū)υ撔蛄凶魃蚺判颍埥o出初始堆以及第一趟排序的結果。（5分）五算法填空，（每空2分,共20分）1. 下面算法實

10、現(xiàn)對一個不帶頭結點的單鏈表L進行就地（不增加額外存儲空間）逆置。請在_處填上適當內(nèi)容，使其成為一個完整算法。typedef int DataType;typedef struct DataType data; struct Node *next;Node;typedef Node * LinkList;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. 下面是一個采

11、用二叉鏈表存儲結構, 中序遍歷線索二叉樹T的算法。 Visit是對結點操作的應用函數(shù)。請在_處填上適當內(nèi)容，使其成為一個完整算法。/*二叉樹的二叉線索存儲表示*/Typedef enum PointerTagLink, Thread; typedef struct BiThrNode TelemType data;struct BiThrNode *lchild, *rchild;PointerTag LTag, RTag; BiThrNode, *BiThrTree;Status InOrderTraverse_Thr(BiThrTree T, Status(* Visit)(TelemTy

12、pe e)BiThrNode *p;p= (3) while(p!=T) /空樹或遍歷結束時p=T while(p-LTag=Link) (4) if(!Visit(p-data) return ERROR; while (p-RTag=Thread & (5) (6) Visit（p-data）； (7) return OK;3. 下面是一個利用遞歸對二叉排序樹進行查找的算法。請在_處填上適當內(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(itemdata)return Find( (9) , item );else return Find( (10)