2011年暨南大學(xué)830數(shù)據(jù)結(jié)構(gòu)考研試題

1、2011 年全國碩士研究生統(tǒng)一入學(xué)考試自命題試題*學(xué)科與專業(yè)名稱：計算機(jī)技術(shù), 軟件工程考試科目代碼與名稱：數(shù)據(jù)結(jié)構(gòu)考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。一. 選擇題(每題 2 分，共 30 分)1. 算法分析的目的是（）。A. 找出數(shù)據(jù)結(jié)構(gòu)的合理性C. 分析算法的效率以求改進(jìn)2. 下列函數(shù)中漸近時間復(fù)雜度最小的是（B. 研究算法中的輸入和輸出關(guān)系D. 分析算法的易讀性和文檔性）。233. 線性表的動態(tài)鏈表存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)相比，優(yōu)點是（）。A. 所有的操作算法實現(xiàn)簡單C. 便于插入與刪除B. 便于隨機(jī)存取D. 便于節(jié)省存儲器空間4若進(jìn)棧序列為 1,2,3,4,

2、5,6, 且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列為( )。A 3,2,6,1,4,5C 5,1,2,3,4,6B5,6,4,2,3,1D3,4,2,1,6,55. 順序存儲的線性表的第一個元素的存儲地址是 100，每個元素的長度為 4，則第 4 個元素的存儲地址是（ ）。A. 108B. 112C.116D. 1206. 在任意一棵二叉樹的先序序列和后序序列中，各葉子之間的相對次序關(guān)系 ( )。A不一定相同B互為逆序C都不相同D都相同7. 高度為 5 的二叉樹至多有結(jié)點數(shù)為（）。A. 63B. 3 2C. 31D.648. 圖的鄰接矩陣表示法適用于表示（）。A無向圖B有向圖C稠密圖D稀

3、疏圖9. 在一個單鏈表中,若 p 所指的結(jié)點不是最后一個結(jié)點,在 p 之后插入 s 所指的結(jié)點, 則執(zhí)行( )。A. s->next=p; p->next=sC. p=s; s->next=p->nextB. p->next=s; s->next=pD. s->next=p->next; p->next=s10. 若在線性表中采用折半查找法查找元素，該線性表應(yīng)該是（）。A. 元素按值有序C. 元素按值有序且采用順序存儲結(jié)構(gòu)B. 采用順序存儲結(jié)構(gòu)D. 元素按值有序 且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)考試科目：數(shù)據(jù)結(jié)構(gòu)共 5 頁，第 1頁A. T1(n)=lo

4、g2n+5000n B. T2(n)=n -8000nC. T3(n)=n +5000n D. T4(n)=2nlog2n-1000n11. 已知一棵二叉樹結(jié)點的先序序列為 ABDGCFK, 中序序列為 DGBAFCK, 則結(jié)點的后序序列為( )。A. GDBFKCA B. DGBFKCA C. KFCABDG D. CAFKGDB12. 對于元素是整數(shù)(占 2 個字節(jié))的 n 行 n 列對稱矩陣 A,采用以行序為主的壓縮存儲方式存儲到一維數(shù)組 sn*(n+1)/2中(下三角),若 A11的起始地址是 400，問元素 A85的存儲地址是( ).A. 432 B. 563 C. 484 D. 4

5、6413. 在所有排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無關(guān)的是（）。A. Shell 排序B. 冒泡排序C. 直接插入排序D. 直接選擇排序14. 具有 6 個頂點的無向圖至少應(yīng)有（）條邊才能確保是一個連通圖。A5B6 C7D815. 如果 T2 是由樹 T1 轉(zhuǎn)換而來的二叉樹, 那 T1 中結(jié)點的先序就是 T2 中結(jié)點的( )。A. 先序B. 中序C. 后序D. 層次序二填空題(每題 2 分，共 20 分)1. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)分和。2. 若對關(guān)鍵字序列(12,18,4,3,6,13,2,9,19,8)進(jìn)行快速排序（以第一個元素為支點），則第一趟排序得到的結(jié)果為3. 堆排

6、序采用了記錄，就建立。作為其數(shù)據(jù)結(jié)構(gòu)，如果希望第一次就能找出最小關(guān)鍵字堆。4. 二叉樹中度為 0 的結(jié)點數(shù)為 30，度為 1 的結(jié)點數(shù)為 30，總結(jié)點數(shù)為。5. 向棧中壓入元素的操作是先，后。6. 在的情況下，鏈隊列的出隊操作需要修改尾指針。7. 所謂連通圖 G 的生成樹,是 G 的包含其全部 n 個頂點的一個極小連通子圖。它必定包含且包含 G 的條邊。8. 對于一個有向圖，若一個頂點的度為 k1，出度為 k2，則對應(yīng)鄰接表中該頂點單鏈表中的邊節(jié)點數(shù)為。9. 設(shè) GetHead(p)為求廣義表 p 的表頭函數(shù)，GetTail(p)為求廣義表 p 的表尾函數(shù)。其中()是函數(shù)符號，運算 GetTa

