PAGE1《數(shù)據(jù)結(jié)構(gòu)》復習資料1一、選擇題1.一棵二叉樹中第６層上最多有（）個結(jié)點。A.２B.31C.32D.642.順序表中數(shù)據(jù)元素的存取方式為（）。A.隨機存取B.順序存取C.索引存取D.連續(xù)存取3.設有無向圖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)}。對G進行深度優(yōu)先遍歷，正確的遍歷序列是（）。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b4.在待排元素序列基本有序的前提下，效率最高的排序方法是（）。A.插入B.選擇C.快速D.歸并5.設表中含100個數(shù)據(jù)元素，用折半查找法進行查找，則所需最大比較次數(shù)為（）。A.50B.25C.10D.76.設哈希表地址范圍為0~19，哈希函數(shù)H(key)=key%17，使用二次探測再散列法處理沖突。若表中已存放有關(guān)鍵字值為6、22、38、55的記錄，則再放入關(guān)鍵字值為72的記錄時，其存放地址應為（）。A.2B.3C.4D.7E.8F.以上都不對7.設對下圖從頂點a出發(fā)進行深度優(yōu)先遍歷，則（）是可能得到的遍歷序列。A.acfgdebB.abcdefgC.acdgbefD.abefgcd8.若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A.快速排序B.堆排序C.歸并排序D.直接插入排序9.設有一組關(guān)鍵字值（46,79,56,38,40,84），則用堆排序的方法建立的初始堆為（）。A.79,46,56,38,40,84B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,3810.設廣義表L=((a,()),b,(c,d,e))，則Head(Tail(Tail(L)))的值為（）。A.bB.cC.(c)D.(c,d,e)11.在樹形結(jié)構(gòu)中，數(shù)據(jù)元素間存在（）的關(guān)系。A.一對一B.一對多C.多對多D.除同屬一個集合外別無關(guān)系12.一棵度為3的樹中，度為3的結(jié)點有2個，度為2的結(jié)點有2個，度為1的結(jié)點有2個，則度為0的結(jié)點有（）。A.5個B.6個C.7個D.8個13.（）是數(shù)據(jù)的不可分割的最小單位。A.數(shù)據(jù)元素B.數(shù)據(jù)對象C.數(shù)據(jù)項D.數(shù)據(jù)結(jié)構(gòu)14.直接插入排序在最好情況下的時間復雜度為（）。A.O(logn)B.O(n)C.O(n*logn)D.O(n2)15.以下屬單鏈表優(yōu)點的是（）。A.順序存取B.插入操作能在O(1)的時間復雜度上完成C.插入時不需移動數(shù)據(jù)元素D.節(jié)省存儲空間16.在長為n的順序表中刪除一個數(shù)據(jù)元素，平均需移動（）個數(shù)據(jù)元素。A.nB.n-1C.n/2D.(n-1)/217.若采用順序映象，則數(shù)據(jù)元素在內(nèi)存中占用的存儲空間（）。A.一定連續(xù)B.一定不連續(xù)C.可連續(xù)可不連續(xù)18.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前隊尾指針rear和隊頭指針front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（）。A.1和5B.2和4C.4和2D.5和119.串的長度是指（）。A.串中所含不同字母的個數(shù)B.串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D.串中所含非空格字符的個數(shù)20.設在一不帶頭結(jié)點的鏈隊列中，front和rear分別為其隊頭和隊尾指針，則判定該隊中只有一個結(jié)點的條件是（）。A.front->nextB.rear->nextC.front==rearD.front!=rear二、填空題1．具有N個結(jié)點的無向完全圖共有________條邊。2．數(shù)據(jù)結(jié)構(gòu)課程是研究數(shù)據(jù)的________、________、________等三個方面的內(nèi)容。3．對一棵二叉排序樹進行中序遍歷時，得到的結(jié)點序列是一個________。4．已知二維數(shù)組a[10][8]采用行優(yōu)先存儲方式，每個元素占2個存儲單元，第一個元素的存儲地址是1012，則元素a[4][5]的存儲地址為________。5．畫出具有3個結(jié)點的二叉樹的所有形態(tài)：________。6．對于一個單鏈接存儲的線性表，假定表頭指針指向鏈表的第一個結(jié)點，則在表頭插入結(jié)點的時間復雜度為________，在表尾插入結(jié)點的時間復雜度為________。7．已知完全二叉樹的第8層有8個結(jié)點，則其葉子結(jié)點數(shù)是________。三、問答題1.假設將循環(huán)隊列定義為：以域變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)，試寫出其入隊和出隊算法（在出隊算法中要返回隊頭元素）。2.設有上三角矩陣(aij)n×n，將其上三角元素逐行存于數(shù)組B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下標變換公式。3.設n為正整數(shù)，則在下面的程序段中，語句“a+=2;”的頻度為多少？for(x=0;x<n;++x)for(y=0;y<n;++y)a+=2;4.設哈希函數(shù)H(key)=key%13，用公共溢出區(qū)法處理沖突，試在長度為18的散列地址空間中對關(guān)鍵字序列（71，28，46，14，2，20，85，58）構(gòu)造哈希表，要求畫出哈希表存儲結(jié)構(gòu)示意圖，并求等概率下查找成功時的平均查找長度。5.設用于通信的電文由8個字母組成，字母在電文中出現(xiàn)的頻率分別為0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。試為這8個字母設計哈夫曼編碼，要求畫出設計過程中所構(gòu)造的哈夫曼二叉樹。答案1一．選擇題1-5CADAA6-10DACBD11-15BCCDC16-20DABBC二．填空題1.N(N+1)/22.操作對象、關(guān)系、操作3.有序序列4.10505.6.O(1),O(n)7.68三．問答題1.#defineMAXQSIZE100typedefstruct{ElemTypebase[MAXQSIZE];intrear;intlength;}Queue;StatusEnQueue(Queue&Q,ElemTypee){if(Q.length==MAXQSIZE)returnERROR;Q.rear=(Q.rear+1)%MAXQSIZE;Q.base[Q.rear]=e;Q.length++;returnOK;}//EnQueueStatusDeQueue(Queue&Q,ElemType&e){if(!Q.length)returnERROR;front=(Q.rear-Q.length+1)%MAXQSIZE;e=Q.base[head];Q.length--;}//DeQueue2.3.n24.H(71)=6H(28)=2H(46)=7H(14)=1H(2)=2H(20)=7H(85)=7H(58)=6ASL=(1+1+1+1+2+3+4+5)/8=9/45.編碼：0.02:001000.03:001010.05:00110.08:0000.12:1000.17:1010.22:010.31:11《數(shù)據(jù)結(jié)構(gòu)》復習資料2一．選擇題1.在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（

