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

1、目前剛整理了2009-2015的試題 過幾天2016的也會(huì)上傳上去 希望對(duì)你有幫助。20091.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(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。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag，則棧S的容量至少是 A1 B.2 C.3 D.43.給定二叉樹圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3，1，7，5

2、，6，2，4，則其遍歷方式是 ALRN B.NRL C.RLN D.RNL4.下列二叉排序樹中，滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是A39 B.52 C.111 D.1196.將森林轉(zhuǎn)換為對(duì)應(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ǔ).只有II B.I和II C.I和III D.I、II和III7.下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是I所有頂點(diǎn)的度之和為偶數(shù) II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1 III.

3、至少有一個(gè)頂點(diǎn)的度為1A.只有I B.只有II C.I和II D.I和III8.下列敘述中，不符合m階B樹定義要求的是A根節(jié)點(diǎn)最多有m棵子樹 B.所有葉結(jié)點(diǎn)都在同一層上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)整后得到的小根堆是A3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C3，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是

4、采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是A起泡排序 B.插入排序 C.選擇排序 D.二路歸并排序41.（10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法：設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；選擇離u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v；重復(fù)步驟，直到u是目標(biāo)頂點(diǎn)時(shí)為止。請(qǐng)問上述方法能否求得最短路徑？若該方法可行，請(qǐng)證明之；否則，請(qǐng)舉例說明。42.（15分）已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)

5、結(jié)構(gòu)為datalink假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第k個(gè)位置上的結(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ì)語(yǔ)言描述算法（使用C或C+或JAVA語(yǔ)言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡(jiǎn)要注釋。20101、若元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（ ）A：dcebfa B：cbdaef C：dbcaef D：afed

6、cb2、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是（ ）A：bacde B：dbace C：dbcae D：ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（ ）4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（ ）A：13，48 B：24，48 C：24，53 D：24，905、在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹T的葉節(jié)點(diǎn)個(gè)數(shù)是（ ）A：41 B：82 C：113 D：1

7、226、對(duì)n(n大于等于2)個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是（ ）A：該樹一定是一棵完全二叉樹B：樹中一定沒有度為1的結(jié)點(diǎn)C：樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D：樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值7、若無(wú)向圖G-（V.E）中含7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（ ）A：6 B：15 C：16 D：218、對(duì)下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是（ ）A：4 B：3 C：2 D：19、已知一個(gè)長(zhǎng)度為16的順序表L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多是（ ）A：4 B：5

