計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)統(tǒng)考?xì)v年真題2009-2016年

.目前剛整理了2009-2015的試題過幾天2016的也會上傳上去希望對你有幫助。。。。。。。20091.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是A.棧B.隊(duì)列C.樹D.圖2.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空,元素abcdefg依次進(jìn)入棧S。若每個元素出棧后立即進(jìn)入隊(duì)列Q,且7個元素出隊(duì)的順序是bdcfeag,則棧S的容量至少是A．1B.2C.3D.43.給定二叉樹圖所示。設(shè)N代表二叉樹的根,L代表根結(jié)點(diǎn)的左子樹,R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3,1,7,5,6,2,4,則其遍歷方式是A．LRNB.NRLC.RLND.RNL4.下列二叉排序樹中,滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層〔設(shè)根為第1層有8個葉結(jié)點(diǎn),則完全二叉樹的結(jié)點(diǎn)個數(shù)最多是A．39B.52C.111D.1196.將森林轉(zhuǎn)換為對應(yīng)的二叉樹,若在二叉樹中,結(jié)點(diǎn)u是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn),則在原來的森林中,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)于無向連通圖特性的敘述中,正確的是I．所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個數(shù)減1III.至少有一個頂點(diǎn)的度為1A.只有IB.只有IIC.I和IID.I和III8.下列敘述中,不符合A．根節(jié)點(diǎn)最多有m棵子樹C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.葉結(jié)點(diǎn)之間通過指針鏈接9.已知關(guān)鍵序列5,8,12,19,28,20,15,22是小根堆〔最小堆,插入關(guān)鍵字3,調(diào)整m階B樹定義要求的是B.所有葉結(jié)點(diǎn)都在同一層上后得到的小根堆是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.二路歸并排序41.〔10分帶權(quán)圖〔權(quán)值非負(fù)是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑,現(xiàn)有一種解決該問題的方法：①設(shè)最短路徑初始時僅包含初始頂點(diǎn),令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；u最近且尚未在最短路徑中的一個頂點(diǎn)v,加入到最短路徑中,修改當(dāng)前頂點(diǎn)u=v；,表示邊連接的兩頂點(diǎn)間的距離的最短路徑問題②選擇離1/11

