PAGEPAGE1數據結構期末試卷（適用計算機應用專業)一二三總分得分評分人一。選擇題（30分）1.計算機算法指的是＿＿＿A.計算方法B。排序方法C。解決問題的有限運算序列D。調度方法2線性表若采用鏈式存儲結構時,要求內存中可用存儲單元的地址＿＿＿。A.必須是連續的B。部分地址必須是連續的C。一定是不連續的D。連續不連續都可以3.一個棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是＿＿＿。A.edcbaB.decbaC。dceabD.abcde4.棧的特點是＿＿，隊列的特點是＿＿。A.先進先出B.先進后出5.判定一個隊列QU（最多元素為mo)為空的條件是＿＿＿。A.QUàrear-QUàfront==moB。QUàrear-QUàfront—1==moC.QUàfront==QUàrearD.QUàfront==QUàrear+16。在循環雙鏈表的P所指結點之后插入S所指結點的操作是＿＿＿。A。Pàright=S；Sàleft=P;Pàrightàleft=S；Sàright=PàrightB.Pàright=S;Pàrightàleft=S；Sàleft=P；Sàright=PàrightC。Sàleft=P；Sàright=Pàright；Pàright=S;Pàrightàleft=SD。Sàleft=P;Sàright=Pàright；Pàrightàleft=S；Pàright=S7.在一個單鏈表中，已知q所指結點是P所指結點的前驅結點，若在q和P之間插入S結點，則執行＿＿＿。A。Sànext=Pànext；Pànext=S；B.Pà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。16B。32C。31D。10得分評分人二.填空題：（20分）1。在一個長度為n的向量中的第i個元素（1<=i<=n)之前插入一個元素時，需向后移動個元素.2.在一個長度為n的向量中刪除第i個元素(1<=i〈=n）時，需向前動個元素。3。向棧中壓入元素的操作是。4。一個棧的輸入序列是12345，則棧的輸出序列43512是。5。在雙鏈表中,每個結點有兩個指針域，一個指向,另一個指向.6。帶有一個頭結點的單鏈表head為空的條件是。7。在一個單鏈表中p所指結點之后插入一個s所指結點時，應執行s->next=和p—>next=的操作.8。非空的循環單鏈表head的尾結點(由p所指向），滿足條件.9.在棧頂指針為HS的鏈表中,計算該鏈棧中結點個數的函數是。10。已知一個圖的鄰接矩陣表示，計算第三個結點的入度的方法是。得分評分人三、簡答題（35分）1．試比較鏈式存儲結構和順序存儲結構的優缺點：2．設如圖所示的邏輯結構圖示,給出它的邏輯結構：eq\o\ac（○,A1)eq\o\ac（○,A2）eq\o\ac(○，A3）eq\o\ac(○，A6）eq\o\ac（○,A4）eq\o\ac（○，A8)eq\o\ac(○，A7)eq\o\ac（○，A5）eq\o\ac（○,A9）3．對于一個棧,給出輸入項A，B，C,如果輸入項序列由A，B,C所組成，試寫出全部可能的輸出序列。4.由如圖所示的二叉樹，回答以下問題:eq\o\ac(○，a)(1）其中序遍歷序列（2）其前序遍歷序列eq\o\ac（○,b)eq\o\ac(○,c)（3）其后序遍歷序列(4）該二叉樹的中序線索二叉樹eq\o\ac(○,d）eq\o\ac(○,e）eq\o\ac（○,f）（5）該二叉樹的后序線索二叉樹（6）該二叉樹對應的森林eq\o\ac（○，g)eq\o\ac(○,h）eq\o\ac（○，i）5。一棵二叉樹的結點數據采用順序存儲結構，存儲于數組t中,如圖所示，則該二叉樹的鏈接表示形式Eafdgcjihb123456789101112131415161718192021圖得分評分人五、程序設計（20分）1。已知一個順序表L，其