）。A．內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B.靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu) D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)2．某無向圖G是連通的，則結(jié)點數(shù)n和邊數(shù)e一定有如下關(guān)系（

）。A.e>=n-1

B.e>=n-2

C.

e>=n-3

D.e>=n-43．能采用二分查找的數(shù)據(jù)結(jié)構(gòu)是（

）A.線性表

B.二叉樹

C.有序表

D.哈希表4．下列哪一個不屬于算法的性質(zhì)（

）。A．輸入性

B．輸出性

C．可執(zhí)行性

D．可修改性5．一棵有n（n>0）個結(jié)點的滿二叉樹共有（

）個葉子結(jié)點。A.2n

B.2n-1

C.2n+1

D.(n-1)/26．假設指針p指向單鏈表中的某一結(jié)點，若在p指針的后面插入一個新結(jié)點q，只需修改下列哪個指針值即可（

）。A．p=q;q=p.next;

B．p=q.next;q.next=p.nextC．p.next=q;q.next=p.next;

D．q.next=p.next;p.next=q;7．若進棧系列為：a，b，c，d，則下列哪一個不可能是出棧系列（

）。A．a(chǎn)，b，c，d

B．c，d，b，aC．a(chǎn)，c，d，b

D．c，a，b，d8.將一個遞歸算法改為對應的非遞歸算法時，通常需要使用（