.③重復(fù)步驟②,直到u是目標(biāo)頂點(diǎn)時為止。請問上述方法能否求得最短路徑？若該方法可行,請證明之；否則,請舉例說明。42.〔15分已知一個帶有表頭結(jié)點(diǎn)的單鏈表,結(jié)點(diǎn)結(jié)構(gòu)為假設(shè)該鏈表只給出了的前提下,請?jiān)O(shè)計(jì)一個盡可datalink頭指針list。在不改變鏈表能高效的算法,查找鏈表中倒數(shù)第k個位置上的結(jié)點(diǎn)〔k為正整數(shù)。若查找成功,算法輸出該結(jié)點(diǎn)的data值,并返回1；否則,只返回0。要求：〔1描述算法的基本設(shè)計(jì)思想〔2描述算法的詳細(xì)實(shí)現(xiàn)步驟〔3根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟,采用程序設(shè)計(jì)語言描述算法〔使用C或C++或JAVA語言實(shí)現(xiàn),關(guān)鍵之處請給出簡要注釋。20101、若元素a,b,c,d,e,f依次進(jìn)棧,允許進(jìn)棧連續(xù)三次進(jìn)行退棧工作,則不可能得到的出棧序列是〔A：dcebfaB：cbdaefC：dbcaefD：afedcb2、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作,但僅允許在一端進(jìn)行出隊(duì)操作,則不可能得到的順序是〔、退棧操作交替進(jìn)行。但不允許A：bacdeB：dbaceC：dbcaeD：ecbad3、下列線索二叉樹中〔用虛線表示線索,符合后序線索樹定義的是〔4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹,在新平衡二叉樹中,關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是〔A：13,48B：24,48C：24,53D：24,905、在一棵度為4的樹T中,若有20個度為4的結(jié)點(diǎn),10個度為3的結(jié)點(diǎn),1個度為2的結(jié)點(diǎn),10個度為1的結(jié)點(diǎn),則樹T的葉節(jié)點(diǎn)個數(shù)是〔2/11.A：41B：82C：113D：1226、對n<n大于等于2>個權(quán)值均不相同的字符構(gòu)成哈夫曼樹,關(guān)于該樹的敘述中,錯誤的是〔A：該樹一定是一棵完全二叉樹B：樹中一定沒有度為1的結(jié)點(diǎn)C：樹中兩個權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D：樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值7、若無向圖G-〔V.E中含7個頂點(diǎn),則保證圖G在任何情況下都是連通的,則需要的邊數(shù)最少是〔A：6B：15C：16D：218、對下圖進(jìn)行拓補(bǔ)排序,可以得到不同的拓補(bǔ)序列的個數(shù)是edacb〔A：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ū)可以減少遞歸次數(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=〔key×3MODT,處理沖突采用線性探測再散列法,要求裝填〔載因子為0.7問題：〔1請畫出所構(gòu)造的散列表；〔2分別計(jì)算等概率情況下,查找成功和查找不成功的平均查找長度。42.〔13分設(shè)將n<n,1>個整數(shù)存放到一維數(shù)組R中,試設(shè)計(jì)一個在時間和空間兩方面盡可能有效的算法,將R中保有的序列循環(huán)左移P〔0﹤P﹤n個位置,即將R中的數(shù)據(jù)由〔X0X1……Xn-1變換為〔XpXp+1……Xn-1X0X1……Xp-1要求：〔1給出算法的基本設(shè)計(jì)思想?！?根據(jù)設(shè)計(jì)思想,采用C或C++或JAVA語言表述算法關(guān)鍵之處給出注釋?！?說明你所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度3/11.20111.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù),下面程序片段的時間復(fù)雜度是x=2;while<x<n/2>x=2*x;A.O<log2n>B.O<n>C.O<nlog2n>D.O<n2>2.元素a,b,c,d,e依次進(jìn)入初始為空的棧中,若元素進(jìn)棧后可停留、可出棧,直到所有元素都出棧,則在所有可能的出棧序列中,以元素d開頭的序列個數(shù)是A.3B.4C.5D.63.已知循環(huán)隊(duì)列存儲在一維數(shù)組A[0..n-1]中,且隊(duì)列非空時front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始時隊(duì)列為空,且要求第1個進(jìn)入隊(duì)列的元素存儲在A[0]處,則初始時front和rear的值分別是A.0,0B.0,n-1C.n-1,0D.n-1,n-14.若一棵完全二叉樹有768個結(jié)點(diǎn),則該二叉樹中葉結(jié)點(diǎn)的個數(shù)是A.257B.258C.384D.3855.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1,2,3,4和4,3,2,1,則該二叉樹的中序遍歷序列不會是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,16.已知一棵有2011個結(jié)點(diǎn)的樹,其葉結(jié)點(diǎn)個數(shù)為116,該樹對應(yīng)的二叉樹中無右孩子的結(jié)點(diǎn)個數(shù)是A.115B.116C.1895D.18967.對于下列關(guān)鍵字序列,不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,348.下列關(guān)于圖的敘述中,正確的是I.回路是簡單路徑II.存儲稀疏圖,用鄰接矩陣比鄰接表更省空間III.若有向圖中存在拓?fù)湫蛄?則該圖不存在回路A.僅IIB.僅I、IIC.僅IIID.僅I、III9.為提高散列<Hash>表的查找效率,可以采取的正確措施是I.增大裝填<載>因子II.設(shè)計(jì)沖突<碰撞>少的散列函數(shù)III.處理沖突<碰撞>時避免產(chǎn)生聚集<堆積>現(xiàn)象A.僅IB.僅IIC.僅I、IID.僅II、III10.為實(shí)現(xiàn)快速排序算法,待排序序列宜采用的存儲方式是A.順序存儲B.散列存儲C.鏈?zhǔn)酱鎯.索引存儲11.已知序列25,13,10,12,9是大根堆,在序列尾部插入新元素18,將其再調(diào)整為大根堆,調(diào)整過程中元素之間進(jìn)行的比較次數(shù)是A.1B.2C.4D.541.<8分>已知有6個頂點(diǎn)<頂點(diǎn)編號為0~5>的有向帶權(quán)圖G,其鄰接矩陣A為上三角矩陣,按行為主序<行優(yōu)先>保存在如下的一維數(shù)組中。4/11.要求：<1>寫出圖G的鄰接矩陣A。<2>畫出有向帶權(quán)圖G。<3>求圖G的關(guān)鍵路徑,并計(jì)算該關(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,試設(shè)計(jì)一個在時間和空間兩方面都盡可能高效的算法,找出兩個序列A和B的中位數(shù)。要求:<1>給出算法的基本設(shè)計(jì)思想。<2>根據(jù)設(shè)計(jì)思想,采用C或C++或JAVA語言描述算法,關(guān)鍵之處給出注釋。<3>說明你所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度。20121、求整數(shù)n<n≥0>階乘的算法如下,其時間復(fù)雜度是<>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)換為等后綴表達(dá)式ab+acd+e/f-**-g+時,用棧來存放暫時還不能確定運(yùn)算次序的操作符,若棧初始時為空,則轉(zhuǎn)換過程中同時保存棧中最大個數(shù)是‘>’。將中綴表達(dá)式價(jià)的的操作符的<>A.5B.7C.8D.113、若一顆二叉樹的前序遍歷序列為a,e,b,d,c,后續(xù)遍歷序列為b,c,d,e,a,則根節(jié)點(diǎn)的孩子節(jié)點(diǎn)A.只有eB.有e、bC.有e、cD.無法確定4、若平衡二叉樹的高度為6,且所有非葉節(jié)點(diǎn)的平衡因子均為1,則該叉樹的節(jié)點(diǎn)總數(shù)為<>平衡二<>A.10B.20C.32D.335、對有n個節(jié)點(diǎn)、e條邊且使用鄰接表存儲的有向圖進(jìn)行廣度優(yōu)先遍歷,其算法時間復(fù)雜度<>A.O<n>B.O<e>C.O<n+e>D.O<n*e>6、若用鄰接矩陣存儲有向圖,矩陣中主對角線以下的元素均為零,則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)構(gòu)是<>A.存在C.存在,可能不唯一D.無法確定是否存在7、如下有向帶權(quán)圖,若采用迪杰斯特拉〔Dijkstra算法求點(diǎn)的最短路徑,得到的第一短路徑的目標(biāo)頂點(diǎn)是b,第二條最短路徑的目標(biāo)頂點(diǎn)是c,后續(xù)得到的其短路徑的依次是<>,且唯一B.存在,且不唯一源點(diǎn)a到其他各頂條最余各最目標(biāo)頂點(diǎn)A.d,e,fB.e,d,fC.f,d,eD.f,e,d8、下列關(guān)Ⅰ、最小生成樹的代價(jià)唯一Ⅱ、所有權(quán)小的邊一定會出現(xiàn)在所有的最小生成樹中于最小生成樹的說法中,正確的是<>值最5/11

