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

1、一、填空題1、算法的五個(gè)重要特性是：有窮性、_、可行性、輸入、輸出。2、數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法，由此得到兩種不同的存儲(chǔ)結(jié)構(gòu)： _和鏈?zhǔn)浇Y(jié)構(gòu)。3在有n個(gè)元素的順序表中刪除一個(gè)元素，所需要移動(dòng)元素的平均個(gè)數(shù)是_，具體移動(dòng)元素的個(gè)數(shù)與元素位置有關(guān)。4、在一個(gè)長(zhǎng)度為n的循環(huán)鏈表中，刪除其元素的值為x的節(jié)點(diǎn)的時(shí)間復(fù)雜度為_(kāi)。5、1，2，3，n按照先后順序入棧，則可能的出棧序列有_個(gè)。6假設(shè)有三維數(shù)組A456，每個(gè)元素長(zhǎng)度為2個(gè)字節(jié)，假設(shè)從首地址SA0開(kāi)始以行為主序存放在存儲(chǔ)器中，則元素a345的存儲(chǔ)位置為_(kāi)。7、已知一棵二叉樹(shù)的先序序列為ABCD，中序序列為BCAD，則其后序序

2、列為_(kāi)。8、有29個(gè)結(jié)點(diǎn)的赫夫曼樹(shù)中葉子結(jié)點(diǎn)有_個(gè)。9在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和是圖中邊數(shù)之和的 倍。10一個(gè)有n個(gè)頂點(diǎn)、e條邊的無(wú)向圖的鄰接表中有 個(gè)頂點(diǎn)結(jié)點(diǎn)。11假設(shè)G是一個(gè)具有21條邊的非連通無(wú)向圖（不含自回路和多重邊），則圖G至少有_個(gè)頂點(diǎn)。12、圖的常用存儲(chǔ)結(jié)構(gòu)有以下四種：鄰接矩陣、鄰接表、_、鄰接多重鏈表。13、對(duì)n(n>0)個(gè)記錄進(jìn)行冒泡排序，最少要交換_次記錄。14有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)折半查找到值為82的元素時(shí),經(jīng)過(guò)比較的關(guān)鍵字的序列為： 。二、判斷題（ ）1. 算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所

3、用計(jì)算機(jī)有關(guān)。（ ）2. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位。（ ）3. 順序表的存儲(chǔ)空間必須連續(xù)，單鏈表的存儲(chǔ)空間必須不連續(xù)。（ ）4. 存取順序表中第i個(gè)元素時(shí)花費(fèi)的時(shí)間同i的大小有關(guān)。（ ）5. 棧和隊(duì)列都是限制了存取點(diǎn)的線性結(jié)構(gòu)。（ ）6. 遞歸程序執(zhí)行過(guò)程中必須用到棧。（ ）7數(shù)組不適合作為任何二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。（ ）8一棵樹(shù)中的葉子結(jié)點(diǎn)的個(gè)數(shù)和度為1的結(jié)點(diǎn)個(gè)數(shù)的多少?zèng)]有關(guān)系。（ ）9樹(shù)的前序遍歷和其相應(yīng)的二叉樹(shù)的前序遍歷的結(jié)果是一樣的。（ ）10已知二叉樹(shù)的前序和后序遍歷序列，則可以恢復(fù)出此二叉樹(shù)。（ ）11無(wú)論是有向圖還是無(wú)向圖，其所有頂點(diǎn)度數(shù)之和一定是頂點(diǎn)數(shù)的2倍。（ ）12一個(gè)網(wǎng)（帶權(quán)

4、圖）都有唯一的最小生成樹(shù)。（ ）13 求邊稠密的無(wú)向連通網(wǎng)的最小生成樹(shù)時(shí)，最好使用Kruscal算法。（ ）14順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈接存儲(chǔ)的線性表。 （ ）15 由于哈希查找中是直接計(jì)算待查數(shù)據(jù)的地址，因此其ASL一定為0。（ ）16直接插入排序和希爾排序都是穩(wěn)定的內(nèi)部排序方法。三、選擇題（ ）1下列算法的時(shí)間復(fù)雜度為( )。int suanfa(int n) int t=1；       while(t<=n)          t=t*2；r

5、eturn t； A.O(log2n)      B.O(2n)     C.O(n2)   D.O(n)（ ）2. 鏈表不具有的特點(diǎn)是（ ） A插入、刪除不需要移動(dòng)元素 B可隨機(jī)訪問(wèn)任一元素 C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性長(zhǎng)度成正比（ ）3. 若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲(chǔ)方式最節(jié)省時(shí)間。A 順序表 B單循環(huán)鏈表 C 雙鏈表 D帶頭結(jié)點(diǎn)的雙循環(huán)鏈表（ ）4一個(gè)棧的輸入序列為1 2 3 4 5，則下列中不可能是棧的輸出序列的是

6、（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2（ ）（ ）5. 數(shù)組A0.5,0.6的每個(gè)元素占五個(gè)字節(jié)，將其按列優(yōu)先次序存儲(chǔ)在起始地址為1000的內(nèi)存單元中，則元素A5，5的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210（ ）6. 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 （ ）7. 設(shè)有一個(gè)10階的對(duì)稱矩陣A，采

