109 年 國立中山大學電機工程學系碩士班丙組《資料結構》

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

第 1 題

Question set I

Suppose we have the following function:

kkk(A,i,n) {
  if (n > 1) {
    Exchange the values of A[i] and A[i+n-1];
    kkk(A,i+1,n-2);
  }
}

Note that A is an integer array starting with index 0. Each integer occupies 4 bytes in the byte-addressable memory. Please answer the following questions.

  1. If the address of A[2] is 00EC1600EC_{16}, what is the address of A[5]?
    (A) 00EF1600EF_{16}
    (B) 00EC1600EC_{16}
    (C) 00F81600F8_{16}
    (D) 00FF1600FF_{16}

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

這一題的完整詳解

核心觀念

此題考查「陣列元素位址計算」：

  • 記憶體是以位元組定址，每個位元組都有獨立位址。
  • 每個整數佔 44 bytes，因此相鄰陣列元素的位址相差 44 bytes。
  • 陣列元素位址公式為
Addr⁡(A[k])=Addr⁡(A[j])+(k−j)×sizeof(int)⁡\operatorname{Addr}(A[k]) = \operatorname{Addr}(A[j])+(k-j)\times \operatorname{sizeof(int)}

程式中的 Exchange 只交換元素內容，不會改變陣列元素所在的記憶體位址，因此不影響本題計算。

解題方法

已知：

Addr⁡(A[2])=00EC16\operatorname{Addr}(A[2])=00EC_{16}

A[5]A[5] 比 A[2]A[2] 後面 5−2=35-2=3 個元素，因此位移量為

3×4=1210=0C163\times 4=12_{10}=0C_{16}

所以：

Addr⁡(A[5])=00EC16+000C16=00F816\operatorname{Addr}(A[5]) = 00EC_{16}+000C_{16} = 00F8_{16}

選項分析

🔒

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

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

免費註冊

第 2 題

Question set I

Suppose we have the following function:

kkk(A,i,n) {
  if (n > 1) {
    Exchange the values of A[i] and A[i+n-1];
    kkk(A,i+1,n-2);
  }
}

Note that A is an integer array starting with index 0. Each integer occupies 4 bytes in the byte-addressable memory. Please answer the following questions.

  1. How many times kkk will be called in the function body of kkk(A,0,4)?
    (A) 1
    (B) 2
    (C) 3
    (D) 4

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

這一題的完整詳解

核心觀念

本題考查遞迴函式的呼叫次數。每次呼叫時：

  • 若 n>1n>1，先交換元素，再遞迴呼叫 kkk(A,i+1,n-2)。
  • 若 n≤1n\leq 1，不再遞迴，直接結束。
  • 每次遞迴都使 nn 減少 22，因此呼叫流程只有單一路徑。

解題方法

關鍵程式碼為：

if (n > 1) {
    Exchange A[i] and A[i+n-1];
    kkk(A, i+1, n-2);
}

從 kkk(A,0,4) 開始追蹤：

呼叫次序函式呼叫是否遞迴
第 1 次kkk(A,0,4)4>14>1，呼叫下一層
第 2 次kkk(A,1,2)2>12>1，呼叫下一層
第 3 次kkk(A,2,0)0≤10\leq1，結束

因此，kkk 的總呼叫次數為

1+1+1=31+1+1=3

也可寫成遞迴式：

🔒

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

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

免費註冊

第 3 題

Question set I

Suppose we have the following function:

kkk(A,i,n) {
  if (n > 1) {
    Exchange the values of A[i] and A[i+n-1];
    kkk(A,i+1,n-2);
  }
}

Note that A is an integer array starting with index 0. Each integer occupies 4 bytes in the byte-addressable memory. Please answer the following questions.

  1. What is the time complexity of this function?
    (A) O(n)O(n)
    (B) O(log⁡2n)O(\log_2 n)
    (C) O(n2)O(n^2)
    (D) O(n3)O(n^3)

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

這一題的完整詳解

核心觀念

本題考查遞迴函式的時間複雜度。判斷重點有兩個：

  • 每次函式呼叫所做的工作量是否為常數。
  • 遞迴參數如何縮小。

每次呼叫只交換 A[i]A[i] 與 A[i+n−1]A[i+n-1]，包含固定次數的陣列存取與指定，因此單次工作為 Θ(1)\Theta(1)。

雖然每次遞迴將 nn 減少 22，但不是除以 22。因此遞迴深度與 nn 成正比。

解題方法

令 T(n)T(n) 表示輸入規模為 nn 時的執行時間。

當 n≤1n\leq 1 時，不進行交換，也不再遞迴：

T(n)=Θ(1),n≤1T(n)=\Theta(1),\qquad n\leq 1

當 n>1n>1 時，函式執行一次常數時間的交換，再呼叫規模為 n−2n-2 的函式：

T(n)=T(n−2)+Θ(1)T(n)=T(n-2)+\Theta(1)

展開遞迴：

T(n)=T(n−2)+c=T(n−4)+2c=T(n−6)+3c ⋮\begin{aligned} T(n) &=T(n-2)+c\\ &=T(n-4)+2c\\ &=T(n-6)+3c\\ &\ \vdots \end{aligned}

每次遞迴只減少 22，大約需要

⌊n2⌋\left\lfloor \frac{n}{2}\right\rfloor

