Try   HackMD

APCS 觀念題 - 遞迴

tags: APCS

第 1 題

給定下方函式 f()，已知 f(14)、f(10)、f(6) 分別回傳 25、18、10，函式中的 (?) 應為下列何者？

int f(int n)
{
    if (n < 2)
    {
        return n;
    }
    else
    {
        return (n + f(___(?)___));
    }
}

(A) (n + 1) / 2
(B) n / 2
(C) (n - 1) / 2
(D) (n / 2) + 1

第 2 題

函數 f() 定義如下，如果呼叫 f(1000)，指令 sum = sum + i 被執行的次數最接近下列何者？

int f(int n)
{
    int sum = 0;

    if (n < 2)
    {
        return 0;
    }

    for (int i = 1; i <= n; i = i + 1)
    {
        sum = sum + i;
    }

    sum = sum + f(2 * n / 3);

    return sum;
}

(A) 1000
(B) 3000
(C) 5000
(D) 10000

第 3 題

請問以 a(13, 15) 呼叫下方 a() 函式，函式執行完後其回傳值為何？

int a(int n, int m)
{
    if (n < 10)
    {
        if (m < 10)
        {
            return n + m;
        }
        else
        {
            return a(n, m - 2) + m;
        }
    }
    else
    {
        return a(n - 1, m) + n;
    }
}

(A) 90
(B) 103
(C) 93
(D) 60

第 4 題

給定下方 g() 函式，g(13) 回傳值為何？

int g(int a)
{
    if (a > 1)
    {
        return g(a - 2) + 3;
    }
    return a;
}

(A) 16
(B) 18
(C) 19
(D) 22

第 5 題

給定下方函式 f1() 及 f2()。f1(1) 運算過程中，以下敘述何者為錯？

void f1(int m)
{
    if (m > 3)
    {
        printf("%d\n", m);
        return;
    }
    else
    {
        printf("%d\n", m);
        f2(m + 2);
        printf("%d\n", m);
    }
}

void f2(int n)
{
    if (n > 3)
    {
        printf("%d\n", n);
        return;
    }
    else
    {
        printf("%d\n", n);
        f1(n - 1);
        printf("%d\n", n);
    }
}

(A) 印出的數字最大的是 4
(B) f1 一共被呼叫二次
(C) f2 一共被呼叫三次
(D) 數字 2 被印出兩次

第 6 題

下方程式輸出為何？

void foo(int i)
{
    if (i <= 5)
    {
        printf("foo: %d\n", i);
    }
    else
    {
        bar(i - 10);
    }
}

void bar(int i)
{
    if (i <= 10)
    {
        printf("bar: %d\n", i);
    }
    else
    {
        foo(i - 5);
    }
}

void main()
{
    foo(15106);
    bar(3091);
    foo(6693);
}

(A)

bar: 6
bar: 1
bar: 8

(B)

bar: 6
foo: 1
bar: 3

(C)

bar: 1
foo: 1
bar: 8

(D)

bar: 6
foo: 1
foo: 3

第 7 題

給定下方函式 f()，當執行 f(10) 時，最終回傳結果為何？

int f(int i)
{
    if (i > 0)
        if (((i / 2) % 2) == 0)
            return f(i - 2) * i;
        else
            return f(i - 2) * (-i);
        else
            return 1;
}

(A) 1
(B) 3840
(C) -3840
(D)執行時導致無窮迴圈，不會停止執行

第 8 題

下方為一個計算 n 階層的函式，請問該如何修改才會得到正確的結果？








int fun(int n) {
    int fac = 1;
    if (n >= 0) {
        fac = n * fun(n - 1);
    }
    return fac;
}

(A) 第 2 行，改為 int fac = n;
(B) 第 3 行，改為 if (n > 0) {
(C) 第 4 行，改為 fac = n * fun(n + 1);
(D) 第 4 行，改為 fac = fac * fun(n - 1);

第 9 題

下方 g(4) 函式呼叫執行後，回傳值為何？

int f(int n)
{
    if (n > 3)
    {
        return 1;
    }
    else if (n == 2)
    {
        return (3 + f(n + 1));
    }
    else
    {
        return (1 + f(n + 1));
    }
}

int g(int n)
{
    int j = 0;

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

        j = j + f(i);
    }
    return j;
}

