1、 北京航空航天大學(xué)2012年碩士研究生入學(xué)考試試題 “數(shù)據(jù)結(jié)構(gòu)與C語(yǔ)言程序設(shè)計(jì)”（科目代碼：991）參考答案一、填空(本題共20分，每小題各2分) 1從總體上說(shuō)，“數(shù)據(jù)結(jié)構(gòu)”課程主要研究數(shù)據(jù)的 邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法 三個(gè)方面的內(nèi)容。 2若對(duì)某線性表最常用的操作是在表中插入元素或者刪除表中元素，則對(duì)于順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)這兩種存儲(chǔ)結(jié)構(gòu)而言，線性表應(yīng)該采用 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。3在長(zhǎng)度為n的非空隊(duì)列中進(jìn)行插瓤入或者刪除操作的時(shí)間復(fù)雜度用大瓤O符號(hào)表示為 O(1) 。4丘若一棵度為4的樹(shù)中度為1、2丘、3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4、2丘、1和1，則該樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)丘為 8 。5若某二叉樹(shù)的中巨序

2、遍歷序列為B,A,F,D,G巨,C,E，按層次遍歷序列為A,巨B,C,D,E,F,G，則該二鉸叉樹(shù)的后序遍歷序列為B,F,鉸G,D,E,C,A。6將狄一棵結(jié)點(diǎn)總數(shù)為n、且具有m個(gè)葉狄結(jié)點(diǎn)的樹(shù)轉(zhuǎn)換為一棵二叉樹(shù)以后，狄該二叉樹(shù)中右子樹(shù)為空的結(jié)點(diǎn)有狄n-m+1個(gè)。7對(duì)于圖G澆=(V,E) 與 G=(V澆,E)，若V包含于V，E桿包含于E，則稱(chēng)G是G的一個(gè)桿子圖。8在順序表(6,1沖5,30,37,65,68,7沖0,72,89,99)中采用折沖半查找法查找元素37，與表中進(jìn)沖行過(guò)比較的元素依次是65,1沖5,30,37。9若已知抖n個(gè)關(guān)鍵字值具有相同的散列函數(shù)抖值，并且采用線性探測(cè)再散列法處抖理沖突

3、，那么，將這n個(gè)關(guān)鍵字值抖全部散列到初始為空的地址空間中抖，發(fā)生散列沖突的次數(shù)是 n*(抖n-1)/2。10若長(zhǎng)度般為n的序列K=(k1,k2,般,kn)當(dāng)且僅當(dāng)滿(mǎn)足kik2般i并且kik2i+1(1i汞n/2)時(shí)，則稱(chēng)該序列為一個(gè)汞小頂堆積(Heap)。根據(jù)該定汞義，序列(26,5,77,1,汞61,11,59,48,15,汞19)對(duì)應(yīng)的小頂堆積是1,5汞,11,15,19,77,59汞,48,26,61。二、簡(jiǎn)答閡題(本題共20分，每小題各5分閡)1答：該鄰接矩陣是稀疏矩閡陣。因?yàn)猷徑泳仃囍幸还灿?00閡00個(gè)元素，只有200個(gè)非零元閡素，非零元素的數(shù)目只占整個(gè)稀疏閡矩陣元素總個(gè)數(shù)的2%，

4、按照題目閡假設(shè)，可以認(rèn)為該鄰接矩陣是稀疏閡矩陣。2答：該方法的基本思冷想是當(dāng)發(fā)生散列沖突時(shí)按照下列方冷法求得后繼散列地址：Di=H(妮k)+di) MOD m i=妮1,2,n (nm-1)妮其中，H(k)為散列函數(shù)，k銻為關(guān)鍵字，m為散列表長(zhǎng)，di為添地址增量序列，可以有以下三種取添法：（1）di=1,2,3,添,m-1 稱(chēng)為線性探測(cè)再散列；添（2）di=12,-12體,22,-22,n體2（nm/2）稱(chēng)為二次探測(cè)再體散列；（3）di=偽隨機(jī)數(shù)序漫列，稱(chēng)為偽隨機(jī)探測(cè)再散列。3農(nóng)答：該結(jié)果是采用了起泡排序法農(nóng)排序得到的。若選擇排序法每一趟農(nóng)排序選擇一個(gè)最大值元素，該最大農(nóng)值元素只需要與當(dāng)前參加

