國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

Function selectionSort(Type data[1..n])

Index i, j, max // 定義索引

    For i←1 to n do

min←i

        For j←i+1 to n do

If data[j] < data[min] then

min←j

Exchange data[i] and data[min]

End

void Select_Sort(int data[ ], int n) { // data[ ] 是欲排序的資料，n 是陣列大小

          int i, j, min, temp;

          for(i = 0; i < n-1; i++){

                    min = i; // 範圍內最左的鍵值索引

                    // 選擇出範圍內最小的鍵值，將它與範圍內最左的鍵值交換

                    for(j = i+1; j < n; j++)

                              if(data[j] < data[min]) // 右鍵值小於左鍵值

                                        min = j; // 最小鍵值索引為右鍵值索引

                    temp = data[min]; data[min] = data[i]; data[i] = temp;

}

}

五、考慮設計中式象棋 (如圖) 電腦程式系統：（每小題5分，共10分）

(一)請設計一資料結構使能隨時表示出棋盤現狀 (current state)，包含所有棋子的位置、有那些棋子在棋盤上。

(二)寫出一演算法能產生「象」或「相」在任意位置之下一步可前往且合規則的所有位置 (next feasible positions)，注意，務必考慮其他棋子阻礙的因素。「象」或「相」的移動規則：(1)田字形的對角移動；(2)田字正中央有棋子時，不能移動前往。

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

30

31

32

帥

仕

仕

相

相

俥

俥

傌

傌

炮

炮

兵

兵

兵

兵

兵

0

空

void move(int i, int j, int direction) { // i, j 棋子座標，direction 移動方向

int temp = board[i][j]; // 舊棋子位置

if(board[i][j] == 4 || board[i][j] == 5 || board[i][j] == 20 || board[i][j] == 21) { // 如果是象或相

// 田字正中央有棋子時，不能移動前往

if((board[i-1][j-1] != NULL && i-1 != 0 && j-1 != 0) ||

(board[i-1][j+1] != NULL && i-1 != 0 && j+1 != 8) ||

(board[i+1][j-1] != NULL && i+1 != 9 && j-1 != 0) ||

(board[i+1][j+1] != NULL && i+1 != 9 && j+1 != 8)) {

        exit(1); // 不能移動前往

}

if(board[i-2][j-2] != NULL && direction = 0) { // 不是邊界，並且往左上角移動

board[ i-2][j-1] = temp; // 新棋子位置

board[i][j] = 0; // 舊棋子位置清空

}

else if(board[i-2][j+2] != NULL && direction = 1) { // 不是邊界，並且往右上角移動

board[ i-2][j-1] = temp;

board[i][j] = 0;

}

else if(board[i+2][j+2] != NULL && direction = 2) { // 不是邊界，並且往右下角移動

board[i+2][j+1] = temp;

board[i][j] = 0;

}

else if(board[i+2][j-2] != NULL && direction = 3) { // 不是邊界，並且往左下角移動

board[ i+2][j-1] = temp;

board[i][j] = 0;

}

}

}

四、迴文 (palindrome) 乃是一個字串不論從左到右或從右到左看結果一模一樣，例如 “油麻地遍地麻油”、“人人為我、我為人人”、“Fall leaves as soon as leaves fall” 等。

(二)請寫出演算法以測試輸入的字串 (字串的長度不超過100個字) 是否為迴文。（10分）

CreateStack( );

while(input not end) {

x←read next character; // 從左自右逐一讀取字元

push(x);

}

scan string again;

while(input not end) {

x←read next character; // 從左自右逐一讀取字元

y = pop( ); // 取出堆疊的字元

if(x≠y) {

print “not palindrome”;

exit;

}

}

print “is palindrome”;

一、請參考圖1：

(三)假設圖1代表 heap 上各個節點 (node) 及其相互指向的關係。p、q、r 三節點代表全域變數 (global variables)，其他的節點代表 heap 上的記憶體區塊。如果 p→a 的指標被消除，那些節點會變成無用的垃圾節點？你必須詳細描述尋找垃圾節點的方法及所需之資料結構。你的演算法只能從 a 節點出發，它必須指出所有的垃圾節點，並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演算法必須在每一個節點儲存那些資料？（15分）

五、若處理的資料，其數值均不同且已知均為1到100之間的整數或小數。若 K≦X＜K+1，集合 Lx 代表數值在 [K, K-1] 間全部資料，1≦K≦99, K 為整數，資料結構支援下列功能。

1.Insert(X)：增加 X，若 X 不存在 Lx 中。

