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

1、2010年考研計(jì)算機(jī)專(zhuān)業(yè)綜合考試數(shù)據(jù)結(jié)構(gòu)試題點(diǎn)評(píng)2010年考研計(jì)算機(jī)專(zhuān)業(yè)綜合考試是統(tǒng)一命題后的第二次考試。本次考試統(tǒng)考科目仍然包括四門(mén)計(jì)算機(jī)專(zhuān)業(yè)課：數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理、操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)，這四門(mén)課程合在一起稱(chēng)為計(jì)算機(jī)科學(xué)專(zhuān)業(yè)基礎(chǔ)綜合，共150分。其中數(shù)據(jù)結(jié)構(gòu)仍然占45分?？傮w上來(lái)看，2010年的考研數(shù)據(jù)結(jié)構(gòu)試題仍然注重對(duì)基礎(chǔ)知識(shí)的考察。重點(diǎn)考察的是對(duì)基本知識(shí)點(diǎn)、基本概念的理解及應(yīng)用。題目的難度適中，沒(méi)有出現(xiàn)超出考試大綱的題目，也沒(méi)有一眼就能看出答案的題目；在基礎(chǔ)題中又有拔高，本次考試并非考查基本概念的填空，考題比較靈活，重點(diǎn)考察了對(duì)基礎(chǔ)知識(shí)的應(yīng)用能力、應(yīng)變能力和實(shí)際動(dòng)手能力。與2009

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

3、是后進(jìn)先出。若元素a、b、c、d、e、f依次進(jìn)棧，要得到出棧序列afedcb，需要進(jìn)行的操作為：a進(jìn)棧，a出棧，b，c，d，e，f分別進(jìn)棧，然后f，e，d，c，b分別依次出棧，連續(xù)出棧操作超過(guò)3次。故答案為D。2.某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是（ ）A.bacdeB.dbaceC.dbcaeD.ecbad點(diǎn)評(píng)：此題考察對(duì)可以?xún)啥巳腙?duì)，一端出隊(duì)的隊(duì)列的操作。一般教材中討論的隊(duì)列都是一端入隊(duì)，一端出隊(duì)，而本題中的隊(duì)列可以?xún)啥巳腙?duì)，一端出隊(duì)，入隊(duì)出隊(duì)操作要復(fù)雜一些，是對(duì)教材內(nèi)容的深化。對(duì)于序列dbcae，要先得到d，a，b，c必須先從一端入隊(duì)，d再?gòu)?/p>

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

5、3139037A.13，48B.24，48C.24，53D.24，90點(diǎn)評(píng)：此題考察對(duì)平衡二叉樹(shù)插入操作的理解及應(yīng)用，要熟悉平衡二叉樹(shù)調(diào)整平衡的4種旋轉(zhuǎn)方法。48插入后作為37的右孩子，此時(shí)破壞了二叉樹(shù)的平衡，需旋轉(zhuǎn)，旋轉(zhuǎn)類(lèi)型為RL型，根據(jù)RL型的操作可知答案為C。5.在一棵度為4的樹(shù)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)，則數(shù)T的葉結(jié)點(diǎn)個(gè)數(shù)是（ ）A.41B.82C.113D.122點(diǎn)評(píng)：此題考察對(duì)樹(shù)中度、結(jié)點(diǎn)、葉子結(jié)點(diǎn)個(gè)數(shù)的計(jì)算。一般教材中多是對(duì)二叉樹(shù)的討論，二叉樹(shù)性質(zhì)3有結(jié)論：n0=n2+1。而本題是一棵度為4的樹(shù)，因此需要引深。n0=n2

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

7、最少是（ ）A.6B.15C.16D.21點(diǎn)評(píng)：此題考察對(duì)圖的連通性的理解。一個(gè)有n個(gè)頂點(diǎn)的圖要連通至少需要n-1條邊。故答案是A。8.對(duì)下圖進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是（ ）edacbA.4B.3C.2D.1點(diǎn)評(píng)：此題考察對(duì)拓?fù)湫蛄械睦斫狻Ｍ負(fù)湫蛄胁晃ㄒ?。根?jù)拓?fù)湫蛄械那蠓芍祟}有3個(gè)不同的拓?fù)湫蛄?。故答案為B。9.已知一個(gè)長(zhǎng)度為16的順序表L，其元素按關(guān)鍵字有序排列，若采用折半查找法查找一個(gè)不存在的元素，則比較次數(shù)最多的是（ ）A.4B.5C.6D.7點(diǎn)評(píng)：此題考察對(duì)折半查找最壞情況下的查找長(zhǎng)度的理解。折半查找的查找過(guò)程可用一棵判定樹(shù)來(lái)表示，折半查找失敗時(shí)的過(guò)程對(duì)應(yīng)判定樹(shù)

