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

計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)統(tǒng)考?xì)v年真題2009-2015目前剛整理了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的容量至少是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個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是A．39B.52C.111D.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ǔ).只有IIB.I和IIC.I和IIID.I、II和III7.下列關(guān)于無向連通圖特性的敘述中，正確的是I．所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1III.至少有一個(gè)頂點(diǎn)的度為1A.只有IB.只有IIC.I和IID.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)整后得到的小根堆是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)間的距離）的最短路徑問題是找出從初始頂點(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)結(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ì)語言描述算法（使用C或C++或JAVA語言實(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：dcebfaB：cbdaefC：dbcaefD：afedcb2、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是（）A：bacdeB：dbaceC：dbcaeD：ecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）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.無法確定是否存在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)于最小生成樹的說法中，正確的是()Ⅰ、最小生成樹的代價(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)鍵字是()A.60B.60,62C.62,65D.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ù)元素，各表中元素按升序排列。要求通過5次兩兩合并，將6個(gè)表最終合并成1個(gè)升序表，并在最壞情況下比較的總次數(shù)達(dá)到最小。請(qǐng)回答下列問題。（1）給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。（2）根據(jù)你的合并過程，描述N(N≥2)個(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è)鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點(diǎn)的位置p）。要求：（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用C或C++或java語言描述算法關(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-3B.n-2C.n-1D.無法確定3.若將關(guān)鍵字1，2，3，4，5，6，7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結(jié)點(diǎn)的個(gè)數(shù)是A.0B.1C.2D.34.已知三叉樹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是后序線索二叉樹中的葉結(jié)點(diǎn)，且X存在左兄弟結(jié)點(diǎn)Y，則X的右線索指向的是A.X的父結(jié)點(diǎn)B.以Y為根的子樹的最左下結(jié)點(diǎn)C.X的左兄弟結(jié)點(diǎn)YD.以Y為根的子樹的最右下結(jié)點(diǎn)6.在任意一棵非空二叉排序樹T1中，刪除某結(jié)點(diǎn)v之后形成二叉排序樹T2，再將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，28.若對(duì)如下無向圖進(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)的工程。通過同時(shí)加快若干活動(dòng)的進(jìn)度可以縮短整個(gè)工程的工期。下列選項(xiàng)中，加快其進(jìn)度就可以縮短整個(gè)工程的工期的是：Ac和eBd和eCf和dDf和h10、在一棵高為2的5階B樹中，所含關(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中沒有主元素。假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中，請(qǐng)計(jì)一個(gè)盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出。要求：

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

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

（3）說明你所設(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á)式的過程中，當(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ì)如下的二叉樹進(jìn)行中序線索化，則結(jié)點(diǎn)x的左、右線索指向的結(jié)點(diǎn)分別是A.e,cB.e,aC.d,cD.b,abbdxeac5.將森林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,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樹中，含關(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,9