對含有n個互不相同元素的集合同時找最大元和最小元至少需進行多少次比較?
答
設變量max和min用於存放最大元和最小元(的位置)第一次取兩個元素進行比較大的放入max小的放入min從第次開始每次取一個元素先和max比較如果大於max則以它替換max並結束本次比較若小於max則再與min相比較在最好的情況下一路比較下去都不用和min相比較所以這種情況下至少要進行n次比較就能找到最大元和最小元
若對具有n個元素的有序的順序表和無序的順序表分別進行順序查找試在下述兩種情況下分別討論兩者在等概率時的平均查找長度
()查找不成功即表中無關鍵字等於給定值K的記錄
()查找成功即表中有關鍵字等於給定值K的記錄
答
查找不成功時需進行n+次比較才能確定查找失敗因此平均查找長度為n+這時有序表和無序表是一樣的
查找成功時平均查找長度為(n+)/有序表和無序表也是一樣的因為順序查找與表的初始序列狀態無關
畫出對長度為的有序的順序表進行二分查找的判定樹並指出在等概率時查找成功的平均查找長度以及查找失敗時所需的最多的關鍵字比較次數
答
等概率情況下查找成功的平均查找長度為
ASL=(+*+*+*+*)/=
查找失敗時最多的關鍵字比較次樹不超過判定樹的深度此處為
為什麼有序的單鏈表不能進行折半查找?
答
因為鏈表無法進行隨機訪問如果要訪問鏈表的中間結點就必須先從頭結點開始進行依次訪問這就要浪費很多時間還不如進行順序查找而且用鏈存儲結構將無法判定二分的過程是否結束因此無法用鏈表實現二分查找
設有序表為(abcefgijkpq)請分別畫出對給定值bg和n進行折半查找的過程
解
()查找b的過程如下(其中方括號表示當前查找區間圓括號表示當前比較的關鍵字)
下標
第一次比較 [a b c d e f (g) h i j k p q]
第二次比較 [a b (c) d e f] g h i j k p q
第三次比較 [a (b)]c d e f g h i j k p q
經過三次比較查找成功
()g的查找過程如下
[a b c d e f (g) h i j k p q]
一次比較成功
()n的查找過程如下
下標
第一次比較 [a b c d e f (g) h i j k p q]
第二次比較 a b c d e f g [h i (j) k p q]
第三次比較 a b c d e f g h i j [k (p) q]
第四次比較 a b c d e f g h i j [k] p q]
經過四次比較查找失敗
將(for case while class protected virtual public private do template const if int)中的關鍵字依次插入初態為空的二叉排序樹中請畫出所得到的樹T然後畫出刪去for之後的二叉排序樹T若再將for 插入T中得到的二叉排序樹T是否與T相同?最後給出T的先序中序和後序序列
答
二叉排序樹T如下圖
刪去for後的二叉排序樹如下圖
再插入結點for後的二叉排序樹T
二叉排序樹T與T不同
T的先序序列是do case class const while protected private if for int virtual public template
T的中序序列是case class const do for if int private protected public template virtual while
T的後序序列是const class case for int if private template public virtual protected while do
對給定的關鍵字集合以不同的次序插入初始為空的樹中是否有可能得到同一棵二叉排序樹?
答
有可能如有兩個序列 和 它們插入空樹所得的二叉排序樹是相同的
將二叉排序樹T的先序序列中的關鍵字依次插入一空樹中所得和二叉排序樹T與T否相同?為什麼?
答
這兩棵二叉樹完全相同
設二叉排序樹中關鍵字由至的整數構成現要查找關鍵字為的結點下述關鍵字序列哪一個不可能是在二叉排序樹上查找到的序列?
(a)
(b) ;
(c) ;
(d)
答
(c)是不可能查找到的序列把這四個序列各插入到一個初始為空的二叉排序樹中結果可以發現(c)序列所形成的不是一條路徑而是有分支的可見它是不可能在查找過程中訪問到的序列
設二叉排序樹中關鍵字互不相同則其中最小元必無左孩子最大元必無右孩子此命題是否正確?最小元和最大元一定是葉子嗎?一個新結點總是插在二叉排序樹的某葉子上嗎?
答
此命題正確假設最小元有左孩子則根據二叉排序樹性質此左孩子應比最小元更小如此一來就產生矛盾了因此最小元不可能有左孩子對於最大元也是這個道理
但最大元和最小元不一定是葉子它也可以是根內部結點(分支結點)等這得根據插入結點時的次序而定
新結點總是作為葉子插入在二叉排序樹中的
在一棵m階的B樹中當將一關鍵字插入某結點而引起該結點的分裂時此結點原有多少個關鍵字?若刪去某結點中的一個關鍵字而導致結點合並時該結點中原有幾個關鍵字?
答
在一棵m階的B樹中若由於一關鍵字的插入某結點而引起該結點的分裂時則該結點原有m個關鍵字
若刪去某結點中一個關鍵字而導致結點合並時該結點中原有┌m/┐個關鍵字
在一棵B樹中空指針數總是比關鍵字數多一個此說法是否正確?請問包含個關鍵字的階B樹(即樹)最多有幾個結點?最少有幾個結點?畫出這兩種情況的B樹
答
這個說法是正確的包含個關鍵字的階B樹最多有個結點最少有個結點
從空樹開始依次輸入畫出建立樹的過程並畫出刪除和後的B樹狀態
答過程如下
() 插入數據結構免費提供，內容來源於互聯網,本文歸原作者所有。
