1、1、為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，、為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是 A.棧棧 B.隊(duì)列隊(duì)列 C.樹樹 D.圖圖 2、設(shè)棧、設(shè)棧S和隊(duì)列和隊(duì)列Q的初始狀態(tài)均為空，元素的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列入隊(duì)列Q，且，且7個(gè)元素出隊(duì)的順序是個(gè)元素出隊(duì)的順序

2、是bdcfeag，則棧，則棧S的容量至少是的容量至少是 A. 1 B. 2 C. 3 D. 4 3 3、給定二叉樹圖所示。設(shè)、給定二叉樹圖所示。設(shè)N N代表二叉樹的根，代表二叉樹的根，L L代代表根結(jié)點(diǎn)的左子樹，表根結(jié)點(diǎn)的左子樹，R R代表根結(jié)點(diǎn)的右子樹。若遍代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為歷后的結(jié)點(diǎn)序列為3 3，7 7，5 5，6 6，1 1，2 2，4 4，則其遍，則其遍歷方式是歷方式是 ALRN B.NRL C.RLN D.RNL 4 4、下列二叉排序樹中，滿足平衡二叉樹定義的是、下列二叉排序樹中，滿足平衡二叉樹定義的是 A B. C. D. 5、已知一棵完全二叉樹的第、已知一棵

3、完全二叉樹的第6層（設(shè)根為第層（設(shè)根為第1層）層）有有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是 A39 B. 52 C. 111 D. 119 6、將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹，若在二叉樹中，、將森林轉(zhuǎn)換為對(duì)應(yīng)的二叉樹，若在二叉樹中，結(jié)點(diǎn)結(jié)點(diǎn)u是結(jié)點(diǎn)是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森的父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，林中，u和和v可能具有的關(guān)系是可能具有的關(guān)系是 I父子關(guān)系父子關(guān)系 II.兄弟關(guān)系兄弟關(guān)系 III. u的父結(jié)點(diǎn)與的父結(jié)點(diǎn)與v的的父結(jié)點(diǎn)是兄弟關(guān)系父結(jié)點(diǎn)是兄弟關(guān)系 A.只有只有II B.I和和II C.I和和III D.I、II和和III 7

4、.下列關(guān)于無向連通圖特性的敘述中，正確的是下列關(guān)于無向連通圖特性的敘述中，正確的是 I.所有頂點(diǎn)的度之和為偶數(shù)所有頂點(diǎn)的度之和為偶數(shù) II.邊數(shù)大于頂點(diǎn)個(gè)數(shù)減邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1 III.至少有一個(gè)頂點(diǎn)的度為至少有一個(gè)頂點(diǎn)的度為1 A. 只有只有I B. 只有只有II C. I和和II D. I和和III 8.下列敘述中，不符合下列敘述中，不符合m階階B樹定義要求的是樹定義要求的是 A.根節(jié)點(diǎn)最多有根節(jié)點(diǎn)最多有m棵子樹棵子樹 B.所有葉結(jié)點(diǎn)都在同一層上所有葉結(jié)點(diǎn)都在同一層上 C.各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)點(diǎn)之間通過指針鏈接葉結(jié)點(diǎn)之間通過指針鏈接 9

5、9、已知關(guān)鍵序列、已知關(guān)鍵序列5 5，8 8，1212，1919，2828，2020，1515，2222是小根堆（最小堆），插入關(guān)鍵字是小根堆（最小堆），插入關(guān)鍵字3 3，調(diào)整后得到，調(diào)整后得到的小根堆是的小根堆是 A A3 3，5 5，1212，8 8，2828，2020，1515，2222，19 19 B. 3 B. 3，5 5，1212，1919，2020，1515，2222，8 8，28 28 C C3 3，8 8，1212，5 5，2020，1515，2222，2828，19 19 D. 3 D. 3，1212，5 5，8 8，2828，2020，1515，2222，19 19 10

6、10、若數(shù)據(jù)元素序列、若數(shù)據(jù)元素序列1111，1212，1313，7 7，8 8，9 9，2323，4 4，5 5是采用下列排序方法之一得到的第二趟排序后的是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是結(jié)果，則該排序算法只能是 A A起泡排序起泡排序 B.B.插入排序插入排序 C.C.選擇排序選擇排序 D.D.二路歸并排序二路歸并排序 41.41.（1010分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始點(diǎn)到目標(biāo)頂點(diǎn)之間的一條