7、il(GetHead(a,b),(c,d,e)的結(jié)果是。10. 對 n 個結(jié)點進(jìn)行快速排序，最大比較次數(shù)是。三判斷題（每題 1 分，共 10 分, 正確的選 t，錯誤的選 f）1 一個廣義表的表尾總是一個廣義表。（）2 順序表用一維數(shù)組作為存儲結(jié)構(gòu)，因此順序表是一維數(shù)組。( )3 雙循環(huán)鏈表中，任一結(jié)點的前驅(qū)指針均為不空。（）4. 存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)。（）5. 當(dāng)從一個最小堆中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止。（）考試科目：數(shù)據(jù)結(jié)構(gòu)共 5 頁，第 2頁6. 棧和隊列都是

8、順序存取的線性表，但它們對存取位置的限制不同。( )7. 一個無序的元素序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序的元素序列。（t）8. 一棵 m 階 B+樹中每個結(jié)點最多有 m 個關(guān)鍵碼，最少有 2 個關(guān)鍵碼。( )9. 拓?fù)渑判蚴且环N內(nèi)部排序的算法。( )10. 空串與空格相同。( )四. 簡答題（50 分）1. 對關(guān)鍵字序列（49，38，65，97，75，13，27，51，55，10）進(jìn)行一趟希爾排序(由小到大)。試寫出第 1 趟（增量 d1=5）希爾排序的結(jié)果及元素移動次數(shù)。 (4 分)2. 已知一個圖如圖 1 所示， (10 分)（1）請寫出其鄰接矩陣和鄰接表。（2）請寫出其拓?fù)渑?/p>

9、序序列。圖 13. 在圖 2 所示的 AOE 網(wǎng)中，試找出此網(wǎng)絡(luò)中的關(guān)鍵活動和關(guān)鍵路徑。（10 分）圖 2考試科目：數(shù)據(jù)結(jié)構(gòu)共 5頁，第 3 頁4. 已知一顆 3 階的 B-樹如圖 3 所示，若刪除 44 和 79 之后，畫出這棵 B-樹的最終狀態(tài)。（8分）圖 35. 設(shè)有一段正文是由字符集A,B,C,D,E,F組成的，正文長度為 100 個字符，其中每個字符在正文中出現(xiàn)的次數(shù)分別為 17,12,5,28,35,3。若采用 Huffman 編碼對這段正文進(jìn)行壓縮存儲，請完成如下工作：（10 分）(1) 構(gòu)造出 Huffman 樹(規(guī)定權(quán)值較小的結(jié)點為左子樹);(2) 寫出每個字符的 Huffm

10、an 編碼；(3) 計算按 Huffman 編碼壓縮存儲這段正文共需要多少個字節(jié)(設(shè)每個字節(jié)為 8 位二進(jìn)制位組成；(4) 若有另一段正文的二進(jìn)制編碼序列為 01101010110011,請用(2)的 Huffman 編碼將它翻譯成所對應(yīng)的正文。6. 設(shè)有一組關(guān)鍵字（47,7,29,11,16,92,22,8,3）采用散列函數(shù) H(key)= key%11，開放地址的線性探測再散列方法解決沖突，試在 010 的散列地址空間中對該關(guān)鍵字序列（按從左到右的次序）構(gòu)造散列表，并計算在查找概率相等的前提下，成功查找的平均查找長度。（8 分）五算法填空，（每空 2 分,共 16 分）1.下面的算法是一個

11、在元素按值遞增排列，并以帶頭結(jié)點的單鏈表作存儲結(jié)構(gòu)的線性表中，刪除表中所有值大于 mink 且小于 maxk 的元素（若表中存在這樣的元素），同時釋放被刪除結(jié)點空間。請在處填上適當(dāng)內(nèi)容，使其成為一個完成算法。Void delmn(LinkList &L, int mink, int maxk)LinkList p=L,q,s;if (p->next)&&(mink<=maxk) while (if(2)(1)p=p->next; q=p->next;while(q->data<maxk) s=q; q=q->next;(3)free(s); 考試科目：數(shù)據(jù)結(jié)構(gòu)共 5 頁，第 4 頁2.下面是一個圖的廣度優(yōu)先非遞歸算法，請在成算法。void BFSTraverse (Graph G, Status(*Visit) (VertexTyp e) for(v=0; v<G.vexnum; v+)visitedv=FALSE;InitQueue(Q);處填上適當(dāng)內(nèi)容，使其成為一個完for(v=0;（4）v+) if(!visitedv) visitedv=TRUE;(5)EnQueue(&Q,v);while(（6）(7)for(w=FirstAdjVex(G,u); w&g