《【桂林電子科技大學(xué) 考研真題】910數(shù)據(jù)結(jié)構(gòu)(2015-A).docx》由會(huì)員分享，可在線閱讀，更多相關(guān)《【桂林電子科技大學(xué) 考研真題】910數(shù)據(jù)結(jié)構(gòu)(2015-A).docx（4頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、桂林電子科技大學(xué)2015年研究生統(tǒng)一入學(xué)考試試題科目代碼：910
科目代碼：910
科目名稱：數(shù)據(jù)結(jié)構(gòu)
請(qǐng)注意：答案必須寫在答題紙上（寫在試題上無效）。
-選擇題（2分/題，共20分）1、在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，另一個(gè)是指針域，指針域指向該結(jié)點(diǎn)的（）。
A. 直接前趨B.直接后繼C.開始結(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)是（）o
A. 棧B.隊(duì)列C.鏈表D.數(shù)組4、若一個(gè)算法的時(shí)間復(fù)雜度用T（
2、n）表示，其中n的含義是（）。
A.問題規(guī)模B.語句條數(shù)C.循環(huán)層數(shù)D.函數(shù)數(shù)量5、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（）。
A.樹B.圖C.棧和隊(duì)列D.廣義表6、以vl為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（）
A.vl,
v2,
v3,
v4,
v5,
v6,
v7
B.vl,
v2,
v5,
v4,
v3,
v7,
v6
C.vl,
v2,
v3,
v4,
v7,
v5,
v6
D.vl,
v2,
v5,
v6,
v7,
v3,
v4
7、對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）以順序方式存儲(chǔ)
A. 以鏈?zhǔn)椒绞酱鎯?chǔ)以
3、順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列
B. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列8、指針pl和p2分別指向兩個(gè)無頭結(jié)點(diǎn)的非空單循環(huán)鏈表中的尾結(jié)點(diǎn)，要將兩個(gè)鏈表鏈接成一個(gè)新的單循環(huán)鏈表，應(yīng)執(zhí)行的操作為（）
A. pl—>next=p2—>next;p2—>next=pl—>next;p2—>next=p1——>next;p1——>next=p2——>next;
B. p=p2—>next;pl—>next=p;p2—>next=pl—>next;p=pl—>next;pl—>next=p2—>next；p2—>next=p;
9、隊(duì)列的特點(diǎn)是（）允許在表的任何位置進(jìn)行插入和刪除
A.
4、 只允許在表的一端進(jìn)行插入和刪除允許在表的兩端進(jìn)行插入和刪除
B. 只允許在表的一端進(jìn)行插入，在另一端進(jìn)行刪除10、在一棵二叉樹中，度為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)棧過程中可以退棧，則退棧時(shí)能否排成序列3,2,5,6,4,1和1,5,4,6,2,3,若能，寫出進(jìn)棧、退棧過程（用push
（X）表示x進(jìn)棧，pop（x）表示x退棧），若不能，簡(jiǎn)述理由。（10分）三、設(shè)待排序的排序碼序列為{12,2,16,30,28,10,16*,20,6,18},試寫出使用直接插入排序每趟
5、排序后的結(jié)果。并說明做了多少次排序碼比較。（1。分）
四、假設(shè)二叉樹的RNL遍歷算法定義如下：
若二叉樹非空，則依次執(zhí)行如下操作：
（1）遍歷右子樹；（2）訪問根節(jié)點(diǎn)；
（3）遍歷左子樹。
已知一棵二叉樹如圖所示，請(qǐng)給出其RNL遍歷的結(jié)果序列。（10分）
五、給定葉子結(jié)點(diǎn)的權(quán)值集合{15,3,14,2,6,9,16,17},構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)路徑長(zhǎng)度。（10分）
六、判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請(qǐng)將它們調(diào)整為堆）。
(1)
100,
85,
98,
77,
80,
60,
82,
40,
20,
10,
66
6、
(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},試按元素的次序依次插入一棵初始為空的二叉排序樹，請(qǐng)畫出插入完成之后的二叉排序樹，并畫出刪除45后的二叉排序樹。(15分)
7、八、(1)畫出下面網(wǎng)絡(luò)的鄰接矩陣；
(2) 給出從頂點(diǎn)1出發(fā)的深度優(yōu)先序列和廣度優(yōu)先序列(相同情況的小標(biāo)號(hào)在前)；
(3) 用prim算法構(gòu)造網(wǎng)絡(luò)的最小生成樹，并給出生成樹的權(quán)值。(15分)
設(shè)哈希(Hash)表的地址范圍為。?17,哈希函數(shù)為：H(K)二KMOD16,K為關(guān)鍵字，用線性探測(cè)再散
列法處理沖突，輸入關(guān)鍵字序列：(10,24,32,17,31,30,46,47,40,63,49)造出哈希表，試回答下列問題：
(1)畫出哈希表示意圖；(2)若查找關(guān)鍵字63,需要依次與哪些關(guān)鍵字比較？
(3) 若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較？
(4) 假定每個(gè)關(guān)鍵字的查找概
8、率相等，求查找成功時(shí)的平均查找長(zhǎng)度。(20分)十、設(shè)有兩個(gè)按升序排列的單鏈表X和Y,其頭指針分別為p,q結(jié)點(diǎn)結(jié)構(gòu)說明如下:typedefstructnodel
intdata；
structnodel*next
}node；
試設(shè)計(jì)一個(gè)算法voidconcat(node*p,*q)將它們合并成一個(gè)以p為頭指針的單鏈表Z,使其仍然有序。(15分)
十一.二叉樹結(jié)點(diǎn)的平衡因子(bf)定義為該結(jié)點(diǎn)的左子樹高度與右子樹高度之差。設(shè)二叉樹結(jié)點(diǎn)結(jié)構(gòu)為：(Ichild,data,bf,rchild),
IchiId,rchiId是左右兒子指針；data是數(shù)據(jù)元素；bf是平衡因子，編寫遞歸算法計(jì)算二
叉樹中各個(gè)結(jié)點(diǎn)的平衡因子。
（15分）
【桂林電子科技大學(xué) 考研真題】910數(shù)據(jù)結(jié)構(gòu)(2015-A).docx
