./目前剛整理了2009-2015的試題過幾天2016的也會上傳上去希望對你有幫助20091.為解決計算機(jī)與打印機(jī)之間速度不匹配的問題,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū),而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù).該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是A.棧B.隊列C.樹D.圖2.設(shè)棧S和隊列Q的初始狀態(tài)均為空,元素abcdefg依次進(jìn)入棧S.若每個元素出棧后立即進(jìn)入隊列Q,且7個元素出隊的順序是bdcfeag,則棧S的容量至少是A．1B.2C.3D.43.給定二叉樹圖所示.設(shè)N代表二叉樹的根,L代表根結(jié)點的左子樹,R代表根結(jié)點的右子樹.若遍歷后的結(jié)點序列為3,1,7,5,6,2,4,則其遍歷方式是A．LRNB.NRLC.RLND.RNL4.下列二叉排序樹中,滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層〔設(shè)根為第1層有8個葉結(jié)點,則完全二叉樹的結(jié)點個數(shù)最多是A．39B.52C.111D.1196.將森林轉(zhuǎn)換為對應(yīng)的二叉樹,若在二叉樹中,結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點,則在原來的森林中,u和v可能具有的關(guān)系是I．父子關(guān)系II.兄弟關(guān)系III.u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系A(chǔ).只有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.二路歸并排序41.〔10分帶權(quán)圖〔權(quán)值非負(fù),表示邊連接的兩頂點間的距離的最短路徑問題是找出從初始頂點到目標(biāo)頂點之間的一條最短路徑.假定從初始頂點到目標(biāo)頂點之間存在路徑,現(xiàn)有一種解決該問題的方法：①設(shè)最短路徑初始時僅包含初始頂點,令當(dāng)前頂點u為初始頂點；②選擇離u最近且尚未在最短路徑中的一個頂點v,加入到最短路徑中,修改當(dāng)前頂點u=v；③重復(fù)步驟②,直到u是目標(biāo)頂點時為止.請問上述方法能否求得最短路徑？若該方法可行,請證明之；否則,請舉例說明.42.〔15分已知一個帶有表頭結(jié)點的單鏈表,結(jié)點結(jié)構(gòu)為datalink假設(shè)該鏈表只給出了頭指針list.在不改變鏈表的前提下,請設(shè)計一個盡可能高效的算法,查找鏈表中倒數(shù)第k個位置上的結(jié)點〔k為正整數(shù).若查找成功,算法輸出該結(jié)點的data值,并返回1；否則,只返回0.要求：〔1描述算法的基本設(shè)計思想〔2描述算法的詳細(xì)實現(xiàn)步驟〔3根據(jù)設(shè)計思想和實現(xiàn)步驟,采用程序設(shè)計語言描述算法〔使用C或C++或JAVA語言實現(xiàn),關(guān)鍵之處請給出簡要注釋.20101、若元素a,b,c,d,e,f依次進(jìn)棧,允許進(jìn)棧、退棧操作交替進(jìn)行.但不允許連續(xù)三次進(jìn)行退棧工作,則不可能得到的出棧序列是〔A：dcebfaB：cbdaefC：dbcaefD：afedcb2、某隊列允許在其兩端進(jìn)行入隊操作,但僅允許在一端進(jìn)行出隊操作,則不可能得到的順序是〔A：bacdeB：dbaceC：dbcaeD：ecbad3、下列線索二叉樹中〔用虛線表示線索,符合后序線索樹定義的是〔4、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹,在新平衡二叉樹中,關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是〔A：13,48B：24,48C：24,53D：24,905、在一棵度為4的樹T中,若有20個度為4的結(jié)點,10個度為3的結(jié)點,1個度為2的結(jié)點,10個度為1的結(jié)點,則樹T的葉節(jié)點個數(shù)是〔A：41B：82C：113D：1226、對n<n大于等于2>個權(quán)值均不相同的字符構(gòu)成哈夫曼樹,關(guān)于該樹的敘述中,錯誤的是〔A：該樹一定是一棵完全二叉樹B：樹中一定沒有度為1的結(jié)點C：樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D：樹中任一非葉結(jié)點的權(quán)值一定不小于下一任一結(jié)點的權(quán)值7、若無向圖G-〔V.E中含7個頂點,則保證圖G在任何情況下都是連通的,則需要的邊數(shù)最少是〔A：6B：15C：16D：218、對下圖進(jìn)行拓補排序,可以得到不同的拓補序列的個數(shù)是〔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ù)排序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)隊列存儲在一維數(shù)組A[0..n-1]中,且隊列非空時front和rear分別指向隊頭元素和隊尾元素.若初始時隊列為空,且要求第1個進(jìn)入隊列的元素存儲在A[0]處,則初始時front和rear的值分別是A.0,0B.0,n-1C.n-1,0D.n-1,n-14.若一棵完全二叉樹有768個結(jié)點,則該二叉樹中葉結(jié)點的個數(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é)點的樹,其葉結(jié)點個數(shù)為116,該樹對應(yīng)的二叉樹中無右孩子的結(jié)點個數(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è)計沖突<碰撞>少的散列函數(shù)III.處理沖突<碰撞>時避免產(chǎn)生聚集<堆積>現(xiàn)象A.僅IB.僅IIC.僅I、IID.僅II、III10.為實現(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個頂點<頂點編號為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.現(xiàn)有兩個等長升序序列A和B,試設(shè)計一個在時間和空間兩方面都盡可能高效的算法,找出兩個序列A和B的中位數(shù).要求:<1>給出算法的基本設(shè)計思想.<2>根據(jù)設(shè)計思想,采用C或C++或JAVA語言描述算法,關(guān)鍵之處給出注釋.<3>說明你所設(shè)計算法的時間復(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、已知操作符包括‘+’、‘-’、‘*’、‘/’、‘<’和‘>’.將中綴表達(dá)式a+b-a*<<c+d>/e-f>+g轉(zhuǎn)換為等價的后綴表達(dá)式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條邊且使用鄰接表存儲的有向圖進(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.存在,且唯一B.存在,且不唯一C.存在,可能不唯一D.無法確定是否存在7、如下有向帶權(quán)圖,若采用迪杰斯特拉〔Dijkstra算法求源點a到其他各頂點的最短路徑,得到的第一條最短路徑的目標(biāo)頂點是b,第二條最短路徑的目標(biāo)頂點是c,后續(xù)得到的其余各最短路徑的目標(biāo)頂點依次是<>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)部排序過程中,對尚未確定最終位置的所有元素進(jìn)行一遍處理稱為一趟排序.下列排序方法中,每一趟排序結(jié)束都至少能夠確定一個元素最終位置的方法是<>Ⅰ.簡單選擇排序Ⅱ.希爾排序Ⅲ.快速排序Ⅳ.堆排序Ⅴ.二路歸并排序A.僅Ⅰ、Ⅲ、ⅣB.僅Ⅰ、Ⅲ、ⅤC.僅Ⅱ、Ⅲ、ⅣD.僅Ⅲ、Ⅳ、Ⅴ11．對一待排序序列分別進(jìn)行折半插入排序和直接插入排序,兩者之間可能的不同之處是<>A.排序的總趟數(shù)B.元素的移動次數(shù)C.使用輔助空間的數(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ù).〔2根據(jù)你的合并過程,描述N<N≥2>個不等長升序表的合并策略,并說明理由.42、〔13分假定采用帶頭結(jié)點的單鏈表保存單詞,當(dāng)兩個單詞有相同的后時綴,則可共享相同的后綴存儲空間,例如,"loaging"和"being",如下圖所示.設(shè)str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點,鏈表結(jié)點結(jié)構(gòu)為〔data,next,請設(shè)計一個時間上盡可能高效的算法,找出由str1和str2所指向兩個鏈表共同后綴的起始位置〔如圖中字符i所在結(jié)點的位置p.要求：〔1給出算法的基本設(shè)計思想.〔2根據(jù)設(shè)計思想,采用C或C++或java語言描述算法關(guān)鍵之處給出注釋.〔3說明你所設(shè)計算法的時復(fù)雜度.20131.已知兩個長度分別為m和n的升序鏈表,若將它們合并為一個長度為m+n的降序鏈表,則最壞情況下的時間復(fù)雜度是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.設(shè)圖的鄰接矩陣A如下所示.各頂點的度依次是A.1,2,1,2B.2,2,1,1C.3,4,2,3D.4,4,2,28.若對如下無向圖進(jìn)行遍歷,則下列選項中,不是廣度優(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個活動的工程.通過同時加快若干活動的進(jìn)度可以縮短整個工程的工期.下列選項中,加快其進(jìn)度就可以縮短整個工程的工期的是：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中沒有主元素.假設(shè)A中的n個元素保存在一個一維數(shù)組中,請計一個盡可能高效的算法,找出A的主元素.若存在主元素,則輸出該元素；否則輸出.要求：〔1給出算法的基本設(shè)計思想.〔2根據(jù)設(shè)計思想,采用C或或語言描述算法,關(guān)鍵之處給出釋.〔3說明你所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度.42.〔4,,,查,p2

=

0.15,p3=0.

15,S4的2.2〔1S使用〔2S使用20141.下列程常段的時間復(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)換為等價后綴表達(dá)式的過程中,當(dāng)掃描到f時,棧中的元素依次是A．B.C.D.3.循環(huán)兩列放在一維數(shù)組A[0…M-1]中,end1指向隊頭元素,end2指向隊尾元素的后一個位置.假設(shè)隊列兩端均可進(jìn)行入隊和出隊操作,隊列中最多能容納M-1個元素.初始時為空,下列判斷隊空和隊滿的條件中,正確的是A.隊空：end1==end2；隊滿：end1==<end2+1>modMB.隊空：end1==end2;隊滿：end2==<end1+1>mod<M-1>C.隊空：end2==<end1+1>modM;隊滿：end1==〔end2+1modMD.隊空：end1==〔end2+1modM;隊滿：end2==<end1+1>mod<M-1>4.若對如下的二叉樹進(jìn)行中序線索化,則結(jié)點x的左、右線索指向的結(jié)點分別是A.e,cB.e,aC.d,cD.b,abbdxeac5.將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T,F中葉結(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.對如下所示的有向圖進(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.用哈希〔散列方法處理沖突〔碰撞時可能出現(xiàn)堆積〔聚集現(xiàn)象,下列選項中,會受堆積現(xiàn)象直接影響的是A.存儲效率B.數(shù)列函數(shù)