8、 C：6 D：710、采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（ ）A：遞歸次數(shù)與初始數(shù)據(jù)的排列次序無(wú)關(guān)B：每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)C：每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D：遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無(wú)關(guān)11、對(duì)一組數(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、、9、14）散列存儲(chǔ)到散列列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開始的一個(gè)一維數(shù)組散列函數(shù)維：H（key）=（key×3）MODT，處理沖突采用線性探測(cè)再散列法，要求裝填（載）因子為0.7問題：（1）請(qǐng)畫出所構(gòu)造的散列表； （2）分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長(zhǎng)度。42.（13分）設(shè)將n(n,1)個(gè)整數(shù)存放到一維數(shù)組R中，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能有效的算法，將R中保有的序列循環(huán)左移P（0Pn）個(gè)位置，即將R中的數(shù)據(jù)由（X0X1Xn-1）變換為（XpXp+1Xn-1X0X1Xp-1）要求：（1）給出算法的基本設(shè)計(jì)思想。 （2）根據(jù)設(shè)計(jì)思想，采用C或C+或

10、JAVA語(yǔ)言表述算法關(guān)鍵之處給出注釋。 （3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度20111.設(shè)n是描述問題規(guī)模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是x = 2;while ( x < n/2 )x = 2*x;A.O(log2n) B.O(n) C.O(n log2n) D.O(n2)2.元素a, b, c, d, e依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個(gè)數(shù)是 A.3 B.4 C.5 D.63.已知循環(huán)隊(duì)列存儲(chǔ)在一維數(shù)組A0.n-1 中，且隊(duì)列非空時(shí)front和rear分別指向隊(duì)頭元素和隊(duì)尾元素。若初始

11、時(shí)隊(duì)列為空，且要求第1個(gè)進(jìn)入隊(duì)列的元素存儲(chǔ)在A0處，則初始時(shí)front和rear的值分別是A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-14.若一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該二叉樹中葉結(jié)點(diǎn)的個(gè)數(shù)是A.257 B.258 C.384 D.3855.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1, 2, 3, 4和4, 3, 2, 1，則該二叉樹的中序遍歷序列不會(huì)是A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 16.已知一棵有2011個(gè)結(jié)點(diǎn)的樹，其葉結(jié)點(diǎn)個(gè)數(shù)為116，該樹對(duì)應(yīng)的二叉樹中無(wú)右孩子的結(jié)點(diǎn)個(gè)數(shù)是A.115

12、B.116 C.1895 D.18967.對(duì)于下列關(guān)鍵字序列，不可能構(gòu)成某二叉排序樹中一條查找路徑的序列是A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 348.下列關(guān)于圖的敘述中，正確的是I. 回路是簡(jiǎn)單路徑II. 存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間III.若有向圖中存在拓?fù)湫蛄?，則該圖不存在回路A.僅II B.僅I、II C.僅III D.僅I、III9.為提高散列(Hash)表的查找效率，可以采取的正確措施是I. 增大裝填(載)因子II. 設(shè)

13、計(jì)沖突(碰撞)少的散列函數(shù)III.處理沖突(碰撞)時(shí)避免產(chǎn)生聚集(堆積)現(xiàn)象A.僅I B.僅II C.僅I、II D.僅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)整過程中元素之間進(jìn)行的比較次數(shù)是A.1 B.2 C.4 D.541.(8分)已知有6個(gè)頂點(diǎn)(頂點(diǎn)編號(hào)為0 5)的有向帶權(quán)圖G，其鄰接矩陣A為上三角矩陣，按行為主序(行優(yōu)先)保存在如下的一維數(shù)組中。要求：(1)寫出圖G的鄰接矩陣A。(2)畫出有向帶權(quán)圖G。

14、(3)求圖G的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長(zhǎng)度。42.(15分)一個(gè)長(zhǎng)度為L(zhǎng)(L1)的升序序列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)說明你所

15、設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。20121、求整數(shù)n(n0)階乘的算法如下，其時(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í)，用棧來存放暫時(shí)還不能確定運(yùn)算次序的操作符，若棧初始時(shí)為空，則轉(zhuǎn)換過程中同時(shí)保存棧中的操作符的最大個(gè)數(shù)是()A.5 B.7 C.8 D.113、若一顆二叉樹的前序遍歷序列為a,e,b,d,

16、c，后續(xù)遍歷序列為b,c,d,e,a，則根節(jié)點(diǎn)的孩子節(jié)點(diǎn)()A.只有e B.有e、b C.有e、c D.無(wú)法確定4、若平衡二叉樹的高度為6，且所有非葉節(jié)點(diǎn)的平衡因子均為1，則該平衡二叉樹的節(jié)點(diǎn)總數(shù)為()A.10 B.20 C.32 D.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)圖，若采用迪杰斯特拉（Dij

17、kstra）算法求源點(diǎn)a到其他各頂點(diǎn)的最短路徑，得到的第一條最短路徑的目標(biāo)頂點(diǎn)是b，第二條最短路徑的目標(biāo)頂點(diǎn)是c，后續(xù)得到的其余各最短路徑的目標(biāo)頂點(diǎn)依次是()A.d,e,f B.e,d,f C.f,d,e D.f,e,d8、下列關(guān)于最小生成樹的說法中，正確的是()、最小生成樹的代價(jià)唯一、所有權(quán)值最小的邊一定會(huì)出現(xiàn)在所有的最小生成樹中、使用普里姆（Prim）算法從不同頂點(diǎn)開始得到的最小生成樹一定相同、使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同A.僅 B.僅 C.僅、 D.僅、9、已知一棵3階B-樹，如下圖所示。刪除關(guān)鍵字78得到一棵新B-樹，其最右葉結(jié)點(diǎn)中的關(guān)鍵字是

