問題一： https://blog.yexca.net/archives/198
問題二： https://blog.yexca.net/archives/201
問題三：這篇文章
問題四： https://blog.yexca.net/archives/202
問題五： https://blog.yexca.net/archives/203

前言

這份考題是演算法題目，初次看到時，有種要放棄治療的感覺，但在做過一遍之後，會覺得難度沒有想像中大，但需要對既有演算法有較高的理解力。之所以說難度沒有想像中大，可能與我心中的預期有關吧，因為我以為可能要設計什麼演算法吧 (我想表達的意思是我並不覺得這份題目簡單)

本考題版權為東京科學大學所有，僅為方便觀看而引用，無任何營利行為

1

以兩種不同的演算法，使用 C 語言實作了將包含 n 個元素的整數陣列 a 依遞增順序排列的處理。請從選項中選出最適合填入程式 3.1、3.2 標題 A、B 的演算法名稱，並回答其符號。

「選項」

甲、選擇排序

乙、氣泡排序

丙、快速排序

丁、插入排序

• 程式 3.1：A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void sort_a(int a[], int n)
{
    int i, j, tmp;
    for(i=0; i<n-1; ++i){
        for(j=n-1; i<j; --j){
            if(a[j]<a[j-1]){
                tmp=a[j];
                a[j]=a[j-1];
                a[j-1]=tmp;
            }
        }
    }
}

• 程式 3.2：B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void sort_b(int a[], int n)
{
    int i, j, tmp;
    for(j=1; j<n; ++j){
        tmp=a[j];
        i=j-1;
        while(0<=i && tmp<a[i]){
            a[i+1]=a[i];
            --i;
        }
        a[i+1]=tmp;
    }
}

答案

這份題目是針對兩種排序演算法的程式碼，判斷其使用了哪種排序方法。A 是氣泡排序 (乙、氣泡排序)，B 是插入排序 (丁、插入排序)

2

關於堆積排序 (Heap Sort)，請回答下列問題。不過，n 為正整數。

a）請說明在二元堆積中，除了根節點以外的任何節點值應滿足的條件 (最大堆積條件或最小堆積條件皆可)。

b）當二元堆積儲存 n 個元素時，請以 n 的算式表示其樹高。樹高定義為根節點與葉節點之間路徑長度的最大值。

c）使用堆積排序法排列 n 個元素時，請從以下選項中分別選出其平均時間複雜度和最差時間複雜度的漸近評估最適合的答案。

甲、$O(1)$

乙、$O(\log n)$

丙、$O(n)$

丁、$O(n\log n)$

戊、$O(n^2)$

這份題目考堆積排序，第一小題要求寫出除了根節點以外的任何節點值應滿足的條件 (二元樹大頂堆或小頂堆擇一即可)；第二小題是寫出所構成的堆積二元樹的高度；第三小題則是選擇平均時間複雜度和最差情況複雜度。

答案

a

• 最大堆積條件：除了根節點以外的任何節點值，都必須小於或等於其父節點的值。
• 最小堆積條件：除了根節點以外的任何節點值，都必須大於或等於其父節點的值。

b

c

平均時間複雜度和最差時間複雜度：丁、$O(n\log n)$

3

設 $A=\{ A[0], A[1], \cdots, A[n-1] \}$ 為包含 n 個相異整數的陣列。對於小於 n 的非負整數 $i,j$，若 $i\lt j$ 且 $A[i]\gt A[j]$，則稱 $(i,j)$ 為 A 的反轉對，A 的反轉對數量則稱為 A 的反轉數。例如，陣列 $\{ 5,7,4,6 \}$ 的反轉對為 $(0,2),(1,2),(1,3)$，反轉數為 3。請回答下列問題。

a）請找出陣列 $\{ 1,0,4,3,2, \}$ 的反轉數。

b）在將集合 $\{ 1,2,\cdots,n \}$ 的所有元素排列而成的陣列 (元素數量為 n 個) 中，請指出反轉數最大的排列方式。此外，請以 n 的算式表示其反轉數。

