數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)習(xí)題

1、1. 數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示指數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示指A. 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)B. 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)C. 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)D. 數(shù)據(jù)元素之間的關(guān)系數(shù)據(jù)元素之間的關(guān)系A(chǔ)2. 串是串是_ A. 不少于一個字母的序列不少于一個字母的序列B. 任意個字母的序列任意個字母的序列C. 不少于一個字符的序列不少于一個字符的序列D. 有限個字符的序列有限個字符的序列D3. 在在n個節(jié)點(diǎn)的線索二叉樹中，線索的數(shù)目為個節(jié)點(diǎn)的線索二叉樹中，線索的數(shù)目為 A. n-1B. nC. n+1D. 2nC4. 順序隊列在實(shí)現(xiàn)的時候，通常將數(shù)組看成是順序隊列在實(shí)現(xiàn)的時候，通常將數(shù)組看成是一個

2、首尾相連的環(huán)，這樣做的目的是為了避免一個首尾相連的環(huán)，這樣做的目的是為了避免產(chǎn)生產(chǎn)生_現(xiàn)象現(xiàn)象假溢出5. 設(shè)有兩個串設(shè)有兩個串p和和q，其中，其中q是是p的子串，求的子串，求q在在p中首次出現(xiàn)的位置的算法稱為中首次出現(xiàn)的位置的算法稱為_模式匹配6. 對二叉排序樹進(jìn)行對二叉排序樹進(jìn)行_遍歷，可以得到按遍歷，可以得到按關(guān)鍵字從小到大排列的節(jié)點(diǎn)序列關(guān)鍵字從小到大排列的節(jié)點(diǎn)序列中序7. 在一組記錄的關(guān)鍵字為在一組記錄的關(guān)鍵字為46,79,56,38,40,84，利用快速排序的方法，以第利用快速排序的方法，以第1個記錄為基準(zhǔn)得到個記錄為基準(zhǔn)得到的第一次劃分結(jié)果為的第一次劃分結(jié)果為_40,38,46,56

