108 年 國立成功大學工程科學系碩士班乙組《資料結構》

📄 試題原卷　免費註冊後即可對照原始考卷 PDF免費註冊

第 1 題12 分

Complete the functions of inserting a newnode into a doubly linked circular list and deleting one node from a doubly linked circular list.

void dinsert(node_pointer node, node_pointer newnode)
{
    (1);
    (2);
    (3);
    (4);
}

void ddelete(node_pointer node, node_pointer deleted)
{
    if (node == deleted) printf("Deletion of head node not permitted.\n");
    else {
        (1);
        (2);
        free(deleted);
    }
}

🖼️【此處有附圖，請對照原卷】

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 1 頁

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查「雙向循環鏈結串列」的節點插入與刪除。

每個節點具有兩個指標：

  • llink：指向前一個節點
  • rlink：指向後一個節點

循環鏈結串列的特性是：

  • 最後一個節點的 rlink 指向第一個節點
  • 第一個節點的 llink 指向最後一個節點

假設 dinsert(node, newnode) 表示將 newnode 插入在 node 的後方。

解題方法

插入新節點時，必須同時更新四個指標：

  1. newnode 的前方指向 node
  2. newnode 的後方指向原本 node 的後方節點
  3. 原後方節點的前方改指向 newnode
  4. node 的後方改指向 newnode

完整程式碼如下：

void dinsert(node_pointer node, node_pointer newnode)
{
    newnode->llink = node;
    newnode->rlink = node->rlink;
    node->rlink->llink = newnode;
    node->rlink = newnode;
}

刪除 deleted 節點時，讓其前方節點與後方節點直接相連：

void ddelete(node_pointer node, node_pointer deleted)
{
    if (node == deleted)
        printf("Deletion of head node not permitted.\n");
    else {
        deleted->llink->rlink = deleted->rlink;
        deleted->rlink->llink = deleted->llink;
        free(deleted);
    }
}

其中 node == deleted 表示欲刪除的是表頭節點，依題目規定不允許刪除。

指標關係檢查

插入後，應符合：

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 2 題8 分

Please write down every sequence of each step for finding the Minimum Cost Spanning Tree using Kruskal and Prim Algorithms.
🖼️【此處有附圖，請對照原卷】

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 2 頁

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

最小成本生成樹（MST）要連接圖中的所有頂點，且不能形成環。含 VV 個頂點的生成樹恰有 V−1V-1 條邊；本題圖中頂點為 a,b,c,d,e,f,h,ia,b,c,d,e,f,h,i，共 88 個，因此 MST 應有 77 條邊。

Kruskal 演算法依邊權重由小到大檢查，只有在加入後不形成環時才選取。Prim 演算法從一個起點開始，每一步選擇連接目前樹內與樹外頂點的最小權重邊。兩種方法都以「不形成環、逐步連通所有頂點」來建立 MST。

解題方法

圖中讀得 8 個頂點及 10 條加權邊：
a−b:5a-b:5、a−d:8a-d:8、a−c:9a-c:9、b−h:8b-h:8、c−e:10c-e:10、c−f:12c-f:12、d−f:14d-f:14、e−h:7e-h:7、e−i:6e-i:6、f−i:3f-i:3。

Kruskal 演算法

將邊依權重由小到大排列；權重相同的邊可任意排列。

次序邊權重判斷
1f−if-i3選取
2a−ba-b5選取
3e−ie-i6選取
4e−he-h7選取
5a−da-d8選取
6b−hb-h8選取
7a−ca-c9選取，加入後共有 77 條邊
8c−ec-e10略過，兩端已連通，加入會形成環
9c−fc-f12略過，兩端已連通，加入會形成環
10d−fd-f14略過，兩端已連通，加入會形成環

選取順序為

f−i, a−b, e−i, e−h, a−d, b−h, a−cf-i,\ a-b,\ e-i,\ e-h,\ a-d,\ b-h,\ a-c

其中權重同為 88 的 a−da-d 與 b−hb-h，先後次序可以交換。

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 3 題80 分

For the sequence: 33, 32, 23, 7, 5, 100, 46, 67, 20. Please write down every sequence of each step while applying Insertion Sort, Quick Sort, Interactive Merge Sort, Recursive Merge Sort, MAX Heap Sort and LSD Radix Sort (5%), then complete the Sort algorithms parts indicated by XXX (2%) (80%)

#define MAX-SIZE 1000/* maximum size of list plus one */
typedef struct {
    int key;
    /* other fields */
} element;
element list[MAX-SIZE];

