清華大學2000年考研專業課試卷數據結構與程序設計

1(12分)

請回答下列關于圖(Graph)的一些問題：

①（4分）有n個頂點的有向連通圖最多有多少條邊?最少有多少條邊？

②（4分）表示一個有1000個頂點、1000條邊的有向圖的鄰接矩陣有多少個矩陣元素?是否稀疏矩陣？

③（4分）對于一個有向圖，不用拓撲排序，如何判斷圖中是否存在環？

2(12分)

斐波那契數列Fn定義如下：
F0=0, F1=1, Fn= Fn-1 + Fn-2,n=2,3,…
請就此斐波那契數列，回答下列問題：

①（7分）在遞歸計算Fn的時候，需要對較小的Fn－1，Fn－2，…，F1，F0精確計算多少次？

②（5分）若干有關大O表示法，試給出遞歸計算Fn時遞歸函數的時間復雜度是多少？
3 （17分）

有一種簡單的排序算法，叫做計數排序(count
sorting)。這種排存算法對一個待排序的表(用數組表示)進行排序，并將排序結果存放到另一個新的表中。必須注意的是，表中所有待排序的關鍵碼互不相同。計數排序算法針對表中的每個記錄，掃描待排序的表一趟，統計表中有多少個記錄的關鍵碼比該記錄的關鍵碼小。假設針對騁桓黽鍬跡�统计除_募剖�值为c,那么，這個記錄在新的有序表中的合適的存放位置即為c。

①（3分）給出適用于計數排序的數據表定義；

②（7分）使用Pascal或C語言編寫實現計數排序的算法；

③（4分）對于有n個記錄的表，關鍵碼比較次數是多少？

④（3分）與簡單選擇排序相比較，這種方法是否更好？為什么？

4 （10分）

在一棵表示有序集S的二叉搜索樹（binary search
tree）中，任意一條從根到葉節點的路徑將S分為3部分：在該路徑左邊節點中的元素組成的集合S1；在該路徑上的節點中的元素組成的集合S2；在該路徑右邊節點中的元素組成的集合S3。S＝S1∪S2∪S3。若對于任意的a∈S1,
b∈S2, c∈S3,是否總有a<=b<=c?為什么？

5 （12分）

請回答下列關于堆（Heap）的一些問題：

①（4分）堆的存儲表示是順序的，還是鏈接的？

②（4分）設有一個最小堆，即堆中任意節點的關鍵碼均大于它的左子女和右子女的關鍵碼。其具有最大值的元素可能在什么地方？

③（4分）對n個元素進行初始建堆的過程中，最多做多少次數據比較（不用大O表示法）？

6 （12分）

已知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的ADT函數和少量工作變量，使用Pascal或C語言編寫一個算法，將隊列Q中的所有元素逆置。
棧的ADT函數有：
makeEmpty(s:stack);置空棧
push(s:stack; value:datatype); 新元素value進棧
pop(s:stack):datatype;出棧，返回棧頂值
isEmpty(s:stack):boolean;判棧空否
隊列的ADT函數有
enqueue(q:queue;value:datatype); 元素value進隊
deQueue(q:queue):datatype;出隊列，返回隊頭值
isEmpty(q:queue):boolean;判隊列空否

7 （13分）

設散列表為HT[0..12],即表的大小為m=13。現采用雙散列法解決沖突。散列函數和在散列函數分別為：
H0(key)=key%13;注：％是求余數運算（＝mod）
Hi=(Hi-1+REV(key+1)%11+1)%13;i=1,2,3,…，m-1
其中，函數REV（x）表示顛倒10進制數x的各位，如REV(37)=73,REV(7)=7等。若插入的關鍵碼序列為{2,8,31,20,19,18,53,27}。

①（8分）試畫出插入這8個關鍵碼后的散列表。

②（5分）計算搜索成功的平均搜索長度ASL。

8 （12分）

從左到右及從右到左遍歷一個單鏈表是可能的，其方法是在從左向右遍歷的過程中將連接方向逆轉，如圖1所示。在圖中的指針p指向當前正在訪問的節點，指針pr指向指針p所指節點的左側的節點。此時，指針p所指節點左側的所有節點的連接方向都已逆轉。
 
圖1題8圖

①（6分）使用Pascal或C語言編寫一個算法，從任一給定位置（pr,p）開始，將指針p右移1個節點。如果p移出鏈表，則將p置為NULL，并讓pr留在鏈表最右邊的節點上。

②（6分）使用Pascal或C語言編寫一個算法，從任一給定位置（pr,p）開始，將指針p左移一個節點。如果p移出鏈表，則將p置為NULL,并讓pr停留在鏈表最左邊的節點上