18、()A.60 B.60,62 C.62,65 D.6510、在內(nèi)部排序過程中，對(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ù)二、問答題。41、（10分）設(shè)有6個(gè)有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200個(gè)數(shù)據(jù)元素，各表中元素

19、按升序排列。要求通過5次兩兩合并，將6個(gè)表最終合并成1個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請(qǐng)回答下列問題。（1）給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。（2）根據(jù)你的合并過程，描述N(N2)個(gè)不等長(zhǎng)升序表的合并策略，并說明理由。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è)鏈表共同后綴的起始位置（如圖中字

20、符i所在結(jié)點(diǎn)的位置p）。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C+或java語(yǔ)言描述算法關(guān)鍵之處給出注釋。（3）說明你所設(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-3 B. n- 2 C. n-1 D. 無(wú)法確定3. 若將關(guān)鍵字1，2，3，

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

22、于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、III B. 僅I、IV C. 僅II、III D. 僅II、IV7. 設(shè)圖的鄰接矩陣A 如下所示。各頂點(diǎn)的度依次是A. 1，2，1，2 B. 2，2，1，1 C. 3，4，2，3 D. 4，4，2，28. 若對(duì)如下無(wú)向圖進(jìn)行遍歷，則下列選項(xiàng)中，不是廣度優(yōu)先遍歷序列的是A. h，c，a，b，d，e，g，f B. e，a，f，g，b，h，c，

23、dC. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g9、下列的AOE網(wǎng)表示一項(xiàng)包含8個(gè)活動(dòng)的工程。通過同時(shí)加快若干活動(dòng)的進(jìn)度可以縮短整個(gè)工程的工期。下列選項(xiàng)中，加快其進(jìn)度就可以縮短整個(gè)工程的工期的是：A c和e B d和e C f 和d D f和h10、在一棵高為2 的5階B樹中，所含關(guān)鍵字的個(gè)數(shù)最少是A 5 B 7 C 8 D14A= ( 0，5，5，3，5，7，5，5 )，側(cè)5為主元素；又如A= ( 0，5，5，3，5，1，5，7 )，則A中沒有主元素。假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)計(jì)一個(gè)盡可能

24、高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出-1。要求：     （1）給出算法的基本設(shè)計(jì)思想。 （2）根據(jù)設(shè)計(jì)思想，采用C或C+或Java語(yǔ)言描述算法，關(guān)鍵之處給出釋。   （3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。42.（10分）設(shè)包含4個(gè)數(shù)據(jù)元素的集合S= "do"，"for"，" repeat"，" while"，各元素查找概率依次為：p1=0.35，p2

25、0;= 0.15，p3=0. 15，p4=0.35。將S保存在一個(gè)長(zhǎng)度為4的順序表中，采用折半查找法，查找成功時(shí)的平均查找長(zhǎng)度為2.2。請(qǐng)回答：（1）若采用順序存儲(chǔ)結(jié)構(gòu)保存S，且要求平均查找長(zhǎng)度更短，則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時(shí)的平均查找長(zhǎng)度是多少？（2）若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)保存S，且要求平均查找長(zhǎng)度更短，則元素應(yīng)如何排列？應(yīng)使用何種查找方法？查找成功時(shí)的平均查找長(zhǎng)度是多少？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)

