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

以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（c）C、哈希表一個向量第一個元素的存儲地址是100，每個元素的長度為 2，則第 5個元素的地址是（B）B、108假設(shè)帶頭結(jié)點的單向循環(huán)鏈表的頭指針為 head,則該鏈表為空的判定條件是（C）Chead>next==headTOC\o"1-5"\h\z若進棧序列為 1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則不可能出現(xiàn)的出棧序列是（ D）D、2，3，5，1，6，4下列關(guān)鍵字序列中，構(gòu)成小根堆的是（ A）A、{12，21，49，33，81，56，69，41}下列數(shù)據(jù)結(jié)構(gòu)中，不屬于二叉樹的是（ A ）A、B樹用順序存儲的方法來存儲一棵二叉樹，存放在一維數(shù)組A[1..N]中，若結(jié)點A[i]有右孩子，則其右孩子是（C）。C、A[2i+1]設(shè)樹T的高度為 4，其中度為 1、2、3、4的結(jié)點個數(shù)分別為4、2、1、1，則T中葉子數(shù)為（D）D、8有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小，則應(yīng)選擇下面哪個序列輸入（B）37，24，12，30，53，45，96對下面有向圖給出了四種可能的拓?fù)湫蛄校渲绣e誤的是（C）C、5，1，6，3，4，2maB-樹中所有非終端（除根之外）結(jié)點中的關(guān)鍵字個數(shù)必須大于或等于 （B）[m/2]-1散列文件也稱為 （C）B、索引文件數(shù)據(jù)結(jié)構(gòu)是（D）D相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合從邏輯關(guān)系來看，數(shù)據(jù)元素的直接前驅(qū)為 0個或1個的數(shù)據(jù)結(jié)構(gòu)只能是（C）C線性結(jié)構(gòu)和樹型結(jié)構(gòu)設(shè)p為指向雙向循環(huán)鏈表中某個結(jié)點的指針， p所指向的結(jié)點的兩個鏈域分別用 p-llink和p-rlink表示，則同樣表示p指針?biāo)赶蚪Y(jié)點的表達(dá)式是（D）D、p—Hlink—>rlink若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間 V[1..m]，top[i]代表第i個棧（i=1,2）棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是（B）top[1]+1=top[2]若一棵二叉樹有 11個葉子結(jié)點，則該二叉樹中度為 2的結(jié)點個數(shù)是（A）A、10樹的先根序列等同于與該樹對應(yīng)的二叉樹的（A）A先序序列下面關(guān)于哈希（Hash,雜湊）查找的說法正確的是（C）C不存在特別好與壞的哈希函數(shù)，要視情況而定下列序列中，（D）是執(zhí)行第一趟快速排序后所得的序列。D、[68，11，69，23，18][93 ，73]下列關(guān)鍵字序列中，構(gòu)成小根堆的是（D）D、（15，28，46，37，84，58，62，41）ISAM文件和VASM：件屬于（C）C索引順序文件下面程序段的時間復(fù)雜度為（C）for（i=0;i<m;i++）for（j=0;j<n;j++）A[i][j]=i*j;C、O（m*n）已知指針p和q分別指向某單鏈表中第一個結(jié)點和最后一個結(jié)點。假設(shè)指針 s指向另一個單鏈表中某個結(jié)點，則在s所指結(jié)點之后插入上述鏈表應(yīng)執(zhí)行的語句為（A）A、q->next=s->next；s->next=p；為便于判別有向圖中是否存在回路，可借助于（D）D拓?fù)渑判蛩惴ㄈ粢許和X分別表示進棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M行的棧操作系列是（D）D、SSSXXSXX設(shè)有一順序棧 S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是（B）3假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素。已知隊列的長度為length，指針rear指向隊尾元素的下一個存儲位置，則隊頭元素所在的存儲位置為（B）。（rear-length+m）%m在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結(jié)點s的操作為（D）。D、rear->next=s;rear=s;對于哈希函數(shù)H（key）=key%13,被稱為同義詞的關(guān)鍵字是（D）D、25和51采用二叉鏈表存儲的 n個結(jié)點的二叉樹，共有空指針（A）個。A、n+1連通網(wǎng)的最小生成樹是其所有生成樹中（D）D、邊的權(quán)值之和最小的生成樹對記錄序列 （314，298，508，123，486，145）依次按個位和十位進行兩趟基數(shù)排序之后所得結(jié)果為（B）B、508，314，123，145，486，298任何一個無向連通圖的最小生成樹（C）。C一棵或多棵無向圖的鄰接矩陣是一個（C）C、對稱矩陣設(shè)無向圖G-=（V,E）和G'=（V',E'）,如G為G的生成樹，則下列說法中不正確的是 （B）。RG為G連通分量以v1為起始結(jié)點對下圖進行深度優(yōu)先遍歷，正確的遍歷序列是（D）D、v1，v2，v5，v6，v7，v3，v4下面幾個符號串編碼集合中，不是前綴編碼的是（B）B、{0,1,00,11}希爾排序的增量序列必須是（B）。B、遞減的采用起泡排序法對n個關(guān)鍵字進行升序排序，若要使排序過程中比較關(guān)鍵字的次數(shù)最多，則初始時的序列應(yīng)滿足條件（D）D、關(guān)鍵字從大到小排列在下列內(nèi)部排序中 （A）是不穩(wěn)定的。A、希爾排序分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是 (C)。A、(100,80,90,60,120,110,130)在查找過程中，沖突指的是(CC、不同鍵值對應(yīng)相同的存儲地址對有14個元素的有序表A[1..14]作二分查找，查找元素A[4]時的被比較元素依次為(D)DA[7],A[3],A[5],A[4]以v1為起始結(jié)點對下圖進行廣度度優(yōu)先遍歷，正確的遍歷序列是(A)A、v1,v2,v3,v4,v5,v6,v7二、填空題(本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分)數(shù)據(jù)的物理結(jié)構(gòu)包括 數(shù)據(jù)元素的存儲和數(shù)據(jù)之間關(guān)系 的存儲。若一個算法中的語句頻度之和為 T(n)=1921n+4nlogn,則算法的時間復(fù)雜度為 nlogn。下面程序段的時間復(fù)雜度是 _log3n_oi=1；while(i<=n)i=i*3；循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，已知其頭尾指針分別是front和rear,則當(dāng)前隊列的元素個數(shù)是(rear-front+m)%m主要是使插入和刪除等操作統(tǒng)一(n-1)/2 。在單鏈表中設(shè)置頭結(jié)點的作用是 深度優(yōu)先。線性表L=(a1,a2,…,an)用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是相同值關(guān)鍵字 。已知一無向圖G=(V,E),其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點 a開始遍歷圖，得到的序列為abecd,則采用的是 前移遍歷方法。如果排序過程不改變時間復(fù)雜度之間的相對次序,則稱該排序方法是穩(wěn)定的。從順序表中刪除一個元素時，表中所有在被刪元素之后的元素均需 出度一個位置。當(dāng)問題的規(guī)模n趨向無窮大時，算法執(zhí)行時間T(n)的數(shù)量級被稱為算法的 10。若以鄰接矩陣表示有向圖，則鄰接矩陣上第 i行中非零元素的個數(shù)即為頂點 vi的sxssxxssxssxxx。一棵含999個結(jié)點的完全二叉樹的深度為 12o假設(shè)S和X分別表示進棧和出棧操作，由輸入序列“ABC”得到輸出序列“BCA”的操作序列為SSXSXX,則由“a*b+c/d”得到J“ab*cd/+”的操作序列為4。如圖所示的有向無環(huán)圖可以排出 L->next->next==L邊 種不同的拓?fù)湫蛄小目諛淦?，依次插入關(guān)鍵字 11,27,35,48,52,66和73構(gòu)造所得的二叉排序樹，在等概率查找的假設(shè)下，查找成功時的平均查找長度為 384o帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是 隊列。求最小生成樹的克魯斯卡爾(Kruskal)算法耗用的時間與圖中 邊稠密、邊稀疏 的數(shù)目正相關(guān)。已知一棵完全二叉樹中共有 768結(jié)點，則該樹中共有 5 個葉子結(jié)點。實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標(biāo)志數(shù)組標(biāo)志已訪問的圖的結(jié)點外，還需要8、64 存放被訪問的結(jié)點以實現(xiàn)遍歷。Prim(普里姆)算法適用于求 2h-1的網(wǎng)的最小生成樹;kruskal(克魯斯卡爾)算法適用于求 2h-1的網(wǎng)的最小生成樹。對長度為20的有序表進行二分查找的判定樹的高度為 n-1。設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為 n,有個葉子結(jié)點。高度為h的完全二叉樹中最少有 棧個結(jié)點，最多有個結(jié)點。設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有 3條邊。構(gòu)造n個結(jié)點的強連通圖，至少有 O(n2)條弧。表達(dá)式求值是 (42,13,94,55,05,46,17 ) 應(yīng)用的一個典型例子。設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1,e2,e3,e4,e5,e6依次通過棧S,一個元素出棧后即進入隊列 Q,若6個元素出隊的序列是e2,e4,e3,e6,e5,e1 ,則棧的容量至少應(yīng)該是。快速排序算法在最差的情況下其時間復(fù)雜度是。對序列｛55,46,13,05,94,17,42｝進行基數(shù)排序，第一趟排序后的結(jié)果是。三、應(yīng)用題(本大題共5小題，每小題6分，共30分)已知二叉樹的先序遍歷序列ABCDEFGH,中序遍歷序列為CBEDFAGH,畫出二叉樹。答案：二叉樹形態(tài)2. 2. 如圖請給出鄰接表、鄰接矩陣及逆鄰接表。參考答案如下:(1)鄰接表：(注意邊表中鄰接點域的值是頂點的序號，這里頂點的序號是頂點的下標(biāo)值參考答案如下:(1)鄰接表：(注意邊表中鄰接點域的值是頂點的序號，這里頂點的序號是頂點的下標(biāo)值-1)vertexfirstedgenext(2)逆鄰接表:(3)vertexfirstedgenext(2)逆鄰接表:(3)&10Iao1oIODO(Joio由字符集｛s,t,a,e,I｝及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫曼樹如圖所示。 已知某段電文的哈夫曼編碼為111000010100,請根據(jù)該哈夫曼樹進行譯碼，寫出原來的電文答案：原來白^電文為：eatst請畫出下圖所示的樹所對應(yīng)的二叉樹，并寫出對應(yīng)二叉樹的先序遍歷和中序遍歷先序遍歷為：12345687中序遍歷為：先序遍歷為：12345687中序遍歷為：348675215.設(shè)散列表為HT[13],散列函數(shù)為H(key)=key%13。用閉散列法解決沖突，對下列關(guān)鍵碼序列5.設(shè)散列表為HT[13],散列函數(shù)為H(key)=key%13。用閉散列法解決沖突，對下列關(guān)鍵碼序列12,23,45,57,20,03,78,31,15,36造表。采用線性探查法尋找下一個空位 ，畫出相應(yīng)的散列表，并計算等概率下搜索成功的平均搜索長度。答案：使用散列函數(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)=1014106. 已知帶權(quán)圖G如圖所示，畫出圖G的一棵最小生成樹假設(shè)用于通信的電文由字符集｛a,b,c,d,e,f,g,h｝中的字母構(gòu)成，這8個字母在電文中出現(xiàn)的概率分別為{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10},請為這8個字母設(shè)計哈夫曼編碼。哈夫曼毋智利 0M0英哈夫曼編碼為：a：1001 b：01c:10111 d:1010e:11f:10110g:00 h:1000注意：答案不唯一試用權(quán)集合{12,4,5,6,1,2} 構(gòu)造哈夫曼樹，并計算哈夫曼樹的帶權(quán)路徑長度。WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69畫出與如圖所示森林對應(yīng)的二叉樹答:10.(2)平均查找長度10.(2)平均查找長度ASL32112 95 5已知一個散列表如下圖所示:35203348590 1 2 3 4 5 6 789 10 11 12其散列函數(shù)為h(key)=key%13,處理沖突的方法為雙重散列法，探查序列為：h=(h(key)+i*h1(key))%mi=0,1，…，m-1其中： h1(key)=key%11+1回答下列問題：(1)對表中關(guān)鍵字35,20,33和48進行查找時，所需進行的比較次數(shù)各為多少?(2)該散列表在等概率查找時查找成功的平均查找長度為多少?答:(1)對關(guān)鍵字35、20、33和48進行查找的比較次數(shù)為3、2、1、1;請畫出與下列二叉樹對應(yīng)的森林。答:答:對于給定結(jié)點的關(guān)鍵字集合 K={5,7,3,1,9,6,4,8,2,10},(1)試構(gòu)造一棵二叉排序樹;(2)求等概率情況下的平均查找長度ASL答:(2)ASL=(1*1+2*2+3*4+4*3)/10=2.913.給出下圖對應(yīng)的鄰接矩陣，并給出A,B,C三個頂點的出度與入度13.答案：鄰接矩陣為：ABCDEFTOC\o"1-5"\h\zA 0 0 0 1 0 0B 1 0 1 0 0 0C 0 0 0 1 1 1D 0 0 0 0 0 0E 1 1 0 1 0 0F 0 1 0 0 1 0其中頂點A的入度為2,出度為1;其中頂點B的入度為2,出度為2;其中頂點C的入度為1,出度為3;14.已知圖5.32如下所示，求從頂點a到其余各頂點的最短路徑。（給出求解過程）14.答:"占八、、最短路徑求解過程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)假設(shè)串由合法的英文字母和空格組成，并以 ’0'作結(jié)束符。設(shè)串s="?？I?am?a???student”？表示空格符)，寫出f30(s)的返回值；(2)簡述算法f30的功能。intf30(char*s)答案：4(2)算法功能：統(tǒng)計單詞的個數(shù)。閱讀下列函數(shù)并回答問題：(1)假設(shè)隊列q中的元素為(a,b,c,d,e)其中"a"為隊頭元素。寫出執(zhí)行函數(shù)調(diào)用 Conv(&q)后的隊列q；(2)簡述算法Conv的功能。答案：e,d,c,b,a將隊列里的值反轉(zhuǎn)閱讀下列函數(shù)并回答問題：已知整形數(shù)組L[1..8]中的元素依次為(19,18,15,17,16,13,12,10),閱讀下列函數(shù)，并寫出執(zhí)行函數(shù)調(diào)用 sort(L,8)時，對L進行的頭兩趟(pass分別為0和1)處理結(jié)果。答案：⑴第一趟(pass=0)1915181617121310(2)第二趟(pass=1)1915161812171013已知帶頭結(jié)點的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長度為m,散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點結(jié)構(gòu)為： 。請在空缺處填入適當(dāng)內(nèi)容，使其成為一個完整算keynextvoidf33(LinkListL,LinkListH口，intm)答案：⑴NULL ⑵p->next=H[j] p=q下列函數(shù)的功能是，對以帶頭結(jié)點的單鏈表作為存儲結(jié)構(gòu)的兩個遞增有序表(表中不存在值相同的數(shù)據(jù)元素)進行如下操作：將所有在Lb表中存在而La表中不存在的結(jié)點插入到 La中，其中La和Lb分別為兩個鏈表的頭指針。請在空缺處填入合適內(nèi)容，使其成為一個完整的算法。答案：⑴pre->next=pb(2)pre->next=pa (3)pre->next=pb閱讀算法f30,并回答問題：下列算法為有向圖拓?fù)渑判?，請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。答案：top==-1 (2)top=graph[j].count (3)graph[k].count==0閱讀算法f31,并回答問題：下列算法功能為在數(shù)組 a的前n(n>=1)個元素中找出第k(1<=k<=n)小的值。這里假設(shè)數(shù)組a中各元素的值都不相同。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。答案：(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], 將二者交換；以后重復(fù)上述二趟過程，直至整個數(shù)組有序。請在空缺處填入合適的內(nèi)容，使其成為一個完整的算法。答案：(1)a[i]=t (2)(i=2;i<=n;i+=2) (3)flag四、算法設(shè)計題(本大題共2小題，每小題10分，共20分)1.已知單鏈表的結(jié)點類型為Lnode,包含next和data成員。編寫算法，實現(xiàn)帶頭結(jié)點單鏈表的逆置算法。1.}}參考答案：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]);}二叉樹采用鏈接存儲結(jié)構(gòu)，結(jié)點類型為 Btree，包括 left、right和data三個成員，試設(shè)計一個算法計算一棵給定二叉樹的度為2的結(jié)點的個數(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);}4.假設(shè)以帶雙親指針的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)的類型說明如下所示：4.typedefcharDataType;typedefstructnode{DataTypedata;structnode*lchild,*rchild;//左右孩子指針structnode*parent; //指向雙親的指針}BinTNode;typedefBinTNode*BinTree;若px為指向非空二叉樹中某個結(jié)點的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點在二叉樹的中序序列中的后繼。(1)就后繼的不同情況，簡要敘述實現(xiàn)求后繼操作的方法；參考答案：(1)分兩種情況討論①當(dāng)*px的右子樹不為空時，則從 *px的右孩子開始，沿其左孩子往下查找，直到找到一個沒有左孩子的節(jié)點為止，則該結(jié)點為*px在中序序列中的后繼；②當(dāng)*px的右孩子為空時，則沿 *px的雙親指針鏈向上查找，直至找到其左子樹中包含*px的最年輕祖先，則該祖先結(jié)點為*px在中序序列中的后繼。(2)編寫算法求 px所指結(jié)點的中序序列后繼，并在算法語句中加注注釋。(2)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;//返回所找到的中序序列后繼結(jié)點的指針//或者無后繼結(jié)點時返回空指針5.已有鄰接表表示的有向圖，請編程判斷從第 u頂點至第v頂點是否有簡單路徑，若有則印出該路徑上的頂點。5.參考答案：voidAllSPdfs(AdjListg,vertypeu,vertypev){//求有向圖 g中頂點u到頂點v的所有簡單路徑，初始調(diào)用形式：AllSPdfs(g,u,v)inttop=0,s[];s[++top]=u;visited[u]=1;while(top>0||p){p=g[s[top]].firstarc;//第一個鄰接點。while(p!=n