數(shù)據(jù)結構試卷

1、精選文檔數(shù)據(jù)結構期末試卷 (適用計算機應用專業(yè))一二三總分得分評分人一.選擇題(30分)1.計算機算法指的是 A.計算方法 B.排序方法 C.解決問題的有限運算序列 D.調度方法2線性表若采用鏈式存儲結構時,要求內存中可用存儲單元的地址。 A.必須是連續(xù)的 B.部分地址必須是連續(xù)的 C.一定是不連續(xù)的 D.連續(xù)不連續(xù)都可以3.一個棧的入棧序列是a、b、c、d、e,則棧的不可能的輸出序列是。 A.edcba B.decba C.dceab D.abcde4.棧的特點是,隊列的特點是。 A.先進先出 B.先進后出5.判定一個隊列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所指結點之后插入S所指結點的操作是。 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.在一個單鏈表中，已知q所指結點是P所指結點的前驅結點，若在q和P之間插入S結點，則執(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.在線索化二叉樹中,t所指結點沒有左子樹的充要條件是。A.tàleft=NULLB.tàltag=1C.tàltag=1且tàleft=NULLD.以上都不對9.如果T2是由有序樹T轉換而來的二叉樹,那么T中結點的前序就是T2中結點的。A.前序 B.中序 C.后序 D.層次序10.深度為5的二叉樹至多有個結點。 A.16 B.32 C.31 D

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

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