次交換。因此：

T(n)=Θ(n2)=Θ(n)T(n)=\Theta\left(\frac{n}{2}\right)=\Theta(n)

所以其時間複雜度為 O(n)O(n)。

題目提供的記憶體資訊不會改變結果。若陣列起始位址為 base\text{base}，則：

addr⁡(A[i])=base+4i\operatorname{addr}(A[i])=\text{base}+4i
🔒

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

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

免費註冊

第 4 題

Question set I

Suppose we have the following function:

kkk(A,i,n) {
  if (n > 1) {
    Exchange the values of A[i] and A[i+n-1];
    kkk(A,i+1,n-2);
  }
}

Note that A is an integer array starting with index 0. Each integer occupies 4 bytes in the byte-addressable memory. Please answer the following questions.

  1. Let A=[20,80,30,40,10,70,50]. After executing kkk(A,0,7), which of the following are true?
    (A) A[0]=70
    (B) A[2]=10
    (C) A[4]=50
    (D) A[6]=20

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

這一題的完整詳解

核心觀念

函式每次交換目前子陣列的首、尾元素：

A[i]↔A[i+n−1]A[i]\leftrightarrow A[i+n-1]

接著將起點向右移一格，子陣列長度縮短兩格：

kkk(A,i+1,n−2)kkk(A,i+1,n-2)

因此，這個函式會由外向內交換元素，實際效果是將陣列反轉。題目所給的「每個整數佔 4 bytes」與本題只判斷陣列內容無關。

解題方法

初始陣列為：

A=[20,80,30,40,10,70,50]A=[20,80,30,40,10,70,50]

依照每次交換的索引逐步計算：

遞迴呼叫交換位置陣列結果
kkk(A,0,7)kkk(A,0,7)A[0]↔A[6]A[0]\leftrightarrow A[6][50,80,30,40,10,70,20][50,80,30,40,10,70,20]
kkk(A,1,5)kkk(A,1,5)A[1]↔A[5]A[1]\leftrightarrow A[5][50,70,30,40,10,80,20][50,70,30,40,10,80,20]
kkk(A,2,3)kkk(A,2,3)A[2]↔A[4]A[2]\leftrightarrow A[4][50,70,10,40,30,80,20][50,70,10,40,30,80,20]
kkk(A,3,1)kkk(A,3,1)不執行交換[50,70,10,40,30,80,20][50,70,10,40,30,80,20]

當 n=1n=1 時，條件 n>1n>1 不成立，遞迴停止。

所以最後陣列為：

🔒

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

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

免費註冊

第 5 題

Question set I

Suppose we have the following function:

kkk(A,i,n) {
  if (n > 1) {
    Exchange the values of A[i] and A[i+n-1];
    kkk(A,i+1,n-2);
  }
}

Note that A is an integer array starting with index 0. Each integer occupies 4 bytes in the byte-addressable memory. Please answer the following questions.

  1. Let A=[15,25,35,45,55,65,75,85]. After executing kkk(A,0,8), which of the following are true?
    (A) A[1]=75
    (B) A[3]=55
    (C) A[5]=35
    (D) A[7]=65

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

這一題的完整詳解

核心觀念

函式每次執行時，會交換目前區間的左右端點：

A[i]↔A[i+n−1]A[i]\leftrightarrow A[i+n-1]

接著將起點向右移一格、區間長度縮短兩格：

kkk⁡(A,i,n)⟶kkk⁡(A,i+1,n−2)\operatorname{kkk}(A,i,n)\longrightarrow \operatorname{kkk}(A,i+1,n-2)

因此，函式會依序交換：

(A[0],A[7]), (A[1],A[6]), (A[2],A[5]), (A[3],A[4])(A[0],A[7]),\ (A[1],A[6]),\ (A[2],A[5]),\ (A[3],A[4])

這正是將陣列反轉的操作。題目提到每個整數佔 4 bytes，但本題只操作陣列索引與元素值，無須計算記憶體位址。

解題方法

初始陣列為：

A=[15,25,35,45,55,65,75,85]A=[15,25,35,45,55,65,75,85]

逐層追蹤遞迴：

呼叫交換位置交換後陣列
kkk(A,0,8)A[0]↔A[7]A[0]\leftrightarrow A[7][85,25,35,45,55,65,75,15][85,25,35,45,55,65,75,15]
kkk(A,1,6)A[1]↔A[6]A[1]\leftrightarrow A[6][85,75,35,45,55,65,25,15][85,75,35,45,55,65,25,15]
kkk(A,2,4)A[2]↔A[5]A[2]\leftrightarrow A[5][85,75,65,45,55,35,25,15][85,75,65,45,55,35,25,15]
🔒

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

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

免費註冊

第 6 題

Question set II

Suppose we have a stack for storing integers. Initially, the stack is empty. We perform 10 operations push(1), push(2), pop(), push(3), pop(), pop(), push(4), push(5), push(6), and pop(). Please answer the following questions.

  1. We use an array A of 10 elements to implement the stack. Which one is true for declaring the array in C?
    (A) integer A:10;
    (B) integer A[0,9];
    (C) integer A[1,10];
    (D) integer A[10];

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

這一題的完整詳解

觀念解析

在 C 語言中，宣告包含 NN 個元素的陣列時，標準語法為：
資料型態 陣列名稱[大小];

