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

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

(

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

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

(

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

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

（1）給出算法的基本設(shè)計(jì)思想。

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

（3）說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。42.（4，，，查，p2

=

0.15，p3=0.

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

A→D→C。

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

①遍歷兩個(gè)鏈表求的它們的長(zhǎng)度，；

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

LinkList

Search_First_Common(LinkList

L1,LinkList

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

int

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

LinkList

longList,shortlist;//分別指向較長(zhǎng)和較短的鏈表

if(len1>len2){

longList=L1->next;

shortlist=L2->next;

L=len1-len2;//表長(zhǎng)之差}//ifelse{

longList=L2->next;

shortlist=L1->next;

L=len2-len1;//表長(zhǎng)之差

}//else

While(L--)

longList=longList->next;

while(longList!=NULL){

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

return

longList;

else{

longList=longList->next;

shortlist=shortlist->next;

}

//else}//while

return

NULL;

}//Search_First_Common

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

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

{

設(shè)置A[0]

對(duì)A}//else}//for

}//Majority42.（1（2采用順序查找方法。（1分）查找成功時(shí)的平均查找長(zhǎng)度=

××××。（2分）

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