7、用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為 第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。A. 13 B. 33 C. 18 D. 40（ ）8對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用( )次序的遍歷實(shí)現(xiàn)編號(hào)。A先序 B. 中序 C. 后序 D. 從根開(kāi)始按層次遍歷（ ）9. 在下述結(jié)論中，正確的是（ ）。 只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0;二叉樹(shù)的度為2；二叉樹(shù)的左右子樹(shù)可任意交換; 深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。 A B C D （ ）10

8、. 一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（ ）A11 B10 C11至1025之間 D10至1024之間（ ）11. 利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空（ ）12. 某二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)。A空或只有一個(gè)結(jié)點(diǎn) B任一結(jié)點(diǎn)無(wú)左子樹(shù) C高度等于其結(jié)點(diǎn)數(shù) D任一結(jié)點(diǎn)無(wú)右子樹(shù) （ ）13. 下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（ ）A有向圖 B無(wú)向圖 CAOV網(wǎng) DAOE網(wǎng)（ ）14. 下面哪一個(gè)算法是用來(lái)求解單源點(diǎn)最短路徑的算法（ ）。A. 迪杰斯特拉算法 B. 弗洛伊德算法 C. 普利姆算法 D.

9、克魯斯卡爾（ ）15. 無(wú)向圖G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是：Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,b,c（ ）16. 分別以下列序列構(gòu)造二叉排序樹(shù)，跟其他序列所構(gòu)造的結(jié)果不同的是( ) A（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (10

10、0，80， 60， 90， 120，130，110)（ ）17. 下列關(guān)于m階B-樹(shù)的說(shuō)法錯(cuò)誤的是( )。A根結(jié)點(diǎn)至多有m棵子樹(shù) B所有葉子都在同一層次上 C. 非葉結(jié)點(diǎn)至少有m/2 (m為偶數(shù))或m/2+1（m為奇數(shù)）棵子樹(shù) D. 根結(jié)點(diǎn)中的數(shù)據(jù)是有序的（ ）18. 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是( )排序法。 A插入 B. 選擇 C. 冒泡 D. 基數(shù) （ ）19. 對(duì)序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?，9，-1，8，20，7，15；則采用的是（ ）排序。A. 選擇 B. 快速 C. 希爾 D. 冒泡（ ）20. 下列四個(gè)序列中，哪一個(gè)是堆（

11、  ）A. 75,65,30,15,25,45,20,10      B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10      D. 75,45,65,10,25,30,20,15 四、綜合應(yīng)用題1一棵二叉樹(shù)的先序、中序、后序序列如下，部分未標(biāo)出，請(qǐng)畫(huà)出該二叉樹(shù)。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G 后序序列 ：_ E F D B _ J I H _ A2對(duì)于表達(dá)

12、式a+b*(c-d)-e/f。(1)畫(huà)出該表達(dá)式對(duì)應(yīng)的二叉樹(shù)。(2)寫出對(duì)該二叉樹(shù)分別進(jìn)行前序，中序和后序遍歷所得的表達(dá)式序列。3某電文共使用5種字符：a,b,c,d,e,它們的出現(xiàn)頻率依次為0.15、0.1、0.25、0.2、0.3。(1)試畫(huà)出對(duì)應(yīng)的赫夫曼樹(shù)（請(qǐng)按照同層結(jié)點(diǎn)權(quán)值由小到大的次序構(gòu)造，不需要寫出構(gòu)造過(guò)程，只畫(huà)出最后樹(shù)形結(jié)果即可)。(2)求出每個(gè)字符的赫夫曼編碼。4有圖如下，請(qǐng)完成以下要求： 1）寫出其深度優(yōu)先遍歷序列（從A開(kāi)始）： 2）按照Prime算法求出最小生成樹(shù)（畫(huà)出最終結(jié)果）ABCDEF1015121278106655、下圖為一個(gè)連通網(wǎng)。(1)畫(huà)出該網(wǎng)的鄰接矩陣表示。(2)寫出從v1出發(fā)對(duì)該網(wǎng)的廣度優(yōu)先搜索序列。(3)從v1開(kāi)始，用Prim算法構(gòu)造該網(wǎng)的最小生成樹(shù)(直接寫出構(gòu)造好的結(jié)果，不必寫過(guò)程)，并求出最小生成樹(shù)上各邊權(quán)值之和。v1v2v4v5v6v365155366426. 采用哈希函數(shù)H(k) =（3*k）mod 13并用線性探測(cè)開(kāi)放地址法處理沖突，在數(shù)列地址空間0.12中對(duì)關(guān)鍵字序列22，41，53，46，30，13，1，67，51；（1）構(gòu)造哈希表（畫(huà)示意圖）； （2）求裝填因子；（3）求等概率下查找成功條件下的平均查找長(zhǎng)度；7、帶權(quán)圖（權(quán)值非空，表示邊連接的兩個(gè)頂點(diǎn)的距離）的最短路