針對宣告存放 10 個元素的整數陣列 AA：

  • (A) integer A:10;：此為結構體位元欄（bit-field）語法誤用，非陣列宣告。
🔒

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

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

免費註冊

第 7 題

Question set II

Suppose we have a stack for storing integers. Initially, the stack is empty. We perform 10 operations push(1), push(2), pop(), push(3), pop(), pop(), push(4), push(5), push(6), and pop(). Please answer the following questions.

  1. We use the array A as defined above to implement the stack. We want to store the first integer at index=0. Let the latest input be stored at index=top. What is the value of top for the empty stack?
    (A) top=0
    (B) top=1
    (C) top=-1
    (D) top=9

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

這一題的完整詳解

核心觀念

本題考查陣列實作堆疊時，top 的定義。

題目規定：

  • 第一個整數存放於索引 00。
  • 堆疊目前最上方、也就是最後存入的元素，位於索引 top。
  • top 指向的是「目前堆疊最上方元素的索引」，不是堆疊元素數量。

空堆疊沒有任何元素，因此不存在有效的索引可供 top 指向。一般以 −1-1 表示空堆疊。

解題方法

採用「執行一次 push，觀察 top 如何變化」的方式：

  1. 初始堆疊為空，設定
    top=−1\text{top}=-1
  2. 執行 push(1) 時，先將 top 加 11：
    top=−1+1=0\text{top}=-1+1=0
    再將 11 存入 A[0]A[0]。
  3. 因此，top=-1 正好表示尚未有任何元素；第一次 push 後才會變成 00。

也可用堆疊大小 nn 與 top 的關係表示：

top=n−1\text{top}=n-1

當堆疊為空時，n=0n=0，所以

top=0−1=−1\text{top}=0-1=-1
🔒

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

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

免費註冊

第 8 題

Question set II

Suppose we have a stack for storing integers. Initially, the stack is empty. We perform 10 operations push(1), push(2), pop(), push(3), pop(), pop(), push(4), push(5), push(6), and pop(). Please answer the following questions.

  1. We use the linked-based implementation for the stack. Let the latest input be stored at the location with address in first. What is the value of first for the empty stack?
    (A) first=-1
    (B) first=0
    (C) first=1
    (D) first=2

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

這一題的完整詳解

觀念解析

在**鏈結串列（Linked List）**的堆疊實作中，指標變數 first 充當堆疊頂端指標（Top Pointer），指向最新加入的節點位址：

🔒

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

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

免費註冊

第 9 題

Question set II

Suppose we have a stack for storing integers. Initially, the stack is empty. We perform 10 operations push(1), push(2), pop(), push(3), pop(), pop(), push(4), push(5), push(6), and pop(). Please answer the following questions.

  1. We use the array A as defined above to implement the stack. After executing the 10 operations in sequence, which of the following are true?
    (A) top=1
    (B) A[0]=4
    (C) A[1]=5
    (D) The stack has 3 integers.

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

這一題的完整詳解

核心觀念

堆疊（stack）採用後進先出（LIFO, Last In First Out）原則：

  • push(x)：將 xx 放到堆疊頂端。
  • pop()：移除並取出堆疊頂端元素。
  • 陣列採 0-based index，top 表示目前頂端元素在陣列中的索引。
  • 空堆疊時 top=−1top=-1；若堆疊有 nn 個元素，則 top=n−1top=n-1。

解題方法

依序記錄每次操作後的堆疊內容，堆疊左側為底端、右側為頂端：

步驟操作操作結果堆疊內容（底 →\rightarrow 頂）top
0初始—[ ][\ ]−1-1
1push(1)放入 11[1][1]00
2push(2)放入 22[1,2][1,2]11
3pop()取出 22[1][1]00
4push(3)放入 33[1,3][1,3]11
5pop()取出 33[1][1]00
6pop()取出 11[ ][\ ]−1-1
7push(4)放入 44[4][4]00
🔒

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

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

免費註冊

第 10 題

Question set II

Suppose we have a stack for storing integers. Initially, the stack is empty. We perform 10 operations push(1), push(2), pop(), push(3), pop(), pop(), push(4), push(5), push(6), and pop(). Please answer the following questions.

  1. We use the linked-based implementation as defined above for the stack. After executing the 10 operations, which of the following are true?
    (A) first is not 0
    (B) first contains the address where 5 is stored
    (C) A[first]=4
    (D) A -> first = 4

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

這一題的完整詳解

一、 堆疊操作動態追蹤

定義 first 為指向鏈結串列頂端（Top）節點之指標。依序執行 10 次堆疊操作：

  1. push(1) →\rightarrow Stack: [1][1]
  2. push(2) →\rightarrow Stack: [1,2][1, 2]
  3. pop() →\rightarrow Stack: [1][1]
  4. push(3) →\rightarrow Stack: [1,3][1, 3]
  5. pop() →\rightarrow Stack: [1][1]
  6. pop() →\rightarrow Stack: ∅\emptyset
  7. push(4) →\rightarrow Stack: [4][4]
  8. push(5) →\rightarrow Stack: [4,5][4, 5]
🔒

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

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

免費註冊

第 11 題

Question set III

Suppose we have an array A containing 9 integers (with the first index being 0):
240, 119, 682, 341, 225, 556, 122, 661, 245

