清華大學1997計算機專業(yè)考研真題

本文格式為Word版，下載可任意編輯——清華大學1997計算機專業(yè)考研真題

考研真題

清華大學97計算機專業(yè)考研試題

一、對于一個使用鄰接表存儲的帶權(quán)有向圖G，試利用深度優(yōu)先探尋放法，對該圖中所有頂點進

行拓撲排序。若鄰接表的數(shù)據(jù)類型定義為Graph，則算法的首部為：

FUNCTIONdfs-toposort(G:Graph):boolean;

若函數(shù)返回true，則表示拓撲成功，圖中不存在環(huán)；若函數(shù)返false，則圖中存在環(huán)，拓撲排

序不成功。在這個算法中嵌套用一個遞歸的深度優(yōu)先探尋算法：

PROCEDUREdfs(G:Graph;V:vtxnum);

在遍歷圖的同時進行拓撲排序。其中，vtxnum是頂點號

（1）給出該圖的鄰接表定義；（4分）

（2）定義在算法中使用的全局輔助數(shù)組；（4分）

（3）寫出拓撲排序的算法。（10分）

二、設(shè)有一頭指針為L的帶有表結(jié)點的非循環(huán)雙向鏈表，其每個結(jié)點中除有pred（前驅(qū)指針），

data（數(shù)據(jù)）和next（后繼指針）域外，還有一個訪問頻度域freq。在鏈表被使用前，其值均

初始化為零。每當在鏈表中進行一次Locate(L,x)運算時，令元素值為x的結(jié)點中freq域的值

增1，并使此鏈表中結(jié)點保持按訪問頻度非增（遞減）的順序排序，同時最近訪問的結(jié)點排

在頻度一致的結(jié)點的最終，以便使頻繁訪問的結(jié)點總是靠近表頭。試編寫符合上述要求的

Locate(L,x)運算的算法，該運算為函數(shù)過程，返回找到結(jié)點的地址，類型為指針型。（10分）

三、已知二叉樹的鏈表存儲結(jié)構(gòu)定義如下：

TYPEbitreptR=^bitrenode;

bitrenode=RECORD

data:char;

lchild,rchild:butreptr

END;

編寫一個遞歸算法，利用葉結(jié)點中空的右鏈指針域rchild，將所有葉結(jié)點自左至右鏈接成一

個單鏈表，算法返回最左葉結(jié)點的地址（鏈頭）。（10分）

四、設(shè)目標為S=“abcaabbcaaabababaabca〞，模是為P=“babab〞，

（1）手工計算模式P的nextval數(shù)組的值；(5分)

（2）寫出利用求得的nextval數(shù)組，按KMP算法對目標S進行模式匹配的過程。（5分）

五、對于一個對稱矩陣采用壓縮存儲，只存放它的上三角部分，并按列存放。例如對于一個n*n的對稱矩陣A，

考研真題

用一個一維數(shù)組B來存放它的上三角部分：

B=[A11，A12，A22，A13，A23，A33，A14。。。。。。。。，A1n，A2n。。。。。。，Ann]

同時有兩個函數(shù)：MAX（i，j）和MIN（i，j），分別計算下標i和j中的大者與小者。試利用它門給出求任意一個Aij在B中存放位置的公式。（若式中沒有MAX（i，j）和MIN（i，j）則不給分）。（10分）

六、有一棵中序遍歷二叉樹，如下圖（a）所示

d^成為

的A^左孩子，原來A^的左孩子B^變成A^的右孩子C^的左孩子，如圖(B)所示（樹中的線索自行畫出0。試針對圖中的實例寫出實現(xiàn)插入的幾條語句。

（2）現(xiàn)在想在插入后的中序線索二叉樹中刪去A^右孩子C^并用C^的左孩子填補原來的c↑的位置，如圖（c）所示。試寫出實現(xiàn)刪除的幾條語句。（15分）

七、設(shè)有一組數(shù)據(jù)black,blue,green,purple,red,white,yellow，它們的查找概率分別為

0.10,0.08,0.12,0.05,0.20,0.25,0.20.試以它們的查找概率為權(quán)值，構(gòu)造一棵次查找樹，并計算其查找成功的平均查找長度。（12分）

八、設(shè)有11個長度（即包含記錄個數(shù)）不同的歸段，它們所包含的記錄個數(shù)分別為25,40,16,38,77,64,53,88,9,48,98.

試根據(jù)它們做4路平均歸并，要求：

（1）指出總的歸并趟數(shù)；（3分）

（2）構(gòu)造最正確歸并樹；（8分）

（3）根據(jù)最正確歸并樹計算每