數(shù)據(jù)結構期末復習題答案

.PAGE.以下與數(shù)據(jù)的存儲構造無關的術語是〔c〕C、哈希表一個向量第一個元素的存儲地址是100，每個元素的長度為2，那么第5個元素的地址是〔B〕B、108假設帶頭結點的單向循環(huán)鏈表的頭指針為head,那么該鏈表為空的判定條件是〔C〕C、head–>next==head假設進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進展，那么不可能出現(xiàn)的出棧序列是〔D〕D、2，3，5，1，6，4以下關鍵字序列中，構成小根堆的是〔A〕A、{12，21，49，33，81，56，69，41}以下數(shù)據(jù)構造中，不屬于二叉樹的是〔A〕A、B樹用順序存儲的方法來存儲一棵二叉樹，存放在一維數(shù)組A[1..N]中，假設結點A[i]有右孩子，那么其右孩子是〔C〕。C、A[2i+1]設樹T的高度為4，其中度為1、2、3、4的結點個數(shù)分別為4、2、1、1，那么T中葉子數(shù)為〔D〕D、8有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開場逐個插入數(shù)據(jù)來形成二叉排序樹，假設希望高度最小，那么應選擇下面哪個序列輸入〔B〕B、37，24，12，30，53，45，96對下面有向圖給出了四種可能的拓撲序列，其中錯誤的選項是〔C〕C、5，1，6，3，4，2m階B-樹中所有非終端〔除根之外〕結點中的關鍵字個數(shù)必須大于或等于(B)B、[m/2]-1散列文件也稱為(C)B、索引文件數(shù)據(jù)構造是〔D〕D、相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合從邏輯關系來看，數(shù)據(jù)元素的直接前驅為0個或1個的數(shù)據(jù)構造只能是〔C〕C、線性構造和樹型構造設p為指向雙向循環(huán)鏈表中某個結點的指針，p所指向的結點的兩個鏈域分別用p→llink和p→rlink表示，那么同樣表示p指針所指向結點的表達式是〔D〕D、p→llink→rlink假設棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，那么棧滿的條件是〔B〕B、top[1]+1=top[2]假設一棵二叉樹有11個葉子結點，那么該二叉樹中度為2的結點個數(shù)是〔A〕A、10樹的先根序列等同于與該樹對應的二叉樹的〔A〕A、先序序列 下面關于哈希(Hash，雜湊)查找的說確的是(C)C、不存在特別好與壞的哈希函數(shù)，要視情況而定以下序列中，〔D〕是執(zhí)行第一趟快速排序后所得的序列。D、[68，11，69，23，18][93，73]以下關鍵字序列中，構成小根堆的是(D)D、(15，28，46，37，84，58，62，41)ISAM文件和VASM文件屬于(C)C、索引順序文件下面程序段的時間復雜度為〔C〕for(i=0;i<m;i++)for(j=0;j<n;j++)A[i][j]=i*j;C、O(m*n)指針p和q分別指向某單鏈表中第一個結點和最后一個結點。假設指針s指向另一個單鏈表中某個結點，那么在s所指結點之后插入上述鏈表應執(zhí)行的語句為〔A〕A、q->next=s->next；s->next=p；為便于判別有向圖中是否存在回路，可借助于〔D〕D、拓撲排序算法假設以S和X分別表示進棧和退棧操作，那么對初始狀態(tài)為空的?？梢赃M展的棧操作系列是〔D〕D、SSS**S**設有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,那么棧的容量至少應該是(B)B、3假設以數(shù)組A[m]存放循環(huán)隊列的元素。隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，那么隊頭元素所在的存儲位置為〔B〕。B、(rear-length+m)%m在一個鏈隊列中，front和rear分別為頭指針和尾指針，那么插入一個結點s的操作為〔D〕。D、rear->next=s;rear=s;對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關鍵字是〔D〕D、25和51采用二叉鏈表存儲的n個結點的二叉樹，共有空指針〔A〕個。A、n+1連通網的最小生成樹是其所有生成樹中〔D〕D、邊的權值之和最小的生成樹對記錄序列(314，298，508，123，486，145)依次按個位和十位進展兩趟基數(shù)排序之后所得結果為〔B〕B、508，314，123，145，486，298任何一個無向連通圖的最小生成樹(C)。C、一棵或多棵無向圖的鄰接矩陣是一個(C)C、對稱矩陣設無向圖G-=(V,E)和G’=(V’,E’),如G’為G的生成樹，那么以下說法中不正確的選項是(B)。B、G’為G連通分量以v1為起始結點對以下圖進展深度優(yōu)先遍歷，正確的遍歷序列是〔D〕 D、v1，v2，v5，v6，v7，v3，v4下面幾個符號串編碼集合中，不是前綴編碼的是〔B〕B、{0,1,00,11}希爾排序的增量序列必須是〔B〕。B、遞減的采用起泡排序法對n個關鍵字進展升序排序，假設要使排序過程中比擬關鍵字的次數(shù)最多，那么初始時的序列應滿足條件〔D〕D、關鍵字從大到小排列在以下部排序中(A)是不穩(wěn)定的。A、希爾排序分別以以下序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是(C)。A、〔100，80，90，60，120，110，130〕在查找過程中，沖突指的是〔C〕。C、不同鍵值對應一樣的存儲地址對有14個元素的有序表A[1..14]作二分查找，查找元素A[4]時的被比擬元素依次為〔D〕。D、A[7]，A[3]，A[5]，A[4]以v1為起始結點對以下圖進展廣度度優(yōu)先遍歷，正確的遍歷序列是〔A〕v1，v2，v3，v4，v5，v6，v7二、填空題(本大題共10小題，每題2分，假設有兩個空格，每個空格1分，共20分)數(shù)據(jù)的物理構造包括數(shù)據(jù)元素的存儲和數(shù)據(jù)之間關系的存儲。假設一個算法中的語句頻度之和為T(n)=1921n+4nlogn,那么算法的時間復雜度為nlogn。下面程序段的時間復雜度是。i=1；while(i<=n)i=i*3；循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，其頭尾指針分別是front和rear，那么當前隊列的元素個數(shù)是〔rear-front+m〕%m主要是使插入和刪除等操作統(tǒng)一〔n-1〕/2。在單鏈表中設置頭結點的作用是深度優(yōu)先。線性表L=〔a1,a2,…,an〕用數(shù)組表示，假定刪除表中任一元素的概率一樣，那么刪除一個元素平均需要移動元素的個數(shù)是一樣值關鍵字。一無向圖G=〔V，E〕，其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點a開場遍歷圖，得到的序列為abecd，那么采用的是前移遍歷方法。如果排序過程不改變時間復雜度之間的相對次序，那么稱該排序方法是穩(wěn)定的。從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需出度一個位置。當問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的10。假設以鄰接矩陣表示有向圖，那么鄰接矩陣上第i行中非零元素的個數(shù)即為頂點vi的sxss**ssxss**x。一棵含999個結點的完全二叉樹的深度為12。假設S和X分別表示進棧和出棧操作，由輸入序列"ABC〞得到輸出序列"BCA〞的操作序列為SSXS**，那么由"a*b+c/d〞得到"ab*cd/+〞的操作序列為4。.如下圖的有向無環(huán)圖可以排出L->next->next==L邊種不同的拓撲序列。從空樹起，依次插入關鍵字1l，27，35，48，52，66和73構造所得的二叉排序樹，在等概率查找的假設下，查找成功時的平均查找長度為384。帶頭結點的雙循環(huán)鏈表L中只有一個元素結點的條件是隊列。求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中邊稠密、邊稀疏的數(shù)目正相關。一棵完全二叉樹中共有768結點，那么該樹中共有5個葉子結點。實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標志數(shù)組標志已訪問的圖的結點外，還需要8、64存放被訪問的結點以實現(xiàn)遍歷。Prim〔普里姆〕算法適用于求2h-1的網的最小生成樹；kruskal〔克魯斯卡爾〕算法適用于求2h-1的網的最小生成樹。對長度為20的有序表進展二分查找的判定樹的高度為n-1。設一棵完全二叉樹有128個結點，那么該完全二叉樹的深度為n，有_個葉子結點。高度為h的完全二叉樹中最少有棧個結點，最多有個結點。設連通圖G中有n個頂點e條邊，那么對應的最小生成樹上有3條邊。構造n個結點的強連通圖，至少有O(n2)條弧。表達式求值是〔42,13,94,55,05,46,17〕應用的一個典型例子。設棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S，一個元素出棧后即進入隊列Q，假設6個元素出隊的序列是e2,e4,e3,e6,e5,e1，那么棧的容量至少應該是。快速排序算法在最差的情況下其時間復雜度是。對序列{55，46，13，05，94，17，42}進展基數(shù)排序，第一趟排序后的結果是。三、應用題〔本大題共5小題，每題6分，共30分〕二叉樹的先序遍歷序列ABCDEFGH，中序遍歷序列為CBEDFAGH，畫出二叉樹。答案：二叉樹形態(tài)如圖請給出鄰接表、鄰接矩陣及逆鄰接表。 V1V1V3V2V4參考答案如下：〔1〕鄰接表：(注意邊表中鄰接點域的值是頂點的序號，這里頂點的序號是頂點的下標值-1)