(A) 6
(B) 11
(C) 13
(D) 14

第 10 題

下方 Mystery() 函式 else 部分運算式應為何，才能使得 Mystery(9) 的回傳值為 34？

int Mystery(int x)
{
    if (x <= 1)
    {
        return x;
    }
    else
    {
        return ___(?)___;
    }
}

(A) x + Mystery(x - 1)
(B) x * Mystery(x - 1)
(C) Mystery(x - 2) + Mystery(x + 2)
(D) Mystery(x - 2) + Mystery(x - 1)

第 11 題

給定下方 G(), K() 兩函式，執行 G(3) 後所回傳的值為何？

int K(int a[], int n)
{
    if (n >= 0)
        return (K(a, n - 1) + a[n]);
    else
        return 0;
}

int G(int n)
{
    int a[] = {5, 4, 3, 2, 1};
    return K(a, n);
}

(A) 5
(B) 12
(C) 14
(D) 15

第 12 題

下方函式以 F(7) 呼叫後回傳值為 12，則 <condition> 應為何？

int F(int a)
{
    if (<condition>)
        return 1;
    else
        return F(a - 2) + F(a - 3);
}

(A) a < 3
(B) a < 2
(C) a < 1
(D) a < 0

第 13 題

下方主程式執行完三次 G() 的呼叫後，p 陣列中有幾個元素的值為 0？

int K(int p[], int v)
{
    if (p[v] != v)
    {
        p[v] = K(p, p[v]);
    }
    return p[v];
}

void G(int p[], int l, int r)
{
    int a = K(p, l), b = K(p, r);
    if (a != b)
    {
        p[b] = a;
    }
}

int main(void)
{
    int p[5] = {0, 1, 2, 3, 4};
    G(p, 0, 1);
    G(p, 2, 4);
    G(p, 0, 4);
    return 0;
}

(A) 1
(B) 2
(C) 3
(D) 4

第 14 題

給定下方 G() 函式，執行 G(1) 後所輸出的值為何？

void G(int a)
{
    printf("%d ", a);

    if (a >= 3)
        return;
    else
        G(a + 1);

    printf("%d ", a);
}

(A) 1 2 3
(B) 1 2 3 2 1
(C) 1 2 3 3 2 1
(D) 以上皆非

第 15 題

下方程式執行後輸出為何？

int G(int B)
{
    B = B * B;
    return B;
}

int main()
{
    int A = 0, m = 5;

    A = G(m);
    if (m < 10)
        A = G(m) + A;
    else
        A = G(m);

    printf("%d \n", A);

    return 0;
}

(A) 0
(B) 10
(C) 25
(D) 50

第 16 題

下方 G() 應為一支遞迴函式，已知當 a 固定為 2，不同的變數 x 值會有不同的回傳值如下表所示。請找出 G() 函式中 (a) 處的計算式該為何？

int G(int a, int x)
{
    if (x == 0)
        return 1;
    else
        return ___(a)___;
}
a 值 x 值 G(a, x) 回傳值
2 0 1
2 1 6
2 2 36
2 3 216
2 4 1296
2 5 7776

(A) ((2 * a) + 2) * G(a, x - 1)
(B) (a + 5) * G(a - 1, x - 1)
(C) ((3 * a) - 1) * G(a, x - 1)
(D) (a + 6) * G(a, x - 1)

第 17 題

下方 G() 為遞迴函式，G(3, 7) 執行後回傳值為何？

int G(int a, int x)
{
    if (x == 0)
        return 1;
    else
        return (a * G(a, x - 1));
}

(A) 128
(B) 2187
(C) 6561
(D) 1024

第 18 題