void adjust(element list[], int root, int n)
{
    int child, rootkey;
    element temp;
    temp=list[root];
    rootkey=list[root].key;
    child=2*root;
    while (child <= n) {
        if ((child < n) && (list[child].key < list[child+1].key))
            child++;
        if (rootkey > list[child].key) break;
        else {
            XXXX_1;
            XXXX_2;
        }
    }
    list[child/2] = temp;
}

void heapsort(element list[], int n)
{
    int i, j;
    element temp;
    for (i=n/2; i>0; i--)
        XXXX_3;
    for (i=n-1; i>0; i--) {
        SWAP(list[1], list[i+1], temp);
        XXXX_4;
    }
}

void quicksort(element list[], int left, int right)
{
    int pivot, i, j;
    element temp;
    if (left < right) {
        i = left; j = right+1;
        pivot = list[left].key;
        do {
            do i++; while (XXXX_5);
            do j--; while (XXXX_6);
            if (i < j) SWAP(list[i], list[j], temp);
        } while (i < j);
        SWAP(list[left], list[j], temp);
        quicksort(XXXX_7);
        quicksort(XXXX_8);
    }
}

void merge(element list[], element sorted[], int i, int m, int n)
{
    int j, k, t;
    j = m+1;
    k = i;
    while (i<=m && j<=n) {
        if (list[i].key<=list[j].key)
            XXXX_9;
        else XXXX_10;
    }
    if (i>m) for (XXXX_11)
        sorted[k+t-j]= list[t];
    else for (XXXX_12)
        sorted[k+t-i] = list[t];
}

void merge_pass(element list[], element sorted[], int n, int length)
{
    int i, j;
    for (i=0; i<n-2*length; i+=2*length)
        merge(XXXX_13);
    if (i+length<n)
        merge(XXXX_14);
    else
        for (j=i; j<n; j++) sorted[j]= list[j];
}

void merge_sort(element list[], int n)
{
    int length=1;
    element extra[MAX-SIZE];
    while (length<n) {
        merge_pass(XXXX_15);
        length *= 2;
        merge_pass(XXXX_16);
        length *= 2;
    }
}

int rmerge(element list[], int lower, int upper)
{
    int middle;
    if (lower >= upper) return lower;
    else {
        middle = XXXX_17;
        return listmerge(XXXX_18);
    }
}

int listmerge(element list[], int first, int second)
{
    int start=n;
    while (first!=-1 && second!=-1) {
        if (list[first].key<=list[second].key) {
            /* key in first list is lower, link this
               element to start and change start to
               point to first */
            XXXX_19;
            start = first;
            XXXX_20;
        } else {
            /* key in second list is lower, link this
               element into the partially sorted list */
            XXXX_21;
            start = second;
            XXXX_22;
        }
    }
    if (first-1)
        list[start].link = second;
    else
        list[start].link = first;
    return list[n].link;
}

#define MAX_DIGIT 3
#define RADIX_SIZE 10
typedef struct list_node *list_pointer;
typedef struct list_node {
    int key[MAX_DIGIT];
    list_pointer link;
} list_node;

list_pointer radix_sort(list_pointer ptr)
{
    list_pointer front[RADIX_SIZE], rear[RADIX_SIZE];
    int i, j, digit;
    for (i=MAX_DIGIT-1; i>=0; i--) {
        for (j=0; j<RADIX_SIZE; j++)
            front[j]=rear[j]=NULL;
        while (ptr) {
            digit=ptr->key[i];
            if (!front[digit]) XXXX_23;
            else rear[digit]->link=ptr;
            XXXX_24;
            ptr=ptr->link;
        }
        /* reestablish the linked list for the next pass */
        ptr= NULL;
        for (j=RADIX_SIZE-1; j>=0; j--)
            if (front[j]) {
                XXXX_25;
                ptr=front[j];
            }
    }
    return ptr;
}

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題綜合考查六種排序法，以及堆積排序、快速排序、合併排序與 LSD 基數排序的程式填空。

排序方向以「由小到大」為一般標準；但題目給出的 radix_sort 在重建鏈結串列時，從 bucket 9 往 0 串接，因此實際結果是「由大到小」。

一、Insertion Sort

Insertion Sort 的想法是：左側視為已排序區，每次取右側第一個元素，插入左側適當位置。

原始序列：

33, 32, 23, 7, 5, 100, 46, 67, 2033,\ 32,\ 23,\ 7,\ 5,\ 100,\ 46,\ 67,\ 20

