清華大學2001年碩士研究生考試數據結構試題內容簡介
清華大學2001年碩士研究生考試數據結構試題
一、試給出下列有關並查集(mfsets)的操作序列的運算結果：
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(3,12) , union(3,13) , union(14,15) , union(16,0) , union(14,16) , union(1,3) , union(1,14)。(union是合並運算，在以前的書中命名為merge)
要求
(1)對於union(i,j)，以i作為j的雙親；(5分)
(2)按i和j為根的樹的高度實現union(i,j)，高度大者為高度小者的雙親；(5分)
(3)按i和j為根的樹的結點個數實現union(i,j)，結點個數大者為結點個數小者的雙親；(5分)
二、設在4地(A,B,C,D)之間架設有6座橋,如圖所示:
要求從某一地出發,經過每座橋恰巧一次,最後仍回到原地
(1)試就以上圖形說明:此問題有解的條件是什麼? (5分)
(2)設圖中的頂點數為n,試用C或Pascal描述與求解此問題有關的數據結構並編寫一個算法,找出滿足要求的一條回路. (10分)
三、針對以下情況確定非遞歸的歸並排序的運行時間(數據比較次數與移動次數):
(1)輸入的n個數據全部有序; (5分)
(2)輸入的n個數據全部逆向有序; (5分)
(3)隨機地輸入n個數據. (5分)
四、簡單回答有關AVL樹的問題.
(1)在有N個結點的AVL樹中,為結點增加一個存放結點高度的數據成員,那麼每一個結點需要增加多少個字位(bit)? (5分)
(2)若每一個結點中的高度計數器有8bit,那麼這樣的AVL樹可以有多少層?最少有多少個關鍵碼? (5分)
五、設一個散列表包含hashSize=13個表項,.其下標從0到12,采用線性探查法解決衝突.請按以下要求,將下列關鍵碼散列到表中.
10 100 32 45 58 126 3 29 200 400 0
(1)散列函數采用除留餘數法,用%hashSize(取餘運算)將各關鍵碼映像到表中.請指出每一個產生衝突的關鍵碼可能產生多少次衝突. (7分)
(2)散列函數采用先將關鍵碼各位數字折疊相加,再用%hashSize將相加的結果映像到表中的辦法.請指出每一個產生衝突的關鍵碼可能產生多少次衝突. (8分)
..............................