清華大學(xué) - 話題

數(shù)據(jù)結(jié)構(gòu):
第一題:15分
1。線性表的定義，表中元素是否必須是同一個類型，為什么？

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

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

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

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


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

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

第4題:
圖類
template class Graph{
int numberOfVectise(Graph G){}//返回圖中頂點數(shù)
.
.
.
}
1) 在圖中用dijsktla算法求從u點出發(fā)到各個點的最短路徑算.5分
template void shortestdist(Graph G,int v, float
*dist,int *path){
//在圖G中求由點c出發(fā)到各點的最點路徑,路徑長度放在數(shù)組dist中,路徑放在數(shù)組
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（）中&&之前的第一個判斷條件

}
}
整個函數(shù)太長,我記不得了，書上應(yīng)該是有的.

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

四川省省會城市是哪里？（答案為兩個字）

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