5、排序的最農(nóng)后那個(gè)元素交換位置，而不需要改農(nóng)變其他元素的位置，顯然，從上述農(nóng)結(jié)果可以看出不是如此。上述結(jié)果農(nóng)符合起泡排序的規(guī)律。4答：檸最小遞歸深度為log2n+1，檸最大遞歸深度n。三、綜合題(本李題共20分，每小題各5分)1棉第條語(yǔ)句有錯(cuò)，正確的語(yǔ)句是楞p-rlink-llink楞=p;2解：若完全二叉樹(shù)的投第7層有10個(gè)葉結(jié)點(diǎn)，則有兩種投情況： 10個(gè)葉結(jié)點(diǎn)集中在聶第7層的最左邊，此時(shí)可求出該二聶叉樹(shù)的結(jié)點(diǎn)總數(shù)為(26-1)聶+10=73。 該完全二叉眠樹(shù)的深度為8，10個(gè)葉結(jié)點(diǎn)集中眠在第7層的最右邊，此時(shí)，可求出確該二叉樹(shù)的結(jié)點(diǎn)總數(shù)為(26-確1)+27-1+108=23確5。因此，根據(jù)

6、題意，該完全二慫叉樹(shù)最多有235個(gè)結(jié)點(diǎn)。3亮證明：設(shè)無(wú)向圖的邊數(shù)為e，頂點(diǎn)亮vi的度為T(mén)D(vi)，根據(jù)圖亮的性質(zhì)，有關(guān)系2e=TD(v酗i) （1in）由于每一余個(gè)頂點(diǎn)最多與圖中其他n-1個(gè)頂余點(diǎn)直接有關(guān)，即圖中每一個(gè)頂點(diǎn)的余度的最大值為n-1，因此，圖中余n個(gè)頂點(diǎn)的度的最大值之和為n(瑤n-1)，即2e=TD(vi增)=n(n-1) （1in增）于是，有 e=n(n-1)意/2 證畢 4解：（注:每怎一趟選擇最大者放前面） （注:怎每一趟選擇最小者放后面）原茵始：80,30,50,10,9茵0,20 原 始：80,30,茵50,10,90,20第1趟侄：90,30,50,10,80侄,20

7、 第1趟：80,30,5侄0,20,90,10第2趟：在90,80,50,10,30,在20 第2趟：80,30,50在,90,20,10第3趟：9貞0,80,50,10,30,2貞0 第3趟：80,90,50,貞30,20,10第4趟：90酗,80,50,30,10,20酗第4趟：80,90,50,3酗0,20,10第5趟：90,釜80,50,30,20,10菌第5趟：90,80,50,30菌,20,10四、算法設(shè)計(jì)題（本構(gòu)題15分）int TOPOTE檔ST(TOPOVLink G檔,vertype V,i檔nt n) Elink *p膏; int i,k;for(傀f臼臼if(Gk.ve

8、rte龔x=Vi) /* 若頂龔點(diǎn)Vi是G中的頂點(diǎn) */避if(Gk.indegre避e!=0) /* 若頂點(diǎn)Vi避的入度不為0 */retu澆rn 0; /* 序列不是該有澆向圖的拓?fù)湫蛄?*/p=G策k.link; /* 若頂點(diǎn)策Vi的入度為0 */wh橫ile(p!=NULL)G狄p-adjvex.ind狄egree-; /* 相關(guān)頂渾點(diǎn)的入度減1 */p=p-摧next; /* p指向下一個(gè)摧邊結(jié)點(diǎn) */ break;漸/* 測(cè)試序列的下一個(gè)頂點(diǎn)漸*/ return雇1; /* 序列是該有向圖的雇拓?fù)湫蛄?*/五、單項(xiàng)選擇題款（本題共20分，每小題各2分）款1C 2D 3A 4豁C 5

9、B 6D 7A 8豁D 9B 10A六、簡(jiǎn)答屯題（本題共20分，每小題各5分屯）1答： 通過(guò)頭文件來(lái)調(diào)鳥(niǎo)用庫(kù)功能。在很多場(chǎng)合，源代碼不鳥(niǎo)便(或不準(zhǔn))向用戶(hù)公布，只向用鳥(niǎo)戶(hù)提供頭文件和二進(jìn)制的庫(kù)即可。鳥(niǎo)用戶(hù)只需要按照頭文件中的接口聲?shū)B(niǎo)明來(lái)調(diào)用庫(kù)功能，而不必關(guān)心接口離怎么實(shí)現(xiàn)的。編譯器會(huì)從庫(kù)中提取離相應(yīng)的代碼。 頭文件能加強(qiáng)詳類(lèi)型安全檢查。如果某個(gè)接口被實(shí)詳現(xiàn)或被使用時(shí)，其方式與頭文件中詳?shù)穆暶鞑灰恢拢幾g器就會(huì)指出錯(cuò)詳誤，這一簡(jiǎn)單的規(guī)則能大大減輕程詳序員調(diào)試、改錯(cuò)的負(fù)擔(dān)。2答襄：#include “file襄name.h”表明該文件是用戶(hù)襄提供的頭文件，查找該文件時(shí)從當(dāng)襄前文件目錄開(kāi)始；#inc

