1、目前剛整理了2009-2015的試題 過幾天2016的也會上傳上去 希望對你有幫助。20091.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是A.棧 B.隊列 C.樹 D.圖2.設棧S和隊列Q的初始狀態均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是 A1 B.2 C.3 D.43.給定二叉樹圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。若遍歷后的結點序列為3，1，7，5

2、，6，2，4，則其遍歷方式是 ALRN B.NRL C.RLN D.RNL4.下列二叉排序樹中，滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數最多是A39 B.52 C.111 D.1196.將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可能具有的關系是I父子關系 II.兄弟關系 III.u的父結點與v的父結點是兄弟關系A.只有II B.I和II C.I和III D.I、II和III7.下列關于無向連通圖特性的敘述中，正確的是I所有頂點的度之和為偶數 II.邊數大于頂點個數減1 III.

3、至少有一個頂點的度為1A.只有I B.只有II C.I和II D.I和III8.下列敘述中，不符合m階B樹定義要求的是A根節點最多有m棵子樹 B.所有葉結點都在同一層上C各結點內關鍵字均升序或降序排列 D.葉結點之間通過指針鏈接9.已知關鍵序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關鍵字3，調整后得到的小根堆是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.若數據元素序列11，12，13，7，8，9，23，4，5是

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

5、結構為datalink假設該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的結點（k為正整數）。若查找成功，算法輸出該結點的data值，并返回1；否則，只返回0。要求：（1）描述算法的基本設計思想（2）描述算法的詳細實現步驟（3）根據設計思想和實現步驟，采用程序設計語言描述算法（使用C或C+或JAVA語言實現），關鍵之處請給出簡要注釋。20101、若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續三次進行退棧工作，則不可能得到的出棧序列是（ ）A：dcebfa B：cbdaef C：dbcaef D：afed

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

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

8、 C：6 D：710、采用遞歸方式對順序表進行快速排序，下列關于遞歸次數的敘述中，正確的是（ ）A：遞歸次數與初始數據的排列次序無關B：每次劃分后，先處理較長的分區可以減少遞歸次數C：每次劃分后，先處理較短的分區可以減少遞歸次數D：遞歸次數與每次劃分后得到的分區處理順序無關11、對一組數據（2，12，16，88，5，10）進行排序，若前三趟排序結果如下（ ）第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88則采用的排序方法可能是：A：起泡排序 B：希爾排序 C：歸并排序 D：基數排序41.（10分）將關鍵字序列（7、8、11、18

9、、9、14）散列存儲到散列列表中，散列表的存儲空間是一個下標從0開始的一個一維數組散列函數維：H（key）=（key×3）MODT，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7問題：（1）請畫出所構造的散列表； （2）分別計算等概率情況下，查找成功和查找不成功的平均查找長度。42.（13分）設將n(n,1)個整數存放到一維數組R中，試設計一個在時間和空間兩方面盡可能有效的算法，將R中保有的序列循環左移P（0Pn）個位置，即將R中的數據由（X0X1Xn-1）變換為（XpXp+1Xn-1X0X1Xp-1）要求：（1）給出算法的基本設計思想。 （2）根據設計思想，采用C或C+或

10、JAVA語言表述算法關鍵之處給出注釋。 （3）說明你所設計算法的時間復雜度和空間復雜度20111.設n是描述問題規模的非負整數，下面程序片段的時間復雜度是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依次進入初始為空的棧中，若元素進棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開頭的序列個數是 A.3 B.4 C.5 D.63.已知循環隊列存儲在一維數組A0.n-1 中，且隊列非空時front和rear分別指向隊頭元素和隊尾元素。若初始

11、時隊列為空，且要求第1個進入隊列的元素存儲在A0處，則初始時front和rear的值分別是A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-14.若一棵完全二叉樹有768個結點，則該二叉樹中葉結點的個數是A.257 B.258 C.384 D.3855.若一棵二叉樹的前序遍歷序列和后序遍歷序列分別為1, 2, 3, 4和4, 3, 2, 1，則該二叉樹的中序遍歷序列不會是A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 16.已知一棵有2011個結點的樹，其葉結點個數為116，該樹對應的二叉樹中無右孩子的結點個數是A.115