3、,79,848. 設(shè)設(shè)n為為3的倍數(shù)，分析以下算法的時間復(fù)雜度的倍數(shù)，分析以下算法的時間復(fù)雜度 void fun(int n) int i, j, x, y; for(i=1; i=n; i+) if(3*i=n) for(j=3*i;j=n;j+) x+; y = 3*x+2; )(6) 1() 13(12n/31in/31in3inOnnin=+= 9. 二維數(shù)組二維數(shù)組A44(即即A0.30.3)的元素起始的元素起始地址是地址是LOC(A00)=1000，元素的長度為，元素的長度為2，則則LOC(A22)為多少？為多少？（2*4+2）*2+1000=102010. 如果一棵哈夫曼樹如果一

4、棵哈夫曼樹T有有n0個葉子節(jié)點(diǎn)，那么，個葉子節(jié)點(diǎn)，那么，樹樹T有多少個節(jié)點(diǎn)，要求給出求解過程有多少個節(jié)點(diǎn)，要求給出求解過程n=2n2+n1+1且n0=n2+1，得n=2n0+n1-1哈夫曼樹n1=0，則n=2n0-111. 有一個有序表有一個有序表R1.13=1,3,9,12,32,41,45,62,75,77,82,95,100，當(dāng)用二分查找法查找關(guān)鍵字為當(dāng)用二分查找法查找關(guān)鍵字為82的節(jié)點(diǎn)時，經(jīng)的節(jié)點(diǎn)時，經(jīng)多少次比較后查找成功，依次與哪些關(guān)鍵字進(jìn)多少次比較后查找成功，依次與哪些關(guān)鍵字進(jìn)行比較行比較判定樹(略)，總共比較4次，依次關(guān)鍵字為：45,77,95,8212. 以關(guān)鍵字序列以關(guān)鍵字序

5、列265,301,751,129,937,863,742,694,76,438為例，為例，給出歸并排序算法的各趟排序結(jié)束時關(guān)鍵字序給出歸并排序算法的各趟排序結(jié)束時關(guān)鍵字序列的狀態(tài)列的狀態(tài)第一趟：265,301,751,129,937,863,742,694,76,438第二趟：129,265,301,751,863,937,694,742,76,438第三趟：129,265,301,694,742,751,863,937,76,438第四趟：76,129,265,301,438,694,742,751,863,93713. 鏈表不具備的特點(diǎn)是鏈表不具備的特點(diǎn)是A. 可隨機(jī)訪問任一節(jié)點(diǎn)可隨機(jī)訪問

6、任一節(jié)點(diǎn)B. 插入刪除不需要移動元素插入刪除不需要移動元素C. 不必事先估計存儲空間不必事先估計存儲空間D. 所需空間與其長度成正比所需空間與其長度成正比A14. 一個棧的進(jìn)棧序列是一個棧的進(jìn)棧序列是abcde，則棧的不可能，則棧的不可能的輸出序列是的輸出序列是 A. edcbaB. decbaC. dceabD. abcdeC15. 用直接插入序列對下面用直接插入序列對下面4個序列進(jìn)行遞增排個序列進(jìn)行遞增排序，元素比較次數(shù)最少的是序，元素比較次數(shù)最少的是 A. 94,32,40,90,80,46,21,69B. 32,40,21,46,69,94,90,80C. 21,32,46,40,80

7、,69,90,94D. 90,69,80,46,21,32,94,40C16. 以下序列不是堆以下序列不是堆(大根或小根大根或小根)的是的是 A. 100,85,98,77,80,60,82,40,20,10,66B. 100,98,85,82,80,77,66,60,40,20,10C. 10,20,40,60,66,77,80,82,85,98,100D. 100,85,40,77,80,60,66,98,82,10,20D17. 廣義表廣義表(),a,(a),(a)的長度是的長度是_，深度，深度是是_4, 318. 具有具有n個節(jié)點(diǎn)的二叉樹采用二叉鏈存儲結(jié)構(gòu)，個節(jié)點(diǎn)的二叉樹采用二叉鏈存儲

8、結(jié)構(gòu)，共有共有_個空指針域個空指針域 n+119.在有在有n個頂點(diǎn)的有向圖中，每個頂點(diǎn)的度最個頂點(diǎn)的有向圖中，每個頂點(diǎn)的度最大可達(dá)大可達(dá)_2(n-1)20. 設(shè)設(shè)n是偶數(shù)，試計算運(yùn)行下列程序段后是偶數(shù)，試計算運(yùn)行下列程序段后m的的值并給出該程序段的時間復(fù)雜度值并給出該程序段的時間復(fù)雜度 int m =0,i,j for(i=1;i=n;i+) for(j=2*i;j=2)個權(quán)值均不同的字符構(gòu)成的哈個權(quán)值均不同的字符構(gòu)成的哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是夫曼樹，關(guān)于該樹的敘述中，錯誤的是_A. 該樹一定是一棵完全二叉樹該樹一定是一棵完全二叉樹B. 該樹中一定沒有度為該樹中一定沒有度為1的節(jié)點(diǎn)

9、的節(jié)點(diǎn)C. 樹中兩個權(quán)值最小的節(jié)點(diǎn)一定是兄弟節(jié)點(diǎn)樹中兩個權(quán)值最小的節(jié)點(diǎn)一定是兄弟節(jié)點(diǎn)D. 樹中任一非葉子節(jié)點(diǎn)的權(quán)值一定不小于下一層樹中任一非葉子節(jié)點(diǎn)的權(quán)值一定不小于下一層任一節(jié)點(diǎn)的權(quán)值任一節(jié)點(diǎn)的權(quán)值A(chǔ)46. 已知一個長度為已知一個長度為16的順序表，其元素按關(guān)鍵的順序表，其元素按關(guān)鍵字有序排序，若采用折半查找法查找一個不存字有序排序，若采用折半查找法查找一個不存在的元素，則比較的次數(shù)最多是在的元素，則比較的次數(shù)最多是 A. 4B. 5C. 6D. 7B47. 將關(guān)鍵字序列將關(guān)鍵字序列7,8,30,11,18,9,14散列存儲到散列存儲到散列表中，散列表的存儲空間是一個下標(biāo)從散列表中，散列表的存

10、儲空間是一個下標(biāo)從0開開始的一維數(shù)組，散列函數(shù)為始的一維數(shù)組，散列函數(shù)為H(key)=(key*3)mod7，處理沖突采用線性探測，處理沖突采用線性探測散列法，要求裝填因子為散列法，要求裝填因子為0.7（1）請畫出所構(gòu)造的散列表）請畫出所構(gòu)造的散列表（2） 分別計算等概率情況下，查找成功和查找分別計算等概率情況下，查找成功和查找不成功的平均查找長度不成功的平均查找長度n=7，0.7 = n/m，因此m=10 H(7) = 0 H(8) = 3 H(30) = 6 H(11) = 5 H(18) = 5 d1 = 6，d2 = 7 H(9) =6 d1 = 7，d2 = 8 H(14) = 0

11、d1 = 10123456789714811301891211133ASL成功成功 = (4+2+6)/7 = 12/7ASL失敗失敗 = (3+2+1+2+1+5+4+3+2+1)/10 = 12/548. 為實(shí)現(xiàn)快速排序法，待排序序列宜采用存儲為實(shí)現(xiàn)快速排序法，待排序序列宜采用存儲方式是方式是A. 順序存儲順序存儲B. 散列存儲散列存儲C. 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯. 索引存儲索引存儲A49. 將一棵有將一棵有80個節(jié)點(diǎn)的完全二叉樹按層編號，個節(jié)點(diǎn)的完全二叉樹按層編號，根節(jié)點(diǎn)的編號為根節(jié)點(diǎn)的編號為1，則對編號為，則對編號為40的結(jié)點(diǎn)的結(jié)點(diǎn)x，該，該節(jié)點(diǎn)節(jié)點(diǎn) A. 無左、右孩子無左、右孩子B. 有

12、左孩子，無右孩子有左孩子，無右孩子C. 有右孩子，無左孩子有右孩子，無左孩子D. 有左、右孩子有左、右孩子B50. 一個一個10階對稱矩陣階對稱矩陣A，采用行優(yōu)先順序壓縮，采用行優(yōu)先順序壓縮存儲上三角元素，存儲上三角元素，a00為第一個元素，其存儲地為第一個元素，其存儲地址為址為0，每個元素占有，每個元素占有1個存儲地址空間，則個存儲地址空間，則a45的地址為的地址為_一個一個10階對稱矩陣階對稱矩陣A，采用行優(yōu)先順序壓縮存，采用行優(yōu)先順序壓縮存儲下三角元素，儲下三角元素，a00為第一個元素，其存儲地址為第一個元素，其存儲地址為為0，每個元素占有，每個元素占有1個存儲地址空間，則個存儲地址空間

13、，則a45的的地址為地址為_35，1951. 假定一棵二叉樹的節(jié)點(diǎn)數(shù)為假定一棵二叉樹的節(jié)點(diǎn)數(shù)為22，則它的最小，則它的最小深度為深度為_，最大深度為，最大深度為_ 5， 2252. 構(gòu)造構(gòu)造n個節(jié)點(diǎn)的強(qiáng)連通圖，至少有個節(jié)點(diǎn)的強(qiáng)連通圖，至少有_條弧條弧A. nB. n/2C. n+1D. n-1A53. 在一個具有在一個具有n個頂點(diǎn)的無向圖中，要連通全個頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要部頂點(diǎn)至少需要_條邊條邊 A. nB. n+1C. n-1D. n/2C54. 將整數(shù)序列將整數(shù)序列30,15,21,40,25,26,36,37中的數(shù)中的數(shù)依次插入到一棵空的二叉排序樹中，試構(gòu)造相依次插入到一棵空的二叉排序樹中，試構(gòu)造相應(yīng)的二叉排序樹，給出構(gòu)造過程應(yīng)的二叉排序樹，給出構(gòu)造過程 3015402136253755. 以數(shù)據(jù)集合以數(shù)據(jù)集合2,5,7,9,13為權(quán)值構(gòu)造一棵哈夫?yàn)闄?quán)值構(gòu)造一棵哈夫曼樹，并計算其帶權(quán)路徑曼樹，并計算其帶權(quán)路徑長度長度 WPL=(2+5)*3+(7+9+13)*2=79362214772513956. 設(shè)設(shè)A、B、C、D、E這這5個字母出現(xiàn)的頻率分個字母出現(xiàn)的頻率分別為別為2,5,7,9,13，要求根據(jù)這，要求根據(jù)這5個字母設(shè)計個字母設(shè)計Huffman編碼，并畫出對應(yīng)的編碼，并畫出對應(yīng)的Huffman樹樹3622147725139A: 01