1、2010年考研計算機專業綜合考試數據結構試題點評2010年考研計算機專業綜合考試是統一命題后的第二次考試。本次考試統考科目仍然包括四門計算機專業課：數據結構、計算機組成原理、操作系統和計算機網絡，這四門課程合在一起稱為計算機科學專業基礎綜合，共150分。其中數據結構仍然占45分。總體上來看，2010年的考研數據結構試題仍然注重對基礎知識的考察。重點考察的是對基本知識點、基本概念的理解及應用。題目的難度適中，沒有出現超出考試大綱的題目，也沒有一眼就能看出答案的題目；在基礎題中又有拔高，本次考試并非考查基本概念的填空，考題比較靈活，重點考察了對基礎知識的應用能力、應變能力和實際動手能力。與2009

2、年的考研數據結構試題相比，難度略有提高，考察的內容更加深入、靈活，并且有針對性。下面我們對2010的考研計算機專業綜合考試進行簡要的分析。一、單項選擇題這部分共有40個選擇題，每題2分，共80分。單選題覆蓋了大綱列出的各章的知識點，主要考察對各種數據結構、基本查找和排序算法的基本概念和特點的理解以及靈活運用。1-11題是數據結構部分的試題。1.若元素a、b、c、d、e、f依次進棧，允許進棧、退棧操作交替進行。但不允許連續三次進行退棧工作，則不可能得到的出棧序列是（ ）A.dcebfaB.cbdaefC.bcaefdD.afedcb點評：此題考察對棧的基本操作（進棧、退棧）的理解和應用。棧的特點

3、是后進先出。若元素a、b、c、d、e、f依次進棧，要得到出棧序列afedcb，需要進行的操作為：a進棧，a出棧，b，c，d，e，f分別進棧，然后f，e，d，c，b分別依次出棧，連續出棧操作超過3次。故答案為D。2.某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順序是（ ）A.bacdeB.dbaceC.dbcaeD.ecbad點評：此題考察對可以兩端入隊，一端出隊的隊列的操作。一般教材中討論的隊列都是一端入隊，一端出隊，而本題中的隊列可以兩端入隊，一端出隊，入隊出隊操作要復雜一些，是對教材內容的深化。對于序列dbcae，要先得到d，a，b，c必須先從一端入隊，d再從

4、另一端入隊，d出隊得到序列中的d，但隊列是先進先出，下面要得到b，而b是在a之后進隊的，只有a先出隊，b才能出隊，故得不到所要求的序列。所以答案為C。3.下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（ ）NullacbdNullacbdNullacbdNullacbdNullABCD點評：此題考察對后序線索樹的定義的理解。先得到后序序列為dbca，然后在后序線索樹中將空的左孩子域指向其后序前驅，空的右孩子域指向其后序后繼，因此答案為D。4.在下列所示的平衡二叉樹中插入關鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關鍵字37所在結點的左、右子結點保存的關鍵字分別是（ ）245

5、3139037A.13，48B.24，48C.24，53D.24，90點評：此題考察對平衡二叉樹插入操作的理解及應用，要熟悉平衡二叉樹調整平衡的4種旋轉方法。48插入后作為37的右孩子，此時破壞了二叉樹的平衡，需旋轉，旋轉類型為RL型，根據RL型的操作可知答案為C。5.在一棵度為4的樹T中，若有20個度為4的結點，10個度為3的結點，1個度為2的結點，10個度為1的結點，則數T的葉結點個數是（ ）A.41B.82C.113D.122點評：此題考察對樹中度、結點、葉子結點個數的計算。一般教材中多是對二叉樹的討論，二叉樹性質3有結論：n0=n2+1。而本題是一棵度為4的樹，因此需要引深。n0=n2