下方函式若以 search(1, 10, 3) 呼叫時， search 函式總共會被執行幾次？

void search(int x, int y, int z)
{
    if (x < y)
    {
        t = ceiling((x + y) / 2);
        if (z >= t)
            search(t, y, z);
        else
            search(x, t - 1, z);
    }
}
// 註：ceiling() 為無條件進位至整數位。例如 ceiling(3.1) = 4, ceiling(3.9) = 4。

(A) 2
(B) 3
(C) 4
(D) 5

第 19 題

給定函式 A1()、 A2() 與 F() 如下，以下敘述何者有誤？

void A1(int n)
{
    F(n / 5);
    F(4 * n / 5);
}

void A2(int n)
{
    F(2 * n / 5);
    F(3 * n / 5);
}

void F(int x)
{
    int i;

    for (i = 0; i < x; i = i + 1)
        printf("*");

    if (x > 1)
    {
        F(x / 2);
        F(x / 2);
    }
}

(A) A1(5) 印的 * 個數比 A2(5) 多
(B) A1(13) 印的 * 個數比 A2(13) 多
(C) A2(14) 印的 * 個數比 A1(14) 多
(D) A2(15) 印的 * 個數比 A1(15) 多

第 20 題

下方 F() 函式回傳運算式該如何寫，才會使得 F(14) 的回傳值為 40 ?

int F(int n)
{
    if (n < 4)
        return n;
    else
        return ___(?)___;
}

(A) n * F(n - 1)
(B) n + F(n - 3)
(C) n - F(n - 2)
(D) F(3n + 1)

第 21 題

若以 B(5, 2) 呼叫下方 B() 函式，總共會印出幾次 "base case"？

int B(int n, int k)
{
    if (k == 0 || k == n)
    {
        printf("base case\n");
        return 1;
    }
    return B(n - 1, k - 1) + B(n - 1, k);
}

(A) 1
(B) 5
(C) 10
(D) 19

第 22 題

若以 G(100) 呼叫下方函式後，n 的值為何?

int n = 0;

void K(int b)
{
    n = n + 1;
    if (b % 4)
        K(b + 1);
}

void G(int m)
{
    for (int i = 0; i < m; i = i + 1)
    {
        K(i);
    }
}

(A) 25
(B) 75
(C) 150
(D) 250

第 23 題

若以 F(15) 呼叫下方 F() 函式，總共會印出幾行數字？

void F(int n)
{
    printf("%d\n", n);
    if ((n % 2 == 1) && (n > 1))
    {
        return F(5 * n + 1);
    }
    else
    {
        if (n % 2 == 0)
            return F(n / 2);
    }
}

(A) 16 行
(B) 22 行
(C) 11 行
(D) 15 行

第 24 題

若以 F(5, 2) 呼叫下方 F() 函式，執行完畢後回傳值為何?

int F(int x, int y)
{
    if (x < 1)
        return 1;
    else
        return F(x - y, y) + F(x - 2 * y, y);
}

(A) 1
(B) 3
(C) 5
(D) 8

解答

1 2 3 4 5
B B B C C
6 7 8 9 10
A C B C D
11 12 13 14 15
C D C B D
16 17 18 19 20
A B C D B
21 22 23 24 25
C D D C -

<< APCS 觀念題 - 函式與變數作用域 | 目錄 | APCS 觀念題 - 演算法與資料結構 >>

Last changed by 
 
kinoe_T
:D
0
2
1401

Read more

APCS 觀念題 - 運算式

下方程式碼執行後輸出結果為何？

Apr 4, 2025
Computer Networking — 2.7 Socket Programming: Creating Network Applications

contributed by <kaeteyaruyo>

Apr 2, 2025
Computer Networking — 3.1 Introduction and Transport-Layer Services

contributed by <kaeteyaruyo>

Mar 26, 2025
Computer Networking — 2.4 DNS — The Internet’s Directory Service

contributed by <kaeteyaruyo>

Mar 24, 2025
Read more from kinoe_T
Published on HackMD