計算機數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案

1、百度文庫20091 .為解決計算機與打印機之間速度不匹配的問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是A.棧B.隊列C.樹D.圖'2 .設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個元素出棧后立即進(jìn)入隊列Q,且7個元素出隊的順序是bdcfeag,則棧S的容量至少是A.1/3 .給定二叉樹圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4,則其遍歷方式是/A.LRN4.下列二叉排序樹中，滿足平衡二叉樹定義的是5

2、.已知一棵完全二叉樹的第6層（設(shè)卞g為第1層）有8個葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是A.396 .將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點，則在原來的森林中，u和v可能具有的關(guān)系是I.父子關(guān)系II.兄弟關(guān)系的父結(jié)點與v的父結(jié)點是兄弟關(guān)系A(chǔ).只有II和II和III、II和III7 .下列關(guān)于無向連通圖特性的敘述中，正確的是I所有頂點的度之和為偶數(shù)II.邊數(shù)大于頂點個數(shù)減1III.至少有一個頂點的度為1A.只有IB.只有II和II和III/8 .下列敘述中，不符合m階B樹定義要求的是/A.根節(jié)點最多有m棵子樹B.所有葉結(jié)點都在同一層上C.各結(jié)點內(nèi)關(guān)鍵字均升序或降序

3、排列D.葉結(jié)點之間通過指針鏈接9 .已知關(guān)鍵序列5,8,12,19,28,20,15,22是小根堆（最小堆）,插入關(guān)鍵字3,調(diào)整后得到的小根堆是/A.3,5,12,8,28,20,15,22,19/,5,12,19,20,15,22,8,28/C.3,8,12,5,20,15,22,28,19,12,5,8,28,20,15,22,19/10 .若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是A.起泡排序B.插入排序C.選擇排序D.二路歸并排序41. （10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點間的距離）的最短路徑問題

4、是找出從初始頂點到目標(biāo)頂點之間的一條最短路徑。假定從初始頂點到目標(biāo)頂點之間存在路徑，現(xiàn)有一種解決該問題的方法：設(shè)最短路徑初始時僅包含初始頂點，令當(dāng)前頂點u為初始頂點；選擇離u最近且尚未在最短路徑中的一個頂點v,加入到最短路徑中，修改當(dāng)前頂點u=v;重復(fù)步驟，直到u是目標(biāo)頂點時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。42. （15分）已知一個帶有表頭結(jié)點的單鏈表，結(jié)點結(jié)構(gòu)為datalink假設(shè)該鏈表只2&出了頭指針list。在不改變鏈表的前提下，請設(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點（k為正整數(shù)）。;若查找成功，算法輸出該結(jié)點的

5、data值，并返回1;否則，只返回0。要求：（1）描述算法的基本設(shè)計思想（2）描述算法的詳細(xì)實現(xiàn)步驟（3）根據(jù)設(shè)計思想和實現(xiàn)步驟，采用程序設(shè)計語言描述算法（使用C或C+或JAVA語言實現(xiàn)），關(guān)鍵之處請給出簡要注釋。20101、若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（）A：dcebfaB:cbdaefC:dbcaefD:afedcb2、某隊列允許在其兩端進(jìn)行入隊操作，但僅允許在一端進(jìn)行出隊操作，則不可能得到的順序是（）A：bacdeB:dbaceC:dbcaeD:ecbad3、下列線索二叉樹中（用虛線表示線索），符

6、合后序線索樹定義的是（）4、在下列所示的平衡二叉樹中插入關(guān)鍵字，48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、，右子結(jié)點中保存的關(guān)鍵字分別是（）A:13,48B:24,48C:24,53D:24,905、在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點,1個度為2的結(jié)點，/10個度為1的結(jié)點，則樹T的葉節(jié)點個數(shù)是（）A:41B:82C:113D:1226、對n（n大于等于2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（）A:該樹一定是一棵完全二叉樹B:樹中一定沒有度為1的結(jié)點C:樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D:樹中任一非葉結(jié)點的

7、權(quán)值一定不小于下一任一結(jié)點的權(quán)值7、若無向圖G-（）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（）A:6B:15C:16D:218、對下圖進(jìn)行拓補排序，可以得到不同的拓補序列的個數(shù)是（）eda-cXf_*vjfbbA:4B:3C:2D:19、已知一個長度為16的順序表L,其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數(shù)最多是（）A:4B:5C:6D:710、采用遞歸方式對順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（、）A:遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B:每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)C:每次劃分后，先處理較短的分區(qū)可