6、+2*n3+3*n4+1=1+2*10+3*20+1=82。故答案為B。6.對n(n2)個權值均不相同的字符構成哈夫曼樹，關于該樹的敘述中，錯誤的是（ ）A.該樹一定是一棵完全二叉樹B.樹中一定沒有度為1的結點C.樹中兩個權值最小的結點一定是兄弟結點D.樹中任一非葉結點的權值一定不小于下一層任一結點的權值點評：此題考察對哈夫曼樹的特性的理解。根據哈夫曼算法哈夫曼樹中沒有度為1的結點，兩個權值最小的結點一定是兄弟結點，任一非葉結點的權值一定不小于下一層任一結點的權值，但哈夫曼樹不是一棵完全二叉樹。因此答案是A。7.若無向圖G=(V，E)中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數

7、最少是（ ）A.6B.15C.16D.21點評：此題考察對圖的連通性的理解。一個有n個頂點的圖要連通至少需要n-1條邊。故答案是A。8.對下圖進行拓撲排序，可以得到不同的拓撲序列的個數是（ ）edacbA.4B.3C.2D.1點評：此題考察對拓撲序列的理解。拓撲序列不唯一。根據拓撲序列的求法可知此題有3個不同的拓撲序列。故答案為B。9.已知一個長度為16的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個不存在的元素，則比較次數最多的是（ ）A.4B.5C.6D.7點評：此題考察對折半查找最壞情況下的查找長度的理解。折半查找的查找過程可用一棵判定樹來表示，折半查找失敗時的過程對應判定樹

8、中從根結點到某個含空指針的結點的路徑，因此，折半查找失敗時關鍵字的比較次數最多不超過判定樹的深度。n個結點的判定樹的深度和n個結點的完全二叉樹的深度相等，均為 log2n +1。故答案為B。10.采用遞歸方式對順序表進行快速排序，下列關于遞歸次數的敘述中，正確的是（ ）A.遞歸次數與初始數據的排列次序無關B.每次劃分后，先處理較長的分區可以減少遞歸次數C.每次劃分后，先處理較短的分區可以減少遞歸次數D.遞歸次數與每次劃分后得到的分區處理順序無關點評：此題考察對遞歸方式下的快速排序算法的理解與應用。快速排序的遞歸的次數與初始數據的排列順序有關，遞歸次數與每次劃分后得到的分區處理順序無關。故答案為

9、D。11.對一組數據（2，12，16，88，5，10）進行排序，若前三趟排序結果如下：（ ）第一趟：2，12，16，5，10，88第二趟：2，12，5，10，16，88第三趟：2，5，10，12，16，88則采用的排序方法可能是A.起泡排序B.希爾排序C.歸并排序D.基數排序點評：此題考察對各種排序方法的步驟、特點的理解及應用。起泡排序第i趟結束后可以把第i大的數放到正確位置。希爾排序第i趟結束后把相距為某一值的同一組中元素排好序。歸并排序第i趟結束后可以得到長度為2i 的有序子序列。基數排序第i趟按第i位分配收集。故答案為A。二、綜合應用題綜合應用題主要考察綜合運用基本知識分析問題、解決問題

10、的能力。41-42為數據結構部分的題。出題風格仍然沿用第一次的出題風格，一道問答題、一道算法設計題。41.（10分）將關鍵字序列（7、8、30、11、18、9、14）散列存儲到散列表中，散列表的存儲空間是一個下標從0開始的一維數組，散列函數：H(key)=(key3) MOD T，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7。問題：（1）請畫出所構造的散列表；（2）分別計算等概率情況下查找成功和查找不成功的平均查找長度。點評：此題考察對散列表相關知識的理解及應用，要求能夠構造散列表，并且能夠計算等概率情況下查找成功和查找不成功的平均查找長度。（1）本題中涉及到裝填（載）因子，在散列

