1、桂林電子科技大學2015 年研究生統一入學考試試題科目代碼： 910科目名稱：數據結構請注意： 答案必須寫在答題紙上（寫在試題上無效）。一 選擇題（ 2分/題，共 20分）1、在單鏈表中，存儲每個結點有兩個域，一個是數據域，另一個是指針域，指針域指向該結點的( )。A 直接前趨B.直接后繼C.開始結點D.終端結點2、在已知頭指針的單鏈表中，要在其尾部插入一新結點，其算法所需的時間復雜度為 ()。A O（1）B.O （ log2n）C.O（n）D.O （ n2）3、常用于函數調用的數據結構是()。A. 棧B.隊列C.鏈表D.數組4、若一個算法的時間復雜度用T(n) 表示，其中 n 的含義是（）。

2、A 問題規模B語句條數C循環層數D函數數量5、具有線性結構的數據結構是（）。A 樹B 圖C棧和隊列D 廣義表6、以 v1為起始結點對下圖進行深度優先遍歷，正確的遍歷序列是（）A v1， v2， v3， v4， v5， v6， v7B v1， v2， v5， v4， v3， v7， v6C v1， v2， v3， v4， v7， v5， v6D v1， v2， v5， v6， v7， v3， v47、對線性表進行二分查找時，要求線性表必須()A. 以順序方式存儲B. 以鏈式方式存儲D. 以鏈接方式存儲，且結點按關鍵字有序排列8、指針p1和 p2分別指向兩個無頭結點的非空單循環鏈表中的尾結點，要將

3、兩個鏈表鏈接成第1頁共4頁一個新的單循環鏈表，應執行的操作為（）A.p1 next=p2 next;p2 next=p1 next;B. p2 next=p1 next;p1 next=p2 next;C. p=p2 next; p1 next=p;p2 next=p1 next;D. p=p1 next; p1 next= p2 next； p2 next=p;9、隊列的特點是（）A. 允許在表的任何位置進行插入和刪除B. 只允許在表的一端進行插入和刪除D. 只允許在表的一端進行插入，在另一端進行刪除10、在一棵二叉樹中，度為2 的結點數為15，度為1 的結點數為3，則葉子結點數為（）A.1

4、2B.16C.18D.20二、在棧的輸入端元素的輸入順序為1， 2，3， 4， 5，6，進棧過程中可以退棧，則退棧時能否排成序列 3， 2， 5， 6， 4，1 和 1， 5，4， 6， 2，3，若能，寫出進棧、退棧過程（用 push （ x）表示 x 進棧， pop(x) 表示 x 退棧），若不能，簡述理由。 （ 10 分）三、設待排序的排序碼序列為12, 2, 16, 30, 28, 10, 16*, 20, 6, 18,試寫出使用直接插入排序每趟排序后的結果。并說明做了多少次排序碼比較。（10 分）四、假設二叉樹的RNL遍歷算法定義如下：若二叉樹非空，則依次執行如下操作：(1) 遍歷右子

5、樹；(2) 訪問根節點；(3) 遍歷左子樹。已知一棵二叉樹如圖所示，請給出其RNL遍歷的結果序列。 （ 10 分）五、給定葉子結點的權值集合15, 3,14, 2, 6, 9, 16, 17，構造相應的哈夫曼樹，并計算其帶權路徑長度。(10 分)六、判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調整為堆）。（ 1） 100，85， 98，77， 80， 60， 82， 40， 20， 10， 66（ 2） 100，98， 85，82， 80， 77， 66， 60， 40， 20， 10（ 3） 100，85， 40，77， 80， 60， 66， 98， 82， 10，

6、20（ 4） 10，20， 40，60， 66， 77， 80， 82 ， 85， 98， 100（ 10 分）第2頁共4頁七、已知元素個數為 8 的字典，其關鍵碼集合為 45 ， 20， 55，30， 75，40， 50， 65 ，試按元素的次序依次插入一棵初始為空的二叉排序樹，請畫出插入完成之后的二叉排序樹，并畫出刪除 45 后的二叉排序樹。 (15 分 )八、（ 1）畫出下面網絡的鄰接矩陣；（ 2）給出從頂點1 出發的深度優先序列和廣度優先序列（相同情況的小標號在前）（ 3）用 prim 算法構造網絡的最小生成樹，并給出生成樹的權值。（15分）；1571254523364568九 . 設

7、哈希 (Hash) 表的地址范圍為 017，哈希函數為： H (K)=K MOD 16, K 為關鍵字，用線性探測再散列法處理沖突，輸入關鍵字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，試回答下列問題：(1) 畫出哈希表示意圖； (2) 若查找關鍵字 63，需要依次與哪些關鍵字比較 ?(3) 若查找關鍵字 60，需要依次與哪些關鍵字比較 ?(4) 假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。（20 分）十、設有兩個按升序排列的單鏈表X 和 Y，其頭指針分別為p， q 結點結構說明如下：typedef struct nodelint data；struct nodel *nextnode ；試設計一個算法void concat（ node *p， *q ）將它們合并成一個以p 為頭指針的單鏈表Z，使其仍然有序。（ 15 分）十一二叉樹結點的平衡因子（bf ）定義為該結點的左子樹高度與右子樹高