2.Delete(X)：移除 X，若 X 存在 Lx 中。

3.List(X)：將 Lx 中的資料全部依序印出。

設計一資料結構滿足在最差情況的條件分析 (Worst Case Analysis)，每個功能的執行時間要求為：Insert(X) and Delete(X) 須在 O(log|Lx|) 時間內完成，List(X) 則須在 O(|Lx|) 時間內完成。請說明設計的資料結構為何？並解釋其執行時間為何滿足需求？（15分）

三、(一)請說明使用何種資料結構及其演算法，可有效判斷一運算式 (expression)中的巢狀 (nested) 括號是否正確配對 (matched)。（10分）

(二)請以兩個運算式實例 {A*[B-(C+D)+8]-16} 及 {A+[B-(C+5])}，分別說明此演算法判斷的過程及結果。（10分）

（注意：未說明判斷的過程，不予計分）

init.

StackA, StackB is empty;

while(scan expression left to right And not EOF) {

x←read( );

if(x is 左括號)

push StackA(x);

}

while(scan expression right to left And not EOF) {

y←read( );

if(y is 右括號)

    push StackB(y);

}

}

while(StackA And StackB not EOF) {

x←pop(StackA);

y←pop(StackB);

if(x 與 y 是同一類型的左右括號)

    output “Match”;

else {

    output “Not Match”;

}

}

if(StackA and StackB empty)

output “Match”;

else

output “Not Match”;

(

[

{

)

]

}

(

[

{

]

)

}

一、假設 A[1: n] 是一個矩陣，存有 n 個不同的整數，且已依序從小到大排列。給定一個整數 s，設計一個線性時間 (linear time) 的演算法，找出在 A[1: n] 中是否存在兩個相異之 A[i] 和 A[j]，使得 A[i]+A[j] = s。若存在，則印出任一組符合條件之 i 和 j；若不存在，則印出0。（須詳述或證明所設計程式之正確性及其計算複雜度，否則不計分）（25分）

#include <iostream>

using namespace std;

int A[ ] = {1, 3, 5, 7, 9};

struct node {

          int i;

          int j;

          struct node* next;

};

typedef struct node* NODEPTR;

// 印出所有符合 A[i]+A[j] = s 的資料

void printlist(NODEPTR head) {

    NODEPTR ptr = head;

    while(ptr != NULL) {

        cout << "A[" << ptr->i << "] = " << A[ptr->i] << ", ";

        cout << "A[" << ptr->j << "] = " << A[ptr->j] << endl;

        ptr = ptr->next;

    }

    cout << endl;

}

int main( ) {

    NODEPTR head, tail, prev;

    head = tail = prev = (NODEPTR)malloc(sizeof(node));

    int s = 12;

    int n = 5; // 5筆資料

    int i = 0;

    int j = n-1;

    bool check = false; // 檢查 A[i]+A[j] = s 是否存在

    while(i < n-1) {

        if(i == j) {

            break; // 結束

        }

        if(A[i]+A[j] > s) { // j 往左移

            j--;

        }

        else if(A[i]+A[j] < s) {// i 往右移

            i++;

        }

        else if(A[i]+A[j] == s) { // 找到 A[i]+A[j] = s

            check = true;

            tail->i = i;

            tail->j = j;

            tail->next = (NODEPTR)malloc(sizeof(node));

            prev = tail;

            tail = tail->next;

            i++;

            continue;

        }

    }

    if(check == false) { // 如果 A[i]+A[j] = s 存在

        printf("0\n");

    }

    else {

        prev->next =  NULL;

        cout << "A[" << head->i << "] = " << A[head->i] << ", ";

        cout << "A[" << head->j << "] = " << A[head->j] << endl;

        // printlist(head);

    }

    return 0;

}

索引

0

1

2

3

4

值

1

3

5

7

9

i

→

←

j

一、考慮數字1到 n，若將其順序重新排置，每個排列順序都稱作一個排列或置換 (Permutation)，例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1到 n 的排列視為一個順序的映射 P，則前述例子可表示為 P(5) = 1、P(1) = 2、P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在一個數字1到 n 的排列 P 中，若一對數字 i 和 j，1 ≦ i < j ≦ n，P( j) < P(i)，也就是在排列 P 中較大的數字 j 出現在較小的數字 i 左邊(前面)，我們稱此對數字為反向 (Inversion)，而排列 P 的反向數 (Inversion number) 則定義為排列 P 中反向的總數量。請回答下列問題：

    (一)數字1到 n 的何種排列會有最大的反向數？最大反向數是多少？（5分）

    (二)若給定一個數字1到 n 的排列 P，請提出一個線性遞迴 (Linear Recursive) 的方式來算出排列 P 的反向數，並提供虛擬碼 (Pseudo-code) 與時間複雜度分析。（10分）

