1、ZH計(jì)0520 九州0520數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)一、填空題：空串的長(zhǎng)度是00，空格串的的長(zhǎng)度是串中中包含的容格格的個(gè)數(shù)。隊(duì)列是一種先進(jìn)進(jìn)先出表，在在隊(duì)列中允許許插入的一端端稱隊(duì)尾，允許刪刪除的另一端端稱隊(duì)頭。兩串相等是指兩兩個(gè)字符串的的長(zhǎng)度相等，且各對(duì)對(duì)應(yīng)位置上的的字符相等。組成數(shù)據(jù)的最小小單位是數(shù)據(jù)據(jù)項(xiàng)。線性結(jié)構(gòu)中元素素之間存在一一對(duì)一的關(guān)系系，樹形結(jié)構(gòu)構(gòu)中元素之間間存在一對(duì)多多的關(guān)系，圖圖形結(jié)構(gòu)中元元素之間存在在多對(duì)多的關(guān)系系。向棧中壓入元素素的操作是：先移動(dòng)棧頂頂指針，后存存入元素。棧的邏輯結(jié)構(gòu)是是線性結(jié)構(gòu)，其其特點(diǎn)是后進(jìn)進(jìn)先出，先進(jìn)后出，棧棧中允許插入入和刪除的一一端稱棧頂。在雙向鏈表中，每每

2、個(gè)結(jié)點(diǎn)有兩兩個(gè)指針域，一一個(gè)指向前驅(qū)驅(qū)結(jié)點(diǎn)，另一一個(gè)指向后繼繼結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)通常包包括四種基本本結(jié)構(gòu)：集合合、線性結(jié)構(gòu)構(gòu)、樹形結(jié)構(gòu)、圖圖形結(jié)構(gòu)、線線性表線性表（a1 ,a2.an）k , aa1 稱表頭元素， an稱表尾元素，線線性表有兩種種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)結(jié)構(gòu)。在一個(gè)順序存儲(chǔ)儲(chǔ)的線性表中中，第1個(gè)元元素的地址是是100，每每個(gè)元素的長(zhǎng)長(zhǎng)度為2，則則第5個(gè)元素素的地址是1108。在線性結(jié)構(gòu)中，第第一個(gè)結(jié)點(diǎn)沒沒有前驅(qū)結(jié)點(diǎn)點(diǎn)，其余每個(gè)個(gè)結(jié)點(diǎn)有且只只有1個(gè)前驅(qū)結(jié)點(diǎn)點(diǎn)；最后一個(gè)個(gè)結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)點(diǎn)，其余每個(gè)個(gè)結(jié)點(diǎn)有且只只有1個(gè)后續(xù)結(jié)點(diǎn)點(diǎn)。二、選擇題具有6個(gè)頂點(diǎn)的的無向圖至少少應(yīng)

3、有A條邊邊才能確保是是一個(gè)連通圖圖。A、d B.cc C.b D.e2、在初始狀態(tài)態(tài)為空的堆棧棧中依次插入入元素f,ee,d,c,a,b后，連連續(xù)進(jìn)行了三三次刪除操作作，則此時(shí)的的棧頂元素是是DA、5 BB、6 C、7 D、83、后序遍歷的的順序是DA、根結(jié)點(diǎn)，左左子樹，右子子樹 B、左子樹樹，根結(jié)點(diǎn)，右右子樹C、右子樹，根根結(jié)點(diǎn)，左子子樹 DD、左子樹，右右子樹，根結(jié)結(jié)點(diǎn)4、設(shè)結(jié)點(diǎn)X有有左孩子結(jié)點(diǎn)點(diǎn)Y，右孩子子結(jié)點(diǎn)Z，用用三種基本遍遍歷方法得到到的遍歷序列列中X （B） 是Y的前驅(qū)，X（B）是Z的后繼，Y（A）是Z的前驅(qū)。A、一定， B、不一一定 CC、一定不5、串是指BA、少于一個(gè)字字母的

4、序列 BB、有限個(gè)字字符的序列 C、不不少于一個(gè)字字符的序列 D、任意意個(gè)字母的序序列6、一個(gè)棧的輸輸入序列為11，2，3，44， 則下列列序列中不可可能是棧的輸輸出序列的是是 CA、2，3，44，1，5 B、22，3，1，44，5 C、5，44，1，2，33 D、11，5，4，33，27、如果結(jié)點(diǎn)AA有3個(gè)兄弟弟，且B是AA的雙親，則則B的度是AAA、4 BB、5 C、1 D、38、通常對(duì)數(shù)組組進(jìn)行的兩種種基本操作是是CA、插入和刪除除 B、索索引和修改 C、查查找和修改 D、刪刪除和修改9、一個(gè)隊(duì)列的的入隊(duì)序列是是1，2，33，4，則隊(duì)隊(duì)列的輸出序序列是BA、4，3，22，1 BB、1，2

5、，33，4 C、1，44，3，2 D、33，2 ，44 ，1計(jì)算機(jī)算法必須須具備輸入、輸輸出和B等五五個(gè)基本特性性A、可行性、可可移植性、和和可擴(kuò)充性BB、可行性、確確定性和可窮窮性C、確定定性、可窮必必和穩(wěn)定性DD、易讀性、穩(wěn)穩(wěn)定性和安全全性11、樹最適合合用來表示CCA、有序數(shù)據(jù)元元素B、無序序數(shù)據(jù)元素CC、元素之間間具有分支層層次關(guān)系的數(shù)數(shù)據(jù)D、元素素之間無聯(lián)系系的數(shù)據(jù)12、排序方法法中，從未排排序序列中依依次取出元素素與已排序序序列（初始時(shí)時(shí)為空）中的的元素進(jìn)行比比較，將其放放入已排序的的正確位置上上的方法，稱稱為：（C）A、希爾排序BB、起泡排序序C、插入排排序D、選擇擇排序13、N