）。A.棧B.隊列C.循環(huán)隊列 D.優(yōu)先隊列9.在循環(huán)隊列中用數(shù)組A[0..m-1]存放隊列元素，其隊頭和隊尾指針分別為front和rear，則當前隊列中的元素個數(shù)是（

）。A.(front-rear+1)%m B.(rear-front+1)%mC.(front-rear+m)%m D.(rear-front+m)%m10.n個頂點的連通圖至少有（

）條邊A.n-1

B.n

C.n+1

D.0二．應用題1．對給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應的哈夫曼樹，并計算它的帶權(quán)路徑長度。2．已知一組元素為（46,25,78,62,12,37,70,29），試畫出按元素排列次序插入生成的一棵二叉排序樹。3．設散列表的長度m=13；散列函數(shù)為H(K)=Kmodm，給定的關(guān)鍵碼序列為19，14，23，01，68，20，84，27，55，11，試畫出用線性探查法解決沖突時所構(gòu)造的散列表。三．算法設計題1.設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點。

答案一．選擇題1.C2.A3.B4.D5.B6.C7.D8.A9.D10.A二．應用題1.構(gòu)造的哈夫曼樹如圖：樹的帶權(quán)路徑長度為：WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202.解答：3.解答：設散列表的長度m=13；散列函數(shù)為H(K)=Kmodm，給定的關(guān)鍵碼序列為19,14,23,01,68,20,84,27,55,11,則有H(19)=6，成功；H(14)=1,成功；H(23)=10,成功；H(01)=1，沖突，=2，成功；H(68)=3,成功；H(20)=7,成功；H(84)=6，沖突，=7，沖突，=8，成功；H(27)=1，沖突，=2，沖突，=3，沖突，=4，成功；H(55)=3，沖突，=4，沖突，=5，成功；H(11)=11,成功。

012345678910111214016827551920842311(1)(2)(1)(4)(3)(1)(1)(3)(1)(1)三．算法設計題1.【解答】ElemTypeMax(LinkListL){//假定第一個結(jié)點中數(shù)據(jù)具有最大值if(L->next==NULL)returnNULL;pmax=L->next;p=L->next->next;////如果下一個結(jié)點存在while(p!=NULL){//如果p的值大于pmax的值，則重新賦值if(p->data>pmax->data)pmax=p;//遍歷鏈表p=p->next;}returnpmax->data;}

《數(shù)據(jù)結(jié)構(gòu)》復習資料3一．應用題1．已知二叉樹的中序遍歷序列和后序遍歷序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。2．若一個圖的邊集為{(A,B),(A,C),(A,D),(B,D),(C,F),(D,E),(D,F)}，從頂點A開始分別對該圖進行深度優(yōu)先搜索和廣度優(yōu)先搜索，要求頂點值小的鄰接點被優(yōu)先訪問，則寫出得到的深度優(yōu)先搜索和廣度優(yōu)先搜索的頂點序列。3．下圖所示是一個無向帶權(quán)圖，請按Prim算法求最小生成樹。4．給定數(shù)據(jù)元素系列為{47，23，2，15，98，57，22，6，12}，請寫出直接選擇排序各趟的結(jié)果。5．已知散列函數(shù)H(k)=kmod12，鍵值序列為(25,37,52,43,84,99,120,15,26,11,70,82)，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度。二、算法設計題1.設計一個算法，在順序線性表L中刪除第i個元素，并返回其值。

答案一．應用題1.二叉樹的構(gòu)造過程如圖：2.深度優(yōu)先搜索得到的頂點序列：A,B,D,E,F,C廣度優(yōu)先搜索得到的頂點序列：A,B,C,D,F,E3.解答：按Prim算法求最小生成樹的過程如下：4.解答：初始：47，23，2，15，98，57，