計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)今年考研真題及答案

1、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的容量至少是A1B.2C.3D.43.給定二叉樹圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點(diǎn)的左

2、子樹，R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為3，1，7，5，6，2，4，則其遍歷方式是ALRNB.NRLC.RLND.RNL4.下列二叉排序樹中，滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)最多是A39B.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

3、.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

4、，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是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是A起泡排序B.插入排序C.選擇排

5、序D.二路歸并排序（）A：13，48B：24，48C：24，53D：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：41B：82C：113D：1226、對(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：樹中任

6、一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一任一結(jié)點(diǎn)的權(quán)值7、若無向圖G（V.E）中含7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（）A：6B：15C：16D：218、對(duì)下圖進(jìn)行拓補(bǔ)排序，可以得到不同的拓補(bǔ)序列的個(gè)數(shù)是（）abcdeA：4B：3C：2D：19、已知一個(gè)長(zhǎng)度為16的順序表L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多是（）A：4B：5C：6D：710、采用遞歸方式對(duì)順序表進(jìn)行快速排序，

7、下列關(guān)于遞歸次數(shù)的敘述中，正確的是（）A：遞歸次數(shù)與初始數(shù)據(jù)的排列次序無關(guān)B：每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)C：每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D：遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無關(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