Please answer the following questions.

  1. We use Bubble Sort to sort the array in ascending order. What is A[8] after the first pass?
    (A) 661
    (B) 556
    (C) 682
    (D) 245

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

這一題的完整詳解

核心觀念

Bubble Sort（冒泡排序）進行升冪排序時，依序比較相鄰兩個元素：

  • 若左邊元素大於右邊元素，便交換兩者。
  • 若左邊元素小於或等於右邊元素，則不交換。
  • 完成第一趟掃描後，原陣列中的最大值會一路向右交換，最後固定在最右端。

本題陣列共有 99 個元素，索引範圍為 00 到 88。第一趟需比較：

(A[0],A[1]),(A[1],A[2]),…,(A[7],A[8])(A[0],A[1]),(A[1],A[2]),\ldots,(A[7],A[8])

解題方法

初始陣列為：

[240,119,682,341,225,556,122,661,245][240,119,682,341,225,556,122,661,245]

依序比較相鄰元素：

比較動作陣列結果
240,119240,119交換[119,240,682,341,225,556,122,661,245][119,240,682,341,225,556,122,661,245]
240,682240,682不交換[119,240,682,341,225,556,122,661,245][119,240,682,341,225,556,122,661,245]
682,341682,341交換[119,240,341,682,225,556,122,661,245][119,240,341,682,225,556,122,661,245]
682,225682,225交換[119,240,341,225,682,556,122,661,245][119,240,341,225,682,556,122,661,245]
682,556682,556交換[119,240,341,225,556,682,122,661,245][119,240,341,225,556,682,122,661,245]
682,122682,122交換[119,240,341,225,556,122,682,661,245][119,240,341,225,556,122,682,661,245]
🔒

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

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

免費註冊

第 12 題

Question set III

Suppose we have an array A containing 9 integers (with the first index being 0):
240, 119, 682, 341, 225, 556, 122, 661, 245

Please answer the following questions.

  1. We use Bubble Sort to sort the array in ascending order. What is A[7] after the second pass?
    (A) 122
    (B) 661
    (C) 556
    (D) 225

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

這一題的完整詳解

核心觀念

Bubble Sort 反覆比較相鄰元素：

  • 若左邊元素大於右邊元素，便交換兩者。
  • 以升冪排序時，每一趟由左向右掃描，該趟最大的未排序元素會逐步「冒泡」到右端。
  • 第 1 趟後，最大值會固定在 A[8]A[8]；第 2 趟後，次大值會固定在 A[7]A[7]。

解題方法

原始陣列為：

[240,119,682,341,225,556,122,661,245][240,119,682,341,225,556,122,661,245]

第 1 趟

由左至右比較相鄰元素，最大值 682682 會一路交換到最後：

[119,240,341,225,556,122,661,245,682][119,240,341,225,556,122,661,245,682]

因此第 1 趟完成後，682682 固定於 A[8]A[8]。

第 2 趟

此時只需處理前 8 個元素：

[119,240,341,225,556,122,661,245][119,240,341,225,556,122,661,245]

依序比較並交換：

  1. 119<240119<240，不交換。

  2. 240<341240<341，不交換。

  3. 341>225341>225，交換：

    [119,240,225,341,556,122,661,245,682][119,240,225,341,556,122,661,245,682]
🔒

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

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

免費註冊

第 13 題

Question set III

Suppose we have an array A containing 9 integers (with the first index being 0):
240, 119, 682, 341, 225, 556, 122, 661, 245

Please answer the following questions.

  1. We use Quick Sort to sort the array in ascending order. For each partition, let the rightmost element be the pivot. Which one stores 245 after the first partition?
    (A) A[3]
    (B) A[7]
    (C) A[5]
    (D) A[4]

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

這一題的完整詳解

核心觀念

Quick Sort 的 partition 會選定一個 pivot，重新排列資料，使其滿足：

左側元素<pivot<右側元素\text{左側元素} < \text{pivot} < \text{右側元素}

Partition 完成後，pivot 已經位於「排序後的正確索引」，但左右兩側的元素尚未完全排序。

本題索引從 00 開始，右端元素為 pivot：

pivot=A[8]=245\text{pivot}=A[8]=245

小於 245245 的元素有：

240, 119, 225, 122240,\ 119,\ 225,\ 122

共有 44 個，因此 pivot 左側會有 44 個元素。由於索引從 00 開始，pivot 的位置為：

0+4=40+4=4

所以 245245 會存放在 A[4]A[4]。

解題方法

依照常見的 Lomuto partition 觀念，掃描 pivot 前面的元素：

  • 240<245240<245，留在左側。
  • 119<245119<245，留在左側。
  • 682>245682>245，放入右側。
  • 341>245341>245，放入右側。
  • 225<245225<245，移至左側。
  • 556>245556>245，留在右側。
  • 122<245122<245，移至左側。
  • 661>245661>245，留在右側。

完成左右分區後，可排列成：

[240, 119, 225, 122, 682, 556, 341, 661, 245][240,\ 119,\ 225,\ 122,\ 682,\ 556,\ 341,\ 661,\ 245]
🔒

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

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

免費註冊

第 14 題

Question set III

Suppose we have an array A containing 9 integers (with the first index being 0):
240, 119, 682, 341, 225, 556, 122, 661, 245