8、以減少遞歸次數(shù)D:遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)11、對一組數(shù)據(jù)（2,12,16,88,5,10）進(jìn)行排序，若前三趟排序結(jié)果如下（）/第一趟：2,12,16-5,10,88/第二趟：2,12,5,10,<16,88/第三趟：2,5,10,12,16,88則采用的排序方法可能是：A:起泡排序B:希爾排序C:歸并排序D:基數(shù)排序41.(10分)將關(guān)鍵字序列(7、8、11、18、9、14)散列存儲到散列列表中，散列表的存儲空間是一個下標(biāo)從0開始的一個一維數(shù)組散列函數(shù)維：H(key)=(keyX3)MODT,處理沖突采用線性探測再散列法，要求裝填(載)因子為問題：(1)請畫出所構(gòu)造的

9、散列表；、(2)分別計算等概率情況下，查找成功和查找不成功的平均查找長度。42.(13分)設(shè)將n(n,1)個整數(shù)存放到一維數(shù)組R中，試設(shè)計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P(0<P<n)個位置，即將R中的數(shù)據(jù)由(X0X1Xr-1)變換為(XpXp+1Xn-1X0X1Xp-1)要求：(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C+或JAVA語言表述算法關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度20111.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時間復(fù)雜度是二x=2;while(x<n/2)x=2*x;(lo

10、g2n)(n)(nlog2n)(n2)2 .元素a,b,c,d,e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數(shù)是3 .已知循環(huán)隊列存儲在一維數(shù)組A0.n-1中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始時隊列為空，且要求第1個進(jìn)入隊列的元素存儲在A0處，則初始時front和rear的值分別是,0,n-1,0,n-14 .若一棵完全二叉樹有768個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)是5.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1,則該二叉樹的中序遍歷序列不會是,2,3

11、,4,3,4,1,2,4,1,3,2,16 .已知一棵有2011個結(jié)點的樹，其葉結(jié)點個數(shù)為116,該樹對應(yīng)的二叉樹中無右孩子的結(jié)點個數(shù)是7 .對于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是,22,91,24,94,71,20,91,34,88,35,89,77,29,36,38,25,71,68,33,348 .下列關(guān)于圖的敘述中，正確的是I .回路是簡單路徑/II .存儲稀疏圖，用鄰接矩陣比鄰接表更省空間/III .若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路A.僅IIB.僅I、IIC.僅IIID.僅I、IIIIV 為提高散列(Hash)表的查找效率，可以采取的正確措施是1 .

12、增大裝填(載)因子、/11 .設(shè)計沖突(碰撞)少的散列函數(shù)111 .處理沖突(碰撞)時避免產(chǎn)生聚集(堆積)現(xiàn)象A.僅IB.僅IIC.僅I、IID.僅II、III112 為實現(xiàn)快速排序算法，待排序序列宜采用的存儲方式是A.順序存儲B.散列存儲C.鏈?zhǔn)酱鎯.索引存儲113 已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18,將其再調(diào)整為大根堆，調(diào)整過程中元素之間進(jìn)行的比較次數(shù)是41 .(8分)已知有6個頂點(頂點編號為05)的有向帶權(quán)圖G,其鄰接矩陣A為上三角矩陣，按行為主序(行優(yōu)先)保存在如下的一維數(shù)組中。480000g50088AqoCO3J要求：(1)寫出圖G的鄰接矩陣A

