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

1、1 (12分) 請回答下列關(guān)于圖(Graph)的一些問題： （4分）有n個頂點的有向連通圖最多有多少條邊?最少有多少條邊？ （4分）表示一個有1000個頂點、1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否稀疏矩陣？ （4分）對于一個有向圖，不用拓?fù)渑判?，如何判斷圖中是否存在環(huán)？2 (12分) 斐波那契數(shù)列Fn定義如下：F0=0, F1=1, Fn= Fn-1 + Fn-2, n=2,3,請就此斐波那契數(shù)列，回答下列問題：（7分）在遞歸計算Fn的時候，需要對較小的Fn1，F(xiàn)n2，F(xiàn)1，F(xiàn)0精確計算多少次？（5分）若干有關(guān)大O表示法，試給出遞歸計算Fn時遞歸函數(shù)的時間復(fù)雜度是多少？3 （17

2、分）有一種簡單的排序算法，叫做計數(shù)排序(count sorting)。這種排存算法對一個待排序的表(用數(shù)組表示)進行排序，并將排序結(jié)果存放到另一個新的表中。必須注意的是，表中所有待排序的關(guān)鍵碼互不相同。計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小。假設(shè)針對某一個記錄，統(tǒng)計出的計數(shù)值為c,那么，這個記錄在新的有序表中的合適的存放位置即為c。（3分）給出適用于計數(shù)排序的數(shù)據(jù)表定義；（7分）使用Pascal或C語言編寫實現(xiàn)計數(shù)排序的算法；（4分）對于有n個記錄的表，關(guān)鍵碼比較次數(shù)是多少？（3分）與簡單選擇排序相比較，這種方法是否更好？為什么？4

3、（10分）在一棵表示有序集S的二叉搜索樹（binary search tree）中，任意一條從根到葉節(jié)點的路徑將S分為3部分：在該路徑左邊節(jié)點中的元素組成的集合S1；在該路徑上的節(jié)點中的元素組成的集合S2；在該路徑右邊節(jié)點中的元素組成的集合S3。SS1S2S3。若對于任意的aS1, bS2, cS3,是否總有a=b=c?為什么？5 （12分）請回答下列關(guān)于堆（Heap）的一些問題：（4分）堆的存儲表示是順序的，還是鏈接的？（4分）設(shè)有一個最小堆，即堆中任意節(jié)點的關(guān)鍵碼均大于它的左子女和右子女的關(guān)鍵碼。其具有最大值的元素可能在什么地方？（4分）對n個元素進行初始建堆的過程中，最多做多少次數(shù)據(jù)比較

4、（不用大O表示法）？6 （12分）已知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的ADT函數(shù)和少量工作變量，使用Pascal或C語言編寫一個算法，將隊列Q中的所有元素逆置。棧的ADT函數(shù)有：makeEmpty(s:stack); 置空棧push(s:stack; value:datatype); 新元素value進棧pop(s:stack):datatype; 出棧，返回棧頂值isEmpty(s:stack):boolean; 判?？辗耜犃械腁DT函數(shù)有enqueue(q:queue;value:datatype); 元素value進隊deQueue(q:queue):datatype; 出

5、隊列，返回隊頭值isEmpty(q:queue):boolean; 判隊列空否7 （13分）設(shè)散列表為HT0.12,即表的大小為m=13?，F(xiàn)采用雙散列法解決沖突。散列函數(shù)和在散列函數(shù)分別為：H0(key)=key%13; 注：是求余數(shù)運算（mod）Hi=(Hi-1+REV(key+1)%11+1)%13; i=1,2,3,，m-1其中，函數(shù)REV（x）表示顛倒10進制數(shù)x的各位，如REV(37)=73,REV(7)=7等。若插入的關(guān)鍵碼序列為2,8,31,20,19,18,53,27。（8分）試畫出插入這8個關(guān)鍵碼后的散列表。（5分）計算搜索成功的平均搜索長度ASL。8 （12分）從左到右及從右到左遍歷一個單鏈表是可能的，其方法是在從左向右遍歷的過程中將連接方向逆轉(zhuǎn)，如圖1所示。在圖中的指針p指向當(dāng)前正在訪問的節(jié)點，指針pr指向指針p所指節(jié)點的左側(cè)的節(jié)點。此時，指針p所指節(jié)點左側(cè)的所有節(jié)點的連接方向都已逆轉(zhuǎn)。圖1 題8圖（6分）使用Pascal或C語言編寫一個算法，從任一給定位置（pr,p）開始，將指針p右移1個節(jié)點。如果p移出鏈表，則將p置為NULL，并讓pr留在鏈表最右邊的