清華歷年計算機(jī)考研題01年

1、2001 年試題(f)一試給出下列有關(guān)并查集（mfsets）的操作序列的運(yùn)算結(jié)果：union(1,2),union(3,4),union(3,5),union(1,7),union(3,6),union(8,9),union(1,8),union(3,10),union(3,11),union(1,12),union(3,13),union(14,15),union(16,0),union(14,16),union(1,3),union(1,14). (union 是合并運(yùn)算，在以前的書中命名為 merge)要求（1）對于 union(i,j),以 i 作為 j 的雙親；（5 分）（2）按 i

2、 和 j 為根的樹的高度實(shí)現(xiàn)union(i,j),高度大者為高度小者的雙親；（5 分）（3）按 i 和 j 為根的樹的結(jié)點(diǎn)個數(shù)實(shí)現(xiàn) union(i,j),結(jié)點(diǎn)個數(shù)大者為結(jié)點(diǎn)個數(shù)小者的雙親。（5 分）二設(shè)在 4 地（A，B，C，D）之間架設(shè)有 6 座橋，：要求從某一地出發(fā)，經(jīng)過每座橋恰巧一次，最后仍回到原地。（1）試就以上圖形說明：此問題有解的條件是什么？（5 分）（2）設(shè)圖中的頂點(diǎn)數(shù)為 n,試用 C 或 PASCAL 描述與求解此問題有關(guān)的數(shù)據(jù)結(jié)構(gòu)并編寫一個算法，找出滿足要求的一條回路。（10 分）三針對以下情況確定非遞歸的歸并排序的運(yùn)行時間（數(shù)據(jù)比較次數(shù)與移動次數(shù)）：輸入的 n 個數(shù)據(jù)全部有

3、序；輸入的 n 個數(shù)據(jù)全部逆向有序；隨機(jī)地輸入 n 個數(shù)據(jù)。（5 分）（5 分）（5 分）四簡單回答有關(guān) AVL 樹。（1）在有 N 個結(jié)點(diǎn)的 AVL 樹中，為結(jié)點(diǎn)增加一個存放結(jié)點(diǎn)高度的數(shù)據(jù)成員，那么每一個結(jié)點(diǎn)需要增加多少個字位（bit）?（5 分）（2）若每一個結(jié)點(diǎn)的高度計數(shù)器有 8bits，那么這樣的 AVL 樹可以有多少層？最少有多少個關(guān)鍵碼？五設(shè)一個散列表含 hashsize=13 個表項(xiàng)，其下標(biāo)從 0 到 12，采用線形探查法解決按以下要求，將下列關(guān)鍵碼散列到表中。101003245581263292004000。請（1） 散列函數(shù)采用除留余數(shù)法，用%hashsize（取余運(yùn)算）將各

4、關(guān)鍵碼映像到表。 （7 分）中，請每一個產(chǎn)生的關(guān)鍵碼可能產(chǎn)生多少次（2） 散列函數(shù)采用先將關(guān)鍵碼各位數(shù)字折疊相加，再用%hashsize 將相加的結(jié)果映像到表中的辦法。請突。六設(shè)一棵二叉樹的結(jié)點(diǎn)定義為每一個產(chǎn)生的關(guān)鍵字碼可能產(chǎn)生多少次沖struct BreeNodeElemType data;BreeNeftChild,*rightChild;現(xiàn)采用輸入廣義表表示建立二叉樹。具體規(guī)定如下：（1）（2）樹的根結(jié)點(diǎn)作為由的表的表名放在表的最前面；每個結(jié)點(diǎn)的省略。樹和右用逗號隔開。若僅有右沒有樹，逗號不能（3）在整個廣義表輸入的結(jié)尾加上一個特殊的符號（例如“#”）表示輸入結(jié)束。例如，對于圖所示的二叉

5、樹，其廣義表A表示為 A（B（D，E（G，），C（，F(xiàn)）。此算法的基本思路是：依次從保存廣義表的字符串 ls 中輸入每個字符。若遇到的是字母（假設(shè)以字母作為結(jié)點(diǎn)的值），則表示是結(jié)BC點(diǎn)的值，應(yīng)為它建立一個新的結(jié)點(diǎn)，并把該DEF結(jié)點(diǎn)作為女（當(dāng)k=1）或若（當(dāng) k=2）到其雙親結(jié)點(diǎn)上。若遇到的是左括號“（”，則表明子表的開始，將 k 置為 1；若遇到的是右括號“）”，則表明子表結(jié)束。若遇到的是逗號“，”，則表示G以置為 2。女為根的處理完畢，應(yīng)接著處理以右為根的，將 K在算法中使用了一個棧S，在進(jìn)入子表之前，將根結(jié)點(diǎn)指針進(jìn)棧，以便括號內(nèi)的鏈結(jié)之用。在子表處理結(jié)束時退棧。相關(guān)的棧操作如下：MAKEE

6、MPTY（S）PUSH（S，P） POP（S） TOP（S）置空棧元素 P 入棧退棧存取棧頂元素的函數(shù)下面給出了建立二叉樹的算法，其中有 5 個語句缺失，請閱讀此算法并把缺失的語句補(bǔ)上。（每空 3 分）reeNode*&BT,char ls)void CreatBStacks;MakeEmpty(s);/置空 2 叉樹BT=NULL;BreeNode*p; k;Istream ins(ls) Char ch; Insch;While (ch != #) Switch(ch)Case (/把串 ls 定義為輸入字符串流對象 ins;/從 ins 順序讀入一個字符/逐個字符處理，知道遇到#為止:K

7、=1;Break; pop(s); Break;Case ):Case,:Break;p=new breenode;Default :P-leftchild=null;p-rightchild=null;if(BT=NULL)else if (k=1) top(s) - leftchild=p;else top(s)- rightchild =p;7.下面是一個用C 語言編寫的快速算法。為了避免情況，取基準(zhǔn)pivot 采用從 left，right 和 mid=（left+right）/2中取中間值，并交換到 right 位置的辦法。數(shù)組a 存放待排序的一組，數(shù)據(jù)類型為 Type，left 和r

8、ight 是待排序子區(qū)間的最左端點(diǎn)和最右端點(diǎn)。Voidquicksort (Type a ,Typetempleft,right) If(leftright) TypeIFor(pivot = median3(a, left, right);/三者取中子程序= left ,j = right-1;) While (Ij & aI pivot) I+; While (Ij & pivotaj) j-; If (I pivot)temp =aI ; aI=aright ; aright= temp;quicksort(a,left,I-1);quicksort(a,I+1,right);/遞歸排序區(qū)間/遞歸排序右子區(qū)間用 C 或 Pascal 實(shí)現(xiàn)三者取中