2009考研數(shù)據(jù)結(jié)構(gòu)試題點(diǎn)評

1、2009 年考研計算機(jī)專業(yè)綜合考試數(shù)據(jù)結(jié)構(gòu)試題點(diǎn)評2009 年考研計算機(jī)專業(yè)綜合考試是統(tǒng)一命題后的首次考試。本次考試統(tǒng)考科目包括四門計算機(jī)專業(yè)課：數(shù)據(jù)結(jié)構(gòu)、計算機(jī)組成原理、操作系統(tǒng)和計算機(jī)網(wǎng)絡(luò)，這四門課程合在一起稱為計算機(jī)科學(xué)專業(yè)基礎(chǔ)綜合，共150 分。其中數(shù)據(jù)結(jié)構(gòu)占45 分?？傮w上來看，2009 年的考研數(shù)據(jù)結(jié)構(gòu)試題注重對基礎(chǔ)知識的考察。重點(diǎn)考察的是對基本知識點(diǎn)、基本概念的理解。在基礎(chǔ)題中又有拔高，重點(diǎn)考察了對基礎(chǔ)知識的應(yīng)用能力、應(yīng)變能力和實(shí)際動手能力。題目總的來說不難，沒有出現(xiàn)超出考試大綱的題目。下面我們對2009 的考研數(shù)據(jù)結(jié)構(gòu)試題進(jìn)行簡要的點(diǎn)評。一、單項(xiàng)選擇題，每小題2分，共 80分。

2、單選題覆蓋了大綱列出的各章的知識點(diǎn)，主要考察對各種數(shù)據(jù)結(jié)構(gòu)、基本查找和排序算法的基本概念和特點(diǎn)的理解以及靈活運(yùn)用。1-10 題是數(shù)據(jù)結(jié)構(gòu)部分的試題。1. 為解決計算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是A.棧B.隊(duì)列C.樹D.圖點(diǎn)評：此題考察對各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)的理解及應(yīng)用。棧的特點(diǎn)是后進(jìn)先出。隊(duì)列的特點(diǎn)是先進(jìn)先出。樹的特點(diǎn)是除根以外的結(jié)點(diǎn)有且只有唯一的前驅(qū)（雙親）。圖是最復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，它的任一結(jié)點(diǎn)都可以有多個前驅(qū)和后繼。據(jù)題意“輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該

3、緩沖區(qū)中取出數(shù)據(jù)”，處理應(yīng)是先來先服務(wù)，因此答案為B。2. 設(shè)棧 S和隊(duì)列 Q的初始狀態(tài)均為空， 元素 abcdefg 依次進(jìn)入棧 S。若每個元素出棧后立即進(jìn)入隊(duì)列 Q，且 7個元素出隊(duì)的順序是 bdcfeag ，則棧 S的容量至少是A 1 B.2 C.3 D.4點(diǎn)評：此題考察對棧和隊(duì)列的特點(diǎn)及基本操作的應(yīng)用。根據(jù)元素的出隊(duì)順序可知元素的進(jìn)棧、出棧順序，從而判斷棧中同時容納多少元素，得出棧的容量。因bdcfeag依次出隊(duì)，故元素的出棧順序也是這樣的，那么他們在棧中操作順序依次為：a 入棧、 b 入棧、 b 出棧、c 入棧、d 入棧、d 出棧、 c出棧、e 入棧、 f入棧、 f出棧、e 出棧、

4、a 出棧、 g入棧、g 出棧。這其間棧中數(shù)據(jù)最多有3 個。因此答案為C。3. 給定二叉樹如圖所示。設(shè) N代表二叉樹的根， L代表根結(jié)點(diǎn)的左子樹， R代表根結(jié)點(diǎn)的右子樹。若遍歷后的結(jié)點(diǎn)序列為 3， 7， 5， 6， 1,2 ， 4，則其遍歷方式是A LRN B.NRL C.RLN D.RNL點(diǎn)評：此題考察對二叉樹的六種遍歷的理解及應(yīng)用。二叉樹有六種遍歷方式：先序遍歷、中序遍歷、 后序遍歷。每種遍歷訪問根結(jié)點(diǎn)的順序不一樣。先序遍歷先訪問根，中序遍歷中間訪問根， 后序遍歷最后訪問根。一般教材中都是先左子樹，后右子樹，但該題用另一種方式，先右子樹，后左子樹。從遍歷得到的序列中第一個遍歷出來的元素是3，

