數(shù)據(jù)結(jié)構(gòu)試卷

1、精選文檔數(shù)據(jù)結(jié)構(gòu)期末試卷 (適用計(jì)算機(jī)應(yīng)用專業(yè))一二三總分得分評(píng)分人一.選擇題(30分)1.計(jì)算機(jī)算法指的是 A.計(jì)算方法 B.排序方法 C.解決問(wèn)題的有限運(yùn)算序列 D.調(diào)度方法2線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲(chǔ)單元的地址。 A.必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.一定是不連續(xù)的 D.連續(xù)不連續(xù)都可以3.一個(gè)棧的入棧序列是a、b、c、d、e,則棧的不可能的輸出序列是。 A.edcba B.decba C.dceab D.abcde4.棧的特點(diǎn)是,隊(duì)列的特點(diǎn)是。 A.先進(jìn)先出 B.先進(jìn)后出5.判定一個(gè)隊(duì)列QU(最多元素為mo)為空的條件是。 A.QUàrear-Q

2、Uàfront= =mo B. QUàrear-QUàfront-1= =mo C. QUàfront= =QUàrear D. QUàfront= =QUàrear+16.在循環(huán)雙鏈表的P所指結(jié)點(diǎn)之后插入S所指結(jié)點(diǎn)的操作是。 A.P àright=S;S àleft=P;P àright àleft=S;S àright=P àright B.P àright=S;P àright à left=S;S àleft =P;S

3、 àright=P àright C.S àleft =P;S àright=P àright;P àright=S;P àright à left=S D.S àleft =P;S àright=P àright;P àright à left=S;P àright=S7.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是P所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和P之間插入S結(jié)點(diǎn)，則執(zhí)行。 A.S ànext=P ànext;P ànext=S; B.P

4、 ànext=S ànext;S ànext=P; C.q ànext=S;S ànext=P; D.P ànext=S;S ànext=P;8.在線索化二叉樹(shù)中,t所指結(jié)點(diǎn)沒(méi)有左子樹(shù)的充要條件是。A.tàleft=NULLB.tàltag=1C.tàltag=1且tàleft=NULLD.以上都不對(duì)9.如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù),那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的。A.前序 B.中序 C.后序 D.層次序10.深度為5的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)。 A.16 B.32 C.31 D

5、.10 得分評(píng)分人二.填空題:(20分)1. 在一個(gè)長(zhǎng)度為n的向量中的第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng) 個(gè)元素。2. 在一個(gè)長(zhǎng)度為n的向量中刪除第i個(gè)元素（1<=i<=n）時(shí)，需向前動(dòng) 個(gè)元素。3. 向棧中壓入元素的操作是 。4. 一個(gè)棧的輸入序列是1 2 3 4 5，則棧的輸出序列4 3 5 1 2是 。5. 在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向 ，另一個(gè)指向 。6. 帶有一個(gè)頭結(jié)點(diǎn)的單鏈表head為空的條件是 。7. 在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s>next= 和p>next= 的操作。8. 非

6、空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向），滿足條件 。9. 在棧頂指針為HS的鏈表中，計(jì)算該鏈棧中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)是 。10. 已知一個(gè)圖的鄰接矩陣表示，計(jì)算第三個(gè)結(jié)點(diǎn)的入度的方法是 。得分評(píng)分人三、簡(jiǎn)答題(35分)1試比較鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：2設(shè)如圖所示的邏輯結(jié)構(gòu)圖示，給出它的邏輯結(jié)構(gòu)： 3對(duì)于一個(gè)棧，給出輸入項(xiàng)A,B,C，如果輸入項(xiàng)序列由A,B,C所組成，試寫出全部可能的輸出序列。4.由如圖所示的二叉樹(shù),回答以下問(wèn)題: (1) 其中序遍歷序列 （2）其前序遍歷序列 （3）其后序遍歷序列 （4）該二叉樹(shù)的中序線索二叉樹(shù) （5）該二叉樹(shù)的后序線索二叉樹(shù) （6）該二叉樹(shù)對(duì)應(yīng)的森林 5.一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)結(jié)構(gòu),存儲(chǔ)于數(shù)組t中,如圖所示,則該二叉樹(shù)的鏈接表示形式Eafdgcjihb1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 圖得分評(píng)分人五、程序設(shè)計(jì)(20分)1.已知一個(gè)順序表L，其中的元素按值非遞減有序排