Please answer the following questions.

  1. We use Quick Sort to sort the array in ascending order. Which of the following are false after the first partition?
    (A) A[0]=240
    (B) A[8]=682
    (C) A[3]=341
    (D) A[7]=661

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

這一題的完整詳解

核心觀念

題目單獨摘錄時未重述分割規則；依原題組前題設定，每次 partition 取目前子陣列的最右端元素為 pivot。原題組題目頁

採用標準的 Lomuto partition：

  1. 取最右端元素為 pivot。
  2. 將小於 pivot 的元素移到左側，大於 pivot 的元素留在右側。
  3. 最後將 pivot 放到其排序後的正確位置。

第一次分割時：

A=[240,119,682,341,225,556,122,661,245]A=[240,119,682,341,225,556,122,661,245]

pivot 為

x=A[8]=245x=A[8]=245

小於 245245 的元素共有 44 個：

240, 119, 225, 122240,\ 119,\ 225,\ 122

因此 pivot 最後必定位於 A[4]A[4]。

解題方法

由左至右掃描 A[0]A[0] 到 A[7]A[7]：

  • 240<245240<245，留在左側。
  • 119<245119<245，留在左側。
  • 682>245682>245，暫留右側。
  • 341>245341>245，暫留右側。
🔒

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

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

免費註冊

第 15 題

Question set III

Suppose we have an array A containing 9 integers (with the first index being 0):
240, 119, 682, 341, 225, 556, 122, 661, 245

Please answer the following questions.

  1. We use Heap Sort to sort the array in ascending order. But first, we have to convert the array into a maxheap. Which of the following are true in the resulting maxheap?
    (A) A[0]=682
    (B) A[3]=341
    (C) A[5]=240
    (D) A[8]=245

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

這一題的完整詳解

觀念說明

建立 Max Heap 採用 Bottom-up 之 Build-Max-Heap 演算法。陣列索引自 00 開始，長度 N=9N = 9，最後一個非葉節點索引為 ⌊N−22⌋=3\lfloor \frac{N-2}{2} \rfloor = 3。依序對索引 i=3,2,1,0i = 3, 2, 1, 0 執行 Max-Heapify 調整。

其中節點 ii 的左子節點索引為 2i+12i + 1，右子節點索引為 2i+22i + 2。

步驟推導

原始陣列：
A=[240,119,682,341,225,556,122,661,245]A = [240, 119, 682, 341, 225, 556, 122, 661, 245]

  1. i=3i = 3 (A[3]=341A[3] = 341)：
    子節點為 A[7]=661,A[8]=245A[7]=661, A[8]=245。最大值為 A[7]A[7]，與 A[3]A[3] 交換。
    A=[240,119,682,661,225,556,122,341,245]A = [240, 119, 682, \mathbf{661}, 225, 556, 122, \mathbf{341}, 245]

  2. i=2i = 2 (A[2]=682A[2] = 682)：
    子節點為 A[5]=556,A[6]=122A[5]=556, A[6]=122。因 A[2]=682>556A[2] = 682 > 556，無須交換。

  3. i=1i = 1 (A[1]=119A[1] = 119)：
    子節點為 A[3]=661,A[4]=225A[3]=661, A[4]=225。最大值為 A[3]A[3]，與 A[1]A[1] 交換：

🔒

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

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

免費註冊

第 16 題

Question set IV

Let the height of a tree be the number of nodes along the longest path from the root node to the leaf nodes. Suppose we have 10 integers 35, 46, 30, 34, 99, 42, 75, 28, 70, 80. Please answer the following questions.

  1. We create binary trees for these integers. What is the minimum height of all the possible trees?
    (A) 1
    (B) 2
    (C) 3
    (D) 4

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

這一題的完整詳解

核心觀念

二元樹的高度定義為「從根節點到最深葉節點所經過的節點數」。因此：

  • 高度 11：只有根節點。
  • 第 ii 層最多有 2i−12^{i-1} 個節點。
  • 高度為 hh 的二元樹，最多包含
1+2+4+⋯+2h−1=2h−11+2+4+\cdots+2^{h-1}=2^h-1

個節點。

本題有 1010 個整數，數值本身不影響樹的最小高度。

解題方法

要求最小高度 hh，必須滿足：

2h−1≥102^h-1\ge 10

因此：

2h≥112^h\ge 11

逐層計算：

  • 高度 33 最多有 23−1=72^3-1=7 個節點，不足 1010 個。
  • 高度 44 最多有 24−1=152^4-1=15 個節點，足以容納 1010 個節點。

高度為 44 的樹確實可以放入這 1010 個數。例如甚至可以排列成二元搜尋樹：

        35
       /  \
     30    75
    / \    / \
  28  34 46  80
          / \   \
         42 70  99
🔒

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

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

免費註冊

第 17 題

Question set IV

Let the height of a tree be the number of nodes along the longest path from the root node to the leaf nodes. Suppose we have 10 integers 35, 46, 30, 34, 99, 42, 75, 28, 70, 80. Please answer the following questions.

  1. We create binary trees for these integers. What is the maximum height of all the possible trees?
    (A) 10
    (B) 9
    (C) 8
    (D) 7

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

這一題的完整詳解

核心觀念