5、可知是中序遍歷，因此答案是D。4. 下列二叉排序樹中，滿足平衡二叉樹定義的是AB.C.D.點(diǎn)評：此題考察對平衡二叉樹的定義的掌握，平衡二叉樹又稱AVL樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對值不超過1。因此答案為B。5. 已知一棵完全二叉樹的第 6層（設(shè)根為第 1層）有 8個葉結(jié)點(diǎn)，則完全二叉樹的結(jié)點(diǎn)個數(shù)最多是A 39 B.52 C.111 D.119點(diǎn)評：此題考察對完全二叉樹的定義的理解及對二叉樹每層最大結(jié)點(diǎn)個數(shù)的計算。完全二叉樹第一層到倒數(shù)第二層結(jié)點(diǎn)個數(shù)均達(dá)到每層的最大值，2i-1 (i為層數(shù) ) ，第 6 層有

6、8 個葉結(jié)點(diǎn)，說明這棵完全二叉樹最多7 層，第 6 層的 32 個結(jié)點(diǎn)有24（ 32-8 ）結(jié)點(diǎn)有孩子結(jié)點(diǎn)，孩子結(jié)點(diǎn)最多有48 個（ 24*2 ） , 所以完全二叉樹的結(jié)點(diǎn)數(shù)最多為：1+2+4+8+16+32+48=111。故答案為C。6. 將森林轉(zhuǎn)換為對應(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和III點(diǎn)評：此題考察森林轉(zhuǎn)化為二叉樹時結(jié)點(diǎn)之間的關(guān)系的變化。根據(jù)森林轉(zhuǎn)化為二叉樹的轉(zhuǎn)化過程可知， 一個結(jié)點(diǎn)和

7、它的第二個孩子結(jié)點(diǎn)轉(zhuǎn)化為二叉樹后就變?yōu)榻Y(jié)點(diǎn)u 是結(jié)點(diǎn)v的父結(jié)點(diǎn)的父結(jié)點(diǎn)， 同一個結(jié)點(diǎn)的第一個孩子u 和第三個孩子v 轉(zhuǎn)化為二叉樹后也變?yōu)榻Y(jié)點(diǎn)u 是結(jié)點(diǎn)v 的父結(jié)點(diǎn)的父結(jié)點(diǎn)，因此可以推出u 和v 在原來的森林中要么是父子關(guān)系，要么是兄弟關(guān)系。因此答案是B。7. 下列關(guān)于無向連通圖特性的敘述中，正確的是I 所有頂點(diǎn)的度之和為偶數(shù)II.邊數(shù)大于頂點(diǎn)個數(shù)減1III. 至少有一個頂點(diǎn)的度為 1A. 只有 IB.只有 IIC.I和 IID.I和 III點(diǎn)評：此題考察圖的度與邊的關(guān)系、無向連通圖特性。在圖中所有頂點(diǎn)的度之和為邊數(shù)的2倍，而連通圖中邊數(shù)不為零，所以一定是偶數(shù)。N個頂點(diǎn)的無向連通圖至少有n-1

8、條邊，頂點(diǎn)的度至少是1。因此答案為A。8. 下列敘述中，不符合 m階 B樹定義要求的是A根節(jié)點(diǎn)最多有m棵子樹B.C各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D.點(diǎn)評： 此題考察對m階 B 樹的定義的理解與應(yīng)用。所有葉結(jié)點(diǎn)都在同一層上葉結(jié)點(diǎn)之間通過指針鏈接B 樹是一種多叉平衡查找樹。一棵m階的B 樹，或?yàn)榭諛?，或?yàn)闈M足下列特性的m叉樹：樹中每個結(jié)點(diǎn)至多有m棵子樹；若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則它至少有兩棵子樹；除根之外的所有非葉子結(jié)點(diǎn)至少有m/2 棵子樹；所有的非葉子結(jié)點(diǎn)中包含下列數(shù)據(jù)信息(n ， A0， K1， A1， K2， A2，, ，Kn， An)其中： Ki (i=1，2，, ，n) 為關(guān)鍵字，且Ki

9、<Ki+1 (i=1，2，, ，n-1)：Ai (i=0，1，, ，n) 為指向子樹根結(jié)點(diǎn)的指針，且Ai-1所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki (i=1，2，, ，n) ， An 所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均大于Kn，n（ m/2-1 n m-1）為關(guān)鍵字的個數(shù)（或n+1 為子樹個數(shù)）所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息( 可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空) 。據(jù)此定義可知答案為D。9. 已知關(guān)鍵序列 5， 8， 12， 19， 28，20， 15， 22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后得到的小根堆是A 3， 5， 12

10、， 8， 28， 20， 15， 22， 19B. 3 ， 5， 12，19， 20，15， 22，8， 28 C 3， 8， 12， 5， 20， 15， 22， 28， 19D. 3 ， 12， 5，8， 28， 20， 15，22， 19點(diǎn)評： 此題考察對堆調(diào)整算法- “篩選”算法的應(yīng)用。篩選算法要求根的左右子樹必須是堆。把 3 插入后，關(guān)鍵序列變?yōu)?5， 8， 12，19，28， 20， 15， 22，3，以 5 為根的左右子樹的堆結(jié)構(gòu)可能被破壞， 因此必須重建堆， 從 n/2 個結(jié)點(diǎn)開始調(diào)用篩選算法， 直到第一個結(jié)點(diǎn)，就可重建堆。答案為 A。10. 若數(shù)據(jù)元素序列 11，12，13，

11、7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的結(jié)果，則該排序算法只能是A 起泡排序B. 插入排序C.選擇排序D. 二路歸并排序點(diǎn)評：此題考察對各種排序方法的步驟、特點(diǎn)的理解及應(yīng)用。起泡排序第i 趟結(jié)束后可以把第 i 大的數(shù)放到正確位置。插入排序第i 趟結(jié)束后前i 個元素是有序的， 但不一定是這些元素的最后位置。選擇排序第i 趟結(jié)束后可以把第i 小的數(shù)放到正確位置。二路歸并排序第 i 趟結(jié)束后可以得到長度為2i的有序子序列。故答案為B。二、綜合應(yīng)用題綜合應(yīng)用題主要考察綜合運(yùn)用基本知識分析問題、解決問題的能力。41-42 為數(shù)據(jù)結(jié)構(gòu)部分的題。 一道問答題、一道算法設(shè)計題。41.

12、 （ 10 分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩頂點(diǎn)間的距離）的最短路徑問題是找出從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假定從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解決該問題的方法：設(shè)最短路徑初始時僅包含初始頂點(diǎn)，令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；選擇離 u最近且尚未在最短路徑中的一個頂點(diǎn)v，加入到最短路徑中，修改當(dāng)前頂點(diǎn)u=v；重復(fù)步驟，直到u是目標(biāo)頂點(diǎn)時為止。請問上述方法能否求得最短路徑？若該方法可行，請證明之；否則，請舉例說明。點(diǎn)評：此題考察對最短路徑的理解及應(yīng)用。最短路徑就是從初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的路徑上權(quán)值和最小的路徑。題目中的方法在選擇頂點(diǎn)時并沒有找到下一條權(quán)值最下的邊，所以該方法求得

13、的路徑不一定是最短路徑。例如，對于下圖所示的帶權(quán)圖，如果按照題中的原則，從 A 到 C 的最短路徑為AB C，事實(shí)上其最短路徑為A D C。42. （ 15分）已知一個帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為 data link假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點(diǎn)（k為正整數(shù)）。若查找成功，算法輸出該結(jié)點(diǎn)的data值，并返回 1；否則，只返回0。要求：（ 1） 描述算法的基本設(shè)計思想（ 2） 描述算法的詳細(xì)實(shí)現(xiàn)步驟（ 3） 根據(jù)設(shè)計思想和實(shí)現(xiàn)步驟， 采用程序設(shè)計語言描述算法 （使用 C或 C+或 JAVA語言實(shí)現(xiàn)），關(guān)鍵之

14、處請給出簡要注釋。點(diǎn)評： 此題是一道算法設(shè)計題，算法設(shè)計是數(shù)據(jù)結(jié)構(gòu)課程的一個重點(diǎn)內(nèi)容，也是一個難點(diǎn)。此題考察對單鏈表的基本運(yùn)算的理解及靈活運(yùn)用。一般教材中在單鏈表中查找結(jié)點(diǎn)都是從頭數(shù)第i 個結(jié)點(diǎn)， 而本題中要倒數(shù)第k 個結(jié)點(diǎn)， 難度就大了， 要把單鏈表的基本運(yùn)算進(jìn)行改寫，關(guān)鍵在于要查倒數(shù)第K個位置上的結(jié)點(diǎn)，此時需要兩個流動指針，一個整型變量，從鏈表頭向后遍歷，其中指針P1 指向當(dāng)前遍歷的結(jié)點(diǎn)，指針P 指向 P1 所指向結(jié)點(diǎn)的前K個結(jié)點(diǎn)，如果P1 之前沒有K 個結(jié)點(diǎn)，那么P 指向表頭結(jié)點(diǎn)。用整型變量i 表示當(dāng)前遍歷了多少結(jié)點(diǎn)，當(dāng)i>k 時，指針 P 隨著每次遍歷，也向前移動一個結(jié)點(diǎn)。當(dāng)遍歷完成時，P 或者指向表頭就結(jié)點(diǎn)，或者指向鏈表中倒數(shù)第k