清華大學(xué)2000年研究生考試數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)專(zhuān)

1、1、（、（12分）分）請(qǐng)回答下列關(guān)于圖（Graph）的一些問(wèn)題：①（4分）有分）有n個(gè)頂點(diǎn)的有向點(diǎn)的有向連通圖最多有多少條最多有多少條邊？最少有多少條？最少有多少條邊？②（4分）表示一個(gè)有分）表示一個(gè)有1000個(gè)頂點(diǎn)、點(diǎn)、1000條邊的有向的有向圖的鄰接矩接矩陣有多少個(gè)矩有多少個(gè)矩陣元素元素？是否稀疏矩？是否稀疏矩陣？③（4分）分）對(duì)于一個(gè)有向于一個(gè)有向圖，不用拓?fù)渑判?，如何判斷，不用拓?fù)渑判颍绾闻袛鄨D中是否存在中是否存在環(huán)？2、（、

2、（12分）分）斐波那契數(shù)列Fn定義如下：F0=0，F(xiàn)1=1，F(xiàn)n=Fn1Fn2，n=2，3，…請(qǐng)就此斐波那契數(shù)列，回答下列問(wèn)題：①（7分）在分）在遞歸計(jì)遞歸計(jì)算Fn的時(shí)候，需要候，需要對(duì)較對(duì)較小的小的Fn－1，F(xiàn)n－2，…，F(xiàn)1，F(xiàn)0精確精確計(jì)算多算多少次？少次？②（5分）若干有關(guān)大分）若干有關(guān)大O表示法，表示法，試給試給出遞歸計(jì)遞歸計(jì)算Fn時(shí)遞歸時(shí)遞歸函數(shù)的函數(shù)的時(shí)間時(shí)間復(fù)雜度是多少度是多少？3、（、（17分）分）有一種簡(jiǎn)單的排序算法

3、，叫做計(jì)數(shù)排序（countsting）。這種排存算法對(duì)一個(gè)待排序的表（用數(shù)組表示）進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同。計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小。假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c.①（3分）分）給出適用于出適用于計(jì)數(shù)排序的數(shù)據(jù)表定數(shù)排序的數(shù)據(jù)表定義；②（7

4、分）使用分）使用Pal或C語(yǔ)言編寫(xiě)實(shí)現(xiàn)計(jì)實(shí)現(xiàn)計(jì)數(shù)排序的算法；數(shù)排序的算法；deQueue（q：queue）：datatype；出隊(duì)列，返回隊(duì)頭值isEmpty（q：queue）：boolean；判隊(duì)列空否7、（、（13分）分）設(shè)散列表為HT[0……12]，即表的大小為m=13.現(xiàn)采用雙散列法解決沖突。散列函數(shù)和在散列函數(shù)分別為：H0（key）=key%13；注：％是求余數(shù)運(yùn)算（＝mod）Hi=（Hi1REV（key1）%111）%13；

5、i=1，2，3，…，m1其中，函數(shù)REV（x）表示顛倒10進(jìn)制數(shù)x的各位，如REV（37）=73，REV（7）=7等。若插入的關(guān)鍵碼序列為2，8，31，20，19，18，53，27.①（8分）分）試畫(huà)出插入畫(huà)出插入這8個(gè)關(guān)個(gè)關(guān)鍵碼鍵碼后的散列表。后的散列表。②（5分）分）計(jì)算搜索成功的平均搜索算搜索成功的平均搜索長(zhǎng)度ASL.8、（、（12分）分）從左到右及從右到左遍歷一個(gè)單鏈表是可能的，其方法是在從左向右遍歷的過(guò)程中將連接方向逆轉(zhuǎn)，如圖

6、1所示。在圖中的指針p指向當(dāng)前正在訪問(wèn)的節(jié)點(diǎn)，指針pr指向指針p所指節(jié)點(diǎn)的左側(cè)的節(jié)點(diǎn)。此時(shí)，指針p所指節(jié)點(diǎn)左側(cè)的所有節(jié)點(diǎn)的連接方向都已逆轉(zhuǎn)。圖1題8圖①（6分）使用分）使用Pal或C語(yǔ)言編寫(xiě)一個(gè)算法，從任一寫(xiě)一個(gè)算法，從任一給定位置（定位置（pr，p）開(kāi)始，將指）開(kāi)始，將指針p右移右移1個(gè)節(jié)點(diǎn)。如果點(diǎn)。如果p移出移出鏈表，表，則將p置為NULL，并，并讓pr留在留在鏈表最右表最右邊的節(jié)點(diǎn)上點(diǎn)上。②（6分）使用分）使用Pal或C語(yǔ)言編寫(xiě)一