13、o(2)畫出有向帶權(quán)圖G(3)求圖G的關(guān)鍵路徑，并計算該關(guān)鍵路徑的長度。42 .(15分)一個長度為L(L>1)的升序序列S,處在第eL/2cl個位置的數(shù)稱為S的中位數(shù)。例如，若序列S1=(11,13,15,17,19),則S1的中位數(shù)是15。兩個序列的中位數(shù)是含它們所有元素的升序序列的中位數(shù)。例如，若S2=(2,4,6,8,20),則S1和S2的中位數(shù)是11?，F(xiàn)有兩個等長升序序列A和B,試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數(shù)。要求：(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C+域JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)

14、計算法的時間復(fù)雜度和空間復(fù)雜度。20121、求整數(shù)n(n>0)階乘的算法如下，其時間復(fù)雜度是()intfact(intn)if(n<=1)return1;returnn*fact(n-1);(log2n)(n)C.(nlog2n)(n2)2、已知操作符包括+、'-'、*'、'/'、(和)。將中綴表達(dá)式a+b-a*(c+d)/e-f)+g轉(zhuǎn)換為等價的后綴表達(dá)式ab+acd+e/f-*-g+時，用棧來存放暫時還不能確定運算次序的操作符，若棧初始時為空，則轉(zhuǎn)換過程中同時保存棧中的操作符的最大個數(shù)是()3、若一顆二叉樹的前序遍歷序列為a,e,b,d&

15、#163;后續(xù)遍歷序列為b,c,d,e,q則根節(jié)點的孩子節(jié)點()A.只有eB.有e、bC.有e、cD.無法確定4、若平衡二叉樹的高度為6,且所有非葉節(jié)點的平衡因子均為1,則該平衡二叉樹的節(jié)點總數(shù)為()5、對有n個節(jié)點、e條邊且使用鄰接表存儲的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時間復(fù)雜度()（n）（e）（n+e）（n*e）6、若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)構(gòu)是（）A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.無法確定是否存在7、如下有向帶權(quán)圖，若采用迪杰斯特拉（Dijkstra）算法求源點a到其他各頂點的最短路徑，得到的第一條最短路徑的目標(biāo)

16、頂點是b,第二條最短路徑的目標(biāo)頂點是c,后續(xù)得到的其余各最短品&徑的目標(biāo)頂點依次是（）,e,f,d,f,d,e,e,d8、下列關(guān)于最小生成樹的說法中，正確的是（）I、最小生成樹的代價唯一n所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中田、使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同IV、使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同A.僅IB.僅HC.僅I、mD.僅H、IV9、已知一棵3階B-樹，如下圖所示。刪除關(guān)鍵字78得到一棵新B-樹，其最右葉結(jié)點中的關(guān)鍵字是（）1C21374762,62,6510、在內(nèi)部排序過程中，對尚未確定最終位置

17、的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束都至少能夠確定一個元素最終位置的方法是（）I.簡單選擇排序L希爾排序田.快速排序/IV.堆排序V.二路歸并排序/A.僅I、m、IVB.僅I、m、V/C.僅H、m、IVD.僅出、IV、V/11.對一待排序序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同之處是（）A.排序的總趟數(shù)B.元素的移動次數(shù)C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)二、問答題。41、(10分)設(shè)有6個有序表A、B、C、D、E、F,分別含有10、35、40、50、60和200個數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個表最終合并成1

18、個升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請回答下列問題。(1)給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。(2)根據(jù)你的合并過程，描述N(N>2)個不等長升序表的合并策略，并說明理由。42、(13分)假定采用帶頭結(jié)點的單鏈表保存單詞，當(dāng)兩個單詞有相同的后時綴，則可共享相同的后綴存儲空間，例如，"loaging"、和“being"，如下圖所示。strl、對r2:i|-一tp|-Ag*WEHU設(shè)str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為(data,next,請設(shè)計一個時間上盡可能高效的算法，找出由stU和str2所指向兩個鏈

