》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2015年廣西桂林電子科技大學數據結構考研真題一選擇題（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的含義是（）。

A．問題規模B．語句條數C．循環層數D．函數數量5、具有線性結構的數據結構是（）。

A．樹B．圖C．棧和隊列D．廣義表6、以v1為起始結點對下圖進行深度優先遍歷，正確的遍歷序列是（）

A．v1，v2，v3，v4，v5，v6，v7

B．v1，v2，v5，v4，v3，v7，v6

C．v1，v2，v3，v4，v7，v5，v6

D．v1，v2，v5，v6，v7，v3，v47、對線性表進行二分查找時，要求線性表必須()

A.以順序方式存儲

B.以鏈式方式存儲

C.以順序方式存儲，且結點按關鍵字有序排列

D.以鏈接方式存儲，且結點按關鍵字有序排列8、指針p1和p2分別指向兩個無頭結點的非空單循環鏈表中的尾結點，要將兩個鏈表鏈接成一個新的單循環鏈表，應執行的操作為（）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.只允許在表的一端進行插入和刪除C.允許在表的兩端進行插入和刪除D.只允許在表的一端進行插入，在另一端進行刪除10、在一棵二叉樹中，度為2的結點數為15，度為1的結點數為3，則葉子結點數為（）A.12B.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)遍歷右子樹；

(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，20（4）10，20，40，60，66，77，80，82，85，98，100（10分）七、已知元素個數為8的字典，其關鍵碼集合為{45，20，55，30，75，40，50，65}，試按元素的次序依次插入一棵初始為空的二叉排序樹，請畫出插入完成之后的二叉排序樹，并畫出刪除45后的二叉排序樹。(15分)八、（1）畫出下面網絡的鄰接矩陣；（2）給出從頂點1出發的深度優先序列和廣度優先序列（相同情況的小標號在前）；（3）用prim算法構造網絡的最小生成樹，并給出生成樹的權值。（15分）九.設哈希(Hash)表的地址范圍為0～17，哈希函數為：H(K)=KMOD16,K為關鍵字，用線性探測再散列法處理沖突，輸入關鍵字序列:(10,24,32,17,31,30,46,47,40,63,49)造出哈希表，試回答下列問題：(1)畫出哈希表示意圖；(2)若查找關鍵字63，需要依次與哪些關鍵字比較?(3)若查找關鍵字60，需要依次與哪些關鍵字比較?(4)假定每個關鍵字的查找概率相等，求查找成功時的平均查找長度。（20分）十、設有兩個按升序排列的單鏈表X和Y，其頭指針分別為p，q結點結構說明如下：試設計一個算法voidconcat（node*p，*q）將它們合并成一個以p為頭指針的單鏈表Z，使其仍然有序。（15分）十一、樹結點的平衡因子（bf）定義為該結點的左