對含有n個互不相同元素的集合同時找最大元和最小元至少需進行多少次比較?
若對具有n個元素的有序的順序表和無序的順序表分別進行順序查找試在下述兩種情況下分別討論兩者在等概率時的平均查找長度
()查找不成功即表中無關鍵字等於給定值K的記錄
()查找成功即表中有關鍵字等於給定值K的記錄
畫出對長度為的有序的順序表進行二分查找的判定樹並指出在等概率時查找成功的平均查找長度以及查找失敗時所需的最多的關鍵字比較次數
為什麼有序的單鏈表不能進行折半查找?
設有序表為(abcefgijkpq)請分別畫出對給定值bg和n進行折半查找的過程
將(for case while class protected virtual public private do template const if int)中的關鍵字依次插入初態為空的二叉排序樹中請畫出所得到的樹T然後畫出刪去for之後的二叉排序樹T若再將for 插入T中得到的二叉排序樹T是否與T相同?最後給出T的先序中序和後序序列
對給定的關鍵字集合以不同的次序插入初始為空的樹中是否有可能得到同一棵二叉排序樹?
將二叉排序樹T的先序序列中的關鍵字依次插入一空樹中所得和二叉排序樹T與T否相同?為什麼?
設二叉排序樹中關鍵字由至的整數構成現要查找關鍵字為的結點下述關鍵字序列哪一個不可能是在二叉排序樹上查找到的序列?
(a)
(b) ;
(c) ;
(d)
設二叉排序樹中關鍵字互不相同則其中最小元必無左孩子最大元必無右孩子此命題是否正確?最小元和最大元一定是葉子嗎?一個新結點總是插在二叉排序樹的某葉子上嗎?
在一棵m階的B樹中當將一關鍵字插入某結點而引起該結點的分裂時此結點原有多少個關鍵字?若刪去某結點中的一個關鍵字而導致結點合並時該結點中原有幾個關鍵字?
在一棵B樹中空指針數總是比關鍵字數多一個此說法是否正確?請問包含個關鍵字的階B樹(即樹)最多有幾個結點?最少有幾個結點?畫出這兩種情況的B樹
從空樹開始依次輸入畫出建立樹的過程並畫出刪除和後的B樹狀態
畫出依次插入zvopwy到圖(h)所示的階B樹的過程
在含有n個關鍵字的m階B樹中進行查找至多讀盤多少次?完全平衡的二叉排序樹的讀盤次數大約比它大多少倍?
為什麼在內存中使用的B樹通常是階的而不使用更高階的B樹?
為什麼二叉排序樹長高時新結點總是一個葉子而B樹長高時新結點總是根?哪一種長高能保證樹平衡?
已知關鍵字序列為(PALLAPPAMMAPPATPETSETSATTATBAT)試為它們設計一個散列函數將其映射到區間[n]上要求碰撞盡可能的少這裡n=
對於一組給定的固定不變的關鍵字序列有可能設計出無沖突的散列函數H此時稱H為完備的散列函數(perfect hashing function)若H能無沖突地將關鍵字完全填滿散列表則稱H是最小完備(minimal perfect)的散列函數通常找完備的散列函數非常困難找最小完備的散列函數就更困難請問
()若h是已知關鍵字集合K的完備的散列函數若要增加一個新的關鍵字到集合K一般情況下H還是完備的嗎?
()已知關鍵字集合為()散列函數為H(x)=(x+)/請問H是完備的嗎?它是最小完備的嗎?
()考慮由字符串構成的關鍵字集合(BretJaneShirleyBryceMichelleHeather)試為散列表[] 設計一個完備的散列函數(提示考慮每個字符串的第個字符即s[])
設散列函數為h(key)=key%解決沖突的方法為線性探查表中用表示空單元若刪去散列表HT中的(即令HT[]=)之後在表HT中查找將會發生什麼?若將刪去的表項標記為查找時探查到繼續向前搜索探查到時終止搜索請問用這種方法刪後能否正確地查找到?
┌──┬──┬──┬──┬───────────┬─┐
HT│ │ │ │ │ │ │
└──┴──┴──┴──┴───────────┴─┘
From:http://tw.wingwit.com/Article/program/sjjg/201311/23578.html
