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

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

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