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

1、.一、選擇題1.棧和隊列的共同特點是( )。A.只允許在端點處插入和刪除元素B.都是先進后出 C.都是先進先出D.沒有共同點 2.用鏈接方式存儲的隊列，在進行插入運算時( ). A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D.頭、尾指針可能都要修改3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( ) A. 隊列 B. 棧 C. 線性表 D. 二叉樹4.設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在（ ）位置，腳注(10)表示用10進制表示。 A688 B678 C692 D6965.樹最適合用

2、來表示( )。 A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù)6.二叉樹的第k層的結(jié)點數(shù)最多為( ). A2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進行二分查找，則查找A3的比較序列的下標依次為( ) A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，38.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為( ) A. O（1） B. O（n） C. O（1og2n） D. O（n2）9.對于線性表（7，34，55，25，64，46，2

3、0，10）進行散列存儲時，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個， A1 B2 C3 D410.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個連通圖。 A.5 B.6 C.7 D.811.一個鏈隊列中，f，r分別為隊首、隊尾指針，則插入s所指結(jié)點的操作為( )。A）f-next=c；f=s； B） r-next=s；r=s；C）s-next=r；r=s； D） s-next=f；f=s；12.下列說法正確的是（ ）。A）二叉樹中每個結(jié)點的度都為2 B）二叉樹的度為2C）一棵二叉樹的度可小于2 D）二叉樹中至少有一個結(jié)點的度213.一棵非空二叉樹先序遍歷

4、與后序遍歷序列正好相反，則該二叉樹（ ）。A）所有的結(jié)點均無左孩子 B）所有的結(jié)點均無右孩子C）只有一個葉子結(jié)點 D）是任意一棵二叉樹14.二叉排序樹中，鍵值最小的結(jié)點一定（ ）。A）左指針為空 B）右指針為空C）左右指針均為空 D）左右指針均非空15.n個頂點的強連通圖至少有（ ）條邊。 A） n-1 B） n C）n+1 D）n(n-1)16.在一個有向圖中，頂點入度之和與頂點出度之和的比值（ ）。A）1/2 B）1 C）2 D）417.高度為h的二叉樹只有度為0和2的結(jié)點，則此二叉樹至少為（）結(jié)點。 A）2*h B）2*h-1 C）2*h+1 D）h+118設(shè)某完全無向圖中有n個頂點，則

5、該完全無向圖中有（ ）條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-119設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（ ）。(A) 9(B) 10(C) 11(D) 1220設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有（ ）個表頭結(jié)點。(A) n-1(B) n(C) n+1(D) 2n-121設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準進行一趟快速排序的結(jié)果為（ ）。(A) 2，3，5，8，6(B) 3，2，5，8，6(C) 3，2，5，6，8(D) 2，3，6，5，822.按照二叉樹的定義，具有3個結(jié)點的二叉樹有

6、( )種形態(tài)。 A）3 B）4 C）5 D）623.下列排序算法中，可能會出現(xiàn)在最后一趟開始之前，所有元素都不在其最終位置上是( ). A） 堆排序 B） 冒泡排序 C）快速排序 D） 插入排序24.一組記錄的排序碼為46,79,56,38,40,84。用堆排序方法建立的初始堆為( )。A） 79,46,56,38,40,80 B） 84,79,56,38,40,46C） 84,79,56,46,40,38 D） 84,56,79,40,46,3825.將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時，通常需要使用( )。 A）棧 B）隊列 C）鏈表 D）樹26.有10個結(jié)點的連通無向圖，其邊數(shù)至少有( )

7、。 A）8條 B）9條 C）10條 D）11條27.一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是( )。A）edcba B） decba C） dceab D） abcde28.高度為h的完全二叉樹中所包含的結(jié)點數(shù)至少為( )。 A）2*h個 B）2h-1個 C）2*h+1個 D）h+1個29設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（ ）。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)30設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（ ）個結(jié)點。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-131設(shè)某無向圖中有

8、n個頂點e條邊，則該無向圖中所有頂點的入度之和為（ ）。(A) n(B) e(C) 2n(D) 2e32在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（ ）。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)33設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（ ）條有向邊。(A) n(B) n-1(C) m(D) m-134設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（ ）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A) 3(B) 4(C) 5(D) 835設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（ ）。(A) 必須

9、判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不作任何判別36設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（ ）。(A) O(1)(B) O(log2n)(C)(D) O(n2)37設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為（ ）。(A) n，e(B) e，n(C) 2n，e(D) n，2e38. 設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（ ）條邊。(A) n(n-1)(B) n+1(C) n(D) n(n+1)39設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下