10、lud襄傘明這個(gè)文件是一個(gè)工程或者標(biāo)準(zhǔn)頭傘文件，查找過(guò)程會(huì)檢查預(yù)定義的目傘錄。3答： 生命周期不同胚： 全局變量隨主程序創(chuàng)建和孽創(chuàng)建，隨主程序銷(xiāo)毀而銷(xiāo)毀； 市局部變量在局部函數(shù)內(nèi)部，甚至市局部循環(huán)體等內(nèi)部存在，退出就不市存在； 內(nèi)存中分配在全局?jǐn)?shù)據(jù)區(qū)市。 使用方式不同： 通欺過(guò)聲明后全局變量程序的各個(gè)部分欺都可以用到； 局部變量只能喜在局部使用。4答：指針變量焉也占用內(nèi)存單元，而且所有指針變焉量占用內(nèi)存單元的數(shù)量都是相同的焉，就是說(shuō)，不管是指向何種對(duì)象的焉指針變量，它們占用內(nèi)存的字節(jié)數(shù)焉都是一樣的，并且要足夠把程序中焉所能用到的最大地址表示出來(lái)（通隕常是一個(gè)機(jī)器字長(zhǎng)）。七、填空題洲（本題共20

11、分，每小題各2分）洲 1 50 x2言(-1)*f 2*i+1沿3 c=c+5 c=c醫(yī)-214 *t *s氈-*t5 str3k幼=str2j+ st幼r1i=06余argc1 *argv余7 a+ r f援p2 fgetc(fp2)援 8統(tǒng)計(jì)正整數(shù)n的位數(shù)9增判斷輸入的字符串是否為“回文”增10以追加方式打開(kāi)文件“f預(yù)ile.txt”后向文件寫(xiě)入“預(yù)data”，然后查看(輸出)文預(yù)件指針位置。八、程序設(shè)計(jì)題（本傘題15分）#include瓤#incl紐冷int func(char *冷s,int n,char ch冷) int j,k=0;s細(xì)n=ch;sn+1=王0;while(sk瘸!=ch)k+;if(k欺=n)return 0; /灑* 字符串中不存在該字符 */灑else /* 字符串中存瑤在該字符 */for(j=k札sj=轅sj+1; /* 刪除首次轅出現(xiàn)的該字符 *sj-1胰=0;return k訝+1; /* 該字符在字符串中永位置 */ main( )援 char s80,ch造;int len,posit許ion; gets(s);p蟄uts(s); /* 輸出刪除蟄前的字符串 */printf擲(“Input a char”擲); /* 輸入字符串