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

PAGEPAGE1數(shù)據(jù)結(jié)構(gòu)期末試卷（適用計(jì)算機(jī)應(yīng)用專業(yè))一二三總分得分評分人一。選擇題（30分）1.計(jì)算機(jī)算法指的是＿＿＿A.計(jì)算方法B。排序方法C。解決問題的有限運(yùn)算序列D。調(diào)度方法2線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲單元的地址＿＿＿。A.必須是連續(xù)的B。部分地址必須是連續(xù)的C。一定是不連續(xù)的D。連續(xù)不連續(xù)都可以3.一個(gè)棧的入棧序列是a、b、c、d、e，則棧的不可能的輸出序列是＿＿＿。A.edcbaB.decbaC。dceabD.abcde4.棧的特點(diǎn)是＿＿，隊(duì)列的特點(diǎn)是＿＿。A.先進(jìn)先出B.先進(jìn)后出5.判定一個(gè)隊(duì)列QU（最多元素為mo)為空的條件是＿＿＿。A.QUàrear-QUàfront==moB。QUàrear-QUàfront—1==moC.QUàfront==QUàrearD.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à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.在一個(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ànext=Sànext；Sànext=P；C.qànext=S;Sànext=P;D.Pànext=S;Sànext=P；8。在線索化二叉樹中,t所指結(jié)點(diǎn)沒有左子樹的充要條件是＿＿＿。A。tàleft==NULLB。tàltag==1C.tàltag==1且tàleft==NULLD.以上都不對9.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的＿＿＿。A。前序B.中序C。后序D.層次序10.深度為5的二叉樹至多有＿＿＿個(gè)結(jié)點(diǎn)。A。16B。32C。31D。10得分評分人二.填空題：（20分）1。在一個(gè)長度為n的向量中的第i個(gè)元素（1<=i<=n)之前插入一個(gè)元素時(shí)，需向后移動(dòng)個(gè)元素.2.在一個(gè)長度為n的向量中刪除第i個(gè)元素(1<=i〈=n）時(shí)，需向前動(dòng)個(gè)元素。3。向棧中壓入元素的操作是。4。一個(gè)棧的輸入序列是12345，則棧的輸出序列43512是。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。非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向），滿足條件.9.在棧頂指針為HS的鏈表中,計(jì)算該鏈棧中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)是。10。已知一個(gè)圖的鄰接矩陣表示，計(jì)算第三個(gè)結(jié)點(diǎn)的入度的方法是。得分評分人三、簡答題（35分）1．試比較鏈?zhǔn)酱鎯Y(jié)構(gòu)和順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)：2．設(shè)如圖所示的邏輯結(jié)構(gòu)圖示,給出它的邏輯結(jié)構(gòu)：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．對于一個(gè)棧,給出輸入項(xiàng)A，B，C,如果輸入項(xiàng)序列由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）該二叉樹對應(yīng)的森林eq\o\ac（○，g)eq\o\ac(○,h）eq\o\ac（○，i）5。一棵二叉樹的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組t中,如圖所示，則該二叉樹的鏈接表示形式Eafdgcjihb123456789101112131415161718192021圖得分評分人五、程序設(shè)計(jì)（20分）1。已知一個(gè)順序表L，其