數據結構考研分類復習真題 第九章 集合[35]

　　 設二叉排序樹中關鍵字由到的整數組成現要查找關鍵字為的結點下述關鍵字序列哪一個不可能是在二叉排序樹中查到的序列？說明原因【東北大學 一   (分)】

　　() ()

　　 用關鍵字的四個結點()能構造出幾種不同的二叉排序樹？其中()最優查找樹有幾種？()AVL樹有幾種？()完全二叉樹有幾種？試畫出這些二叉排序樹【北京工業大學 二   ( 分)】

　　類似本題的另外敘述有

　　()設有關鍵字ABC和D依照不同的輸入順序共可能組成多少不同的二叉排序樹請畫出其中高度較小的種【北京大學 】

　　 一棵具有m層的AVL樹至少有多少個結點最多有多少個結點？【浙江大學 六  (分)】

　　 設T是一棵高度平衡樹(又稱平衡樹)給定關鍵詞K如果在T中查找K失敗且查找路徑上的任一結點的平衡系數皆為零試回答用高度平衡樹插入算法在T中插入關鍵詞為K的新結點後樹T的高度是否一定增加?並回答為什麼【吉林大學 四】

　　．設二叉樹HT是一棵高度平衡樹當使用二叉查找與插入算法插入一個新的結點時該操作可能會破壞HT的平衡性試列舉出可能破壞HT的平衡性的所有情況並論證你的結論的正確性(即要證明你所列舉的情況恰好是可能破壞HT的平衡性的所有情況)【吉林大學 四  六  (分)】

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []