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

2、5,6, 且進棧和出棧可以穿插進行，則可能出現的出棧序列為( )。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. 在任意一棵二叉樹的先序序列和后序序列中，各葉子之間的相對次序關系 ( )。A不一定相同B互為逆序C都不相同D都相同7. 高度為 5 的二叉樹至多有結點數為（）。A. 63B. 3 2C. 31D.648. 圖的鄰接矩陣表示法適用于表示（）。A無向圖B有向圖C稠密圖D稀

3、疏圖9. 在一個單鏈表中,若 p 所指的結點不是最后一個結點,在 p 之后插入 s 所指的結點, 則執行( )。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. 若在線性表中采用折半查找法查找元素，該線性表應該是（）。A. 元素按值有序C. 元素按值有序且采用順序存儲結構B. 采用順序存儲結構D. 元素按值有序 且采用鏈式存儲結構考試科目：數據結構共 5 頁，第 1頁A. T1(n)=lo

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

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

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

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

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

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

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

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