vertexfirstedge

next

〔2〕逆鄰接表：〔3〕由字符集{s，t，a，e，I}及其在電文中出現(xiàn)的頻度構建的哈夫曼樹如下圖。某段電文的哈夫曼編碼為0，請根據(jù)該哈夫曼樹進展譯碼，寫出原來的電文。答案：原來的電文為：eatst請畫出以下圖所示的樹所對應的二叉樹，并寫出對應二叉樹的先序遍歷和中序遍歷。112345678答案：112345678先序遍歷為：12345687中序遍歷為：34867521設散列表為HT[13],散列函數(shù)為H(key)=key%13。用閉散列法解決沖突,對以下關鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用線性探查法尋找下一個空位,畫出相應的散列表,并計算等概率下搜索成功的平均搜索長度。答案：使用散列函數(shù)H(key)=keymod13，有 H(12)=12, H(23)=10, H(45)=6, H(57)=5, H(20)=7, H(03)=3, H(78)=0, H(31)=5, H(15)=2, H(36)=10.利用線性探查法造表：012345678910111278150357452031233612(1)(1)(1)(1)(1)(1)(4)(1)(2)(1)搜索成功的平均搜索長度為 ASLsucc=(1+1+1+1+1+1+4+1+2+1)=帶權圖G如下圖，畫出圖G的一棵最小生成樹。答：假設用于通信的電文由字符集{a,b,c,d,e,f,g,h}中的字母構成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，請為這8個字母設計哈夫曼編碼。哈夫曼編碼為：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000注意：答案不唯一試用權集合{12,4,5,6,1,2}構造哈夫曼樹，并計算哈夫曼樹的帶權路徑長度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69畫出與如下圖森林對應的二叉樹。答：一個散列表如以下圖所示：35203348590123456789101112其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：hi=(h(key)+*h1(key))%m=0,1,…，m-1其中：h1(key)=key%11+1答復以下問題：〔1〕對表中關鍵字35，20，33和48進展查找時，所需進展的比擬次數(shù)各為多少？〔2〕該散列表在等概率查找時查找成功的平均查找長度為多少？答：〔１〕對關鍵字35、20、33和48進展查找的比擬次數(shù)為３、２、１、１；〔２〕平均查找長度請畫出與以下二叉樹對應的森林。答：對于給定結點的關鍵字集合K={5，7，3，1，9，6，4，8，2，10}，〔1〕試構造一棵二叉排序樹；〔2〕求等概率情況下的平均查找長度ASL。答：774312596108〔2〕ASL=(1*1+2*2+3*4+4*3)/10=2.9給出以下圖對應的鄰接矩陣，并給出A，B，C三個頂點的出度與入度答案:鄰接矩陣為：ABCDEF其中頂點A的入度為2，出度為1；其中頂點B的入度為2，出度為2；其中頂點C的入度為1，出度為3；圖5.32如下所示，求從頂點a到其余各頂點的最短路徑?！步o出求解過程〕54543223356abdfce答：終點最短路徑求解過程b6(a,b)5(a,c,b)c3(a,c)d6(a,c,d)6(a,c,d)e7(a,c,e)7(a,c,e)7(a,c,e)f9(a,c,d,f)9(a,c,d,f)vjcbdefS{a,c}{a,c,b}{a,c,d}{a,c,e}{a,c,d,f}閱讀以下算法，并答復以下問題：〔1〕假設串由合法的英文字母和空格組成，并以’\0’作完畢符。設串s=〞??I?am?a???student〞(?表示空格符)，寫出f30〔s〕的返回值；〔2〕簡述算法f30的功能。intf30(char*s)答案：(1)4(2)算法功能：統(tǒng)計單詞的個數(shù)。閱讀以下函數(shù),并答復以下問題：〔1〕假設隊列q中的元素為(a,b,c,d,e),其中"a〞為隊頭元素。寫出執(zhí)行函數(shù)調用Conv(&q)后的隊列q；〔2〕簡述算法Conv的功能。答案：e，d，c，b，a將隊列里的值反轉閱讀以下函數(shù),并答復以下問題：整形數(shù)組L［1..8］中的元素依次為〔19，18，15，17，16，13，12，10〕，閱讀以下函數(shù)，并寫出執(zhí)行函數(shù)調用sort(L,8)時，對L進展的頭兩趟〔pass分別為0和1〕處理結果。答案：〔1〕第一趟〔pass=0〕 〔2〕第二趟〔pass=1〕keynextkeynextvoidf33(LinkListL,LinkListH［］,intm)答案：NULL 〔2〕p->next=H[j]p=q以下函數(shù)的功能是，對以帶頭結點的單鏈表作為存儲構造的兩個遞增有序表〔表中不存在值一樣的數(shù)據(jù)元素〕進展如下操作：將所有在Lb表中存在而La表中不存在的結點插入到La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入適宜容，使其成為一個完整的算法。答案：〔1〕pre->next=pb〔2〕pre->next=pa〔3〕pre->next=pb閱讀算法f30，并答復以下問題：以下算法為有向圖拓撲排序,請在空缺處填入適宜的容，使其成為一個完整的算法。答案：(1〕top==-1〔2〕top=graph[j].count〔3〕graph[k].count==0閱讀算法f31，并答復以下問題：以下算法功能為在數(shù)組a的前n(n>=1)個元素中找出第k(1<=k<=n)小的值。這里假設數(shù)組a中各元素的值都不一樣。請在空缺處填入適宜的容，使其成為一個完整的算法。答案：〔1〕(i==k)return;〔2〕i+1〔3〕i-1閱讀算法f33，并答復以下問題：以下算法功能為奇偶交換排序，思路如下：第一趟對所有奇數(shù)的i,將a[i]和a[i+1]進展比擬,第二趟對所有偶數(shù)的i,將a[i]和a[i+1]進展比擬,每次比擬時假設a[i]>a[i+1],將二者交換;以后重復上述二趟過程,直至整個數(shù)組有序。請在空缺處填入適宜的容，使其成為一個完整的算法。答案：(1)a[i]=t(2)(i=2;i<=n;i+=2)(3)flag四、算法設計題〔本大題共2小題，每題10分，共20分〕單鏈表的結點類型為Lnode，包含next和data成員。編寫算法，實現(xiàn)帶頭結點單鏈表的逆置算法。參考答案：voidinvent(Lnode*head){Lnode*p,*q;if(!head->next)returnERROR;p=head->next;q=p->next;p->next=NULL;while(q){p=q;q=q->next;p->next=head->next;head->next=p;}}編寫一個函數(shù)，要求借助一個棧把一個數(shù)組中的數(shù)據(jù)元素逆置。其中，棧類型為SeqStack，可以直接使用InitStack(SeqStack**)、Push(SeqStack*,ElemType)、Pop(SeqStack*,ElemType*)函數(shù)。參考答案：voidInverse(ElemTypearr[],intn){ SeqStack*s; inti; InitStack(&s); for(i=0;i<n;i++)//數(shù)組元素依次入棧 Push(s,arr[i]); for(i=0;i<n;i++)//棧中元素依次出棧，存入數(shù)組，是數(shù)組逆序 Pop(s,&arr[i]);}二叉樹采用存儲構造，結點類型為Btree，包括left、right和data三個成員，試設計一個算法計算一棵給定二叉樹的度為2的結點的個數(shù)。參考答案：inttwochild(Btree*b){intnum1,num2;if(b==NULL)return0;else{num1=twochild1(b->left);num2=twochild1(b->right);if(b->left!=NULL&&b->right!=NULL)return(num1+num2+1);elsereturn(num1+num2);}}假設以帶雙親指針的二叉鏈表作為二叉樹的存儲構造，其結點構造的類型說明如下所示：typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;//左右孩子指針structnode*parent;//指向雙親的指針}BinTNode;typedefBinTNode*BinTree;假設px為指向非空二叉樹中某個結點的指針，可借助該構造求得px所指結點在二叉樹的中序序列中的后繼。(1)就后繼的不同情況，簡要表達實現(xiàn)求后繼操作的方法；參考答案：〔1〕分兩種情況討論=1\*GB3①當*px的右子樹不為空時，那么從*px的右孩子開場，沿其左孩子往下查找，直到找到一個沒有左孩子的節(jié)點為止，那么該結點為*px在中序序列中的后繼；=2\*GB3②當*px的右孩子為空時，那么沿*px的雙親指針鏈向上查找，直至找到其左子樹中包含*px的最年輕祖先，那么該祖先結點為*px在中序序列中的后繼。(2)編寫算法求px所指結點的中序序列后繼，并在算法語句中加注注釋?！?〕BinTreef34(BinTreepx) { BinTreeq=px->rchild; if(q!=NULL){//沿左孩子往下查找 px=q; while(px->lchild!=NULL) px=px->lchild;}else{//沿雙親指針鏈向上查找 while(px!=NULL&&px->rchild==q){ q=px; px=px->parent;}}returnpx;//返回所找到的中序序列后繼結點的指針 //或者無后繼結點時返回空指針}已有鄰接表表示的有向圖，請編程判斷從第u頂點至第v頂點是否有簡單路徑，假設有那么印出該路徑上的頂點。參考答案：voidAllSPdfs(AdjListg,vertypeu,vertypev){//求有向圖g中頂點u到頂點v的所有簡單路徑，初始調用形式：AllSPdfs(g,u,v)inttop=0,s[];s[++top]=u;visited[u]=1;while(top>0||p){p=g[s[top]].firstarc;//第一個鄰接點。while(p!=null&&visited[p->adjvex]==1)p=p->next;//下一個訪問鄰接點表。if(p==null)top--;//退棧。else{i=p->adjvex;//取鄰接點〔編號〕。if(i