每次插入後：

  1. 插入 3232

    32, 33, 23, 7, 5, 100, 46, 67, 20

  2. 插入 2323

    23, 32, 33, 7, 5, 100, 46, 67, 20

  3. 插入 77

    7, 23, 32, 33, 5, 100, 46, 67, 20

  4. 插入 55

    5, 7, 23, 32, 33, 100, 46, 67, 20

  5. 插入 100100

    5, 7, 23, 32, 33, 100, 46, 67, 20

  6. 插入 4646

    5, 7, 23, 32, 33, 46, 100, 67, 20

  7. 插入 6767

    5, 7, 23, 32, 33, 46, 67, 100, 20

  8. 插入 2020

    5, 7, 20, 23, 32, 33, 46, 67, 100

時間複雜度：平均與最壞為 O(n2)O(n^2)，最佳為 O(n)O(n)；額外空間為 O(1)O(1)。

二、Quick Sort

程式採用：

  • pivot：區間最左側元素
  • i 從左往右找第一個 ≥pivot\geq pivot 的元素
  • j 從右往左找第一個 ≤pivot\leq pivot 的元素
  • 若 i<ji<j，交換兩者
  • 最後將 pivot 與 list[j] 交換

因此填空為：

XXXX_5：list[i].key < pivot
XXXX_6：list[j].key > pivot

第一次 partition

pivot =33=33：

原始：

33, 32, 23, 7, 5, 100, 46, 67, 20

交換 100100 與 2020：

33, 32, 23, 7, 5, 20, 46, 67, 100

pivot 與 2020 交換：

20, 32, 23, 7, 5, 33, 46, 67, 100

分成：

  • 左區間：20, 32, 23, 7, 5
  • 右區間：46, 67, 100

排序左區間

pivot =20=20：

20, 32, 23, 7, 5

交換 3232 與 55：

20, 5, 23, 7, 32

交換 2323 與 77：

20, 5, 7, 23, 32

pivot 與 77 交換：

7, 5, 20, 23, 32

接著排序 7, 5：

5, 7, 20, 23, 32

排序右區間

右區間為：

46, 67, 100

pivot =46=46，已符合分割結果：

46, 67, 100

再以 6767 為 pivot：

46, 67, 100

Quick Sort 各階段結果

33, 32, 23, 7, 5, 100, 46, 67, 20
20, 32, 23, 7, 5, 33, 46, 67, 100
7, 5, 20, 23, 32, 33, 46, 67, 100
5, 7, 20, 23, 32, 33, 46, 67, 100

填空：

XXXX_7：left, j-1
XXXX_8：j+1, right

完整遞迴呼叫為：

quicksort(list, left, j-1);
quicksort(list, j+1, right);

平均時間複雜度為 O(nlog⁡n)O(n\log n)，最壞為 O(n2)O(n^2)；遞迴堆疊平均為 O(log⁡n)O(\log n)。

三、Interactive Merge Sort

Iterative Merge Sort 每一輪將相鄰的已排序區段合併，區段長度依序為：

1, 2, 4, 8,…1,\ 2,\ 4,\ 8,\ldots

長度為 11 的區段合併

32, 33, 7, 23, 5, 100, 46, 67, 20

長度為 22 的區段合併

7, 23, 32, 33, 5, 46, 67, 100, 20

長度為 44 的區段合併

5, 7, 23, 32, 33, 46, 67, 100, 20

長度為 88 的區段合併

5, 7, 20, 23, 32, 33, 46, 67, 100

merge 的參數是：

merge(list, sorted, 起點, 左半結束位置, 右半結束位置);

填空：

XXXX_9：sorted[k++] = list[i++]
XXXX_10：sorted[k++] = list[j++]

剩餘元素拷貝：

XXXX_11：t=j; t<=n; t++
XXXX_12：t=i; t<=m; t++

兩個 merge_pass：

XXXX_13：list, sorted, i, i+length-1, i+2*length-1
XXXX_14：list, sorted, i, i+length-1, n-1

merge_sort 中：

XXXX_15：list, extra, n, length
XXXX_16：extra, list, n, length

完整核心程式：

while (length < n) {
    merge_pass(list, extra, n, length);
    length *= 2;
    merge_pass(extra, list, n, length);
    length *= 2;
}

時間複雜度為 O(nlog⁡n)O(n\log n)，額外空間為 O(n)O(n)。

四、Recursive Merge Sort

Recursive Merge Sort 先不斷切割，再由下而上合併。

第一次合併相鄰單一元素：

32, 33, 23, 7, 5, 100, 46, 67, 20
32, 33, 7, 23, 5, 100, 46, 67, 20

合併前四個元素：

7, 23, 32, 33, 5, 100, 46, 67, 20

右半部先合併：

7, 23, 32, 33, 5, 100, 46, 67, 20
7, 23, 32, 33, 5, 46, 67, 100, 20

最後合併：

5, 7, 23, 32, 33, 46, 67, 100, 20
5, 7, 20, 23, 32, 33, 46, 67, 100

填空：

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 4 題

Complete the following sorting functions by filling in the blanks.

Recursive Merge Sort

merge_pass(____);
length *= 2;

merge_pass(____);
length *= 2;
}
}

int rmerge(element list[], int lower, int upper)
{
    int middle;

    if (lower >= upper)
        return lower;
    else {
        middle = ____;
        return listmerge(____);
    }
}

int listmerge(element list[], int first, int second)
{
    int start = n;

    while (first != -1 && second != -1) {
        if (list[first].key <= list[second].key) {
            /* key in first list is lower, link this
               element to start and change start to
               point to first */
            ____;
            start = first;
            ____;
        }
        else {
            /* key in second list is lower, link this
               element into the partially sorted list */
            ____;
            start = second;
            ____;
        }
    }

    if (first == -1)
        list[start].link = second;
    else
        list[start].link = first;

    return list[n].link;
}

LSD Radix Sort

#define MAX_DIGIT 3
#define RADIX_SIZE 10

typedef struct list_node *list_pointer;

typedef struct list_node {
    int key[MAX_DIGIT];
    list_pointer link;
}

list_pointer radix_sort(list_pointer ptr)
{
    list_pointer front[RADIX_SIZE],
                 rear[RADIX_SIZE];
    int i, j, digit;

    for (i = MAX_DIGIT - 1; i >= 0; i--) {
        for (j = 0; j < RADIX_SIZE; j++)
            front[j] = rear[j] = NULL;

        while (ptr) {
            digit = ptr->key[i];

            if (!front[digit])
                ____;
            else
                rear[digit]->link = ptr;

            ____;
            ptr = ptr->link;
        }

        /* reestablish the linked list for the next pass */
        ptr = NULL;

        for (j = RADIX_SIZE - 1; j >= 0; j--)
            if (front[j]) {
                ____;
                ptr = front[j];
            }
    }

    return ptr;
}

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考兩種排序法，以及如何用鏈結欄位 link 操作串列：

  • 合併排序（Merge Sort）：將已排序的子串列合併。每次合併兩個長度約為 length 的子串列後，下一輪的子串列長度加倍。
  • 遞迴合併排序：把索引範圍切成左右兩半，遞迴排序後，再合併兩個排序好的鏈結串列。
  • LSD 基數排序：從個位數開始，依序按低位數到高位數分桶；每一輪都須維持同一桶內元素的原相對次序，才能確保排序正確。

解題方法

1. 兩趟交替的合併排序

每次 merge_pass 把來源陣列中的相鄰子串列合併到目的陣列。兩個陣列交替當來源與目的地，避免每一輪都把結果複製回原陣列。

merge_pass(list, extra, n, length);
length *= 2;

merge_pass(extra, list, n, length);
length *= 2;

第一趟將 list 合併到 extra；子串列長度加倍後，第二趟再將 extra 合併回 list。每趟完成後，已排序子串列的長度加倍。

2. 遞迴合併排序與串列合併

遞迴分割的中點為 ⌊(lower+upper)/2⌋\lfloor (lower+upper)/2 \rfloor。左右兩半各自排序後，將兩個排序串列的起點交給 listmerge。

int rmerge(element list[], int lower, int upper)
{
    int middle;

    if (lower >= upper)
        return lower;
    else {
        middle = (lower + upper) / 2;
        return listmerge(
            list,
            rmerge(list, lower, middle),
            rmerge(list, middle + 1, upper)
        );
    }
}

listmerge 使用 n 作為虛擬起點：每次比較兩串列目前節點的鍵值，將較小節點接到已排序串列尾端，再移動該串列的指標。鍵值相等時選 first，因此合併具有穩定性。

int listmerge(element list[], int first, int second)
{
    int start = n;

    while (first != -1 && second != -1) {
        if (list[first].key <= list[second].key) {
            list[start].link = first;
            start = first;
            first = list[first].link;
        }
        else {
            list[start].link = second;
            start = second;
            second = list[second].link;
        }
    }

    if (first == -1)
        list[start].link = second;
    else
        list[start].link = first;

    return list[n].link;
}

其中 -1 表示串列結尾。迴圈結束時，最多只剩一串列尚未接完，因此可直接把剩餘串列接到 start 後方。list[n].link 是合併結果的起點。

3. LSD 基數排序

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

其他考古題

其他學校的工程科學與其他考古題

臺灣大學130清華大學46政治大學63中央大學4中正大學14臺北大學39