19、表共同后綴的起始位置(如圖中字符i所在結(jié)點的位置p)o要求：(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C+或java語言描述算法關(guān)鍵之處給出注釋。(3)說明你所設(shè)計算法的時復(fù)雜度。20131 .已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復(fù)雜度是A.O(n)B.O(m*n)C.O(min(m,n)D.O(max(m,n)2>一個棧的入棧序列為1,2,3,n,其出棧序列是p1,p2,p3,pn=若p2=3,則p3可能取值的個數(shù)是：/A.n-3B.n-2C.n-1D.無法確定/3.若將關(guān)鍵字1,2,3,4,5,6,7依次插入

20、到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結(jié)點的個數(shù)是/A.0B.1C.2D.34 .已知三叉樹T中6個葉結(jié)點的權(quán)分別是2,3,4,5,6,7,T的帶權(quán)(外部)路徑長度最小是A.27B.46C.54D.565 .若X是后序線索二叉樹中的葉結(jié)點，且X存在左兄弟結(jié)點Y,則X的右線索指向的是A.X的父結(jié)點B.以Y為根的子樹的最左下結(jié)點C.X的左兄弟結(jié)點YD.以Y為根的子樹的最右下結(jié)點6.在任意一棵非空二叉排序樹T1'中，刪除某結(jié)點v之后形成二叉排序樹T2,再將v插入T2形成二叉排序樹T3。下列關(guān)于T1與T3的敘述中，正確的是I .若v是T1的葉結(jié)點，則T1與T3不同II .若v是T

21、1的葉結(jié)點，則T1與T3相同III .若v不是T1的葉結(jié)點，則T1與T3不同IV .若v不是T1的葉結(jié)點，則T1與T3相同A.僅卜IIIB.僅卜IVC.僅II、III、D.僅II、IV7.設(shè)圖的鄰接矩陣，A如下所示。各頂點的度依次是-01or0011A=01001000A.1,2,1,2B.2,2,1,1C.3,4,2,3D.4,4,2,28.若對如下無向圖進(jìn)行遍歷，則下列選項中，不是廣度優(yōu)先遍歷序列的是A.h,c,a,b,d,e,g,fB.e,a,f,g,b,h,c,dC.d,b,c,a,h,e,f,gD.a,b,c,d,h,e,f,g9、下列的AOE網(wǎng)表示一項包含8個活動的工程。通過同時加

22、快若干活動的進(jìn)度可以縮短整個工程的工期。下列選項中，加快其進(jìn)度就可以縮短整個工程的工期的是：Ac和eBd和eCf和dDf和h10、在一棵高為2的5階B樹中，所含關(guān)鍵字的個數(shù)最少是A5B7C8D144L(13分)已知不整數(shù)序列=(%嗎JlLn.J,其中。置。海：若存在4i-口£|白>工且巾>小2(。匹p：</14此嚙r則和3一為a的主沅素、例如=A=(0,5,5,3,5,7,5,5),側(cè)5為主元素；又如A=(0,5,5,3,5,1,5,7),則A中沒有主元素。假設(shè)A中的n個元素保存在一個一維數(shù)組中，請計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；

23、否則輸出-1。要求：(1)給出算法的基本設(shè)計思想。(2)根據(jù)設(shè)計思想，采用C或C+或Java語言描述算法，關(guān)鍵之處給出釋。(3)說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度。42.(10分)4個元素的S="do","for","repeat""while",各元素查找概率依次為：p1=,p2=,p3=0.15,p4=。將S保存在一個長度為4的順序表中，采用折半查找法，查找成功時的平均查找長度為。請回答：(1)若采用順序存儲結(jié)構(gòu)保存S,且要求平均查找長度更短，則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時的平均查找長度

24、是多少？(2)若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)保存S,且要求平均查找長度更短，則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時的平均查找長度是多少？20141 .下列程常段的時間復(fù)雜度是count=0;*for(k=1;k<=n;k=2)for(j=1;j<=n;j+1)count+;(log2n)(n)(nlog2n)(n2)2.假設(shè)棧初始為空，將中綴表達(dá)式a/bcdef/g轉(zhuǎn)換為等價后綴表達(dá)式的過程中，當(dāng)掃描到f時，棧中的元素依次是A.B.C./D./3 .循環(huán)兩列放在一維數(shù)組A0M-1中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進(jìn)行入隊和出隊操作，隊列中最多

25、能容納M-1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是/A.隊空：end1=end2;隊滿：end1=(end2+1)modMB.隊空：end1=end2;隊滿：end2=(end1+1)mod(M-1)C.隊空：end2=(end1+1)modM;隊滿：end1=(end2+1)modMD.隊空：end1=(end2+1)modM;隊滿：end2=(end1+1)mod(M-1)4 .若對如下的二叉樹進(jìn)行中序線索化，則結(jié)點/x的左、右線索指向的結(jié)點分別是,c,a,c,a115.將森林F轉(zhuǎn)換為對應(yīng)的二叉樹 中葉結(jié)點的個數(shù)T, F中葉結(jié)點的個數(shù)等于中度為1的結(jié)點個數(shù)中左孩子指針為空

26、的結(jié)點個數(shù)中右孩子指針為空的結(jié)點個數(shù)6.5個字符有如下4種編碼方案，不是前綴編碼的是,0000,0001,001,1,000,001,010,1,1,2,4,5,6,001,010,011,100,001,010,011,1007.對如下所示的有向圖進(jìn)行拓?fù)渑判?，得到的拓?fù)湫蛄锌赡苁?j,用哈希（散列）方法處理沖突（碰撞）時可能出現(xiàn)堆積（聚集）現(xiàn)象,卜列選項中，會受堆積現(xiàn)象直接影響的是A.存儲效率B.數(shù)列函數(shù)C.裝填（裝載）因子D.平均查找長度9 .在一棵具有15個關(guān)鍵字的4階B樹中，含關(guān)鍵字的結(jié)點數(shù)最多是10 .用希爾排序方法對一個數(shù)據(jù)序列進(jìn)行排序時，若第1趟排序結(jié)果為9,1,4,13,7,

27、8,20,23,15則該趟排序采用的增量（間隔）可能是11 .下列選項中，不可能是快速排序第2趟排序結(jié)果的是,3,5,4,6,7,9,7,5,6,4,3,9,2,5,4,7,6,9,2,3,5,7,6,941.（13分）二叉樹的帶權(quán)路徑長度（WPL）是二叉樹中所有葉結(jié)點的帶權(quán)路徑長度之和，給定一棵二叉樹T,采用二叉鏈表存儲，節(jié)點結(jié)構(gòu)為：leftweightright其中葉節(jié)點的weight域保存該結(jié)點的非負(fù)權(quán)值。設(shè)root為指向T的根節(jié)點的指針，設(shè)計求T的WPL的算法。要求：(1)給出算法的基本設(shè)計思想；(2)使用C或C+語言，給出二叉樹結(jié)點的數(shù)據(jù)類型定義；(3)根據(jù)設(shè)計思想，采用C或C+語言

28、描述算法，關(guān)鍵之處給出注釋。20151 .已知程序如下：ints(intn)return(n<=0)?0:s(n-1)+n;voidmain()cout<<s(1);程序運行時使用棧來保存調(diào)用過程的信息,自棧底到棧頂保存的信息一次對應(yīng)的是1 .main()->S(1)->S(0)B.S(0)->S(1)->main()C.main()->S(0)->S(1)D.S(1)->S(0)->main()2 .先序序列為a,b,c,d的不同二叉樹的個數(shù)是A.13B.14C15D.163 .下列選項給出的是從根分別到達(dá)兩個葉節(jié)點路徑上的權(quán)

29、值序列能屬于同一棵哈夫曼樹的是A.24,10,5和24,10,7B.24,10,5和2412,7C.24,1Q10和24,14,11D24,10,5和24,14,64 .現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二叉樹AVL樹)，對其進(jìn)行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A.根節(jié)點的度一定為2B.樹中最小元素一定是葉節(jié)點C.最后插入的元素一定是葉節(jié)點D,樹中最大元素一定是無左子樹5 .設(shè)有向圖G=(V,E),頂除V=V0,V1,V2,V3，邊集E=<v0,v1>,<v0,v2>,<v0,v3>,<v1,v3>,若從頂點V0開始對

30、圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是A.2B.3C.4D.56.求下面帶權(quán)圖的最小(代價)生成樹時，可能是克魯斯卡(kruskaD算法第二次選中但不是普里姆(Prim)算法(從V4開始)第2次選中的邊是A.(V1,V3)B.(V1,V4)C.(V2,V3)D.(V3,V4)7 .下列選項中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是A.500,200,450,180B500,450,200,180C.180,500,200,450D.180,200,500,4508 .已知字符串S為"abaabaabacacaabaabC忒比t為"abaab冰川KMP算進(jìn)行匹配，第

31、一次出現(xiàn)失配"(si=ti)時，i=j=5,則下次開始匹配時,i和j的值分另A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=29 .下列排序算法中元素的移動次數(shù)和關(guān)鍵字的初始排列次序無關(guān)的是A.直接插入排序B.起泡排序C,基數(shù)排序D.快速排序10.已知/討艮堆為8, 15, 10, 21, 過程中，關(guān)鍵字之間的比較數(shù)是34, 16, 12,刪除關(guān)鍵字8之后需重建堆,18A.1B.2C.3D.411.希爾排序的組內(nèi)排序采用的是()A.直接插入排序B,折半插入排序C.快速排序D.歸并排序41 .用單鏈表保存m個整數(shù)，節(jié)點的結(jié)構(gòu)為(data,link),且|data|

32、<n(M正整數(shù))。州要求設(shè)計一個時間復(fù)雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留一次出現(xiàn)的節(jié)點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈或head如下HEAD刪除節(jié)點后的head為HEAD要求：(1)給出算法的基本思想使用c或C+®言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義根據(jù)設(shè)計思想，采用C或C+語言描述算法，關(guān)鍵之處給出注釋(4)說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度42 .已知有5個頂點的圖G如下圖所示請回答下列問題(1)寫出圖G的鄰接矩陣A(行、列下標(biāo)從0開始(2)求A2,矩陣A2中位于0行3列元素值的含義是什么？(3)若已知具有n(n>=2)個頂點的鄰接矩

33、陣為B則，Bm(2<=m<=n)非零元素的含義是什么？20091-5:BCDBC6-10:BADBA41該方法求得的路徑不一定是最 短路徑。例如，對于下圖所示的帶權(quán) 圖，如果按照題中的原則，從 A至U C 的最短路徑為A 一B一C,事實上其最 短路徑為A> D C。從4到口的最10路徑為A-JC+事宴上其最混路行為kA*U-+C(A210D)Y/.342. (1)算法的基本設(shè)計思想：定義兩個指針變量p和q,初始時均指向頭結(jié)點的下一個結(jié)點。P指針沿鏈表移動；當(dāng)p指針移動到第k個結(jié)點時，q指針開始與p指針同步移動；當(dāng)p指針移動到鏈表最后一個結(jié)點時，q指針?biāo)冈貫榈箶?shù)第k個結(jié)點。

34、以上過程對鏈表僅進(jìn)行一遍掃描。(2)算法的詳細(xì)實現(xiàn)步驟：count=0,p和q指向鏈表表頭結(jié)點的下一個結(jié)點；若p為空，轉(zhuǎn)；若count等于k,則q指向下一個結(jié)點；否則,count=count+1;'p指向下一個結(jié)點，轉(zhuǎn)步驟；若count等于k,則查找成功，輸出該結(jié)點的data域白值，返回1;返回;查找失敗，返回0;算法結(jié)束。(3)算法實現(xiàn)：/typedefstructLNodeintdata;structLNode*link;*LinkList;/intSearchN(LinkListlist,intk)LinkListp,q;intcount=0;/*計數(shù)器賦初值*/p=q=list

35、->link;/*p和q指向鏈表表頭結(jié)點的下一個結(jié)點*/while(p!=NULL)/if(count<k)count+;/*計數(shù)器+1*/elseq=q->link;/*q移到下一個結(jié)點*/p=p->link;/*p移到下一個結(jié)點*/if(count<k)return(0);/*如果鏈表的長度小于k,查找失敗*/elseprintf("%d”,q->data);/*查找成功*/return(1);1)構(gòu)造的散列表如下下標(biāo)01I23456789關(guān)鍵字7-1481130189(2)查找成功的平均查找長度：ASL成功=12/7。查找不成功的平均查找長度

36、：ASL不成功=18/7。42.(1)給出算法的基本設(shè)計思想：先將n個數(shù)據(jù)x0x1-xp-xn-1原地逆置,得到xn-1xpxp-1)。,然后再將前n-p個和后p個元素分別原地逆置，得到最終結(jié)果:xpxp+1xn-1x0x1xp-1。(2)算法實現(xiàn)：voidreverse(intr口,intleft,intright)intk=left,j=right,temp;分筆記圖最后一題42.(1)算法的基本設(shè)計思想：(5分)1)比較笨的方法：將兩升序序列歸并排序，然后求其中位數(shù)，時間復(fù)雜度是O(n),空間復(fù)雜度O(n)。2)高效的方法：分別求兩個升序序列A和B的中位數(shù)，設(shè)為a和b。如果a=b,則a或