8、中從根結(jié)點(diǎn)到某個(gè)含空指針的結(jié)點(diǎn)的路徑，因此，折半查找失敗時(shí)關(guān)鍵字的比較次數(shù)最多不超過(guò)判定樹(shù)的深度。n個(gè)結(jié)點(diǎn)的判定樹(shù)的深度和n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度相等，均為 log2n +1。故答案為B。10.采用遞歸方式對(duì)順序表進(jìn)行快速排序，下列關(guān)于遞歸次數(shù)的敘述中，正確的是（ ）A.遞歸次數(shù)與初始數(shù)據(jù)的排列次序無(wú)關(guān)B.每次劃分后，先處理較長(zhǎng)的分區(qū)可以減少遞歸次數(shù)C.每次劃分后，先處理較短的分區(qū)可以減少遞歸次數(shù)D.遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無(wú)關(guān)點(diǎn)評(píng)：此題考察對(duì)遞歸方式下的快速排序算法的理解與應(yīng)用?？焖倥判虻倪f歸的次數(shù)與初始數(shù)據(jù)的排列順序有關(guān)，遞歸次數(shù)與每次劃分后得到的分區(qū)處理順序無(wú)關(guān)。故答案為

9、D。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.起泡排序B.希爾排序C.歸并排序D.基數(shù)排序點(diǎn)評(píng)：此題考察對(duì)各種排序方法的步驟、特點(diǎn)的理解及應(yīng)用。起泡排序第i趟結(jié)束后可以把第i大的數(shù)放到正確位置。希爾排序第i趟結(jié)束后把相距為某一值的同一組中元素排好序。歸并排序第i趟結(jié)束后可以得到長(zhǎng)度為2i 的有序子序列?；鶖?shù)排序第i趟按第i位分配收集。故答案為A。二、綜合應(yīng)用題綜合應(yīng)用題主要考察綜合運(yùn)用基本知識(shí)分析問(wèn)題、解決問(wèn)題

10、的能力。41-42為數(shù)據(jù)結(jié)構(gòu)部分的題。出題風(fēng)格仍然沿用第一次的出題風(fēng)格，一道問(wèn)答題、一道算法設(shè)計(jì)題。41.（10分）將關(guān)鍵字序列（7、8、30、11、18、9、14）散列存儲(chǔ)到散列表中，散列表的存儲(chǔ)空間是一個(gè)下標(biāo)從0開(kāi)始的一維數(shù)組，散列函數(shù)：H(key)=(key3) MOD T，處理沖突采用線性探測(cè)再散列法，要求裝填（載）因子為0.7。問(wèn)題：（1）請(qǐng)畫(huà)出所構(gòu)造的散列表；（2）分別計(jì)算等概率情況下查找成功和查找不成功的平均查找長(zhǎng)度。點(diǎn)評(píng)：此題考察對(duì)散列表相關(guān)知識(shí)的理解及應(yīng)用，要求能夠構(gòu)造散列表，并且能夠計(jì)算等概率情況下查找成功和查找不成功的平均查找長(zhǎng)度。（1）本題中涉及到裝填（載）因子，在散列

11、函數(shù)中還有一個(gè)未知數(shù)T（可認(rèn)為是散列表的長(zhǎng)度）。因此需先求出T。=數(shù)據(jù)個(gè)數(shù)/表長(zhǎng)，由裝載因子0.7，數(shù)據(jù)總數(shù)7個(gè)可知存儲(chǔ)空間長(zhǎng)度為10即T =10。所以，散列函數(shù)為H(key)=(key3) MOD 10，線性探測(cè)再散列函數(shù)為：Hi=( H(key)+di) MOD 10，(di=1,2,3,9)因此，各數(shù)據(jù)的下標(biāo)為：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構(gòu)造的散列表為：地址0123456789關(guān)鍵字30714118189（2）在等概率情況下，手工計(jì)算查找成功時(shí)的平均查找長(zhǎng)度可用下列公式計(jì)算： ASLsucc=其中，ci為查找第i個(gè)元素所需的比較次數(shù)，即裝入第i個(gè)元素時(shí)所需的比較次數(shù)。處理沖突用線性探測(cè)再散列法，得到其哈希表及各關(guān)鍵字的比較次數(shù)如下圖所示地址0123456789關(guān)鍵字30714118189比較次數(shù)1111211按照上述公式，在等概率情況下，查找成功時(shí)的平均查找長(zhǎng)度為：查找成功的ASL=（1+1+1+1+2+1+1）/7=8/7在等概率情況下，查找不成功時(shí)的平均查找長(zhǎng)度是指在表中查找不到待查

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

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

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