7、最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法：問題的方法： 設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)點(diǎn)u u為初始頂點(diǎn)；為初始頂點(diǎn)； 選擇離選擇離u u最近且尚未在最短路徑中的一個(gè)頂點(diǎn)最近且尚未在最短路徑中的一個(gè)頂點(diǎn)v v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=vu=v； 重復(fù)步驟重復(fù)步驟，直到，直到u u是目標(biāo)頂點(diǎn)時(shí)為止。是目標(biāo)頂點(diǎn)時(shí)為止。 請(qǐng)問上述方法能否求得最短路徑？若該方法可行，請(qǐng)問上述方法能否求得最短路徑？若該方法可行，請(qǐng)證明之；否則，請(qǐng)舉例說明。

8、請(qǐng)證明之；否則，請(qǐng)舉例說明。 42.42.（1515分）已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)分）已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為點(diǎn)結(jié)構(gòu)為 假設(shè)該鏈表只給出了頭指針假設(shè)該鏈表只給出了頭指針listlist。在不改變鏈表。在不改變鏈表的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找的前提下，請(qǐng)?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查找鏈表中倒數(shù)第鏈表中倒數(shù)第k k個(gè)位置上的結(jié)點(diǎn)（個(gè)位置上的結(jié)點(diǎn)（k k為正整數(shù)）。為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的若查找成功，算法輸出該結(jié)點(diǎn)的datadata值，并返回值，并返回1 1；否則，只返回否則，只返回0 0。要求：。要求： （1 1） 描述算法的基本設(shè)計(jì)思想描述算法

9、的基本設(shè)計(jì)思想 （2 2） 描述算法的詳細(xì)實(shí)現(xiàn)步驟描述算法的詳細(xì)實(shí)現(xiàn)步驟 （3 3） 根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)計(jì)語言描述算法（使用語言描述算法（使用C C或或C+C+或或JAVAJAVA語言實(shí)現(xiàn)），語言實(shí)現(xiàn)），關(guān)鍵之處請(qǐng)給出簡要注釋。關(guān)鍵之處請(qǐng)給出簡要注釋。 datalinkB C D B C B A D A B 20091 1、若元素、若元素a a、b b、c c、d d、e e、f f依次進(jìn)棧，允許進(jìn)依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是（）退棧工作

10、，則不可能得到的出棧序列是（） A A、dcebfadcebfa B B、cbdaefcbdaef C C、bcaefdbcaefd D D、afedcbafedcb2 2、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允、某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順順序許在一端進(jìn)行出隊(duì)操作，則不可能得到的順順序是（）是（） A A、bacdebacde B B、dbacedbace C C、dbcaedbcae D D、ecbadecbad3、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（） A B C DABCDABCDABCDABCD4 4、在下列所示

11、的平衡二叉樹中插入關(guān)鍵字、在下列所示的平衡二叉樹中插入關(guān)鍵字4848后得后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字字3737所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是（）別是（） A A、1313，48 B48 B、2424，4848 C C、2424，53 D53 D、2424，909090241353375 5、在一棵度數(shù)為、在一棵度數(shù)為4 4的樹的樹T T中，若有中，若有2020個(gè)度為個(gè)度為4 4的結(jié)的結(jié)點(diǎn)，點(diǎn)，1010個(gè)度為個(gè)度為3 3的結(jié)點(diǎn)，的結(jié)點(diǎn)，1 1個(gè)度為個(gè)度為2 2的結(jié)點(diǎn)，的結(jié)點(diǎn)，1010個(gè)

12、度個(gè)度為為1 1的結(jié)點(diǎn)，則樹的結(jié)點(diǎn)，則樹T T的葉結(jié)點(diǎn)個(gè)數(shù)是（）的葉結(jié)點(diǎn)個(gè)數(shù)是（） A A、41 B41 B、82 C82 C、113 D113 D、1221226 6、對(duì)、對(duì)n n（n=2n=2）個(gè)權(quán)值均不相同的字符構(gòu)成哈弗）個(gè)權(quán)值均不相同的字符構(gòu)成哈弗曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是（）曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是（）A A、該樹一定是一棵完全二叉樹、該樹一定是一棵完全二叉樹B B、樹中一定沒有度為、樹中一定沒有度為1 1的結(jié)點(diǎn)的結(jié)點(diǎn)C C、樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D D、樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任、樹中任一非葉結(jié)點(diǎn)的權(quán)值

