2015年廣西桂林電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題

》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2015年廣西桂林電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題一選擇題（2分/題，共20分）1、在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)的()。

A．直接前趨B.直接后繼C.開(kāi)始結(jié)點(diǎn)D.終端結(jié)點(diǎn)2、在已知頭指針的單鏈表中，要在其尾部插入一新結(jié)點(diǎn)，其算法所需的時(shí)間復(fù)雜度為()。

A．O（1）B.O（log2n）C.O（n）D.O（n2）

3、常用于函數(shù)調(diào)用的數(shù)據(jù)結(jié)構(gòu)是()。

A.棧B.隊(duì)列C.鏈表D.數(shù)組4、若一個(gè)算法的時(shí)間復(fù)雜度用T(n)表示，其中n的含義是（）。

A．問(wèn)題規(guī)模B．語(yǔ)句條數(shù)C．循環(huán)層數(shù)D．函數(shù)數(shù)量5、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（）。

A．樹(shù)B．圖C．棧和隊(duì)列D．廣義表6、以v1為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（）

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、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須()

A.以順序方式存儲(chǔ)

B.以鏈?zhǔn)椒绞酱鎯?chǔ)

C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列

D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列8、指針p1和p2分別指向兩個(gè)無(wú)頭結(jié)點(diǎn)的非空單循環(huán)鏈表中的尾結(jié)點(diǎn)，要將兩個(gè)鏈表鏈接成一個(gè)新的單循環(huán)鏈表，應(yīng)執(zhí)行的操作為（）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、隊(duì)列的特點(diǎn)是（）A.允許在表的任何位置進(jìn)行插入和刪除B.只允許在表的一端進(jìn)行插入和刪除C.允許在表的兩端進(jìn)行插入和刪除D.只允許在表的一端進(jìn)行插入，在另一端進(jìn)行刪除10、在一棵二叉樹(shù)中，度為2的結(jié)點(diǎn)數(shù)為15，度為1的結(jié)點(diǎn)數(shù)為3，則葉子結(jié)點(diǎn)數(shù)為（）A.12B.16C.18D.20二、在棧的輸入端元素的輸入順序?yàn)?，2，3，4，5，6，進(jìn)棧過(guò)程中可以退棧，則退棧時(shí)能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，寫(xiě)出進(jìn)棧、退棧過(guò)程（用push（x）表示x進(jìn)棧，pop(x)表示x退棧），若不能，簡(jiǎn)述理由。（10分）三、設(shè)待排序的排序碼序列為{12,2,16,30,28,10,16*,20,6,18},試寫(xiě)出使用直接插入排序每趟排序后的結(jié)果。并說(shuō)明做了多少次排序碼比較。（10分）四、假設(shè)二叉樹(shù)的RNL遍歷算法定義如下：

若二叉樹(shù)非空，則依次執(zhí)行如下操作：

(1)遍歷右子樹(shù)；

(2)訪問(wèn)根節(jié)點(diǎn)；

(3)遍歷左子樹(shù)。

已知一棵二叉樹(shù)如圖所示，請(qǐng)給出其RNL遍歷的結(jié)果序列。（10分）五、給定葉子結(jié)點(diǎn)的權(quán)值集合{15,3,14,2,6,9,16,17}，構(gòu)造相應(yīng)的哈夫曼樹(shù)，并計(jì)算其帶權(quán)路徑長(zhǎng)度。(10分)六、判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請(qǐng)將它們調(diào)整為堆）。（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分）七、已知元素個(gè)數(shù)為8的字典，其關(guān)鍵碼集合為{45，20，55，30，75，40，50，65}，試按元素的次序依次插入一棵初始為空的二叉排序樹(shù)，請(qǐng)畫(huà)出插入完成之后的二叉排序樹(shù)，并畫(huà)出刪除45后的二叉排序樹(shù)。(15分)八、（1）畫(huà)出下面網(wǎng)絡(luò)的鄰接矩陣；（2）給出從頂點(diǎn)1出發(fā)的深度優(yōu)先序列和廣度優(yōu)先序列（相同情況的小標(biāo)號(hào)在前）；（3）用prim算法構(gòu)造網(wǎng)絡(luò)的最小生成樹(shù)，并給出生成樹(shù)的權(quán)值。（15分）九.設(shè)哈希(Hash)表的地址范圍為0～17，哈希函數(shù)為：H(K)=KMOD16,K為關(guān)鍵字，用線性探測(cè)再散列法處理沖突，輸入關(guān)鍵字序列:(10,24,32,17,31,30,46,47,40,63,49)造出哈希表，試回答下列問(wèn)題：(1)畫(huà)出哈希表示意圖；(2)若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字比較?(3)若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較?(4)假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。（20分）十、設(shè)有兩個(gè)按升序排列的單鏈表X和Y，其頭指針?lè)謩e為p，q結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明如下：試設(shè)計(jì)一個(gè)算法voidconcat（node*p，*q）將它們合并成一個(gè)以p為頭指針的單鏈表Z，使其仍然有序。（15分）十一、樹(shù)結(jié)點(diǎn)的平衡因子（bf）定義為該結(jié)點(diǎn)的左