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

計算機數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案20091.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應該是A.棧B.隊列C.樹D.圖2.設棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是A．1B.2C.3D.43.給定二叉樹圖所示。設N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3，1，7，5，6，2，4，則其遍歷方式是A．LRNB.NRLC.RLND.RNL4.下列二叉排序樹中，滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是A．39B.52C.111D.1196.將森林轉(zhuǎn)換為對應的二叉樹，若在二叉樹中，結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點，則在原來的森林中，u和v可能具有的關(guān)系是I．父子關(guān)系II.兄弟關(guān)系III.u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列關(guān)于無向連通圖特性的敘述中，正確的是I．所有頂點的度之和為偶數(shù)II.邊數(shù)大于頂點個數(shù)減1III.至少有一個頂點的度為1A.只有IB.只有IIC.I和IID.I和III8.下列敘述中，不符合m階B樹定義要求的是A．根節(jié)點最多有m棵子樹B.所有葉結(jié)點都在同一層上C．各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列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，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若數(shù)據(jù)元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是A．起泡排序B.插入排序C.選擇排序D.二路歸并排序II.設計沖突(碰撞)少的散列函數(shù)III.處理沖突(碰撞)時避免產(chǎn)生聚集(堆積)現(xiàn)象A.僅IB.僅IIC.僅I、IID.僅II、III10.為實現(xiàn)快速排序算法，待排序序列宜采用的存儲方式是A.順序存儲B.散列存儲C.鏈式存儲D.索引存儲11.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，將其再調(diào)整為大根堆，調(diào)整過程中元素之間進行的比較次數(shù)是A.1B.2C.4D.541.(8分)已知有6個頂點(頂點編號為0~5)的有向帶權(quán)圖G，其鄰接矩陣A為上三角矩陣，按行為主序(行優(yōu)先)保存在如下的一維數(shù)組中。要求：(1)寫出圖G的鄰接矩陣A。(2)畫出有向帶權(quán)圖G。(3)求圖G的關(guān)鍵路徑，并計算該關(guān)鍵路徑的長度。42.(15分)一個長度為L(L≥1)的升序序列S，處在第éL/2ù個位置的數(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，試設計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數(shù)。要求:(1)給出算法的基本設計思想。(2)根據(jù)設計思想，采用C或C++或JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設計算法的時間復雜度和空間復雜度。20121、求整數(shù)n(n≥0)階乘的算法如下，其時間復雜度是()intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A.O(log2n)B.O(n)C.(nlog2n)D.O(n2)2、已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。將中綴表達式a+b-a*((c+d)/e-f)+g轉(zhuǎn)換為等價的后綴表達式ab+acd+e/f-**-g+時，用棧來存放暫時還不能確定運算次序的操作符，若棧初始時為空，則轉(zhuǎn)換過程中同時保存棧中的操作符的最大個數(shù)是()A.5B.7C.8D.113、若一顆二叉樹的前序遍歷序列為a,e,b,d,c，后續(xù)遍歷序列為b,c,d,e,a，則根節(jié)點的孩子節(jié)點()A.只有eB.有e、bC.有e、cD.無法確定4、若平衡二叉樹的高度為6，且所有非葉節(jié)點的平衡因子均為1，則該平衡二叉樹的節(jié)點總數(shù)為()A.10B.20C.32D.335、對有n個節(jié)點、e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法時間復雜度()A.O(n)B.O(e)C.O(n+e)D.O(n*e)6、若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓撲序列的結(jié)構(gòu)是()A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.無法確定是否存在7、如下有向帶權(quán)圖，若采用迪杰斯特拉（Dijkstra）算法求源點a到其他各頂點的最短路徑，得到的第一條最短路徑的目標頂點是b，第二條最短路徑的目標頂點是c，后續(xù)得到的其余各最短路徑的目標頂點依次是()A.d,e,fB.e,d,fC.f,d,eD.f,e,d8、下列關(guān)于最小生成樹的說法中，正確的是()Ⅰ、最小生成樹的代價唯一Ⅱ、所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中Ⅲ、使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同Ⅳ、使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同A.僅ⅠB.僅ⅡC.僅Ⅰ、ⅢD.僅Ⅱ、Ⅳ9、已知一棵3階B-樹，如下圖所示。刪除關(guān)鍵字78得到一棵新B-樹，其最右葉結(jié)點中的關(guān)鍵字是()A.60B.60,62C.62,65D.6510、在內(nèi)部排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結(jié)束都至少能夠確定一個元素最終位置的方法是()Ⅰ.簡單選擇排序Ⅱ.希爾排序Ⅲ.快速排序Ⅳ.堆排序Ⅴ.二路歸并排序A.僅Ⅰ、Ⅲ、ⅣB.僅Ⅰ、Ⅲ、ⅤC.僅Ⅱ、Ⅲ、ⅣD.僅Ⅲ、Ⅳ、Ⅴ11．對一待排序序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同之處是()A.排序的總趟數(shù)B.元素的移動次數(shù)C.使用輔助空間的數(shù)量D.元素之間的比較次數(shù)二、問答題。41、（10分）設有6個有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200個數(shù)據(jù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個表最終合并成1個升序表，并在最壞情況下比較的總次數(shù)達到最小。請回答下列問題。（1）給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。（2）根據(jù)你的合并過程，描述N(N≥2)個不等長升序表的合并策略，并說明理由。42、（13分）假定采用帶頭結(jié)點的單鏈表保存單詞，當兩個單詞有相同的后時綴，則可共享相同的后綴存儲空間，例如，“l(fā)oaging”和“being”，如下圖所示。設str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為（data,next），請設計一個時間上盡可能高效的算法，找出由str1和str2所指向兩個鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點的位置p）。要求：（1）給出算法的基本設計思想。（2）根據(jù)設計思想，采用C或C++或java語言描述算法關(guān)鍵之處給出注釋。（3）說明你所設計算法的時復雜度。20131.已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是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依次插入到初始為空的平衡二叉樹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是T1的葉結(jié)點，則T1與T3相同III.若v不是T1的葉結(jié)點，則T1與T3不同IV.若v不是T1的葉結(jié)點，則T1與T3相同A.僅I、IIIB.僅I、IVC.僅II、IIID.僅II、IV7.設圖的鄰接矩陣A如下所示。各頂點的度依次是A.1，2，1，2B.2，2，1，1C.3，4，2，3D.4，4，2，28.若對如下無向圖進行遍歷，則下列選項中，不是廣度優(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個活動的工程。通過同時加快若干活動的進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短整個工程的工期的是：Ac和eBd和eCf和dDf和h10、在一棵高為2的5階B樹中，所含關(guān)鍵字的個數(shù)最少是A5B7C8D14A=

(

0，5，5，3，5，7，5，5

)，側(cè)5為主元素；又如A=

(

0，5，5，3，5，1，5，7

)A中沒有主元素。假設A中的n個元素保存在一個一維數(shù)組中，請計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出。要求：

（1）給出算法的基本設計思想。

（2）根據(jù)設計思想，采用C或或語言描述算法，關(guān)鍵之處給出釋。

（3）說明你所設計算法的時間復雜度和空間復雜度。42.（4，，，查，p2

=

0.15，p3=0.

15，S4的2.2（1S使用（2S使用20141.下列程常段的時間復雜度是count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j+1)count++;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2.假設棧初始為空，將中綴表達式轉(zhuǎn)換為等價后綴表達式的過程中，當掃描到f時，棧中的元素依次是A．B.C.D.3.循環(huán)兩列放在一維數(shù)組A[0…M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納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.若對如下的二叉樹進行中序線索化，則結(jié)點x的左、右線索指向的結(jié)點分別是A.e,cB.e,aC.d,cD.b,abbdxeac5.將森林F轉(zhuǎn)換為對應的二叉樹T，F(xiàn)中葉結(jié)點的個數(shù)等于A.T中葉結(jié)點的個數(shù)B.T中度為1的結(jié)點個數(shù)C.T中左孩子指針為空的結(jié)點個數(shù)D.T中右孩子指針為空的結(jié)點個數(shù)6.5個字符有如下4種編碼方案，不是前綴編碼的是A.01,0000,0001,001,1B.011,000,001,010,1C.000,001,010,011,100D.000,001,010,011,1007.對如下所示的有向圖進行拓撲排序，得到的拓撲序列可能是A.3,1,2,4,5,6B.3,1,2,4,6,5C.3,1,4,2,5,6D.3,1,4,2,6,511254638.用哈希（散列）方法處理沖突（碰撞）時可能出現(xiàn)堆積（聚集）現(xiàn)象，下列選項中，會受堆積現(xiàn)象直接影響的是A.存儲效率B.數(shù)列函數(shù)C.裝填（裝載）因子D.平均查找長度9.在一棵具有15個關(guān)鍵字的4階B樹中，含關(guān)鍵字的結(jié)點數(shù)最多是A.5B.6C.10D.1510.用希爾排序方法對一個數(shù)據(jù)序列進行排序時，若第1趟排序結(jié)果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是A.2B.3C.4D.511.下列選項中，不可能是快速排序第2趟排序結(jié)果的是A.2,3,5,4,6,7,9B.2,7,5,6,4,3,9C.3,2,5,4,7,6,9D.4,2,3,5,7,6,941.（13分）二叉樹的帶權(quán)路徑長度（WPL）是二叉樹中所有葉結(jié)點的帶權(quán)路徑長度之和，給定一棵二叉樹T，采用二叉鏈表存儲，節(jié)點結(jié)構(gòu)為：leftweightright其中葉節(jié)點的weight域保存該結(jié)點的非負權(quán)值。設root為指向T的根節(jié)點的指針，設計求T的WPL的算法。要求：（1）給出算法的基本設計思想；（2）使用C或C++語言，給出二叉樹結(jié)點的數(shù)據(jù)類型定義；（3）根據(jù)設計思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋。20151

{

{

A．

B．C．m

D．2．

A．B．C．D．3

A．24，10，5和

24，10，

B．，，5和，，7

C．，，和

24，14，D．24，10，5和

24，14，4．（AVL樹）,ABCD5．，01,V23}，邊集0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},VA．B．

C．

D．PrimV42

A．

B．

C．

D．

A．500，200，，

B．，450，200，C．，500，200，D．180，，，8S為t為采用“失配時，i和j

A．，

B．，

C．，

D．，

9

A

B

C

D108，15，10，21，34，16，128

A．1

B．

C．

D．4

11

A

B

C

Dm，且)。

head如下為要求：

使用c或

c或

5G

GA(0

求A2A20行3

B則，Bm么？20091-5：BCDBC 6-10：BADBA41.該方法求得的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則，從A到C的最短路徑為A→B→C，事實上其最短路徑為

A→D→C。

42.（1）算法的基本設計思想：定義兩個指針變量p和q，初始時均指向頭結(jié)點的下一個結(jié)點。P指針沿鏈表移動；當p指針移動到第k個結(jié)點時，q指針開始與p指針同步移動；當p指針移動到鏈表最后一個結(jié)點時，q指針所指元素為倒數(shù)第k個結(jié)點。以上過程對鏈表僅進行一遍掃描。（2）算法的詳細實現(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)：typedefstructLNode{ intdata; structLNode*link;}*LinkList;intSearchN(LinkListlist,intk){ LinkListp,q; intcount=0;/*計數(shù)器賦初值*/ p=q=list->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,查找失敗*/else {printf("%d",q->data);/*查找成功*/ return(1);}//else}//SearchN20101-5：DCDCB 6-11：ACBBDA41.（1）構(gòu)造的散列表如下下標0123456789關(guān)鍵字71481130189（2）查找成功的平均查找長度:ASL成功=12/7。查找不成功的平均查找長度:ASL不成功=18/7。42.（1）給出算法的基本設計思想：先將n個數(shù)據(jù)x0x1…xp…xn-1原地逆置，得到xn-1…xpxp-1…x0,然后再將前n-p個和后p個元素分別原地逆置，得到最終結(jié)果:xpxp+1…xn-1x0x1…xp-1。（2）算法實現(xiàn)：voidreverse(intr[],intleft,intright){ intk=left,j=right,temp;//k等于左邊界left,j等于右邊界right while(k<j){//交換r[k]和r[j] temp=r[k]; r[k]=r[j]; r[j]=temp; k++;//k右移一個位置 j--;//j左移一個位置 }}voidleftShift(intr[],intn,intp){ if(p>0&&p<n){ reverse(r,0,n-1);//將全部數(shù)據(jù)逆置 reverse(r,0,n-p-1);//將前n-p個元素逆置 reverse(r,n-p,n-1);//將后p個元素逆置 }}（3）說明算法復雜性：上述算法的時間復雜度為O(n),空間復雜度為O(1)。20111-5：ABBCC 6-10：DACBA41.高分筆記圖最后一題(1)算法的基本設計思想：(5分)1)比較笨的方法：將兩升序序列歸并排序，然后求其中位數(shù)，時間復雜度是O(n)，空間復雜度O(n)。2)高效的方法：分別求兩個升序序列A和B的中位數(shù)，設為a和b。如果a=b，則a或者b即為所求的中位數(shù)。原因：如果將兩序列歸并排序，則最終序列中，排在子序列ab前邊的元素為先前兩序列中排在a和b前邊的元素;排在子序列ab后邊的元素為先前兩序列a和b后邊的元素。所以子序列ab一定位于最終序列的中間，有因為a=b，顯然a就是中位數(shù)。如果a≠b(假設a<p>原因：同樣可以用歸并排序后的序列來驗證，歸并后排序后必然有形如…a…b…的序列出現(xiàn)，中位數(shù)必然出現(xiàn)在(a，b)范圍內(nèi)。因此可以做如下處理：舍棄a所在序列A之中比較小的一半，同時舍棄b所在序列B之中比較大的一半。在保留的兩個升序序列中求出新的中位數(shù)a和b，重復上述過程，直到兩個序列只含一個元素為止，則較小者即為所求中位數(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(A[mid1]==B[mid2])returnA[mid1];if(A[mid1]<p){//分別考慮奇數(shù)和偶數(shù)，保持兩個子數(shù)組元素個數(shù)相等if((s1+e1)%2==0){//若元素個數(shù)為奇數(shù)s1=mid1;//舍棄A中間點以前部分且保留中間點e2=mid2;//舍棄B中間點以后部分且保留中間點}//ifelse{//若元素個數(shù)為偶數(shù)s1=mid1+1;//舍棄A中間點以前部分且保留中間點e2=mid2;//舍棄B中間點以后部分且保留中間點}//else}//ifelse{if((s1+e1)%2==0){//若元素個數(shù)為奇數(shù)個e1=mid1;//舍棄A中間點以后部分且保留中間點s2=mid2;//舍棄B中間點以前部分且保留中間點}//ifelse{//若元素個數(shù)為偶數(shù)個e1=mid1+1;//舍棄A中間點以后部分且保留中間點s2=mid2;//舍棄B中間點以前部分且保留中間點}//else}//else}//whilereturn(A[s1])}//search(3)上述所給算法的時間、空間復雜度分別是O(log2n)和O(1)。(2分)因為每次總的元素個數(shù)變?yōu)樵瓉淼囊话耄杂校旱谝淮危涸貍€數(shù)為n/2=n/(21)第二次：元素個數(shù)為n/4=n/(22)…………第k次：元素個數(shù)為n/(2k)最后元素個數(shù)為2則有n/(2k)=2解得k=log2n–1因此：時間復雜度為O(log2n)，而空間復雜度從上述程序中可看出為O(1)。20121-5：BAABC 6-11：CCADAD高分筆記排序最后一題42.（1）算法思想：順序遍歷兩個鏈表到尾結(jié)點時，并不能保證兩個鏈表同時到達尾結(jié)點。這是因為兩個鏈表的長度不同。假設一個鏈表比另一個鏈表長k個結(jié)點，我們先在長鏈表上遍歷k個結(jié)點，之后同步遍歷兩個鏈表。這樣我們就能夠保證它們同時到達最后一個結(jié)點了。由于兩個鏈表從第一個公共結(jié)點到鏈表的尾結(jié)點都是重合的。所以它們肯定同時到達第一個公共結(jié)點。于是得到算法思路：

①遍歷兩個鏈表求的它們的長度，；

②比較，，找出較長的鏈表，并求L=|L1-L2|；③先遍歷長鏈表的L各結(jié)點；④同步遍歷兩個鏈表，直至找到相同結(jié)點或鏈表結(jié)束。（2）算法的C語言代碼描述

LinkList

Search_First_Common(LinkList

L1,LinkList

L2){//本算法實現(xiàn)線性時間內(nèi)找到兩個單鏈表的第一個公共結(jié)點

int

len1=Length(L1),len2=Length(L2);

LinkList

longList,shortlist;//分別指向較長和較短的鏈表

if(len1>len2){

longList=L1->next;

shortlist=L2->next;

L=len1-len2;//表長之差}//ifelse{

longList=L2->next;

shortlist=L1->next;

L=len2-len1;//表長之差

}//else

While(L--)

longList=longList->next;

while(longList!=NULL){

if(longList==shortList)//同步尋找共同結(jié)點

return

longList;

else{

longList=longList->next;

shortlist=shortlist->next;

}

//else}//while

return

NULL;

}//Search_First_Common

（3）算法的時間復雜度為O(len1+len2)，空間復雜度為

O(1)。20131-5：DCDBA 6-10：CCDCA41.（1（4分）。①到c中記錄1則計數(shù)加一，否則計數(shù)減一0c1②判斷ccn（2（7

{

設置A[0]

對A}//else}//for

}//Majority42.（1（2采用順序查找方法。（1分）查找成功時的平均查找長度=

××××。（2分）

（2（2分）（1××××。（2（2分）20141-5：CBADC 6-11：DDDDBC41考查二叉樹的帶權(quán)路徑長度，二叉樹的帶權(quán)路徑長度為每個葉子結(jié)點的深度與權(quán)的總和，可以使用先序遍歷或?qū)哟伪闅v解決問題。1）算法的基本設計思想：①基于先序遞歸遍歷的算法思想是用一個變量記錄wpl，把每個結(jié)點的深度作為遞歸函數(shù)的一個參數(shù)傳遞，算法步驟如下：若該結(jié)點是葉子結(jié)點，那么變量wpl加上該結(jié)點的深度與權(quán)值之積；若該結(jié)點非葉子結(jié)那么若左子樹不為空，對左子樹調(diào)用遞歸算法，若右子樹不為空，對右子樹調(diào)用遞歸算法，深度參數(shù)均為本結(jié)點的深度參數(shù)加一；最后返回計算出的②基于層次遍歷的算法思想是使用隊列進行層次遍歷，并記錄當前的層數(shù)，當遍歷到葉子結(jié)點時，累計；當遍歷到非葉子結(jié)點時對該結(jié)點的把該結(jié)點的子樹加入隊列；當某結(jié)點為該層的最后一個結(jié)點時，層數(shù)自增1；隊列空時遍2)二叉樹結(jié)點的數(shù)據(jù)類型定義如下：structBiTNode{intBiTNode3)算法代碼如下：①基于先序遍歷的算法：introot){wpl_PreOrder(root,}//intintroot,intdeep){static=0;//定義一個變量存儲if(root->lchildroot->lchild//若為葉子結(jié)點，累積deep*root->weight;if(root->lchild//若左子樹不空，對左子樹遞歸遍歷wpl_PreOrder(root->lchild,deep+1);if(root->rchild//若右子樹不空，對右子樹遞歸遍歷wpl_PreOrder(root->rchild,deep+1);}//②基于層次遍歷的算法：MaxSize100//設置隊列的最大容量introot){q[MaxSize];//聲明隊列，為頭指針，為尾指針intend2;//隊列最多容納MaxSize-1==0;//頭指針指向隊頭元素，尾指針指向隊尾的后一個元素int=deep=0;//初始化和深度lastNode;//lastNode用來記錄當前層的最后一個結(jié)點newlastNode;//newlastNode用來記錄下一層的最后一個結(jié)點lastNode=ro