2011計算機等考二級公共基礎(chǔ)知識講義：第1章(7)

　　點擊進入：2011計算機等考二級公共基礎(chǔ)知識講義匯總>>

　　1.7 查找技術(shù)

　　查找：根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素。

　　查找結(jié)果：(查找成功：找到;查找不成功：沒找到。)

　　平均查找長度：查找過程中關(guān)鍵字和給定值比較的平均次數(shù)。

　　1、順序查找

　　基本思想：從表中的第一個元素開始，將給定的值與表中逐個元素的關(guān)鍵字進行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒有要找的元素，查找不成功。

　　在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進行比較，最壞情況下需要比較n次。

　　順序查找一個具有n個元素的線性表，其平均復(fù)雜度為O(n)。

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

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

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

　　2、二分法查找

　　思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止。

　　前提：必須在具有順序存儲結(jié)構(gòu)的有序表中進行。

　　查找過程：

　　1)若中間項(中間項mid=(n-1)/2，mid的值四舍五入取整)的值等于x，則說明已查到;

　　2)若x小于中間項的值，則在線性表的前半部分查找;

　　3)若x大于中間項的值，則在線性表的后半部分查找。

　　特點：比順序查找方法效率高。最壞的情況下，需要比較log2n次。

　　二分法查找只適用于順序存儲的線性表，且表中元素必須按關(guān)鍵字有序(升序)排列[注釋1] 。對于無序線性表和線性表的鏈式存儲結(jié)構(gòu)只能用順序查找。在長度為n的有序線性表中進行二分法查找，其時間復(fù)雜度為O(log2n)。（注釋1：允許相鄰元素值相等。）

　　1.8 排序技術(shù)

　　排序是指將一個無序序列整理成按值非遞減順序排列的有序序列，即是將無序的記錄序列調(diào)整為有序記錄序列的一種操作。

　　1、交換類排序法(方法：冒泡排序，快速排序)。

　　2、插入類排序法(方法：簡單插入排序，希爾排序)。

　　3、選擇類排序法(方法：簡單選擇排序，堆排序)。

　　總結(jié)：各種排序法比較

　　本章應(yīng)考點撥：本章內(nèi)容在筆試中會出現(xiàn)5-6個題目，是公共基礎(chǔ)知識部分出題量比較多的一章，所占分值也比較大，約10分。

　　相關(guān)推薦：

　　2011計算機等考二級公共基礎(chǔ)知識要點匯總

　　2010年9月計算機等級考試成績查詢時間匯總

　　2011年上半年計算機等級考試報名時間匯總