10、列（ ）方法可以達到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序40.下列四種排序中（ ）的空間復(fù)雜度最大。(A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序二、填空題1. 設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為_，快速排序的平均時間復(fù)雜度為_。2. 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的語句序列為_（設(shè)結(jié)點中的兩個指針域分別為llink和rlink）。3. 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為_。4. 深度為k的完全二叉樹中最少有_個結(jié)點。5. 設(shè)初始記錄關(guān)鍵字序列為(K1，K

11、2，Kn)，則用篩選法思想建堆必須從第_個元素開始進行篩選。6. 設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有_個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有_個空指針域。7. 設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲_個隊列元素；當(dāng)前實際存儲_個隊列元素（設(shè)頭指針F指向當(dāng)前隊頭元素的前一個位置，尾指針指向當(dāng)前隊尾元素的位置）。8. 設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_個元素。9. 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則以20為中軸的一趟快速排序結(jié)果為_

12、。10. 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_。11.頭結(jié)點為H的單循環(huán)鏈表為空的條件是_ _。12.線性表作為棧時，被稱為_ _。13.在堆排序、快速排序和歸并排序中，若只從最壞情況下排序最快并且要節(jié)省內(nèi)存空間考慮，應(yīng)選取 方法。14.一棵二叉樹有11個度數(shù)為0的結(jié)點，則該二叉樹的二度結(jié)點個數(shù)為_ _。15.平衡二叉樹是每個結(jié)點的左右子樹深度之差的絕對值不超過1的_ _。16.關(guān)鍵碼序列為21,12,20,35,40,51,87,33,42,90,2,18,34。步長因子序列為3,1時，一趟希爾排序結(jié)果序列為_ _。17.

13、順序存儲的線性表相對與鏈接存儲的線性表，其優(yōu)點是_ _。18.就排序的穩(wěn)定性而言，簡單選擇排序方法是_ _。19.設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是_。20.設(shè)無向圖對應(yīng)的鄰接矩陣為A，則A中第i上非0元素的個數(shù)_第i列上非0元素的個數(shù)（填等于，大于或小于）。21for(i=1，t=1，s=0；i=n；i+) t=t*i；s=s+t；的時間復(fù)雜度為_。22設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X，則進行插入操作的語句序列為_（設(shè)結(jié)點的指針域為next）。23設(shè)有向圖G的二元組形式表示為G =（D，R），D=1，2，

14、3，4，5，R=r，r=，則給出該圖的一種拓撲排序序列_。24設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是_。25設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有_個結(jié)點數(shù)。26設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為_。27設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_。28簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為_。29快速排序算法的空間復(fù)雜度平均情況下為_，最壞的情況下為_。30.散列表中解決沖突的兩種方法是_和_。31.設(shè)指針變量p指向雙向鏈表

15、中的結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X的操作序列為_=p；s-right=p-right；_=s； p-right-left=s；（設(shè)結(jié)點中的兩個指針域分別為left和right）。32.設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有_條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有_條無向邊。33.設(shè)關(guān)鍵字序列為(Kl，K2，Kn)，則用篩選法建初始堆必須從第_個元素開始進行篩選。34.解決散列表沖突的兩種方法是_和_。35.設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有_個。36.高度為h的完全二叉樹中最少有

16、_個結(jié)點，最多有_個結(jié)點。37.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是_。38.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是_。39.設(shè)一棵二叉樹的前序序列為ABC，則有_種不同的二叉樹可以得到這種序列。40.順序存儲的長度為m的循環(huán)隊列為空的條件是_ _。41.線性表作為隊時，被稱為_ _。42.就快排序和堆排序，若原始記錄接近正序或反序，則最好選用 方法。43.在有序表(12、24、36、48、60、72、84)中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為_ _。44.

17、二叉排序樹每個結(jié)點的左右子樹深度之差的絕對值不超過1，稱為_ _。45.n階對稱方陣A，以下三角矩陣壓縮到一維數(shù)組Sn*(n+1)/2中，若按行序為主存儲，則A的第i行第j列元素(i=j)對應(yīng)在S中的存儲位置是_ _。46.順序存儲的線性表相對與鏈接存儲的線性表，其缺點是_ _。47.就排序的穩(wěn)定性而言，快排序方法是_ _。48.設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_。49.設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有_條邊。50.設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它

18、們調(diào)整成初始堆只需把16與_相互交換即可。三、解答題1、序列70,50,18,26,37,45,62,23,46,59,105,按順序插入結(jié)點，建立一棵二叉排序樹，然后刪除結(jié)點37，刪除后樹高不能增高。分別畫出該二叉排序樹及刪除結(jié)點37后的二叉排序樹。2、對帶權(quán)圖,給出以Prim算法構(gòu)造最小生成樹過程，并計算該樹的權(quán)。3、對帶權(quán)圖, 給出以克魯斯卡亞算法構(gòu)造最小生成樹過程，并計算該樹的權(quán)。4、正文為“CDDDAABBEECAAECDAACEDDABE”,設(shè)計ABCDE這5個字母的哈夫曼編碼，使得正文編碼最短。5、給定權(quán)值6,12,3,75,40,30,20,65,34，給出按算法建立的哈夫曼樹

19、靜態(tài)三叉鏈表存儲結(jié)構(gòu)。6、給定權(quán)值6,12,3,75,40,30,20,65,34，構(gòu)建哈夫曼樹。7、先序遍歷序列a,b,c,s,g,f,d,e,j,h,k,i和中序遍歷序列s,c,b,d,f,e,g,a,h,k,j,i，的二叉樹,畫出此二叉樹，并給出其后序遍歷序列。8、畫出深林轉(zhuǎn)化的二叉樹,并給出二叉樹的先序、中序、后序遍歷序列。9、給定按關(guān)鍵碼序列76,42,32,17,73,54,48,62,98,89,92,105，構(gòu)建小頂堆逐步篩選過程。V4V5V3V2V110、給定按關(guān)鍵碼序列76,42,32,17,73,54,48,62,78,89,2,10，構(gòu)建大頂堆逐步篩選過程。11、畫出有

20、向圖的鄰接表和逆鄰接表存儲示意圖。12、畫出圖的鄰接表存儲示意圖，并按鄰接表給出深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。13、給定關(guān)鍵碼序列30,25,46,12,7,6,21,13,15,42,哈希函數(shù)h(key)=key%7，基本表長度為10，用線性探測法解決沖突，關(guān)鍵碼按給出的順序填入表中。請畫出哈希表，并求等概率情況下查找成功的平均查找長度。14、給定關(guān)鍵碼序列30,25,46,12,7,6,21,13,15,42,哈希函數(shù)h(key)=key%7，基本表長度為10，用二次探測法解決沖突，關(guān)鍵碼按給出的順序填入表中。請畫出哈希表，并求等概率情況下查找成功的平均查找長度。15、給定關(guān)鍵碼序列

21、30,25,46,12,7,6,21,13,15,42,哈希函數(shù)h(key)=key%7，基本表長度為7，用拉鏈法解決沖突，關(guān)鍵碼按給出的順序填入表中，且總是在鏈表的第一個結(jié)點前插入。請畫出哈希表，并求等概率情況下查找成功的平均查找長度。#defineTBLLEN2000class CQTBL public:void H1();private:MYTYPE tTBLLEN;intcnt;/記錄表中元素個數(shù);void CQTBL:H1()int low,high;MYTYPE m;for(low=0,high=cnt-1;lowhigh;)while(lowhigh & tlow.m60) lo

22、w+;while(low=60) high-;if(low=0 & jb.tj.c) tlen=ti-;elsetlen=b.tj+;for(;t;j+,len-) tlen=b.tj;cnt=cnt+t;5.bool CQTBL:AddElem(MYTYPE &a)/返回真，添加成功boolv=false;if(cnt=0 & ext!=NULL & pf-next-e.c e.c;) pf=pf-next;q=s;s=s-next;q-next=pf-next;pf-next=q;pf=q;b.h.next=NULL;7.void LINKTBL:NZ()NODE

23、TYPE *s,*q;for(s=h.next,h.next=NULL;s!=NULL;)q=s;s=s-next;q-next=h.next;h.next=q;8.int LINKTBL:GetNodeNum()intv=0;NODETYPE *s;for(s=h.next;s!=&h;s=s-next) v+;return v;四、算法設(shè)計題1、對數(shù)學(xué)成績，將不及格和及格的學(xué)生分成前后兩部分，使表前面為不及格的學(xué)生，后面為及格的學(xué)生。不要求對這些元素按數(shù)學(xué)成績排序，但要求盡量減少交換次數(shù)。2、表A按語文成績非遞減有序，表B按語文成績非遞增有序，將B表學(xué)生添加到A表，使A表依然按語文成績非遞減有序，B表不變。要求移動元素次數(shù)不超過兩表長度之和。5、表A按語文成績非遞減有序，向表中添加一個學(xué)生，并保持A表的有序性。6、對兩個按語文成績非遞減有序的帶頭結(jié)點單鏈表A和B，將B表并入A表，而不改變其排序性，并將B表設(shè)置為空表。7、逆置單鏈表，即將結(jié)點順序為：H-a1-a2-an，置換為：H-an-a2-a1。要求，不交換元素值，通過修改結(jié)點指針完成。8、求帶頭結(jié)點的單循環(huán)鏈表中的結(jié)點個數(shù)，不包括頭結(jié)點。9、統(tǒng)計二叉樹中葉子結(jié)點數(shù)目typedefstruct nodeELEMe;struct node *lc,*rc;NODE;class CTREE public:int