台綜大B30 計概114 第十題 解答 ※ 販售必究 ※ 台灣台灣綜合大學, 資訊管理系, 轉學考

 Q10. 數學上定義一個複數 (Complex Number) 具有實數部分 + 虛數部分 * i，例如 5 + 4*i。以下請撰寫 ComplexNumber 類別的程式碼（含實部 realpart 與虛部 imagpart），包含簡單的四則運算、模長 magnitude()與共軛 conjugate()。

Ans: 

台綜大B30 計概114 第九題 解答 ※ 販售必究 ※ 台灣綜合大學, 資訊管理系, 轉學考

Q9.  對於給定的表列 ( A ( B ( E ( K, L), F, W ), C ( G ), D ) )：

A) 畫出對應的多路樹 (multi-way tree)；

B) 將多路樹轉換為二元樹 (binary tree)，並畫出該二元樹。

Ans:

A) 多路樹 (Multi-way Tree)

規則：

• 每個節點可以有多個子節點。

• 括號中的內容表示該節點的子節點。

分析

• 根節點：A

• A 的子節點：B, C, D

• B 的子節點：E, F, W

• E 的子節點：K, L

• C 的子節點：G

• D 沒有子節點

多路樹結構圖

        A
      / | \
     B  C  D
   / | \   \
  E  F  W   -
 / \
K   L
|
-

• 說明：每個節點用直線連到它的子節點。

• - 表示該節點沒有更多子節點。

---

B) 將多路樹轉換為二元樹 (Binary Tree)

轉換規則 (左子 + 右兄弟表示法 Left-child, Right-sibling)

1. 每個節點的 第一個子節點 成為 左子節點 (left child)。

2. 其他子節點依序成為 右兄弟 (right sibling)。

轉換步驟

• A 左子節點 → B

• B 右兄弟 → C，C 右兄弟 → D

• B 的左子節點 → E

• E 右兄弟 → F，F 右兄弟 → W

• E 的左子節點 → K

• K 右兄弟 → L

• C 的左子節點 → G

• D 沒有子節點

對應二元樹結構圖

        A
       /
      B
     / \
    E   C
   / \   \
  K   F   D
   \   \
    L   W
       /
      G

為了更清楚，我整理成標準二元樹表示：

A
|
B
| \
E  C
| \  \
K  F  D
 \   \
  L   W
      |
      G

台綜大B30 計概114 第八題 解答 ※ 販售必究 ※ 台灣綜合大學; 資訊管理系; 轉學考

 Q8. MyFibo 數列定義為 f₀ = 1, f₁ = 2, f₂ = 3, 且 fₖ = fₖ₋₁ + fₖ₋₂ + fₖ₋₃ (k ≥ 2)。請分別寫出該數列的遞迴與迭代演算法（以虛擬碼或 C/C#/Java 語法撰寫）。

Ans:

好的，我幫你整理 MyFibo 數列 的 遞迴 與 迭代 演算法。

定義：

• f₀ = 1

• f₁ = 2

• f₂ = 3

• fₖ = fₖ₋₁ + fₖ₋₂ + fₖ₋₃, for k ≥ 3

---

遞迴演算法 (Recursive)

偽代碼 / C-like 語法

int MyFibo(int k) {
    if (k == 0) return 1;
    if (k == 1) return 2;
    if (k == 2) return 3;
    return MyFibo(k - 1) + MyFibo(k - 2) + MyFibo(k - 3);
}

---

迭代演算法 (Iterative)

偽代碼 / C-like 語法

int MyFiboIter(int k) {
    if (k == 0) return 1;
    if (k == 1) return 2;
    if (k == 2) return 3;

    int f0 = 1, f1 = 2, f2 = 3;
    int f = 0;

    for (int i = 3; i <= k; i++) {
        f = f0 + f1 + f2;
        // shift window
        f0 = f1;
        f1 = f2;
        f2 = f;
    }

    return f;
}

---

👉 範例：計算前幾項

• f₀ = 1

• f₁ = 2

• f₂ = 3

• f₃ = 1 + 2 + 3 = 6

• f₄ = 2 + 3 + 6 = 11

• f₅ = 3 + 6 + 11 = 20

所以序列開頭是： 1, 2, 3, 6, 11, 20, …