26、 C.O(nlog2n) D.O(n2)2. 假設(shè)棧初始為空，將中綴表達(dá)式轉(zhuǎn)換為等價(jià)后綴表達(dá)式的過程中，當(dāng)掃描到f時(shí)，棧中的元素依次是A B. C. D. 3. 循環(huán)兩列放在一維數(shù)組A0M-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）

27、modMD.隊(duì)空：end1=（end2+1）modM; 隊(duì)滿：end2=(end1+1)mod(M-1)4. 若對(duì)如下的二叉樹進(jìn)行中序線索化，則結(jié)點(diǎn)x的左、右線索指向的結(jié)點(diǎn)分別是A.e,c B.e,a C.d,c D.b,abdxeac5. 將森林F轉(zhuǎn)換為對(duì)應(yīng)的二叉樹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,1 B.011,000,001,010,1C.000,001,010,011,100 D.000,001,

28、010,011,1007. 對(duì)如下所示的有向圖進(jìn)行拓?fù)渑判?，得到的拓?fù)湫蛄锌赡苁茿.3,1,2,4,5,6 B.3,1,2,4,6,5 C.3,1,4,2,5,6 D.3,1,4,2,6,51254638. 用哈希（散列）方法處理沖突（碰撞）時(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樹中，含關(guān)鍵字的結(jié)點(diǎn)數(shù)最多是A.5 B.6 C.10 D.1510. 用希爾排序方法對(duì)一個(gè)數(shù)據(jù)序列進(jìn)行排序時(shí)，若第1趟排序結(jié)果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（

29、間隔）可能是A.2 B.3 C.4 D.511. 下列選項(xiàng)中，不可能是快速排序第2趟排序結(jié)果的是A.2,3,5,4,6,7,9 B.2,7,5,6,4,3,9 C.3,2,5,4,7,6,9 D.4,2,3,5,7,6,941.（13分）二叉樹的帶權(quán)路徑長(zhǎng)度（WPL）是二叉樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，給定一棵二叉樹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ǔ)言，給出二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義；（3）根據(jù)設(shè)計(jì)思想

30、，采用C或C+語(yǔ)言描述算法，關(guān)鍵之處給出注釋。20151已知程序如下： int s(int n)  return (n<=0) ? 0 : s(n-1) +n;  void main()  cout<< s(1);   程序運(yùn)行時(shí)使用棧來保存調(diào)用過程的信息，自棧底到棧頂保存的信息一次對(duì)應(yīng)的是  Amain()->S(1)->S(0)   BS(0)

31、->S(1)->main() Cmain()->S(0)->S(1)  DS(1)->S(0)->main() 2先序序列為a,b,c,d的不同二叉樹的個(gè)數(shù)是 A13  B14  C15  D163下列選項(xiàng)給出的是從根分別到達(dá)兩個(gè)葉節(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是 A24，10，5和 24，10，7  B24，10，5和24，12，7 C24，10，10和 24，14，11  D24，10，5和&

32、#160;24，14，6 4現(xiàn)在有一顆無(wú)重復(fù)關(guān)鍵字的平衡二叉樹（AVL樹）,對(duì)其進(jìn)行中序遍歷可得到一個(gè)降序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是A根節(jié)點(diǎn)的度一定為2  B樹中最小元素一定是葉節(jié)點(diǎn)C最后插入的元素一定是葉節(jié)點(diǎn) D樹中最大元素一定是無(wú)左子樹5設(shè)有向圖G=(V,E)，頂點(diǎn)集V=V0,V1,V2,V3，邊集E=<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>,若從頂點(diǎn)V0 開始對(duì)圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個(gè)數(shù)是 A2  B3   C4   D5 6 求下面帶權(quán)圖的最?。ù鷥r(jià)）生成樹時(shí)，可能是克魯斯卡（kruskal）算法第二次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是 A(V1,V3)   B(V1,V4)    C(V2,V3)   D(V3,V4) 7下列選項(xiàng)中，不能構(gòu)成折半查找中關(guān)鍵字比較序列的是 A500，200，450，180&