某順序存儲(chǔ)的表格,其中有90000個(gè)元素,已按關(guān)鍵字遞增有序排列,現(xiàn)假定對(duì)各個(gè)元素進(jìn)行查找的概率是相同的,并且各個(gè)元素的關(guān)鍵字皆不相同。
用順序查找法查找時(shí),平均比較次數(shù)約為__(1)__,最大比較次數(shù)為__(2)__。
現(xiàn)把90000個(gè)元素按排列順序劃分成若干組,使每組有g(shù)個(gè)元素(最后一組可能不足g個(gè))。查找時(shí),先從第一組開始,通過比較各組的最后一個(gè)元素的關(guān)鍵字,找到欲查找的元素所在的組,然后再用順序查找法找到欲查找的元素。在這種查找法中,使總的平均比較次數(shù)最小的g是__(3)__,此時(shí)的平均比較次數(shù)是__(4)__。當(dāng)g的值大于等于90000時(shí),此方法的查找速度接近于__(5)__。
A.25000
B.30000
C.45000
D.90000
您可能感興趣的試卷
你可能感興趣的試題
A.G的列數(shù)與行數(shù)相同
B.G的列的上界與G的行的上界相同
C.G的列的上界與G的行的下界相同
D.G的列的上下界與G的行的上下界相同
最新試題
快速排序的最壞情況如何改進(jìn)?
鏈表中為什么要引入頭結(jié)點(diǎn)?
將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表,其最少的比較次數(shù)是(),最多的比較次數(shù)是()。
某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問順序是()。
在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列Q[0…M-1],頭尾指針分別是front和rear,判斷隊(duì)空的條件為(),判斷隊(duì)滿的條件為()。
設(shè)有一稀疏圖G,則G采用()存儲(chǔ)較省空間。
對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的序列,如果采用插入排序,所需的最大比較次數(shù)是(),所需的最大移動(dòng)次數(shù)是()。
對(duì)于一個(gè)具有n個(gè)元素序列如果采用快速排序,那么所需的最少比較次數(shù)是(),所需的最大比較次數(shù)是(),且此序列為()序列。
m階B-樹具有k個(gè)后繼的非葉子結(jié)點(diǎn)含有k-1個(gè)鍵值。
如果無向圖G有n個(gè)頂點(diǎn),那么G的一棵生成樹有且僅有()條邊。