題目考查二元樹高度的定義與極端樹形。

  • 高度定義為：從根節點到葉節點的最長路徑上，所包含的節點數。
  • 二元樹中，每個節點最多有兩個子節點，但允許只有一個子節點。
  • 對含有 nn 個節點的二元樹而言，最大高度為 nn，發生在所有節點連成單鏈的情況。

解題方法

本題共有 1010 個整數，因此建立的二元樹共有 1010 個節點。

將所有節點安排成單側傾斜的樹形，例如：

35→46→30→34→99→42→75→28→70→8035 \rightarrow 46 \rightarrow 30 \rightarrow 34 \rightarrow 99 \rightarrow 42 \rightarrow 75 \rightarrow 28 \rightarrow 70 \rightarrow 80

此時根節點到最深葉節點的路徑包含全部 1010 個節點，因此：

最大高度=10\text{最大高度}=10

題目採用「路徑上的節點數」定義高度，所以不需扣除根節點，也不需將節點數減一。

選項分析

🔒

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

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

免費註冊

第 18 題

Question set IV

Let the height of a tree be the number of nodes along the longest path from the root node to the leaf nodes. Suppose we have 10 integers 35, 46, 30, 34, 99, 42, 75, 28, 70, 80. Please answer the following questions.

  1. We create an AVL tree by considering the integers one by one, starting with the first one, 30. Which of the following is true?
    (A) The height of the resulting tree is 5
    (B) The root of the resulting tree is 75
    (C) The node for 46 has one child
    (D) The parent of 99 is the node for 75

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

這一題的完整詳解

觀念說明

AVL 樹為高度平衡二元搜尋樹（Height-Balanced BST），每個節點的平衡因子（Balance Factor, BF=height(left)−height(right)BF = \text{height}(\text{left}) - \text{height}(\text{right})）必須維持在 {−1,0,1}\{-1, 0, 1\}。若插入節點後破壞平衡，需依不平衡型態（LL、RR、LR、RL）進行旋轉調整。

AVL 樹建構步驟

依序插入數值 35, 46, 30, 34, 99, 42, 75, 28, 70, 80：

  1. 插入 35, 46, 30, 34, 99, 42：皆符合平衡條件，無須旋轉。
  2. 插入 75：
    • 節點 4646 之右子節點為 9999，於 9999 之左側插入 7575，導致節點 4646 發生 RL 不平衡（BF=−2BF = -2）。
🔒

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

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

免費註冊

第 19 題

Question set IV

Let the height of a tree be the number of nodes along the longest path from the root node to the leaf nodes. Suppose we have 10 integers 35, 46, 30, 34, 99, 42, 75, 28, 70, 80. Please answer the following questions.

  1. We create a binary search tree by considering the integers one by one, starting with the first one, 30. Which of the following are true?
    (A) The node for 75 is a leaf node
    (B) The node for 42 is an internal node
    (C) The node for 99 has only one child
    (D) The height of the resulting tree is 5

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

這一題的完整詳解

二元搜尋樹建構過程

依序將整數序列 35,46,30,34,99,42,75,28,70,8035, 46, 30, 34, 99, 42, 75, 28, 70, 80 插入二元搜尋樹（BST）：

  1. 插入 3535：作為根節點（Root）。
  2. 插入 4646：46>3546 > 35，放置於 3535 的右子節點。
  3. 插入 3030：30<3530 < 35，放置於 3535 的左子節點。
  4. 插入 3434：34<3534 < 35 且 34>3034 > 30，放置於 3030 的右子節點。
  5. 插入 9999：99>3599 > 35 且 99>4699 > 46，放置於 4646 的右子節點。
  6. 插入 4242：42>3542 > 35 且 42<4642 < 46，放置於 4646 的左子節點。
  7. 插入 7575：75>4675 > 46 且 75<9975 < 99，放置於 9999 的左子節點。
  8. 插入 2828：28<3028 < 30，放置於 3030 的左子節點。
  9. 插入 7070：70<7570 < 75，放置於 7575 的左子節點。
  10. 插入 8080：80>7580 > 75，放置於 7575 的右子節點。
🔒

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

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

免費註冊

第 20 題

Question set IV

Let the height of a tree be the number of nodes along the longest path from the root node to the leaf nodes. Suppose we have 10 integers 35, 46, 30, 34, 99, 42, 75, 28, 70, 80. Please answer the following questions.

  1. Based on the binary search tree obtained in Question 19, we delete 99 from the tree. Which of the following are true?
    (A) The parent of 75 is the node for 46
    (B) The node for 30 has two children
    (C) The node for 70 is an internal node
    (D) The height of the resulting tree is 4

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

這一題的完整詳解

一、 建樹與刪除節點推導

1. 原始二元搜尋樹（BST）建立

將數列 35,46,30,34,99,42,75,28,70,8035, 46, 30, 34, 99, 42, 75, 28, 70, 80 依序插入空 BST 中：

  • 根節點為 3535。
  • 3535 的左子樹：根為 3030（左子 2828、右子 3434）。
  • 3535 的右子樹：根為 4646（左子 4242、右子 9999）；9999 的左子為 7575（左子 7070、右子 8080）。

2. 刪除節點 99

  • 節點 9999 僅有單一子節點（左子節點 7575）。
  • 依 BST 刪除規則，直接由 7575 接替 9999 的位置，成為 4646 的右子節點。
🔒

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

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

免費註冊

第 21 題

Question set V

Suppose we have an undirected graph G=(V,E), where V={a,b,c,d,e,f,g,i} and E={[(a,i), 2], [(a,b), 6], [(a,g), 4], [(b,c), 7], [(b,e), 9], [(c,d), 4], [(d,g), 5], [(e,g), 8], [(f,g), 2], [(f,i), 3]}. Note that [(x,y),w] indicates that there is an edge, with weight w, between vertices x and y. Please answer the following questions.

  1. We find a spanning tree for the graph using the depth-first search algorithm, starting with vertex e. Note that if two or more vertices qualify, then the one with the least alphabetical order is selected. What is the sum of the weights involved in the resulting tree?
    (A) 31
    (B) 32
    (C) 33
    (D) 34

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

這一題的完整詳解

核心觀念

深度優先搜尋（Depth-First Search, DFS）從起點出發，沿著尚未拜訪的頂點一路深入；當目前頂點沒有未拜訪鄰點時，便回溯至上一層。

DFS 所形成的 spanning tree：

  • 每個新拜訪的頂點，透過一條邊連接到發現它的頂點。
  • 若圖有 ∣V∣|V| 個頂點，spanning tree 必有 ∣V∣−1|V|-1 條邊。
  • 本題共有 88 個頂點，因此結果應有 77 條樹邊。
  • 邊的選擇依 DFS 與字母順序決定，並非依權重大小選擇，因此不是最小生成樹問題。

解題方法

各頂點的鄰接頂點依字母順序排列：

  • e: b,ge:\ b,g
  • b: a,c,eb:\ a,c,e
  • a: b,g,ia:\ b,g,i
  • g: a,d,e,fg:\ a,d,e,f
  • d: c,gd:\ c,g
  • c: b,dc:\ b,d
  • f: g,if:\ g,i
  • i: a,fi:\ a,f

從 ee 開始進行 DFS：

  1. 拜訪 ee，選最小字母鄰點 bb：加入 (e,b)(e,b)，權重 99。
  2. 在 bb 選尚未拜訪的 aa：加入 (b,a)(b,a)，權重 66。
  3. 在 aa 選尚未拜訪的 gg：加入 (a,g)(a,g)，權重 44。
  4. 在 gg 的鄰點中，a,ea,e 已拜訪，選 dd：加入 (g,d)(g,d)，權重 55。
  5. 在 dd 選尚未拜訪的 cc：加入 (d,c)(d,c)，權重 44。
🔒

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

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

免費註冊

第 22 題

Question set V

Suppose we have an undirected graph G=(V,E), where V={a,b,c,d,e,f,g,i} and E={[(a,i), 2], [(a,b), 6], [(a,g), 4], [(b,c), 7], [(b,e), 9], [(c,d), 4], [(d,g), 5], [(e,g), 8], [(f,g), 2], [(f,i), 3]}. Note that [(x,y),w] indicates that there is an edge, with weight w, between vertices x and y. Please answer the following questions.

  1. We find a spanning tree for the graph using the breadth-first search algorithm, starting with vertex e. Note that if two or more vertices qualify, then the one with the least alphabetical order is selected. What is the sum of the weights involved in the resulting tree?
    (A) 40
    (B) 39
    (C) 38
    (D) 37

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

這一題的完整詳解

核心觀念

廣度優先搜尋（Breadth-First Search, BFS）以「距離起點的層數」逐層拜訪頂點：

  1. 先拜訪起點。
  2. 將目前頂點尚未發現的鄰接點加入佇列。
  3. 依佇列先進先出順序處理。
  4. 若有多個候選頂點，依題意採字母順序較小者優先。

BFS 產生的 spanning tree（生成樹）中，每個頂點第一次被發現時所使用的邊，便是生成樹的邊。注意：BFS 的選擇依鄰接關係與拜訪順序決定，不會依邊的權重大小選邊。

解題方法

由頂點 ee 開始，依字母順序處理鄰接頂點。

第 1 層：由 ee 出發

ee 的鄰接頂點為 b,gb,g，依字母順序先 bb 後 gg：

  • 加入邊 (e,b)(e,b)，權重 99
  • 加入邊 (e,g)(e,g)，權重 88

佇列：

[b,g][b,g]

處理 bb

bb 的鄰接頂點為 a,c,ea,c,e。其中 ee 已發現，因此依序發現：

  • 加入邊 (b,a)(b,a)，權重 66
  • 加入邊 (b,c)(b,c)，權重 77

佇列：

[g,a,c][g,a,c]

處理 gg

gg 的鄰接頂點為 a,d,e,fa,d,e,f。

  • aa 已被 bb 發現
  • ee 已被拜訪
  • dd 尚未發現，加入邊 (g,d)(g,d)，權重 55
  • ff 尚未發現，加入邊 (g,f)(g,f)，權重 22

佇列：

🔒

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

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

免費註冊
📄 以下 3 題共用同一段題幹

Suppose we have an undirected graph G=(V,E)G=(V,E), where

V={a,b,c,d,e,f,g,i}V=\{a,b,c,d,e,f,g,i\}

and

