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

　　點(diǎn)擊進(jìn)入：2011計(jì)算機(jī)等考二級(jí)公共基礎(chǔ)知識(shí)講義匯總>>

　　1.7 查找技術(shù)

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

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

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

　　1、順序查找

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

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

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

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

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

　　2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也只能用順序查找。

　　2、二分法查找

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

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

　　查找過程：

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

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

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

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

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

　　1.8 排序技術(shù)

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

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

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

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

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

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

　　相關(guān)推薦：

　　2011計(jì)算機(jī)等考二級(jí)公共基礎(chǔ)知識(shí)要點(diǎn)匯總

　　2010年9月計(jì)算機(jī)等級(jí)考試成績查詢時(shí)間匯總

　　2011年上半年計(jì)算機(jī)等級(jí)考試報(bào)名時(shí)間匯總