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

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

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

3、 3 的結(jié)點(diǎn)數(shù)為 2 個(gè)，度為 2 的結(jié)點(diǎn)數(shù)為 1 個(gè)，度為 1 的結(jié)點(diǎn)數(shù)為 2 個(gè)，則度為 0 的結(jié)點(diǎn)數(shù)為（）個(gè)。A.8.A.9.4B.5C.6D.7為了方便對(duì)圖狀結(jié)構(gòu)的數(shù)據(jù)進(jìn)行存取操作，則其中數(shù)據(jù)結(jié)構(gòu)應(yīng)該采用（）B. 鏈?zhǔn)紺. 索引D. 散列順序?qū)τ?18 個(gè)元素的有序表做二分（折半）查找，則查找 A3的比較序列的下標(biāo)為（）A. 1.2.3B. 9.5.2.3C. 9.5.3D. 9.4.2.310. 對(duì)任意的 7 個(gè)關(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)也需要做如下三件事情：（）；（）；（）。二叉樹(shù)的第 i 層上至多有（）個(gè)結(jié)點(diǎn)。帶權(quán)的圖稱作（）。5. 哈希表的檢索平均檢索長(zhǎng)度取決于（）、（）和（）這三個(gè)。題號(hào)12345678910任何遞歸定義必須同時(shí)滿足如下兩個(gè)條件：（）；（）。兩個(gè)串相等的充要條件是（），并且（）。隊(duì)列的操作原則是（），棧的操作原則是（）。9.線性表的鏈?zhǔn)浇Y(jié)構(gòu)為（）。三、判斷題 (每小題 1 分,共 10 分)1.串是由有限個(gè)字符的連續(xù)序列，串長(zhǎng)度為串中字符的個(gè)數(shù)。（）KMP 算法的最大特點(diǎn)是指示主串的指針不需要回溯。（）若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（）二叉樹(shù)就是結(jié)點(diǎn)度為

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

6、,T2,T3,T4 轉(zhuǎn)換為一棵二叉樹(shù)。（5 分）3.數(shù)組 A1.2,0.2 的以列序?yàn)橹餍虻捻樞蛄?、?wèn)答題 (共 20 分)結(jié)構(gòu)。（5 分）一只一棵樹(shù)邊的集合為(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),請(qǐng)回答以下問(wèn)題：（1）（2）（3）（4）（5）（6）（7）（8）哪個(gè)是根節(jié)點(diǎn)？ 哪些是葉子結(jié)點(diǎn)？哪些是結(jié)點(diǎn)g 的雙親？哪些是結(jié)點(diǎn)g 的祖先？哪些是結(jié)點(diǎn)g 的孩子？哪些是結(jié)點(diǎn)e 的子孫？哪些是結(jié)點(diǎn)e 的兄弟？那些是結(jié)點(diǎn)f 的兄弟？結(jié)點(diǎn) b 和結(jié)點(diǎn) n 的層次號(hào)分別是多少？j12345678模式串a(chǎn)baabcacNextj（9） 樹(shù)的深度是多