查看匯總：2014年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)總結(jié)匯總
查找技術(shù)
考點(diǎn)9 順序查找
考試鏈接：
考點(diǎn)9在筆試考試中考核幾率在30%，一般出現(xiàn)選擇題中，分值為2分，讀者應(yīng)該具體掌握順序查找的算法。
查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中查找某個(gè)指定的元素。從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功;若線性表中所有的元素都與被查找元素進(jìn)行了比較但都不相等，則表示查找失敗。
在下列兩種情況下也只能采用順序查找：
(1)如果線性表為無(wú)序表，則不管是順序存儲(chǔ)結(jié)構(gòu)還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，只能用順序查找。
(2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。
考點(diǎn)10 二分法查找
考試鏈接：
考點(diǎn)10在筆試考試中考核幾率為30%，一般出現(xiàn)填空題中，分值為2分，考核比較多查找的比較次數(shù)，讀者應(yīng)該具體掌握二分查找法的算法。
二分法只適用于順序存儲(chǔ)的，按非遞減排列的有序表，其方法如下：
設(shè)有序線性表的長(zhǎng)度為n，被查找的元素為i，
(1)將i與線性表的中間項(xiàng)進(jìn)行比較;
(2)若i與中間項(xiàng)的值相等，則查找成功;
(3)若i小于中間項(xiàng)，則在線性表的前半部分以相同的方法查找;
(4)若i大于中間項(xiàng)，則在線性表的后半部分以相同的方法查找。
疑難解答：二分查找法適用于哪種情況?
二分查找法只適用于順序存儲(chǔ)的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列(即從小到大，但允許相鄰元素值相等)。
這個(gè)過程一直進(jìn)行到查找成功或子表長(zhǎng)度為0為止。
對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。
相關(guān)推薦：
計(jì)算機(jī)等級(jí)考試合格標(biāo)準(zhǔn)
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |