二級c語言考試基礎(chǔ)知識--第1章數(shù)據(jù)結(jié)構(gòu)與算法-資料下載頁
2025-08-22 08:05本頁面
【正文】 兩種情況下也只能采用順序查找：（1）如果線性表為無序表，則不管是順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，只能用順序查找。（2）即使是有序線性表，如果采用鏈式存儲結(jié)構(gòu)，也只能用順序查找?？键c 10二分法查找【考點精講】二分法查找，也稱拆半查找，是一種高效的查找方法。能使用二分法查找的線性表必須滿足兩個條件：用順序存儲結(jié)構(gòu)；線性表是有序表。在本書中，為了簡化問題，而更方便討論，“有序”是特指元素按非遞減排列，即從小到大排列，但允許相鄰元素相等。下一節(jié)排序中，有序的含義也是如此。對于長度為 n 的有序線性表，利用二分法查找元素 X 的過程如下。6步驟 1：將 X 與線性表的中間項比較：步驟 2：如果 X 的值與中間項的值相等，則查找成功，結(jié)束查找；步驟 3：如果 X 小于中間項的值，則在線性表的前半部分以二分法繼續(xù)查找；步驟 4： 如果 X 大于中間項的值，則在線性表的后半部分以二分法繼續(xù)查找。例如，長度為 8 的線性表關(guān)鍵碼序列為：[6，13，27，30，38，46，47，70]，被查元素為 38，首先將與線性表的中間項比較，即與第 4 個數(shù)據(jù)元素 30 相比較，38 大于中間項 30 的值，則在線性表[38，46，47，70]繼續(xù)查找；接著與中間項比較，即與第 2 個元素 46 相比較，38 小于 46，則在線性表[38]繼續(xù)查找，最后一次比較相等，查找成功。順序查找法每一次比較，只將查找范圍減少 1，而二分法查找，每比較一次，可將查找范圍減少為原來的一半，效率大大提高。對于長度為 ．的有序線性表，在最壞情況下，二分法查找只需比較 log．．次，而順序查找需要比較 ．次。考點 11排序【考點精講】．．．．．．（1）冒泡排序法首先，從表頭開始往后掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大于后面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往后移動，最后最大者到了線性表的最后。然后，從后到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若后面的元素小于前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最后最小者到了線性表的最前面。對剩下的線性表重復(fù)上述過程，直到剩下的線性表變空為止，此時已經(jīng)排好序。在最壞的情況下，冒泡排序需要比較次數(shù)為 ．（．－．）．。（2）快速排序法任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小于或等于基準元素的排序碼，右子序列的排序碼則大于基準元素的排序碼，然后分別對兩個子序列繼續(xù)進行排序，直至整個序列有序。2．插入類排序法：①簡單插入排序法，最壞情況需要 n(n1)/2 次比較；②希爾排序法，最壞情況需要 O()次比較。3．選擇類排序法：①簡單選擇排序法，最壞情況需要 n(n1)/2 次比較；②堆排序法，最壞情況需要 O(nlog2n)次比較。相比以上幾種(除希爾排序法外)，堆排序法的時間復(fù)雜度最小。7n ． 2n n．．．．． ．1．交換類排序法．．．．．．．．．．．．．．．．．．．n n 1 /2
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1