37、者b即為所求的中位數(shù)。原因：如果將兩序列歸并排序，則最終序列中，排在子序列ab前邊的元素為先前兩序列中排在a和b前邊的元素；排在子序列ab后邊的元素為先前兩序列a和b后邊的元素。所以子序列ab一定位于最終序列的中間，有因為a=b,顯然a就是中位數(shù)。%如果awb貿(mào)設(shè)a<p>原因：同樣可以用歸并排序后的序列來驗證，歸并后排序后必然有形如a.b的序列出現(xiàn)，中位數(shù)必然出現(xiàn)在(a,b)范圍內(nèi)。因此可以做如下處理：舍棄a所在序列A之中比較小的一半，同時舍棄b所在序列B之中比較大的一半。一在保留的兩個升序序列中求出新的中位數(shù)a和b,重復(fù)上述過程，直到兩個序列只含一個元素為止，則較小者即為所求中位

38、數(shù)。(2)算法實現(xiàn)(高效方法)：(8分)/intSearch(intA,intB口，intn)ints1,e1,mid1,s2,e2,mid2;s1=0;e1=n-1;s2=1;e2=n-1;while(s1!=e1|s2!=e2)mid1=(s1+e1)/2;mid2=(s2+e2)/2;if(Amid1=Bmid2)returnAmid1;if(Amid1<p)1)算法思想：順序遍歷兩個鏈表到尾結(jié)點時，并不能保證兩個鏈表同時到達(dá)尾結(jié)點。這是因為兩個鏈表的長度不同。假設(shè)一個鏈表比另一個鏈表長k個結(jié)點，我們先在長鏈表上遍歷k個結(jié)點，之后同步遍歷兩個鏈表。這樣我們就能夠保證它們同時到達(dá)最后