c）使用氣泡排序法將集合 $\{ 1,2,\cdots,n \}$ 的所有元素排列而成的任意陣列 B (元素數量為 n 個) 依遞增順序排列。此時，「氣泡排序法中的 X 與陣列 B 的反轉數相等」的關係成立。請回答填入 X 的適當詞語，並簡潔地說明該關係成立的理由。

這份題目首先引入了「逆序」的概念 ( 宋浩老師的線性代數課程 有提到)，第一小題要求找出逆序數；第二小題要求找出最大逆序數；第三小題則是寫出氣泡排序法中的什麼與逆序數相等，並說明理由。

答案

• a

反轉數為 4，分別為 (1,0), (4,3), (4,2), (3,2)

• b

最大的反轉數是當排列方式為

對於 n 有 n-1 個，對於 n-1 有 n-2 個，以此類推。反轉數為其總和。

• c

X：交換次數

理由：因為每次交換操作都消除一個反轉對。

氣泡排序法是將每兩個元素進行比較，將順序不對的進行交換，一次操作就是消除一個反轉對。

4

程式 3.3 是以合併排序 (Merge Sort) 演算法為基礎，使用 C 語言實作將整數陣列依遞增順序排列的處理。請回答下列問題。

• 程式 3.3：合併排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int mergesort(int a[], int begin, int end, int w[]){
    int mid = (begin+end)/2;
    int i = begin, j = mid+1, k, c=0;
    
    printf("(%d, %d)\n", begin, end);
    if(begin<end){
        mergesort(a, begin, mid, w);
        mergesort(a, mid+1, end, w);
        
        for(k=begin; k<=end; ++k){
            if(mid<i){
                A
            }else if(end<j){
                B
            }else{
                /* ++c */
                if(a[i]<a[j]){
                    C
                }else{
                    D
                }
            }
        }
        for(k=begin; k<=end; ++k){
            E
        }
    }
    return 0;
}

a）請從選項中選出適當的程式碼，填入空格 A、B、C、D、E，以完成程式。不過，假設欲排序的陣列為 a，排序時用於工作區的陣列為 w，並且 mergesort 函式將以下兩行程式碼呼叫。

1
2

int a[5] = {3, 5, 1, 4, 2}, w[5];
mergesort(a, 0, 4, w);

• 選項

b）當使用 a）中所示的程式碼呼叫 mergesort 函式時，標準輸出的第 1 行會印出 $(0,4)$。請分別回答第 3 行、第 5 行、第 7 行會印出的內容。

c）我們希望找出 mergesort 函式在將引數指定的範圍內陣列元素排序前，執行程式 3.3 第 18 行的總次數 (元素比較次數)。因此，我們將第 17 行 (取消註解) 改為 ++c;，但這還不夠。若要將比較次數儲存到變數 count 中，且使用以下兩行程式碼呼叫，程式 3.3 應如何修改？

1
2

int a[5] = {3, 5, 1, 4, 2}, w[5];
int count = mergesort(a, 0, 4, w);

不過，不允許使用全域變數或靜態變數。此外，除了第 17 行的修改外，對程式進行的變更僅限於 3 次行替換。行替換指的是將某行的程式碼替換為 60 個字元以內 (不計算空白字元) 的其他程式碼。作答時，請按照下方「答案寫法 (範例)」所示，標註修改的行號和替換後的程式碼。假設第 17 行的註解已取消，請說明其他必要的修改。

• 「答案寫法 (範例)」

6行目：printf("hello\n");

30行目：c= end - begin + 1;

答案

a

• A: w[k] = a[j++]; 即 卯
• B: w[k] = a[i++]; 即 子
• C: w[k] = a[i++]; 即 子
• D: w[k] = a[j++]; 即 卯
• E: a[k] = w[k]; 即 庚

b

• 第 3 行: (0,1)

• 第 5 行: (1,1)

• 第 7 行: (3,4)

c

• 第 8 行: c += mergesort(a, begin, mid, w);

• 第 9 行: c += mergesort(a, mid + 1, end, w);

• 第 31 行: return c;

這份題目乍看之下挺嚇人的，但仔細閱讀後會發現考的內容其實還好，理解合併排序後應該就能比較容易解出來。順帶一提，因為我快把演算法忘光了，而且以前都是看動畫來理解 (比較直觀)，解題時很慶幸發現了 不錯的動畫演算法網站