|
1.順序查找法的平均查找長(cháng)度為_(kāi)___；折半查找法的平均查找長(cháng)度為_(kāi)___；哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長(cháng)度為_(kāi)___。
2.在各種查找方法中，平均查找長(cháng)度與結點(diǎn)個(gè)數n無(wú)關(guān)的查找方法是____。
3.折半查找的存儲結構僅限于____，且是____。
4. 假設在有序線(xiàn)性表A[1..20]上進(jìn)行折半查找，則比較一次查找成功的結點(diǎn)數為_(kāi)___，則比較二次查找成功的結點(diǎn)數為_(kāi)___，則比較三次查找成功的結點(diǎn)數為_(kāi)___，則比較四次查找成功的結點(diǎn)數為_(kāi)___，則比較五次查找成功的結點(diǎn)數為_(kāi)___，平均查找長(cháng)度為_(kāi)___。
5. 對于長(cháng)度為n的線(xiàn)性表，若進(jìn)行順序查找，則時(shí)間復雜度為_(kāi)___；若采用折半法查找，則時(shí)間復雜度為_(kāi)___；
6．已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當用折半查找90時(shí)，需進(jìn)行 次查找可確定成功；查找47時(shí)，需進(jìn)行 次查找成功；查找100時(shí)，需進(jìn)行 次查找才能確定不成功。
7．二叉排序樹(shù)的查找長(cháng)度不僅與 有關(guān)，也與二叉排序樹(shù)的 有關(guān)。
8．一個(gè)無(wú)序序列可以通過(guò)構造一棵 樹(shù)而變成一個(gè)有序樹(shù)，構造樹(shù)的過(guò)程即為對無(wú)序序列進(jìn)行排序的過(guò)程。
9．平衡二叉排序樹(shù)上任一結點(diǎn)的平衡因子只可能是 、 或 。
10． 法構造的哈希函數肯定不會(huì )發(fā)生沖突。
11．在散列函數H(key)=key%p中，p應取____。
12．在散列存儲中，裝填因子a的值越大，則____；a的值越小，則____。
江蘇農信社招聘網(wǎng) 參考答案
1. （n+1）/2 、((n+1)*log2(n+1))/n-1 、1+a（a為裝填因子）
2. 哈希表查找法 3. 順序存儲結構、有序的
4. 1、2、4、8、5、3．7
（依題意，構造一棵有序二叉樹(shù)，共12個(gè)結點(diǎn)，第一層1個(gè)結點(diǎn)，第二層2個(gè)結點(diǎn)，第三層4個(gè)結點(diǎn)，第四層5個(gè)結點(diǎn)，則：ASL=（1*1+2*2+3*4+4*5）/12=37/12）
5. O（n）、O(log2n) 6．2、4、3 7．結點(diǎn)個(gè)數n、生成過(guò)程
8．二叉排序樹(shù) 9．0、1、-1 10．直接定址
11．素數
12．存取元素時(shí)發(fā)生沖突的可能性就越大、存取元素時(shí)發(fā)生沖突的可能性就越小
|
