清華大學(xué) - 話題

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

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

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

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

5。散列有n個(gè)位置，0~n-1。判斷散列函數(shù)是否正確，插入和查找是否能正確執(zhí)行
，如正確，判斷好壞，不正確說(shuō)明原因。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小的素?cái)?shù)


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

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

第4題:
圖類(lèi)
template class Graph{
int numberOfVectise(Graph G){}//返回圖中頂點(diǎn)數(shù)
.
.
.
}
1) 在圖中用dijsktla算法求從u點(diǎn)出發(fā)到各個(gè)點(diǎn)的最短路徑算.5分
template void shortestdist(Graph G,int v, float
*dist,int *path){
//在圖G中求由點(diǎn)c出發(fā)到各點(diǎn)的最點(diǎn)路徑,路徑長(zhǎng)度放在數(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;
....

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

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

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

中國(guó)哪個(gè)名族人口最多？

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