P(j)

P(i)

1

2

3

4

5

5

4

3

2

1

j

i

#include <iostream>

using namespace std;

int Inversion(int *A, int n, int j, int i) {

    cout << "j = " << j << ", i = " << i << endl;

    if(j == n) {

        return 0;

    }

    else if(i == n) {

        return Inversion(A, n, j+1, j+2);

    }

    if(A[j] > A[i]) {

        return Inversion(A, n, j, i+1)+1;

    }

    else if(A[j] <= A[i]) {

        return Inversion(A, n, j, i+1);

    }

}

int main( ) {

    int A[ ] = {5, 4, 3, 12, 1};

    int n = 5;

    int count = 0;

    cout << Inversion(A, n, 0, 1) << endl;

    return 0;

}

三、一個工廠有 n 台機器 M₁, M₂, …, M_n 及 k 份工作 J₁, J₂, …, J_k，每份工作都有其所需的執行時間 T(J₁), T(J₂), …,T(J_k)。每一台機器一次只能執行一份工作，每份工作只能交給一台機器執行，n 台機器可同時執行n 份不同的工作。

(一)請設計一個 Greedy (貪婪) 的演算法，來解決工作排程的問題，使得完成 k 份工作的時間最短。（15分）

(二)此 Greedy 演算法適合使用何種資料結構來完成？（5分）

(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5分）

二、假設收銀機內銅板的集合 S = {$50, $20, $20, $15, $10, $2, $1, $1, $1}，而預計找錢給顧客的金額 W = $75。(一)請設計一個 Greedy (貪婪) 的演算法，來解決找錢給顧客的問題，使得找給顧客金額 W 所使用的銅板數量最少，並依此 Greedy 的演算法列出找給顧客金額 W = $75 的過程。（15分）(二)此 Greedy 演算法適合使用何種資料結構來完成。（5分）(三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5分）

#include <stdio.h>

int main( ) {

    int coin[ ] = {50, 20, 20, 15, 10, 2, 1, 1, 1};

    int sum = 75;

    int amount = 0;

    for(int i = 0; i < 9; i++) {

        int cnt = 0;

        if(sum >= coin[i]) {

            sum = sum-coin[i];

            amount += 1;

            cnt += 1;

            printf("找回%d元銅板%d個\n", coin[i], cnt);

        }

        else {

            i++;

        }

    }

    printf("總共使用%d個銅板\n", amount);

    return 0;

}

五、(一)如下圖設背包限重100，有 A、B、C、D、E 共五個不可分割物件，請 問依貪婪策略 (Greedy Algorithm)，0_1整數背包問題 (knapsack problem) / 貨物裝載問題 (cargo loading problem) 其最大利益為何？其對應的0_1整數規劃為何？（20分）

    (二)有 A、B、C、D、E 共五個可分割物件，請問依貪婪策略，0_1 分數背包其最大利益為何？（10分）

物件

重量

利益

利益/重量

C

30

66

2.2

A

10

20

2

B

20

30

1.5

E

50

60

1.2

D

40

40

1

三、7個工作的利潤及處理的最後期限如下表所示，並假設每個工作的處理時間均為一個時間單位，請求出最適排程及最大利潤 (maximal profit) 為何？（20分）

工作編號

1

2

3

4

5

6

7

利潤

40

15

60

20

45

10

55

最後期限

2

4

3

2

1

3

1

工作編號

3

7

5

1

4

2

6

利潤

60

55

45

40

20

15

10

最後期限

3

1

1

2

2

4

3

工作編號

3

7

5

1

4

2

6

利潤

60

55

45

40

20

15

10

最後期限

1

1

1

2

2

4

3

工作編號

1

4

2

6

利潤

40

20

15

10

最後期限

2

2

4

3

工作編號

2

6

利潤

15

10

最後期限

4

3

工作編號

利潤

最後期限

工作編號

7

5

1

4

3

6

2

利潤

55

45

40

20

60

10

15

最後期限

1

1

2

2

3

3

4

工作編號

7

5

1

4

3

6

2

利潤

55

45

40

20

60

10

15

最後期限

1

1

2

2

3

3

4

工作編號

1

4

3

6

2

利潤

40

20

60

10

15

最後期限

2

2

3

3

4

工作編號

3

6

2

利潤

60

10

15

最後期限

3

3

4

工作編號

2

利潤

15

最後期限

4