39、一個結(jié)點了。由于兩個鏈表從第一個公共結(jié)點到鏈表的尾結(jié)點都是重合的。所以它們肯定同時到達(dá)第一個公共結(jié)點。于是得到算法思路：遍歷兩個鏈表求的它們的長度L1,L2;比較L1,L2,找出較長的鏈表，并求L=|L1-L2|;先遍歷長鏈表的L各結(jié)點；同步遍歷兩個鏈表，直至找到相同結(jié)點或鏈表結(jié)束。(2)算法的C語言代碼描述LinkListSearch_First_Common(LinkListL1,LinkListL2)1)給出算法的基本設(shè)計思想：依分)算法的策略是從前向后掃描數(shù)組元素，標(biāo)記出一個可能成為主元素的元素Num=然后重新計數(shù)，確認(rèn)Num是否是主元素。算法可分為以下兩步：選取候選的主元素：依次掃描所給數(shù)組中的每個整數(shù)，將第一個遇到的整數(shù)Num保存iJc中記錄Num的出現(xiàn)次數(shù)為1;若遇到的J個整數(shù)仍等于Num則計數(shù)加一，否則計數(shù)減一；當(dāng)計數(shù)減到0時，將遇到的下一個整數(shù)保存至匕中，計數(shù)重新記為1,