6、個(gè)頂點(diǎn)點(diǎn)的強(qiáng)連通圖圖至少有 （A） 條邊HA、N B、N+11 C、N-11 D、NN（N-1）H14、棧通常采采用的兩種存存儲(chǔ)結(jié)構(gòu)是（AA）A、順序存儲(chǔ)結(jié)結(jié)構(gòu)和鏈表存存儲(chǔ)結(jié)構(gòu)B、散散列方式和索索引方式C、鏈鏈表存儲(chǔ)結(jié)構(gòu)構(gòu)和數(shù)組D、線線性存儲(chǔ)結(jié)構(gòu)構(gòu)和非線性存存儲(chǔ)結(jié)構(gòu)15、深度為44的二叉樹至至多有（D）個(gè)個(gè)結(jié)點(diǎn)A、8 B、166 C、7 D、11516、對(duì)線性表表進(jìn)行二分查查找時(shí)，要求求線性表必須須（C）A、以順序方式式存儲(chǔ)B、以以鏈接方式存存儲(chǔ)C、以順順序方式，且且結(jié)點(diǎn)按關(guān)鍵鍵字有序排序序D、以鏈接接方式存儲(chǔ)，且且結(jié)點(diǎn)按關(guān)鍵鍵字有序排序序17、線性表的的順序存儲(chǔ)結(jié)結(jié)構(gòu)是一種（AA）的存儲(chǔ)結(jié)結(jié)

7、構(gòu)、A、隨機(jī)存取BB、順序存取取C、索引存存取D、散列列存取18、串是一種種特殊的線性性表，其特殊殊性體現(xiàn)在（BB）A、可以順序存存儲(chǔ)B、數(shù)據(jù)據(jù)元素是一個(gè)個(gè)字符C、可可以鏈接存儲(chǔ)儲(chǔ)D、數(shù)據(jù)元元素可以是多多個(gè)字符19、任何一個(gè)個(gè)無向連通圖圖的最小生成成樹有BA、只有一棵BB、有一棵或或多棵C、一一定有多棵DD、可能不存存在20、在一棵非非空二叉樹的的中序遍歷序序列中，根結(jié)結(jié)點(diǎn)的右邊AA只有右子樹上的的所有結(jié)點(diǎn)BB、只有右子子樹上的部分分結(jié)點(diǎn)C、只只有左子樹上上的部分結(jié)點(diǎn)點(diǎn)D、只有左左子樹上的所所有結(jié)點(diǎn)、三、試分別按先先根遍歷，中中根遍歷，后后根遍歷法寫寫出二叉樹的的遍歷序列CEIGFJBAD先根

8、序列：ABBDHIEJJCFGCEIGFJBAD中根序列：HDDIBEJAAFCGH后根序列：HIIDJEBFFGCAH 四、畫出含有三三個(gè)結(jié)點(diǎn)的二二叉樹的所有有形態(tài)。五、給出圖中每每個(gè)頂點(diǎn)的入入度，出度和和頂點(diǎn)的度41415 頂點(diǎn) 入度 出度度 度5 22 1 36 22 2 4623 11 3 423 33 0 3 22 3 5 1 2 3六、用Dijkkstra算算法求圖中VV1到其余各各頂點(diǎn)的最短短路徑1 8 13 最最短路徑 長(zhǎng)度123 V11 V2 1323 322 7 VV1 V3 874 5 30 7 V1 V4(經(jīng)V3) 1374 V1 V5(經(jīng)經(jīng)V3,V44) 1965 6

9、6 17 9 V1 VV6(經(jīng)V33,V4,VV5) 21165 2 V1 V7(經(jīng)經(jīng)V2) 20七、已知無向圖圖，試給出：1.從A出發(fā)的的“深度優(yōu)先”遍歷序列2.從A出發(fā)的的“廣度優(yōu)先”遍歷序列3.該圖是連通通圖嗎？答：ABDCCEGFABCDEEFG是EBEBAGDAGDFCFC八、對(duì)照?qǐng)D未的的樹回答下列列問題CACAB BEDHGFEDHGFLKJNILKJNIMM1.樹中哪些是是葉結(jié)點(diǎn)？哪哪個(gè)是根結(jié)點(diǎn)點(diǎn)？答：葉結(jié)點(diǎn)D M N FF J K L；根結(jié)點(diǎn)點(diǎn)：A2.結(jié)點(diǎn)C的雙雙親結(jié)點(diǎn)是哪哪一個(gè)？A3.結(jié)點(diǎn)C的孩孩子有哪些？F G HH4.哪些是G的的兄弟？F、HHC的深度是多多少？3樹的深度

10、是多多少？5E的子孫哪些些？I M N九、用krusskal算法法求圖的最小小生成樹。21 144 2136 1 200 9 236 21 11 6 7 54 54 116 22213 22133 1 11 1 66 23455511 11 455511122 12241 9 22 14 22 414365365 1 6 1 9 64365365十、對(duì)于給定的的一組權(quán)W=14，115，7，44，20，113，5，88，10，試試畫出一棵哈哈夫曼樹，并并算出帶權(quán)路路徑長(zhǎng)度WPPL答：WPL=2292 1010573996202730199151514135487573996202730199151514135487十一、用Priim算法求圖圖的最小生成成樹2151155216452 114 14 1442151155216452 2 3 1 20 9 1 1 11 2233