.Ⅲ、使用普里姆〔Prim算法從不同頂點(diǎn)開始得到的最小生成樹一定相同Ⅳ、使用普里姆算法和克魯斯卡爾〔Kruskal算法得到的最小生成樹總不相同A.僅ⅠB.僅ⅡC.僅Ⅰ、ⅢD.僅Ⅱ、Ⅳ9、已知一棵3階B-樹,如下圖所示。刪除關(guān)鍵字78得到一棵新B-樹,其最中的關(guān)鍵字是<>右葉結(jié)點(diǎn)A.60B.60,62C.62,65D.6510、在內(nèi)部排序過程中,對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序。下列排序方法中,每一的方法是<>Ⅰ.簡單選擇排序Ⅱ.希爾排序Ⅲ.快速排序Ⅳ.堆排序Ⅴ.二路歸并排序A.僅Ⅰ、Ⅲ、ⅣB.僅Ⅰ、Ⅲ、趟排序結(jié)束都至少能夠確定一個元素最終位置ⅤC.僅Ⅱ、Ⅲ、ⅣD.僅Ⅲ、Ⅳ、Ⅴ11．對一待排序序列分別進(jìn)行折半插入排序和直接插入排序,兩者之間可能的不同之處是<>A.排序的總趟數(shù)C.使用輔助空間的數(shù)量二、問答題。B.元素的移動次數(shù)D.元素之間的比較次數(shù)41、〔10分設(shè)有6個有序表A、B、C、D、E、F,分別含有10、35、40、50、60和200個數(shù)據(jù)元素,各表中元素按升序排列。要求通過5次兩兩合并,將6個表最終合并成1個升序表,并在最壞情況下比較的總次數(shù)達(dá)到最小。請回答下列問題。〔1給出完整的合并過程,并求出最壞情況下比較的總次數(shù)?！?根據(jù)你的合并過程,描述N<N≥2>個不等長升序表的合并策略,并說明理由。42、〔13分假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞,當(dāng)兩個單詞有相同的后時綴,則可共享相同的后綴存儲空間,例如,"loaging"和"being",如下圖所示。設(shè)str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點(diǎn)請?jiān)O(shè)計(jì)一個時間上盡可能高效的算法,找出由str1和str2所指向兩個鏈表共同后綴的起始位置〔如圖中字符i所在結(jié)點(diǎn)的位置p。要求：〔1給出算法的基本設(shè)計(jì)思想。,鏈表結(jié)點(diǎn)結(jié)構(gòu)為〔data,next,〔2根據(jù)設(shè)計(jì)思想,采用C或C++或java語言描述算法關(guān)鍵之處給出注釋?！?說明你所設(shè)計(jì)算法的時復(fù)雜度。20131.已知兩個長度分別為m和n的升序鏈表,若將它們合并為一個長度為6/11.m+n的降序鏈表,則最壞情況下的時間復(fù)雜度是A.O<n>B.O<m*n>C.O<min<m,n>>D.O<max<m,n>>2.一個棧的入棧序列為p3可能取值的個數(shù)是A.n-3B.n-2C.n-1D.無法確定3.若將關(guān)鍵字1,2,3,4,5,6,7依次插入到初始為空的平衡二叉樹0的分支結(jié)點(diǎn)的個數(shù)是1,2,3,,n,其出棧序列是p1,p2,p3,pn。若p2=3,則:T中,則T中平衡因子為A.0B.1C.2D.34.已知三叉樹T中6個葉結(jié)點(diǎn)的權(quán)分別是2,3,4,5,6,7,T的帶權(quán)〔外部路徑長度最小是A.27B.46C.54D.565.若X是后序線索二叉樹中的葉結(jié)點(diǎn),且X存在左兄弟結(jié)點(diǎn)Y,則X的右線索指向的是A.X的父結(jié)點(diǎn)C.X的左兄弟結(jié)點(diǎn)6.在任意一棵非空二叉排序樹T1中,刪除某結(jié)點(diǎn)v插入T2形成二叉排序樹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,2B.以Y為根的子樹的最左下結(jié)點(diǎn)D.以Y為根的子樹的最右下結(jié)點(diǎn)v之后形成二叉排序樹T2,,正確的是Y再將8.若對如下無向圖進(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)包含加快若干活動的縮短整個工程的工期。下列選項(xiàng)中工期的是：Ac和eBd和eCf和dDf和h10、在一棵高為2的5階B樹中,所含關(guān)鍵字的個數(shù)最少是A5B7C8A=<0,5,5,3,5,7,5,5>,側(cè)5為主元素；又如A=<0,5,5,3,5,1,5,7>,則A8個活動的工程。通過同時進(jìn)度可以,加快其進(jìn)度就可以縮短整個工程的D14中沒有主元素。假設(shè)A中的n個元素保存在一個一維數(shù)組中,請計(jì)一個盡可能高效的算法,找出A的主元素。若存在主元素,則輸出該元素；否則輸出-1。要求：〔1給出算法的基本設(shè)計(jì)思想?！?根據(jù)設(shè)計(jì)思想,采用C或C++或Java語言描述算法,關(guān)鍵之處給出釋。〔3說明你所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度。42.〔10分設(shè)包含概率依次為：p1=0.35,p2=0.15,p3=0.15,p4=0.35。將序表中,采用折半查找法,查找成功時的平均查找長度為2.2。請回答：4個數(shù)據(jù)元素的集合S={"do","for","repeat","while"},各元素查找S保存在一個長度為4的順7/11.〔1若采用順序存儲結(jié)構(gòu)保存S,且要求平均查找長度更短,則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時的平均查找長度是多少？〔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++;A.O<log2n>2.假設(shè)棧初始為空,當(dāng)掃描到B.O<n>C.O<nlog2n>D.O<n2>,將中綴表達(dá)式abcdefg轉(zhuǎn)換為等價(jià)后綴表達(dá)式的過程中f時,棧中的元素依次是A．B.C.D.3.循環(huán)兩列放在一維數(shù)組A[0…M-1]中,end1指向隊(duì)頭元素,end2指向隊(duì)尾,隊(duì)列中最多能容納,下列判斷隊(duì)空和隊(duì)滿的條件中,正確的是end1==end2；隊(duì)滿：B.隊(duì)空：end1==end2;隊(duì)滿：C.隊(duì)空：end2==<end1+1>modM;D.隊(duì)空：end1==〔end2+1modM;隊(duì)滿：4.若對如下的二叉樹進(jìn)行中序線索化,則結(jié)點(diǎn)x的左、右線索指向的結(jié)點(diǎn)分別是元素的后一個位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作M-1個元素。初始時為空A.隊(duì)空：end1==<end2+1>modMend2==<end1+1>mod<M-1>隊(duì)滿：end1==〔end2+1modMend2==<end1+1>mod<M-1>A.e,cB.e,aC.d,cD.b,aabcdxe5.將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T,F中葉結(jié)點(diǎn)的個數(shù)等A.T中葉結(jié)點(diǎn)的個數(shù)B.T中度為1的結(jié)點(diǎn)個數(shù)C.T中左孩子指針為空的結(jié)點(diǎn)個數(shù)D.T中右孩子指針為空的結(jié)點(diǎn)個數(shù)6.5個字符有如下4種編碼方案,不是前綴編碼的是于8/11.A.01,0000,0001,001,1C.000,001,010,011,100B.011,000,001,010,1D.000,001,010,011,1007.對如下所示的有向圖進(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,51245368.用哈希〔散列方法處理沖突〔碰撞時可能出現(xiàn)堆積〔聚集現(xiàn)象,下列選項(xiàng)中,會受堆積現(xiàn)象直接影響的是A.存儲效率B.數(shù)列函數(shù)C.裝填〔裝載因子D.平均查找長度9.在一棵具有15個關(guān)鍵字的4階B樹中,含關(guān)鍵字的結(jié)點(diǎn)數(shù)最多是A.5B.6C.10D.1510.用希爾排序方法對一個數(shù)據(jù)序列進(jìn)行排序時,若第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,9C.3,2,5,4,7,6,9B.2,7,5,6,4,3,9D.4,2,3,5,7,6,941.〔13分二叉樹的帶權(quán)路徑長度〔WPL是二叉樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和,給定一棵二叉樹T,采用二叉鏈表存儲,節(jié)點(diǎn)結(jié)構(gòu)為：其中葉節(jié)點(diǎn)的weight域保存該結(jié)點(diǎn)的非負(fù)權(quán)值。設(shè)leftweightrightroot為指向〔1給出算法的〔2使用C或C++語言〔3根據(jù)設(shè)計(jì)思想,采用C或C++語言描述算法,關(guān)鍵之處給出T的根節(jié)點(diǎn)的指針,設(shè)計(jì)求T的WPL的算法。要求：設(shè)計(jì)思想；,給出二叉樹結(jié)點(diǎn)的數(shù)據(jù)基本類型定義；注釋。20151．已知程序如下：ints<intn>{return<n<=0>?0:s<n-1>+n;}voidmain<>{cout<<s<1>;}程序運(yùn)行時使用棧來保存調(diào)用過程的信息,自棧底到棧頂保存的信息一次對應(yīng)的是A．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ù)是9/11.A．13B．14C．15D．163．下列選項(xiàng)給出的是從根分別到達(dá)兩個葉節(jié)點(diǎn)路徑上的權(quán)值序列,能屬于同一棵哈夫曼樹的是A．24,10,5和24,10,7B．24,10,5和24,12,7C．24,10,10和24,14,11D．24,10,5和24,14,64．現(xiàn)在有一顆無重復(fù)關(guān)鍵字的平衡二叉樹〔AVL樹,對其進(jìn)行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中,正確的是A．根節(jié)點(diǎn)的度一定為2B．樹中最小元素一定是葉節(jié)點(diǎn)定是葉節(jié)點(diǎn)D．樹中C．最后插入的元素一最大元素一定是無左子