清華大學 - 話題

數據結構:
第一題:15分
1。線性表的定義，表中元素是否必須是同一個類型，為什么？

2。線性表有兩種存儲形式，定義如下，然后給了一個線性鏈表類的空架字，一個
靜態數組實現類，一個單鏈表實現類，后兩個繼承于第一個。問使用時如何選用哪
種類型的實現。

3。二叉樹給你前序和中序排列，求后序
所給序列已經記不清了，可能是前序ABDEFCFHIJ，中序DBCEAFCHIJ。

4。B樹相關計算
一個磁盤塊大小4，000（實際為4096，但是為計算方便，按4000算），一個地址指
針需要5個字節。有一個有20，000，000條記錄的文件。一個關鍵字占5個字節，求
B樹的最大階數，當記錄不是按順序排列時，求索引需要占用的磁盤塊數。

5。散列有n個位置，0~n-1。判斷散列函數是否正確，插入和查找是否能正確執行
，如正確，判斷好壞，不正確說明原因。random(n)函數能隨機產生0~n-1之間的數
。
1) H(Key)=Key/n；
2) H(Key)=1;
3) H(Key+random(n))%n;
4) H(Key)%p(n)，其中p(n)是比n小的素數


第2題:5分
證明:在前序序列、中序序列和后序序列中葉節點相對(前后)的排列位置不變

第3題:15分
AVL樹的插入和刪除
1) 從空樹開始插入數值,(數值序列也記不清楚了,只能寫個大概,大家參考20,12,
9,27,22,17,16,15,18,10),畫出插入后的狀態,如需旋轉,標明旋轉的種類(有單右
旋轉,單左旋轉,先左后右旋轉,先右后左旋轉).
2) 從剛才生成的AVL樹中刪除22,...,9和10,畫出刪除后的狀態和旋轉的類型.刪除
的非葉子結點用中序前趨結點代替.

第4題:
圖類
template class Graph{
int numberOfVectise(Graph G){}//返回圖中頂點數
.
.
.
}
1) 在圖中用dijsktla算法求從u點出發到各個點的最短路徑算.5分
template void shortestdist(Graph G,int v, float
*dist,int *path){
//在圖G中求由點c出發到各點的最點路徑,路徑長度放在數組dist中,路徑放在數組
path里,maxWeight是float型所能表示的最大值
int n=numberOfVectise(G);
int *S=new int[n];
for(int i=0;i {
......
if(value(u,i) else path=-1;
....

后面有兩個空是if（）中&&之前的第一個判斷條件

}
}
整個函數太長,我記不得了，書上應該是有的.

2) 在一個圖中,從u點出發,到圖中各個點的最短路徑中距離最長的叫做點u在這個
圖中的偏心距.圖中偏心距最小的點叫做中心.設計算法求一個圖的中心.函數頭為
template int centre(Graph G, float &mindist);
函數返回值是中心點編號,mindist返回的是最小偏心距.10分
這個題我記得練習冊上有原題,只是換了一種表述,實質是一樣的.

中秋節中國人一般會吃什么？

考研論壇提示：
1、請勿發布個人聯系方式或詢問他人聯系方式，包括QQ和手機等。
2、未經允許不得發布任何資料出售、招生中介等廣告信息。
3、如果發布了涉及以上內容的話題或跟帖，您在考研網的注冊賬戶可能被禁用。