以下為插入排序（insertion sort）的程式碼，A 是一個整數陣列，請問以下那個 A 陣列會讓 line5 被執行最少次？ 1. INSERTION-SORT (A) 2. for j = 2 to A.leng…

Question

以下為插入排序（insertion sort）的程式碼，A 是一個整數陣列，請問以下那個 A 陣列會讓 line5 被執行最少次？
1. INSERTION-SORT (A)
2.   for j = 2 to A.length
3.       key = A [j]
4.       i = j - 1
5.       while i > 0 and A[i] > key
6.           A [i + 1] = A[i]
7.           i = i - 1
8.       A[i +1] = key
(A) A = [1,2,3,4,5,6,7,8]
(B) A = [8,7,6,5,4,3,2,1]
(C) A = [7,5,3,1,2,4,6,8]
(D) A = [2,3,2,3,2,3,2,3]

Accepted Answer

正確答案為 A。 插入排序法在處理已遞增排序的陣列時為最佳情況，while 迴圈的條件判斷次數最少。 (A) 陣列已遞增排序，為插入排序法的最佳情況。每次外層迴圈執行時，內層 while 條件判斷一次即為假，不進入迴圈主體，總執行次數最少。 (B) 陣列遞減排序，為最差情況。每次內層 while 迴圈皆需執行到 i=0 才停止，條件判斷次數最多。

以下為插入排序（insertion sort）的程式碼，A 是一個整數陣列，請問以下那個 A 陣列會讓 line5 被執行最少次？ 1. INSERTION-SORT (A) 2. for j = 2 to A.length 3. key = A [j] 4. i = j - 1 5. while i > 0 and A[i] > key 6. A [i + 1] = A[i] 7. i = i - 1 8. A[i +1] = key

逐選項解析

立即註冊,看完整詳解

資訊科技相關題目

想練更多資訊科技考古題？

以下為插入排序（insertion sort）的程式碼，A 是一個整數陣列，請問以下那個 A 陣列會讓 line5 被執行最少次？ 1. INSERTION-SORT (A) 2. for j = 2 to A.length 3. key = A [j] 4. i = j - 1 5. while i > 0 and A[i] > key 6. A [i + 1] = A[i] 7. i = i - 1 8. A[i +1] = key

逐選項解析

立即註冊,看完整詳解

資訊科技 相關題目

想練更多資訊科技考古題？

資訊科技相關題目