12、B.116 C.1895 D.18967.對于下列關鍵字序列，不可能構成某二叉排序樹中一條查找路徑的序列是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.下列關于圖的敘述中，正確的是I. 回路是簡單路徑II. 存儲稀疏圖，用鄰接矩陣比鄰接表更省空間III.若有向圖中存在拓撲序列，則該圖不存在回路A.僅II B.僅I、II C.僅III D.僅I、III9.為提高散列(Hash)表的查找效率，可以采取的正確措施是I. 增大裝填(載)因子II. 設

13、計沖突(碰撞)少的散列函數III.處理沖突(碰撞)時避免產生聚集(堆積)現象A.僅I B.僅II C.僅I、II D.僅II、III10.為實現快速排序算法，待排序序列宜采用的存儲方式是A.順序存儲 B.散列存儲 C.鏈式存儲 D.索引存儲11.已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18，將其再調整為大根堆，調整過程中元素之間進行的比較次數是A.1 B.2 C.4 D.541.(8分)已知有6個頂點(頂點編號為0 5)的有向帶權圖G，其鄰接矩陣A為上三角矩陣，按行為主序(行優先)保存在如下的一維數組中。要求：(1)寫出圖G的鄰接矩陣A。(2)畫出有向帶權圖G。

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

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

16、c，后續遍歷序列為b,c,d,e,a，則根節點的孩子節點()A.只有e B.有e、b C.有e、c D.無法確定4、若平衡二叉樹的高度為6，且所有非葉節點的平衡因子均為1，則該平衡二叉樹的節點總數為()A.10 B.20 C.32 D.335、對有n個節點、e條邊且使用鄰接表存儲的有向圖進行廣度優先遍歷，其算法時間復雜度()A.O(n) B.O(e) C.O(n+e) D.O(n*e)6、若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關于該圖拓撲序列的結構是()A.存在，且唯一 B.存在，且不唯一C.存在，可能不唯一 D.無法確定是否存在7、如下有向帶權圖，若采用迪杰斯特拉（Dij

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

18、()A.60 B.60,62 C.62,65 D.6510、在內部排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結束都至少能夠確定一個元素最終位置的方法是().簡單選擇排序 .希爾排序 .快速排序 .堆排序 .二路歸并排序A.僅、 B.僅、C.僅、 D.僅、11對一待排序序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同之處是()A.排序的總趟數 B.元素的移動次數C.使用輔助空間的數量 D.元素之間的比較次數二、問答題。41、（10分）設有6個有序表A、B、C、D、E、F，分別含有10、35、40、50、60和200個數據元素，各表中元素

19、按升序排列。要求通過5次兩兩合并，將6個表最終合并成1個升序表，并在最壞情況下比較的總次數達到最小。請回答下列問題。（1）給出完整的合并過程，并求出最壞情況下比較的總次數。（2）根據你的合并過程，描述N(N2)個不等長升序表的合并策略，并說明理由。42、（13分）假定采用帶頭結點的單鏈表保存單詞，當兩個單詞有相同的后時綴，則可共享相同的后綴存儲空間，例如，“loaging”和“being”，如下圖所示。設str1和str2分別指向兩個單詞所在單鏈表的頭結點，鏈表結點結構為（data,next），請設計一個時間上盡可能高效的算法，找出由str1和str2所指向兩個鏈表共同后綴的起始位置（如圖中字

20、符i所在結點的位置p）。要求：（1）給出算法的基本設計思想。（2）根據設計思想，采用C或C+或java語言描述算法關鍵之處給出注釋。（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 可能取值的個數是:A. n-3 B. n- 2 C. n-1 D. 無法確定3. 若將關鍵字1，2，3，

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

22、于T1 與T3 的敘述中，正確的是I. 若v 是T1 的葉結點，則T1 與T3 不同II. 若v 是T1 的葉結點，則T1 與T3 相同III. 若v 不是T1 的葉結點，則T1 與T3 不同IV. 若v 不是T1 的葉結點，則T1 與T3 相同A. 僅I、III B. 僅I、IV C. 僅II、III D. 僅II、IV7. 設圖的鄰接矩陣A 如下所示。各頂點的度依次是A. 1，2，1，2 B. 2，2，1，1 C. 3，4，2，3 D. 4，4，2，28. 若對如下無向圖進行遍歷，則下列選項中，不是廣度優先遍歷序列的是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網表示一項包含8個活動的工程。通過同時加快若干活動的進度可以縮短整個工程的工期。下列選項中，加快其進度就可以縮短整個工程的工期的是：A c和e B d和e C f 和d D f和h10、在一棵高為2 的5階B樹中，所含關鍵字的個數最少是A 5 B 7 C 8 D14A= ( 0，5，5，3，5，7，5，5 )，側5為主元素；又如A= ( 0，5，5，3，5，1，5，7 )，則A中沒有主元素。假設A中的n個元素保存在一個一維數組中，請計一個盡可能

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

