一基礎知識題
對含有n個互不相同元素的集合同時找最大元和最小元至少需進行多少次比較?
答我們可以設立兩個變量max和min用於存放最大元和最小元(的位置)第一次取兩個元素進行比較大的放入max小的放入min從第次開始每次取一個元素先和max比較如果大於max則以它替換max並結束本次比較;若小於max則再與min相比較在最好的情況下一路比較下去都不用和min相比較所以這種情況下至少要進行n次比較就能找到最大元和最小元(順便說一下最壞情況下要進行n次比較才能得到結果)
若對具有n個元素的有序的順序表和無序的順序表分別進行順序查找試在下述兩種情況下分別討論兩者在等概率時的平均查找長度()查找不成功即表中無關鍵字等於給定值K的記錄;()查找成功即表中有關鍵字等於給定值K的記錄
答查找不成功時需進行n+次比較才能確定查找失敗因此平均查找長度為n+這時有序表和無序表是一樣的
查找成功時平均查找長度為(n+)/有序表和無序表也是一樣的因為順序查找對表的原始序列的有序性不感興趣
畫出對長度為的有序的順序表進行二分查找的判定樹並指出在等概率時查找成功的平均查找長度以及查找失敗時所需的最多的關鍵字比較次數
答請看題圖
等概率情況下查找成功的平均查找長度為
ASL=(+*+*+*+*)/=
也可以用公式代大約為ASL=(+)lg(+)/=
查找失敗時最多的關鍵字比較次樹不超過判定樹的深度此處為如圖
為什麼有序的單鏈表不能進行折半查找?
答因為鏈表無法進行隨機訪問如果要訪問鏈表的中間結點就必須先從頭結點開始進行依次訪問這就要浪費很多時間還不如進行順序查找而且用鏈存儲結構將無法判定二分的過程是否結束因此無法用鏈表實現二分查找
設有序表為(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的先序序列是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如下圖
刪去for後的二叉排序樹如下圖圈內的for表示再插入後的結點
對給定的關鍵字集合以不同的次序插入初始為空的樹中是否有可能得到同一棵二叉排序樹?
答有可能如有兩個序列 和 它們插入空樹所得的二叉排序樹是相同的
將二叉排序樹T的先序序列中的關鍵字依次插入一空樹中所得和二叉排序樹T與T是否相同?為什麼?
答這兩棵二叉樹完全相同
設二叉排序樹中關鍵字由至的整數構成現要查找關鍵字為的結點下述關鍵字序列哪一個不可能是在二叉排序樹上查找到的序列?
(a) ;
(b) ;
(c) ;
(d)
答(c)是不可能查找到的序列我們可以把這四個序列各插入到一個初始為空的二叉排序樹中結果可以發現(c)序列所形成的不是一條路徑而是有分支的可見它是不可能在查找過程中訪問到的序列
設二叉排序樹中關鍵字互不相同則其中最小元必無左孩子最大元必無右孩子此命題是否正確?最小元和最大元一定是葉子嗎?一個新結點總是插在二叉排序樹的某葉子上嗎?
答此命題正確假設最小元有左孩子則根據二叉排序樹性質此左孩子應比最小元更小如此一來就產生矛盾了因此最小元不可能有左孩子對於最大元也是這個道理
但最大元和最小元不一定是葉子它也可以是根內部結點(分支結點)等這得根據插入結點時的次序而定如 這個集合根據不同的插入次序可以得到不同的二叉排序樹
○
/ \
○ ○
\
○
○
/ \
○ ○
\
○
○
\
○
\
○
\
○
○
/ \
○ ○
/
○
新結點總是插入在二叉排序樹的某個葉子上的
在一棵m階的B樹中當將一關鍵字插入某結點而引起該結點的分裂時此結點原有多少個關鍵字?若刪去某結點中的一個關鍵字而導致結點合並時該結點中原有幾個關鍵字?
答在此樹中若由於一關鍵字的插入某結點而引起該結點的分裂時則該結點原有m個關鍵字
若刪去某結點中一個關鍵字而導致結點合並時該結點中原有┌m/┐個關鍵字
在一棵B樹中空指針數總是比關鍵字數多一個此說法是否正確?請問包含個關鍵字的階B樹(即樹)最多有幾個結點?最少有幾個結點?畫出這兩種情況的B樹
答這個說法是正確的
包含個關鍵字的階B樹最多有個結點最少有個結點
見題圖:圖如下
在含有n個關鍵字的m階B樹中進行查找至多讀盤多少次?完全平衡的二叉排序樹的讀盤次數大約比它大多少倍?
答在含有n個關鍵字的m階B樹中進行查找至多讀盤次數不超過B樹高h即logt((n+)/)+ (注此處t為底值是除根外的每個內部結點的最小度數┌m/┐)
完全平衡的二叉樹高為lgn所以它的讀盤次數至多也是lgn它與上述B樹的讀盤次數的比值約為lgt倍(此處底是)
為什麼在內存中使用的B樹通常是階的而不使用更高階的B樹?
答因為查找等操作的cpu時間在B樹上是O(lgn·(m/lgt))而m/lgt>所以m較大時它所費時間比平衡的二叉排序樹上相應操作時間大得多因此僅在內存中使用的B樹通常取最小值
為什麼二叉排序樹長高時新結點總是一個葉子而B樹長高時新結點總是根?哪一種長高能保證樹平衡?
答因為在二叉排序樹中關鍵字總是作為一個葉子結點插入以原來的樹中所以當樹增高時新結點總是一個葉子;而B樹中關鍵字插入總是插入到葉子結點內部在葉結點中的關鍵字數目尚未超過它能夠容納的數目之前是不會增加結點的當關鍵字數超過結點可容納的數目時葉結點就會發生分裂產生一個新結點(但不一定引起樹增高)並且將其中的中間結點傳至上一層只有當這種分裂操作傳遞至根結點並引起根結點的分裂時才能引起樹高增加此時產生一個新的根結點所以說B樹長高時新結點總是根
顯然後一種長高總能保證樹的平衡
已知關鍵字序列為(PALLAPPAMMAPPATPETSETSATTATBAT)試為它們設計一個散列函數將其映射到區間[n]上要求碰撞盡可能的少這裡n=
解我的設計的散列函數是這樣的把關鍵字串中的每一個字符按其所在位置分別將其ASCII值乘以一個不同的數然後把這些值相加的和去對n求余余數即為散列表中的位置函數如下
int Hash (char key[])
{
return (int)(key[]+key[]*+key[]*)%n;
}
我們可以設計一個程序來看看用這個散列函數得到的所有關鍵字映射到區間的位置
#include
#define n file://先 用來代入我們可以用依次代入驗證
int Hash (char key[])
{
return (int)(key[]+key[]*+key[]*)%n;
file://此 處我用了系數和你也可以用其他的數代入看有沒有更好的系數
}
void main()
{
char s[][]={PALLAPPAMMAPPATPETSETSATTATBAT};
// 以上用<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23624.html