11、函數中還有一個未知數T（可認為是散列表的長度）。因此需先求出T。=數據個數/表長，由裝載因子0.7，數據總數7個可知存儲空間長度為10即T =10。所以，散列函數為H(key)=(key3) MOD 10，線性探測再散列函數為：Hi=( H(key)+di) MOD 10，(di=1,2,3,9)因此，各數據的下標為：H(7)=（7*3）MOD 10=1 H(8)=（8*3）MOD 10=4 H(30)=（30*3）MOD 10=0H(11)=（11*3）MOD 10=3 H(18)=（18*3）MOD 10=4 H1=(H(18)+1) MOD 10=5H(9)=（9*3）MOD 10=7

12、H(14)=（14*3）MOD 10=2構造的散列表為：地址0123456789關鍵字30714118189（2）在等概率情況下，手工計算查找成功時的平均查找長度可用下列公式計算： ASLsucc=其中，ci為查找第i個元素所需的比較次數，即裝入第i個元素時所需的比較次數。處理沖突用線性探測再散列法，得到其哈希表及各關鍵字的比較次數如下圖所示地址0123456789關鍵字30714118189比較次數1111211按照上述公式，在等概率情況下，查找成功時的平均查找長度為：查找成功的ASL=（1+1+1+1+2+1+1）/7=8/7在等概率情況下，查找不成功時的平均查找長度是指在表中查找不到待查

13、記錄，但找到插入位置的平均探測次數，它是表中所有可能散列的位置上要插入新記錄時為找到空位置的探測次數的平均值。在等概率情況下，手工計算查找不成功時的平均查找長度可用下列公式計算：ASLunsucc=其中，ci為哈希函數取值為i時查找不成功的比較次數。查找不成功的情況：（1）遇到空單元（2）按處理沖突的方法完全探測一遍后仍未找到。0到r-1相當于r個不成功查找的入口，從每個入口進入后，直到確定查找不成功為止，其關鍵字比較次數就是與該入口對應的不成功查找長度。在本題中，在線性探測再散列法處理沖突得到的哈希表中查找，假設待查的關鍵字k不在該表中，若H(k)=0，將HT0中的關鍵字和k比較后發現HT0

14、為空，即查找不成功，比較次數為1；若H(k)=1，則必須將HT0.5 中的關鍵字和k比較后，再與HT6中的關鍵字比較時發現HT6為空，查找失敗，比較次數為7，同理，位置2，3，5，6的比較次數分別為6，5，2，1次，位置7，8，9的比較次數分別為2，1，1，因此，在等概率情況下，查找不成功時的平均查找長度為查找不成功的ASL=（7+6+5+4+3+2+1+2+1+1）/10=3.242.（13分）設將n（n1）個整數存放到一維數組R中。試設計一個在時間和空間兩方面都盡可能高效的算法，將R中保存的序列循環左移p（0pn）個位置，即將R中的數據由（x0,x1,xn-1）變換為(xp,xp+1,xn

15、-1,x0,x1,xp-1)。要求：（1）給出算法的基本設計思想。（2）根據設計思想，采用C或C+或JAVA語言描述算法，關鍵之處給出注釋。（3）說明設計算法的時間復雜度和空間復雜度。點評：此題是一道算法設計題，算法設計是數據結構課程的一個重點內容，也是一個難點。此題考察對順序表的基本運算的理解及靈活運用、時間復雜度和空間復雜度的概念及應用。要求時間和空間兩方面都盡量最優的情況下，實現數組的循環左移，還要求算法的時間、空間的復雜度。具體要求給出算法思想，并且能用C、C+、Java描述該算法。思想可以描述為：建立一個可以存放P個整數的輔助隊列，將數組R中的前p個整數依次進隊；將R中后面的n-p個整數依次前移p個位置，然后將輔助隊列中的p個數依次出隊，依次放入數組末尾即第n-p開始的位置即可。 算法描述：void shift(int *pr,int n,int p) /pr是指向數組R的指針，n為存放的整數個數，/p為循環左移的個數 int tempp;/輔助數組，存放要移出的整數int i=0;while (ip)/將R中前p個數據存入輔助數組中t