台綜大B30 計概114 第七題 解答 ※ 販售必究 ※ 台灣綜合大學, 資訊管理系, 轉學考

Q7. 請將下列類似C語言的運算式寫成前序表示式 (prefix form)。請注意 && 與 || 的優先順序相同（且為由左至右）：

A) a && b || (c>d) || !(e>f) || a+b

B) !a && (b<c) || x

Ans:

題目有特別說明：&& 與 || 的優先順序相同，且由左至右 (left-to-right)。這跟標準 C 稍微不同，標準 C 其實是 && 比 || 優先，但這裡規則是相同、且左結合。

---

A) a && b || (c>d) || !(e>f) || a+b

1. 先看結合方向：

   (((a && b) || (c > d)) || !(e > f)) || (a + b)
   

   這樣從左到右展開。

2. 前序表示：

   • (a && b) → && a b

   • ((a && b) || (c > d)) → || (&& a b) (> c d)

   • (((a && b) || (c > d)) || !(e > f)) → || (|| (&& a b) (> c d)) (! (> e f))

   • 最後再和 (a + b) →

     || (|| (|| (&& a b) (> c d)) (! (> e f))) (+ a b)
     

✅ 前序結果：

|| (|| (|| (&& a b) (> c d)) (! (> e f))) (+ a b)

---

B) !a && (b<c) || x

1. 按左至右結合：

   ((!a && (b < c)) || x)
   

2. 前序表示：

   • !a → ! a

   • (b < c) → < b c

   • (!a && (b < c)) → && (! a) (< b c)

   • ((!a && (b < c)) || x) → || (&& (! a) (< b c)) x

✅ 前序結果：

|| (&& (! a) (< b c)) x

台綜大B30 計概114 第六題 解答 ※ 販售必究 ※ 台灣綜合大學, 資訊管理系, 轉學考

※ 請供考生參考 / 營利必究 ※

 Q6. 如下，請計算當 n = 5 時，第 6 行語句（r = r + 1;）會被執行多少次。

int mystery(n) {

    int r = 0;

    for (int i = 1; i <= n - 1; i++)

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

            for (int k = 1; k <= j; k++)

                for (int m = 1; m <= k; m++)

                    r = r + 1;

    return r;

}

Ans:

int mystery(n) {

    int r = 0;

    for (int i = 1; i <= n - 1; i++)          // ①

        for (int j = i + 1; j <= n; j++)      // ②

            for (int k = 1; k <= j; k++)      // ③

                for (int m = 1; m <= k; m++)  // ④

                    r = r + 1;                // ⑤ (我們要計算的次數)

    return r;

}

內層迴圈展開

最內層 (m 迴圈)：

• for (m = 1; m <= k; m++)

• 執行次數 = k

所以對於固定的 k，⑤ 執行次數 = k

---

第三層迴圈 (k 迴圈)

• for (k = 1; k <= j; k++)

• 執行總次數 = 1 + 2 + 3 + ... + j = j(j+1)/2

所以對於固定的 j，⑤ 執行次數 = j(j+1)/2

---

第二層迴圈 (j 迴圈)

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

• 所以對於固定的 i，⑤ 執行次數 =

  $$\sum_{j=i+1}^{n} \frac{j(j+1)}{2}$$

---

第一層迴圈 (i 迴圈)

• for (i = 1; i <= n-1; i++)

• 所以總次數 =

  $$\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{j(j+1)}{2}$$

---

代入 n = 5

我們要算：

$$\sum_{i=1}^{4} \sum_{j=i+1}^{5} \frac{j(j+1)}{2}$$

逐步計算：

• i = 1 → j = 2..5

  $$\frac{2\cdot3}{2} + \frac{3\cdot4}{2} + \frac{4\cdot5}{2} + \frac{5\cdot6}{2} = 3 + 6 + 10 + 15 = 34$$

• i = 2 → j = 3..5

  $$6 + 10 + 15 = 31$$

• i = 3 → j = 4..5

  $$10 + 15 = 25$$

• i = 4 → j = 5

  $$15$$

---

總和

$$34 + 31 + 25 + 15 = 105$$

---

✅ 答案：當 n = 5 時，語句 r = r + 1; 會執行 105 次。