算法與數(shù)據(jù)結(jié)構(gòu)試題電信061-2

1、班級 學(xué)號 2008 年2009 年第 1 學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)試題(B)（除第一題選擇題外，所有一、單項選擇題(從下列各題四個備選寫在答題紙上，寫在其它地方無效）中選出一個正確,將其代號 (A,B,C,D)寫在下表中,答題寫在其它地方無效；每小題 1 分,共 10 分)1.A.B.C.D.2.關(guān)于線性表的表述正確的是（）每個元素都有一個直接前趨和一個直接后繼線性表中至少要有一個元素表中元素的排列順序必須是由小到大或者由大到小除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前趨和直接后繼一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應(yīng)該設(shè)置（）A.堆棧 B.隊列 C.堆棧或隊列 D.數(shù)

2、組3.A.4.A.5.設(shè)棧的輸入序列為 1.2.3.n，若輸出序列的第一個元素是 n，則第 i 個輸出元素是（）不確定 B. ni+1C.iD. ni若廣義表滿足 Head（A）Tail（A），則 A 為（）（）B. （）C.（），（） D.（），（），（）設(shè)有 13 個值，用它們組成一棵樹，則該樹共有（）個結(jié)點。A13B. 12C.26D.256.A.C.7.下面幾個符號編碼集合中，不是前綴編碼的是（）（0，10，110，1111）B. （11，10，001，101，0001）（00，010，0110，1000） D.（B,C,AA,AC,ABA,ABB,ABC）在一棵度為 3 的樹中，度為

3、 3 的結(jié)點數(shù)為 2 個，度為 2 的結(jié)點數(shù)為 1 個，度為 1 的結(jié)點數(shù)為 2 個，則度為 0 的結(jié)點數(shù)為（）個。A.8.A.9.4B.5C.6D.7為了方便對圖狀結(jié)構(gòu)的數(shù)據(jù)進(jìn)行存取操作，則其中數(shù)據(jù)結(jié)構(gòu)應(yīng)該采用（）B. 鏈?zhǔn)紺. 索引D. 散列順序?qū)τ?18 個元素的有序表做二分（折半）查找，則查找 A3的比較序列的下標(biāo)為（）A. 1.2.3B. 9.5.2.3C. 9.5.3D. 9.4.2.310. 對任意的 7 個關(guān)鍵字進(jìn)行排序，至少進(jìn)行（）次關(guān)鍵字之間的兩兩比較。A.13B.14C.15D.17二、填空(每空 1 分,共 20 分)1.算法的基本特性是(),(),(),(),()。在

4、從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也需要做如下三件事情：（）；（）；（）。二叉樹的第 i 層上至多有（）個結(jié)點。帶權(quán)的圖稱作（）。5. 哈希表的檢索平均檢索長度取決于（）、（）和（）這三個。題號12345678910任何遞歸定義必須同時滿足如下兩個條件：（）；（）。兩個串相等的充要條件是（），并且（）。隊列的操作原則是（），棧的操作原則是（）。9.線性表的鏈?zhǔn)浇Y(jié)構(gòu)為（）。三、判斷題 (每小題 1 分,共 10 分)1.串是由有限個字符的連續(xù)序列，串長度為串中字符的個數(shù)。（）KMP 算法的最大特點是指示主串的指針不需要回溯。（）若一個廣義表的表頭為空表，則此廣義表亦為空表。（）二叉樹就是結(jié)點度為

5、 2 的樹。（）存在這樣的二叉樹，對它采用任何次序的遍歷，結(jié)果相同。（）6.二叉樹中不存在度大于 2 的結(jié)點，當(dāng)某個結(jié)點只有一棵時無所謂左右之分。（）不使用遞歸也能實現(xiàn)二叉樹的前序，中序和后序遍歷。（）強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。（）有回路的圖不能進(jìn)行拓?fù)渑判颉＃ǎ┧械呐判蛩惴ǘ际遣环€(wěn)定的。（）四、證明計算題(共 10 分)1.證明對任意一棵二叉樹，若終端結(jié)點數(shù)為 n0，度為 2 的結(jié)點數(shù)為 n2，則 n0=n2+1。（6分）2.模式“abaabcac”的 next 函數(shù)值為：（4 分）五、作圖題 (共 15 分)二叉樹有哪幾種基本形態(tài)? 畫圖說明之。（5 分）試將森林 F= T1

6、,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹。（5 分）3.數(shù)組 A1.2,0.2 的以列序為主序的順序六、問答題 (共 20 分)結(jié)構(gòu)。（5 分）一只一棵樹邊的集合為(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c),請回答以下問題：（1）（2）（3）（4）（5）（6）（7）（8）哪個是根節(jié)點？ 哪些是葉子結(jié)點？哪些是結(jié)點g 的雙親？哪些是結(jié)點g 的祖先？哪些是結(jié)點g 的孩子？哪些是結(jié)點e 的子孫？哪些是結(jié)點e 的兄弟？那些是結(jié)點f 的兄弟？結(jié)點 b 和結(jié)點 n 的層次號分別是多少？j12345678模式串a(chǎn)baabcacNextj（9） 樹的深度是多