25、0;= 0.15，p3=0. 15，p4=0.35。將S保存在一個長度為4的順序表中，采用折半查找法，查找成功時的平均查找長度為2.2。請回答：（1）若采用順序存儲結構保存S，且要求平均查找長度更短，則元素應如何排列？應使用何種查找方法？查找成功時的平均查找長度是多少？（2）若采用鏈式存儲結構保存S，且要求平均查找長度更短，則元素應如何排列？應使用何種查找方法？查找成功時的平均查找長度是多少？20141. 下列程常段的時間復雜度是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. 假設棧初始為空，將中綴表達式轉換為等價后綴表達式的過程中，當掃描到f時，棧中的元素依次是A B. C. D. 3. 循環兩列放在一維數組A0M-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）

27、modMD.隊空：end1=（end2+1）modM; 隊滿：end2=(end1+1)mod(M-1)4. 若對如下的二叉樹進行中序線索化，則結點x的左、右線索指向的結點分別是A.e,c B.e,a C.d,c D.b,abdxeac5. 將森林F轉換為對應的二叉樹T，F中葉結點的個數等于A.T中葉結點的個數 B.T中度為1的結點個數 C.T中左孩子指針為空的結點個數 D.T中右孩子指針為空的結點個數6. 5個字符有如下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. 對如下所示的有向圖進行拓撲排序，得到的拓撲序列可能是A.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. 用哈希（散列）方法處理沖突（碰撞）時可能出現堆積（聚集）現象，下列選項中，會受堆積現象直接影響的是A.存儲效率 B.數列函數 C.裝填（裝載）因子 D.平均查找長度9.在一棵具有15個關鍵字的4階B樹中，含關鍵字的結點數最多是A.5 B.6 C.10 D.1510. 用希爾排序方法對一個數據序列進行排序時，若第1趟排序結果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（

29、間隔）可能是A.2 B.3 C.4 D.511. 下列選項中，不可能是快速排序第2趟排序結果的是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分）二叉樹的帶權路徑長度（WPL）是二叉樹中所有葉結點的帶權路徑長度之和，給定一棵二叉樹T，采用二叉鏈表存儲，節點結構為：leftweightright其中葉節點的weight域保存該結點的非負權值。設root為指向T的根節點的指針，設計求T的WPL的算法。要求：（1）給出算法的基本設計思想；（2）使用C或C+語言，給出二叉樹結點的數據類型定義；（3）根據設計思想

30、，采用C或C+語言描述算法，關鍵之處給出注釋。20151已知程序如下： int s(int n)  return (n<=0) ? 0 : s(n-1) +n;  void main()  cout<< s(1);   程序運行時使用棧來保存調用過程的信息，自棧底到棧頂保存的信息一次對應的是  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的不同二叉樹的個數是 A13  B14  C15  D163下列選項給出的是從根分別到達兩個葉節點路徑上的權值序列，能屬于同一棵哈夫曼樹的是 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現在有一顆無重復關鍵字的平衡二叉樹（AVL樹）,對其進行中序遍歷可得到一個降序序列。下列關于該平衡二叉樹的敘述中，正確的是A根節點的度一定為2  B樹中最小元素一定是葉節點C最后插入的元素一定是葉節點 D樹中最大元素一定是無左子樹5設有向圖G=(V,E)，頂點集V=V0,V1,V2,V3，邊集E=<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>,若從頂點V0 開始對圖進行深度優先遍歷，則可能得到的不同遍歷序列個數是 A2  B3   C4   D5 6 求下面帶權圖的最?。ù鷥r）生成樹時，可能是克魯斯卡（kruskal）算法第二次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是 A(V1,V3)   B(V1,V4)    C(V2,V3)   D(V3,V4) 7下列選項中，不能構成折半查找中關鍵字比較序列的是 A500，200，450，180&