數(shù)據(jù)結(jié)構(gòu)第九章《集合》填空題及參考答案_跨考網(wǎng)

　1．順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為__ __次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為__ __?！救A中理工大學(xué) 2000 一、8 （2分）】

　　【參考答案】

　　n n+1
　　
　　2．在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為____。【北方交通大學(xué) 2001 二、2】

　　【參考答案】

　　4

　　3．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標(biāo)依次為__________?！?a target="_blank">中國人民大學(xué) 2001 一、2 （2分）】

　　【參考答案】

　　6,9,11,12

　　4．在有序表A[1..20]中，按二分查找方法進(jìn)行查找，查找長度為5的元素個(gè)數(shù)是________。【合肥工業(yè)大學(xué) 1999 三、9 （2分）】

　　【參考答案】

　　5

　　5．高度為4的3階b-樹中，最多有__________個(gè)關(guān)鍵字?！竞戏使I(yè)大學(xué) 2000 三、9 （2分）】

　　【參考答案】

　　26（第4層是葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)兩個(gè)關(guān)鍵字）

?6．在有序表A[1…20]中，按二分查找方法進(jìn)行查找，查找長度為4的元素的下標(biāo)從小到大依次是________?！竞戏使I(yè)大學(xué) 2000 三、10 （2分）】

　　【參考答案】

　　1,3,6,8,11,13,16,19

　　7．給定一組數(shù)據(jù){6，2，7，10，3，12}以它構(gòu)造一棵哈夫曼樹，則樹高為__________，帶權(quán)路徑長度WPL的值為__________?！?a target="_blank">南京理工大學(xué) 1997 三、4 （2分）】

　　【參考答案】

　　5,96

　　8．在一棵m階B-樹中,若在某結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂,則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是__________;若在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并,則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是__________?！局袊萍即髮W(xué) 1998 一、5 （3分）】【南京理工大學(xué) 2001 二、4 （3分）】

　　【參考答案】

　　m-1 m/2ù-1

　　9．己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當(dāng)用二分法查找90時(shí)，需__________次查找成功，47時(shí)__________成功，查100時(shí)，需__________次才能確定不成功?！灸暇├砉ご髮W(xué) 2000 二、7 （4.5分）】

　　【參考答案】

　　2,4,3

　　10．哈希表是通過將查找碼按選定的__(1)__和 __(2)__，把結(jié)點(diǎn)按查找碼轉(zhuǎn)換為地址進(jìn)行存儲的線性表。哈希方法的關(guān)鍵是_(3)__和 __(4)__。一個(gè)好的哈希函數(shù)其轉(zhuǎn)換地址應(yīng)盡可能__(5)__，而且函數(shù)運(yùn)算應(yīng)盡可能__(6)__?！?a target="_blank">青島大學(xué) 2000 六、2 （2分）】

　　【參考答案】

　　(1)哈希函數(shù)(2)解決沖突的方法 (3)選擇好的哈希函數(shù) (4)處理沖突的方法 (5)均勻(6)簡單