E={[(a,i),2],[(a,b),6],[(a,g),4],[(b,c),7],[(b,e),9],[(c,d),4],[(d,g),5],[(e,g),8],[(f,g),2],[(f,i),3]}.E=\{[(a,i),2],[(a,b),6],[(a,g),4],[(b,c),7],[(b,e),9],[(c,d),4],[(d,g),5],[(e,g),8],[(f,g),2],[(f,i),3]\}.

Note that [(x,y),w][(x,y),w] indicates that there is an edge, with weight ww, between vertices xx and yy. Please answer the following questions.

第 23 題

We find a spanning tree for the graph using Prim’s algorithm, starting with vertex ee. Note that if two or more vertices qualify, then the one with the least alphabetical order is selected.

What is the sum of the weights involved in the resulting tree?

(A) 3030
(B) 2929
(C) 2828
(D) 2727

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

這一題的完整詳解

核心觀念

Prim 演算法從指定起點開始，逐步加入「連接已加入頂點與尚未加入頂點」的最小權重邊，直到所有頂點都加入。若有多個頂點符合條件，依題意選字母順序最小者。

解題方法

原卷圖中的圖形資訊與題幹相符：頂點為 a,b,c,d,e,f,g,ia,b,c,d,e,f,g,i，邊及權重包含 ee 相連的 (e,g)(e,g) 權重 88、(e,b)(e,b) 權重 99；依 Prim 演算法從 ee 開始選邊。各步驟中最小的候選邊如下：

已加入的頂點選入的邊權重
ee(e,g)(e,g)88
e,ge,g(g,f)(g,f)22
e,g,fe,g,f(f,i)(f,i)33
e,g,f,ie,g,f,i(i,a)(i,a)22
e,g,f,i,ae,g,f,i,a(g,d)(g,d)55
🔒

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

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

免費註冊

第 24 題

Which of the following are true for the resulting tree obtained in Question 21?

(A) The node following node aa is node gg.
(B) The edge (e,g)(e,g) is contained in the tree.
(C) The edge (c,d)(c,d) is contained in the tree.
(D) The edge (b,c)(b,c) is contained in the tree.

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

這一題的完整詳解

核心觀念

本題承接第 21 題的深度優先搜尋（DFS）生成樹。DFS 從指定起點開始，沿著尚未拜訪的鄰點深入；若有多個鄰點可選，依題目規定選字母順序最前者。生成樹包含 DFS 過程中首次拜訪新節點時所走的邊。

解題方法

原卷第 21 題指定從頂點 ee 開始做 DFS，若有多個鄰點符合條件，選字母順序最前者。圖中給出頂點 {a,b,c,d,e,f,g,i}\{a,b,c,d,e,f,g,i\} 與加權邊；DFS 只依鄰接關係與字母順序決定走訪，加權數值不影響結果。

依字母順序排列各頂點的鄰點，走訪如下：

  1. 從 ee 出發，鄰點為 b,gb,g，先走 bb，選取樹邊 (e,b)(e,b)。
  2. 在 bb，未拜訪的鄰點為 a,ca,c，先走 aa，選取 (b,a)(b,a)。
  3. 在 aa，未拜訪的鄰點為 g,ig,i，先走 gg，選取 (a,g)(a,g)。
  4. 在 gg，未拜訪的鄰點為 d,fd,f，先走 dd，選取 (g,d)(g,d)。
  5. 在 dd，走到未拜訪的 cc，選取 (d,c)(d,c)；cc 的鄰點已拜訪，回溯。
  6. 回到 gg 後走向 ff，選取 (g,f)(g,f)；
🔒

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

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

免費註冊

第 25 題

Which of the following are true for the resulting tree obtained in Question 23?

(A) The edge (a,g)(a,g) is contained in the tree.
(B) The edge (a,b)(a,b) is contained in the tree.
(C) The edge (b,c)(b,c) is contained in the tree.
(D) The edge (c,d)(c,d) is contained in the tree.

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

這一題的完整詳解

核心觀念

第 23 題以 Prim 演算法從 ee 開始建構最小生成樹。每一步都從已納入樹的頂點，選一條連到樹外頂點且權重最小的邊；選取後若會形成環，就不納入。題目規定權重相同時按字母順序選頂點，本題實際選取過程沒有遇到平手。

解題方法

原卷第 25 題詢問第 23 題所得的樹包含哪些邊；第 23 題指定從 ee 開始執行 Prim 演算法。依題目給的無向加權圖，逐步選取：

步驟新納入頂點選取的邊權重
1gg(e,g)(e,g)8
2ff(g,f)(g,f)2
3ii(f,i)(f,i)3
4aa(i,a)(i,a)2
5dd(g,d)(g,d)5
6cc(d,c)(d,c)4
7bb(a,b)(a,b)6

例如，納入 e,g,f,i,ae,g,f,i,a 後，候選邊中 (g,d)(g,d) 的權重為 55，小於 (a,b)(a,b) 的 66，因此先納入 dd；dd 加入後，連到樹外頂點 cc 的邊 (d,c)(d,c) 權重為 44，比連到 bb 的候選邊更小，所以接著納入 cc。

最後得到的生成樹邊集合為

🔒

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

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

免費註冊

其他考古題

中山大學《資料結構》其他年度

115 年114 年113 年112 年111 年108 年

其他學校的電機系考古題

臺灣大學50臺灣聯合大學系統110成功大學154中央大學13中正大學83暨南國際大學8臺灣科技大學4聯合大學4嘉義大學2