11-12-數(shù)據(jù)結(jié)構(gòu)試卷-A+答案

2011～2012學(xué)年第1學(xué)期期末考試試卷（A卷）課程名稱：數(shù)據(jù)結(jié)構(gòu)任課教師姓名：卷面總分：100分考試時長：100分鐘考試類別：閉卷院（系）：專業(yè)：年級：2010姓名：學(xué)號：題號第一題第二題第三題第四題總分得分閱卷教師（簽字）：裝訂線單項(xiàng)選擇題（每題2分，共10題20分）裝訂線題號12345678910答案ABBBBDDCCA以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？。A．棧B．哈希表C．線索樹D．雙向鏈表鏈表不具有的特點(diǎn)是。A．插入、刪除不需要移動元素B．可隨機(jī)訪問任一元素C．不必事先估計(jì)存儲空間D．所需空間與線性表長度成正比算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為。A．a(chǎn)b+cde/*B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++二維數(shù)組A[10][20]采用列優(yōu)先的存儲方法,若每個元素占2個存儲單元，設(shè)A[0][0]的地址為100，則元素A[7][6]的存儲地址為。A．232B．234C．390D．392若一棵二叉樹具有10個度為2的結(jié)點(diǎn)，5個度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個數(shù)是B。A．9B．11C．15D．不確定一棵二叉樹中序序列為FEABDC，后序序列為FBADCE，則層序序列為D。A.ABCDEFB.EFCDBAC.FECDABD.EFCDABEECFCFDADABB在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是D。A．G中有弧<Vi，Vj>B．G中有一條從Vi到Vj的路徑C．G中沒有弧<Vi,Vj>D．G中有一條從Vj到Vi的路徑對于二叉排序樹，下面的說法C是正確的。A．二叉排序樹是動態(tài)樹表，查找不成功時插入新結(jié)點(diǎn)時，會引起樹的重新分裂和組合(不用移動元素的樹)B．對二叉排序樹進(jìn)行層序遍歷可得到有序序列（應(yīng)該是中序遍歷）C．用逐點(diǎn)插入法構(gòu)造二叉排序樹時，若先后插入的關(guān)鍵字有序，二叉排序樹的深度最大D．在二叉排序樹中進(jìn)行查找，關(guān)鍵字的比較次數(shù)不超過結(jié)點(diǎn)數(shù)的1/2（取決于二叉排序樹的形狀）一組記錄的關(guān)鍵字為{47、75、55、30、42、90}，則用快速排序方法并以第一個記錄為支點(diǎn)得到的第一次劃分結(jié)果是。A.30,42,47,55,75,90B.42,30,47,75,55,90C.42,30,47,55,75,90D.42,30,47,90,55,75下述文件中適合于磁帶存儲的是。A.順序文件B.索引文件C.散列文件D.多關(guān)鍵字文件順序文件：原理是順序表查找法索引文件：原理是線性索引查找(如最大關(guān)鍵碼和次關(guān)鍵碼)多關(guān)鍵字文件：散列文件：原理是散列函數(shù)（哈希函數(shù)）判斷（每題1分，共10題10分）題號12345678910答案×√√××√×√×√順序存儲方式插入和刪除時效率太低，因此它不如鏈?zhǔn)酱鎯Ψ绞胶谩?---()（如果插入和刪除次數(shù)較少時順序存儲方式為首選）KMP算法的特點(diǎn)是在模式匹配時指示主串的指針不會變小。------------()（主串在匹配過程中是不會移動的，只有匹配的串在移動，所以其指針不會動）若輸入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列3,2,5,6,4,1.---()數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入，刪除等操作。---------------------------------------------------------()數(shù)組不能進(jìn)行插入刪除等操作若一個廣義表的表頭為空表，則此廣義表亦為空表。-------------------()完全二叉樹中，若一個結(jié)點(diǎn)沒有左孩子，則它必是樹葉。---------------()完全二叉樹的關(guān)鍵之一就是：元素又是有序排列的，順序不可間斷一個有向圖的鄰接表和逆鄰接表中結(jié)點(diǎn)的個數(shù)可能不等。---------------()必須相等AOE網(wǎng)一定是有向無環(huán)圖。-----------------------------------------()AOE網(wǎng)的特征和定義對一棵二叉排序樹按先序方法遍歷得出的結(jié)點(diǎn)序列是從小到大的序列。---()應(yīng)該是中序排列倒排文件與多重表文件的次關(guān)鍵字索引結(jié)構(gòu)是不同的。-------------()填空題（每題2分，共10題20分）帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個元素結(jié)點(diǎn)的條件是：L->next->next==L。下一個元素的后繼恒為自身已知鏈隊(duì)列的頭尾指針分別是f和r，則將s指向的結(jié)點(diǎn)入隊(duì)的操作是r->next=s；r=s。將插入元素賦值給原隊(duì)尾指針的后繼廣義表A(((),(a,(b),c)))，head(tail(head(tail(head(A))))等于(b)。HeadA=((),(a,(b),c))tail(head(A))=(a,(b),c)head(tail(head(A))=（a,(b)）tail(head(tail(head(A)))=（(b)）head(tail(head(tail(head(A))))=(b)高度為5的完全二叉樹至少有8個葉子結(jié)點(diǎn)一棵樹T中，包括一個度為1的結(jié)點(diǎn)，兩個度為2的結(jié)點(diǎn)，三個度為3的結(jié)點(diǎn)，四個度為4的結(jié)點(diǎn)和若干葉子結(jié)點(diǎn)，則T的葉結(jié)點(diǎn)數(shù)為1+2*1+3*2+4*3=21。求圖的最小生成樹有兩種算法中，prim算法適合于求稠密圖的最小生成樹。具有10個關(guān)鍵字的有序表，折半查找的平均查找長度2.9。高度為7的平衡二叉樹的結(jié)點(diǎn)數(shù)至少有33個。用斐波那契序數(shù)進(jìn)行計(jì)算在一棵m階B-樹中,若在某結(jié)點(diǎn)中插入一個新關(guān)鍵字而引起該結(jié)點(diǎn)分裂,則此結(jié)點(diǎn)中原有的關(guān)鍵字的個數(shù)是m-1。B-樹是一種多路查找樹。M階的B樹具有如下特性：每一個分支結(jié)點(diǎn)都有k-1個元素和k個孩子。？對n個記錄進(jìn)行簡單選擇排序，所需進(jìn)行的關(guān)鍵字間的比較次數(shù)為1+2+3+…+(n-1)=n(n-1)/2。簡答題（每題5分，共10題50分）畫出廣義表（a，（b，c，d），e）的存儲結(jié)構(gòu)圖（采用頭尾指針的鏈表結(jié)構(gòu)，標(biāo)志1表示表結(jié)點(diǎn)，標(biāo)志0表示原子結(jié)點(diǎn)）11111110a0b0c0d0e廣義表的注意點(diǎn)：同一個括號內(nèi)的橫向表示。abcabcdefghijklaabcdefghijkl森林轉(zhuǎn)化為二叉樹的要點(diǎn)：先將每一棵樹都轉(zhuǎn)化為二叉樹，再進(jìn)行組合。給定一組葉子的權(quán)值分別為：8、6、3、2、7、24，填寫下表構(gòu)造一棵赫夫曼樹，并畫出該赫夫曼樹(同一層的左子樹根權(quán)值小于右子樹根權(quán)值)HT：weightparentlchild62462432785111526501890026800337004270057900624110075843811107891510511026118911500610已知某圖的鄰接表（1）．畫出此鄰接表對應(yīng)的圖；（2）．寫出由v1開始的深度優(yōu)先遍歷的序列；（3）．畫出由v1開始的深度優(yōu)先的生成樹；v1開始深度優(yōu)先遍歷的序列:v1-v2-v5-v3-v4-v6V1V2V1V2V3V4V5V6圖V1V2V3V4V5V6生成樹

1212453633181419162111856112161211216123165123616561243616115612453618161156按Dijkstra算法計(jì)算從頂點(diǎn)A到其它各個頂點(diǎn)的最短路徑和最短路徑長度。（寫出每一步計(jì)算得到的最短路徑和相應(yīng)的路徑長度）源點(diǎn)AV(i)路徑終點(diǎn)BCDEi=1路徑路徑長度AB3AC20￥AE45BABi=2路徑路徑長度ABC18￥ABE43CABCi=2路徑路徑長度ABCD38ABE43DABCDi=4路徑路徑長度ABE43EABE

由字符序列(t,d,e,s,u,g,)建立一棵平衡的二叉排序樹(畫出主要過程)。tttdtdetdetdestdesutdesugtdesug最后一步：因?yàn)樵谟易訕渖系淖笞訕渖线M(jìn)行插入所以首先對大右子樹進(jìn)行向右旋轉(zhuǎn)，整體樹再向左旋轉(zhuǎn)，最后整體調(diào)節(jié)一下平衡。已知散列表的地址空間為A[0..11]，散列函數(shù)H（k）=kmod11，采用線性探測法處理沖突。請將下列數(shù)據(jù){25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并計(jì)算出在等概率情況下查找成功時的平均查找長度。關(guān)鍵字251638477982513989151231哈希值35532576180哈希地址01234567891011關(guān)鍵字231897925471638825139151比較次數(shù)11112123243等概率情況下查找成功時的平均查找長度：（1+1+1+1+2+1+2+3+2+4+3）/11=21/11平均查找長度的算法。就是對差值進(jìn)行求和再取平均。已知序列{101，51，19，61，3，71，31，17，18，100，55，20，9，30，50，6}，請采用希爾排序?qū)υ撔蛄凶魃蚺判?，給出每一趟排序結(jié)果（設(shè)：d[1]=5，d[2]=3，d[3]=1）第1趟:6，20，9，18，3，55，31，17，30，50，71，51，19，61，100，101第2趟: