必看!!!!!數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題及部分答案解析

1、0一是非題1. 數(shù)據(jù)結(jié)構(gòu)(應(yīng)該是抽象數(shù)據(jù)類型)可用三元式表示（D，S，P）。其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系，P是對(duì) D的基本操作集。(f)2 簡(jiǎn)單地說(shuō),數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。(t)3 判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表（頭指針為L(zhǎng)）中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn) 的條件是：p-next=L。(t)4 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取?表中任一元素的優(yōu)點(diǎn)。(f) 5 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(f)6. 在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是： P-next= S ; S- next = P-next;。(順序弄反了)(f)7 對(duì)于插入、刪除而言，線性表的鏈?zhǔn)?/p>

2、存儲(chǔ)優(yōu)于順序存儲(chǔ)。(t)8. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(f)9. 棧和隊(duì)列是操作上受限制的線性表。(t)10. 隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。棧和隊(duì)列是操作上受限制的線性表(f)11. 隊(duì)列是一種操作受限的線性表，凡對(duì)數(shù)據(jù)元素的操作僅限一端進(jìn)行。對(duì)列不是(f)12. 棧和隊(duì)列也是線性表。如果需要，可對(duì)它們中的任一元素進(jìn)行操作。(f)13. 棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。(f)14. 二叉樹(shù)中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對(duì)一般的樹(shù)，則無(wú)此限制，所 以，二叉樹(shù)是樹(shù)的 特殊情形。(f)15 二叉樹(shù)是一棵結(jié)點(diǎn)的度最大為二的樹(shù)二叉樹(shù)和樹(shù)相互獨(dú)立。

3、(f) 16 赫夫曼樹(shù)中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。(t)17 在二叉樹(shù)的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(t)18 假設(shè)B是一棵樹(shù)，B是對(duì)應(yīng)的二叉樹(shù)。則B的后根遍歷相當(dāng)于B的后序遍歷 后根遍歷相當(dāng)于中序遍歷。(f)19. 通常，二叉樹(shù)的第i層上有2i-1個(gè)結(jié)點(diǎn)。應(yīng)該為12i-1個(gè)(f)20. 中序線索二叉樹(shù)的優(yōu)點(diǎn)是便于在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。(t)21 二叉樹(shù)的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。(t)22 由樹(shù)結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹(shù)。 (t)23 鄰接多重表可以用以表示無(wú)向圖，也可用以表示有向圖。只能表示無(wú)向圖，有向圖用十

4、字鏈表(f)24 可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡驇Лh(huán)圖沒(méi)有。(f)25 有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。(t)26 關(guān)鍵路徑是AOE網(wǎng)中源點(diǎn)到匯點(diǎn)的最短路徑。(f)27 連通圖G的生成樹(shù)是一個(gè)包含G的所有n個(gè)頂點(diǎn)和n-1條邊的子圖。(f)28 一個(gè)無(wú)向圖的連通分量是其極大的連通子圖。(t)29 十字鏈表可以表示無(wú)向圖，也可用以表示有向圖。(f)30 鄰接表可以表示有向圖，也可以表示無(wú)向圖。（ t ）31. 二叉排序樹(shù)的平均查找長(zhǎng)度為O(log)。(t)32. 二叉排序樹(shù)的最大查找長(zhǎng)度與（LOG2N）同階。(f)33 選用好的HASH函數(shù)可避免沖突。哈希函

5、數(shù)有幾種處理沖突的方法(f)34 折半查找不適用于有序鏈表的查找。(t)35. 對(duì)于目前所知的排序方法，快速排序具有最好的平均性能。(t)36 對(duì)于任何待排序序列來(lái)說(shuō)，快速排序均快于冒泡排序。(f)37 在最壞情況下，堆排序的時(shí)間性能是O(nlogn),比快速排序好(t)38 快速排序具有最好的平均時(shí)間性能，它在任何時(shí)候的時(shí)間復(fù)雜度都是O（n log n）。(f)39. 字符串是數(shù)據(jù)對(duì)象特定的線性表。(t)40. 空串與空格串是相同的。(f)41. 對(duì)于一棵m階的B-樹(shù).樹(shù)中每個(gè)結(jié)點(diǎn)至多有m 個(gè)關(guān)鍵字.除根之外的所有非終端結(jié)點(diǎn)至 少有m/2個(gè)關(guān)鍵字。(f)42. 當(dāng)二叉排序樹(shù)是一棵平衡二叉樹(shù)時(shí)

6、，其平均查找長(zhǎng)度為O(log2n)。(t)43. 廣義表的表頭和表尾都是廣義表。(f)44 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(t)選擇題。1 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成( c )。 A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 順序組織和鏈接組織 C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 基本類型和組合類型2 線性表L在( b )情況下適于使用鏈表結(jié)構(gòu)實(shí)現(xiàn)。 A. 不需修改L的結(jié)構(gòu) B. 需不斷對(duì)L進(jìn)行刪除、插入 C. 需經(jīng)常修改L中結(jié)點(diǎn)值 D. L中含有大量結(jié)點(diǎn)3 帶頭結(jié)點(diǎn)的單鏈表L為空的判斷條件是 b 。 帶頭結(jié)點(diǎn)的循環(huán)鏈表L為空的判斷條件是 c 。 A. L=null B. L-next=null C.

7、 L-next=L D. L!=null4 若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定 的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼（若存在）結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至 表尾。以下為據(jù)此策略編寫(xiě)的算法，請(qǐng)選擇適當(dāng)?shù)膬?nèi)容，完成此功能。 順序表的存儲(chǔ)結(jié)構(gòu)為：typedef struct ElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間，0號(hào)單元作監(jiān)視哨 int length; /表長(zhǎng)度 SSTable;int search_seq(SSTable ST,KeyType key) /在順序表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。/若找到，則將該元素與其后繼交換位置

8、，并返回其在表中的位置，否則為0。ST.elem0.key=key;i=ST.length;while(ST.elemi.key!=key) f ;if( G ) ST.elemiST.elemi+1； e ； return i;A. i0 B. i=0 C. iST.length D. inext非空，此時(shí)若要?jiǎng)h除指針p所指的結(jié)點(diǎn)，可以通過(guò)如下方法進(jìn)行：將p所指結(jié)點(diǎn)的后繼的元素值復(fù)制到該結(jié)點(diǎn)，然后刪除其后繼結(jié)點(diǎn)。相應(yīng)的語(yǔ)句序列為：p-data = p-next-data; p-next = p-next-next; free(p -next)換指針的同時(shí)還要交換數(shù)據(jù)3 線性表的順序存儲(chǔ)結(jié)構(gòu)是

9、以 數(shù)組下標(biāo) 來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系的。4 已知P是單鏈表中某一結(jié)點(diǎn)的指針，P既不是首元結(jié)點(diǎn)也不是尾元結(jié)點(diǎn)，Q是P 的 前驅(qū) 結(jié)點(diǎn)指針。當(dāng)刪除P結(jié)點(diǎn)時(shí)，鏈表的鏈接可用語(yǔ)句（ q-netx = p-next ）實(shí)現(xiàn)。5 已知某樹(shù)的先根遍歷次序?yàn)閍bcdefg后根遍歷次序?yàn)閏debgfa。 若將該樹(shù)轉(zhuǎn)換為二叉樹(shù),其后序遍歷次序?yàn)椋?）。層次遍歷次序?yàn)椋?）。6 已知某二叉樹(shù)的先序遍歷次序?yàn)閍fbcdeg后序遍歷次序?yàn)閏edbgfa。 其后序遍歷次序?yàn)椋?）。層次遍歷次序?yàn)椋?）。7 在二叉樹(shù)的第i層上至少有_1_個(gè)結(jié)點(diǎn), 至多有_2_個(gè)結(jié)點(diǎn) , 深度為k的二叉樹(shù)至多有_2_-1_個(gè)結(jié)點(diǎn).8

10、對(duì)樹(shù)的遍歷有先序遍歷樹(shù)和后序遍歷樹(shù)。若以二叉鏈表作樹(shù)的存儲(chǔ)結(jié)構(gòu), 則樹(shù)的先序遍歷可借用二叉樹(shù)的 遍歷算法來(lái)實(shí)現(xiàn), 而樹(shù)的后序遍歷可借用二叉樹(shù)的 中序遍歷 遍歷算法來(lái)實(shí)現(xiàn)。9 設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少 是 2*h - 1 ，至多是 滿樹(shù) 。10 對(duì)任何一棵二叉樹(shù)T,若其終端結(jié)點(diǎn)數(shù)為n0.度為2的結(jié)點(diǎn)為n2,則n0與n2的關(guān)系為 ( n0 = n2 +1 )。11 如果對(duì)完全二叉樹(shù)中結(jié)點(diǎn)從1開(kāi)始按層進(jìn)行編號(hào)，設(shè)最大編號(hào)為n；那么，可以斷定編 號(hào)為i (i1)的結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為( i/2向下取整 )；所有編號(hào)（ in/2）的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。 1

11、2 n個(gè)頂點(diǎn)的連通圖至少有 條邊，至多有 n*(n-1)/2條邊，此時(shí)即是完全圖 條邊。13 對(duì)于圖的存儲(chǔ)結(jié)構(gòu)有（ 數(shù)組表示法 ）、（ 鄰接表法 ）( 十字鏈表法 ) ( 鄰接多重表法 )等方法。14 在一個(gè)無(wú)向圖的鄰接表中，若表結(jié)點(diǎn)的個(gè)數(shù)是m，則圖中邊的條數(shù)是_m/2_條。15 若有序表中關(guān)鍵字序列為：12，22，33，44，55，66，77，88，99對(duì)其進(jìn)行折半查找， 則在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度是（ ）。查找99時(shí)需進(jìn)行（ ）次比 較。16 在哈希表中，處理沖突的方法有開(kāi)放定址法， 再哈希表法 ， 鏈地址法 等。17 在二叉樹(shù)的第i層上至少有_個(gè)結(jié)點(diǎn), 至多有_個(gè)結(jié)點(diǎn) ,

12、深度為k的二叉樹(shù)至多有 個(gè)結(jié)點(diǎn).18 對(duì)于一棵高度為K的二叉排序樹(shù)，結(jié)點(diǎn)數(shù)最少可有 個(gè)，最多可有 個(gè)。19 用 中序遍歷 遍歷對(duì)二叉排序樹(shù)進(jìn)行訪問(wèn)可得到有序序列。20 已知Hash函數(shù)為 H（K）=K mod 13 ，散列地址為0 -14，用二次探測(cè)再散列 處理沖突，關(guān)鍵字（23，34，56，24，75，12，49, 52，36，92） 的分布如圖，則平均成功的查找長(zhǎng)度為（ ）、平均失敗的查找長(zhǎng)度為（ ）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1452 36925634 232475124921 一棵階的-樹(shù)，第一層至少有一個(gè)結(jié)點(diǎn)；第二層至少有2個(gè)結(jié)點(diǎn)， 除根之外的

13、所有非終端結(jié)點(diǎn)至少有（ ）棵子樹(shù)， 樹(shù)中每個(gè)結(jié)點(diǎn)至多有（ ）棵子樹(shù)。22 在哈希表中，處理沖突的方法有開(kāi)放定址法， ， , 。23 哈希表的查找效率取決于（ 哈希函數(shù)是否均勻； 處理沖突的方法； 哈希表的裝填因子 ）。24高度為4 (包含不帶關(guān)鍵字的葉子結(jié)點(diǎn)層)的7階B樹(shù)最少有 個(gè)關(guān)鍵字，最多 有_個(gè)關(guān)鍵字；如果其中的某結(jié)點(diǎn)正好有2個(gè)兒子，那么，該結(jié)點(diǎn)必定是 結(jié)點(diǎn)。25 對(duì)n個(gè)元素的序列進(jìn)行內(nèi)部排序，若用起泡排序法，最少的比較次數(shù)是 n-1 ，最多的比較次數(shù)是 n(n-1)/2 。25 (算法填空)Status Preordertraverse(Bitree T,Status(*Visit)(

14、Telemtype e) /先序非遞歸遍歷二叉樹(shù)。Initstack ( S ); Push ( S,T );While ( !stackempty( S ) ) While ( gettop( S, p )& _p_ ) if (!Visit (p-data ) ) return ERROR; _push(s,p-lchild)_ ; Pop ( S , p ); if ( _(!stackempty(s) _ ) _ pop(S, p); push( S, p-rchild ); return ok;26 (算法填空)下列算法試圖完成在數(shù)組A中搜索有無(wú)關(guān)鍵字key，若有，返回?cái)?shù)組下標(biāo),若無(wú)

15、，返回-1。在“ ”處填上合適的內(nèi)容,完成該算法。int BinarySearch (keytype A , int low,int high, keytype key )while ( low = high) middle = (low+high) /2;if ( Amiddle = key ) return middle; if (key Amiddle) high = middle -1 ; else low = middle + 1 ;return -1; /end of BinarySearch27 (算法填空)下列函數(shù)為堆排序中的堆調(diào)整過(guò)程（調(diào)整H.rs的關(guān)鍵字，使H.rs.m成為

16、一小頂堆）。請(qǐng)?jiān)凇?”處填上合適的內(nèi)容,完成該算法。Void heapadjust( heaptype H , int s , int m ) rc=H.rs;for (j=2*s;j=m;j*=2) if (jrj ) +j;if ( rc H.rj ) break;H.rs=H.rj; s=j; H.Rs = rc ;/heapadjust圖示結(jié)構(gòu)題1 已知在電文中只出現(xiàn)頻率為 ( 5,26,7,23,20,19 )的個(gè)字符， 畫(huà)出你建的哈夫曼樹(shù)，并給出其哈夫曼編碼。2.已知某二叉樹(shù)的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG 請(qǐng)畫(huà)出該二叉樹(shù)，并為之建立先序線索沒(méi)有左子樹(shù)，

17、則建立該節(jié)點(diǎn)的前驅(qū)，若沒(méi)有右子樹(shù)，這指向該節(jié)點(diǎn)的后繼。3 已知某二叉樹(shù)的先序遍歷次序?yàn)椋篴,b,c,d,e,f,g.中序遍歷次序?yàn)椋篵,a,d,f,e,g,c 畫(huà)出該二叉樹(shù)，并在該二叉樹(shù)上建立中序線索。4 某二叉樹(shù)的中序遍歷次序?yàn)锽EGFDAC， 先序遍歷次序?yàn)锳BDEFGC。 試畫(huà)出該二叉樹(shù)，并為之建立中序線索（圖示之）。5 已知某二叉樹(shù)的后序遍歷和中序遍歷次序分別為FBEDGCA和FBADECG， 請(qǐng)構(gòu)造并畫(huà)出該二叉樹(shù)。6 設(shè)某一電文只出現(xiàn)a,b,c,d,e,f,g 7個(gè)字母；出現(xiàn)頻率分別為30%,10%,05%,04%,13%,18% 及20%，請(qǐng)給出各字母的哈夫曼編碼。7 將圖示森林轉(zhuǎn)

18、換為二叉樹(shù)，并對(duì)該二叉樹(shù)先序全序線索化。 hda jibfec mlkg 8 將圖示森林轉(zhuǎn)換為二叉樹(shù)，并對(duì)該二叉樹(shù)中序全序線索化。 561 97832 4 9 某二叉樹(shù)的結(jié)點(diǎn)數(shù)據(jù)采用順序存儲(chǔ)表示如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19ABCDEFGHI（1）試畫(huà)出此二叉樹(shù)的圖形表示。（2）將此二叉樹(shù)看作森林的二叉樹(shù)表示，試將它還原為森林。 10 已知某有向圖如圖所示：a 1）給出其十字鏈表存儲(chǔ)結(jié)構(gòu) 2）給出其深度優(yōu)先遍歷次序。 3）給出其廣度優(yōu)先遍歷次序。cb 4）給出各強(qiáng)連通分量。ed 11 設(shè)輸入序列為20,45,30,89

19、,70,38,62,19，依次插入到一棵2-3樹(shù)中(初始狀態(tài)為空)，請(qǐng)畫(huà)出該B-樹(shù)。12 右圖為一棵3階B樹(shù)。 （20，25）1)畫(huà)出在該樹(shù)上插入元素15 后的B樹(shù)。 (10，14)（21）（35） 2)接著，再刪除元素35，畫(huà)出刪除后的B樹(shù)。13 已知Hash函數(shù)為 H（K）=K mod 13 ，散列地址為0 -14，用線性探測(cè)再散列處理 沖突，給出關(guān)鍵字（56，34，68，23，16，70，48，35，83，12，14，57） 在散列地址的分布。并指出平均成功的查找長(zhǎng)度是多少? 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 14 根據(jù)插入次序（20，30，70，60

20、，10，100，110，90，80。）建立平衡的二叉排序樹(shù)。 15 設(shè)哈希表長(zhǎng)為16，哈希函數(shù)為H(key)=key mod 13，用開(kāi)放定址法的二次探測(cè)再散列處理沖突（di=12，-12，22，-22，32，-32）。依次存入12個(gè)元素：56，82，17,24,36,21,83,96,13,34,57,50。請(qǐng)畫(huà)出它們?cè)诒碇械姆植记樾巍?6 已知待排序序列為：25,12,9,20,7,31,24,35,17,10，試寫(xiě)出： (1). 堆排序初始建堆(大頂堆)的結(jié)果； (2). 以第一個(gè)元素為樞軸的快速排序一趟掃描的結(jié)果； (3). 希爾排序第一趟(增量為5)的結(jié)果。 算法設(shè)計(jì)題1 設(shè)有一個(gè)帶頭結(jié)點(diǎn)、元素按值遞增有序的單鏈表，結(jié)點(diǎn)