2014年計算機二級公共基礎(chǔ)知識總結(jié)第一章(5)

　　查看匯總：2014年計算機二級公共基礎(chǔ)知識總結(jié)匯總

　　查找技術(shù)

　　考點9 順序查找

　　考試鏈接：

　　考點9在筆試考試中考核幾率在30%，一般出現(xiàn)選擇題中，分值為2分，讀者應(yīng)該具體掌握順序查找的算法。

　　查找是指在一個給定的數(shù)據(jù)結(jié)構(gòu)中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功;若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。

　　在下列兩種情況下也只能采用順序查找：

　　(1)如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，只能用順序查找。

　　(2)即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找。

　　考點10 二分法查找

　　考試鏈接：

　　考點10在筆試考試中考核幾率為30%，一般出現(xiàn)填空題中，分值為2分，考核比較多查找的比較次數(shù)，讀者應(yīng)該具體掌握二分查找法的算法。

　　二分法只適用于順序存儲的，按非遞減排列的有序表，其方法如下：

　　設(shè)有序線性表的長度為n，被查找的元素為i，

　　(1)將i與線性表的中間項進行比較;

　　(2)若i與中間項的值相等，則查找成功;

　　(3)若i小于中間項，則在線性表的前半部分以相同的方法查找;

　　(4)若i大于中間項，則在線性表的后半部分以相同的方法查找。

　　疑難解答：二分查找法適用于哪種情況?

　　二分查找法只適用于順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列(即從小到大，但允許相鄰元素值相等)。

　　這個過程一直進行到查找成功或子表長度為0為止。

　　對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。

　　相關(guān)推薦：

　　計算機等級考試合格標準

　　2014年計算機等考上機六大注意事項

　　考試吧：2014年3月計算機等考真題及答案解析專題