13、一定不小于下一層任一結(jié)點(diǎn)的權(quán)值一結(jié)點(diǎn)的權(quán)值ceadb7 7、若無向圖、若無向圖G=G=（V.EV.E）中含）中含7 7個(gè)頂點(diǎn)，則保證圖個(gè)頂點(diǎn)，則保證圖G G在在任何情況下都是連通的，則需要的邊數(shù)最少是（）任何情況下都是連通的，則需要的邊數(shù)最少是（） A A、6 B6 B、15 C15 C、16 D16 D、21218 8、對(duì)下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫?、?duì)下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是（）列的個(gè)數(shù)是（） A A、4 B4 B、3 C3 C、2 D2 D、1 19 9、已知一個(gè)長度為、已知一個(gè)長度為1616的順序表的順序表L L，其元素按關(guān)鍵字，其元素按關(guān)鍵字有序排列

14、，若采用折半查找法查找一個(gè)不存在的元有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多的是（）素，則比較次數(shù)最多的是（） A A、4 B4 B、5 C5 C、6 D6 D、7 71010、采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)、采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（）于遞歸次數(shù)的敘述中，正確的是（）A A、遞歸次數(shù)于初始數(shù)據(jù)的排列次數(shù)無關(guān)、遞歸次數(shù)于初始數(shù)據(jù)的排列次數(shù)無關(guān)B B、每次劃分后，先處理較長的分區(qū)可以減少遞歸、每次劃分后，先處理較長的分區(qū)可以減少遞歸次數(shù)次數(shù)C C、每次劃分后，先處理較短的分區(qū)可以減少遞歸、每次劃分后，先處理較短的分區(qū)可以

15、減少遞歸次數(shù)次數(shù)D D、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無、遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(guān)關(guān)1111、對(duì)一組數(shù)據(jù)、對(duì)一組數(shù)據(jù)(2(2，1212，1616，8888，5 5，10)10)進(jìn)行排進(jìn)行排序，若前三趟排序結(jié)果如下：序，若前三趟排序結(jié)果如下：()()第一趟：第一趟：2 2，1212，1616，5 5，1010，8888第二趟：第二趟：2 2，1212，5 5，1010，1616，8888第三趟：第三趟：2 2，5 5，1010，1212，1616，8888則采用的排序方法可能是則采用的排序方法可能是 A.A.冒泡排序法冒泡排序法 B.B.希爾排序法希爾排序法 C.C.歸

16、并排序法歸并排序法 D.D.基數(shù)排序法基數(shù)排序法41.41.（1010分）將關(guān)鍵字序列分）將關(guān)鍵字序列(7(7、8 8、3030、1111、1818、9 9、14)14)散列存儲(chǔ)到散列表中，散列表的存儲(chǔ)空間是一散列存儲(chǔ)到散列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從個(gè)下標(biāo)從0 0開始的一個(gè)一維數(shù)組散列開始的一個(gè)一維數(shù)組散列, ,函數(shù)為：函數(shù)為： H(keyH(key)=(key x 3)MOD T)=(key x 3)MOD T，處理沖突采用線性探測(cè)，處理沖突采用線性探測(cè)再散列法，要求裝載因子為再散列法，要求裝載因子為0.70.7問題：問題：(1).(1).請(qǐng)畫出所構(gòu)造的散列表。請(qǐng)畫出所構(gòu)造的散列表。(2).(2).分別計(jì)算等概率情況下，查找成功和查找不分別計(jì)算等概率情況下，查找成功和查找不成功的平均查找長度。成功的平均查找長度。 42.42.（1313分）設(shè)將分）設(shè)將n(nn(n1)1)個(gè)整數(shù)存放到一維數(shù)組個(gè)整數(shù)存放到一維數(shù)組R R中。設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能高效的中。設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面盡可能高效的算法。將算法。將R R中的序列循環(huán)左移中的序列循環(huán)左移P P（0Pn0Pn）個(gè)位置，）個(gè)位置，即將即將R R中的數(shù)據(jù)由中的數(shù)據(jù)由(X0, X1, (