APCS Python 程式識讀｜自訂題目試作 30 題

下列程式執行後，輸出結果為何？

total = 0

for i in range(3):
    for j in range(i, 4, 2):
        for k in range(j, 5):
            total += 1

print(total)

1. 12
2. 14
3. 17
4. 20

下列程式執行後，輸出結果為何？

t = 0

def g(x, y):
    global t
    if x == 0 and y == 1:
        t += 1
    if x <= 0 or y <= 0:
        return 3
    return 5 + f(x, y - 1)

def f(x, y):
    if x <= 0 or y <= 0:
        return 2
    return g(x - 1, y) + 2 * g(x - 2, y - 1)

print(f(5, 5), t)

1. 229 8
2. 229 16
3. 226 8
4. 226 16

下列函式使用「左右端點都包含」的區間進行二分搜尋。空格（甲）、（乙）、（丙）應填入哪一組，才能正確搜尋？

def binary_search(values, target):
    left = 0
    right = len(values) - 1

    while （甲）:
        mid = (left + right) // 2
        if values[mid] == target:
            return mid
        elif values[mid] < target:
            left = （乙）
        else:
            right = （丙）

    return -1

values = [1, 3, 4, 7, 8, 10, 12, 15]
print(binary_search(values, 10),
      binary_search(values, 9))

1. left <= right、mid + 1、mid - 1
2. left < right、mid + 1、mid - 1
3. left <= right、mid、mid
4. left < right、mid、mid

下列程式執行後，輸出結果為何？

data = [95, 27, 90, 49, 80, 58, 6, 9, 18, 50]
count = 0
n = len(data)

for i in range(n - 1):
    for j in range(n - i - 1):
        if data[j] < data[j + 1]:
            data[j], data[j + 1] = data[j + 1], data[j]
            count += 1

print(count, data[0], data[-1])

1. 14 95 6
2. 31 95 6
3. 14 6 95
4. 24 95 6

數字 1、2、3、4、5 只能依此順序放入 Stack(堆疊)，但可在任意時機取出頂端元素。下列程式會判斷指定的取出順序是否可能發生。哪一個選項會使函式回傳 True？

def possible(order):
    stack = []
    next_value = 1

    for x in order:
        while next_value <= 5 and \
              (not stack or stack[-1] != x):
            stack.append(next_value)
            next_value += 1

        if stack and stack[-1] == x:
            stack.pop()
        else:
            return False

    return True

1. [3, 2, 5, 4, 1]
2. [3, 1, 2, 5, 4]
3. [2, 4, 1, 5, 3]
4. [4, 2, 5, 3, 1]

下列程式以列表搭配 front 模擬 Queue(佇列)。每次從佇列前端取出一個數字，轉換後再加入尾端。程式執行後輸出為何？

q = [2, 5, 1, 4]
front = 0

for _ in range(5):
    x = q[front]
    front += 1

    if x % 2 == 0:
        q.append(x // 2)
    else:
        q.append(x + 3)

print(q[front:])

1. [1, 8, 4, 2]
2. [8, 4, 2, 4]
3. [4, 2, 4, 8]
4. [2, 5, 1, 4]

下列程式使用 Stack(堆疊)計算 Postfix Expression(後序運算式)。其中除法使用整數除法。程式執行後輸出為何？

tokens = [9, 2, '-', 4, 3, '+', '*', 5, '/']
stack = []

for token in tokens:
    if isinstance(token, int):
        stack.append(token)
    else:
        b = stack.pop()
        a = stack.pop()

        if token == '+':
            stack.append(a + b)
        elif token == '-':
            stack.append(a - b)
        elif token == '*':
            stack.append(a * b)
        else:
            stack.append(a // b)

print(stack[-1])

1. 7
2. 9
3. 10
4. 49

下列函式使用 Binary Search(二分搜尋)尋找數字 3。四個數列都包含 3，但哪一個數列會使函式錯誤地回傳 -1？

def binary_search(values, target):
    left = 0
    right = len(values) - 1

    while left <= right:
        mid = (left + right) // 2

        if values[mid] == target:
            return mid
        elif values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

1. [1, 2, 3, 4, 5, 6]
2. [1, 4, 5, 2, 3, 6]
3. [2, 2, 3, 4, 4, 5]
4. [1, 1, 2, 3, 3, 3]

下列 Bubble Sort(氣泡排序)不使用暫存變數，也不使用 Python 的多重指定，而是利用加減法交換相鄰元素。空格（甲）、（乙）應填入哪一組，才能正確完成由小到大排序？

def bubble_sort(data):
    n = len(data)

    for i in range(n - 1):
        for j in range(n - i - 1):
            if data[j] > data[j + 1]:
                data[j] = data[j] + data[j + 1]
                data[j + 1] = data[j] - （甲）
                data[j] = data[j] - （乙）

data = [7, 2, 5, 1]
bubble_sort(data)
print(data)

1. （甲）data[j + 1]　（乙）data[j + 1]
2. （甲）data[j]　　　（乙）data[j + 1]
3. （甲）data[j + 1]　（乙）data[j]
4. （甲）data[j]　　　（乙）data[j]

將下列 Infix Expression(中序運算式)轉換成 Postfix Expression(後序運算式)，哪一個結果正確？

3 * 5 + 6 * 8 - 8 / 9

1. 3 5 * 6 8 * + 8 9 / -
2. 3 5 6 8 * + * 8 9 / -
3. 3 5 * 6 8 * 8 9 / - +
4. 3 5 * 6 8 * + 8 9 - /

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

a = [1, 2, 3]
b = a

b[1] = 9
b.append(4)

print(a)

1. [1, 2, 3]
2. [1, 9, 3]
3. [1, 2, 3, 4]
4. [1, 9, 3, 4]

下列程式執行後，a 與 b 分別為何？

a = [[1, 2], [3, 4]]
b = a[:]

b[0][0] = 9
b[1] = [7, 8]

print(a)
print(b)

1. [[1, 2], [3, 4]]
   [[9, 2], [7, 8]]

2. [[9, 2], [3, 4]]
   [[9, 2], [7, 8]]

3. [[9, 2], [7, 8]]
   [[9, 2], [7, 8]]

4. [[1, 2], [7, 8]]
   [[9, 2], [7, 8]]

下列程式原本想建立三個互相獨立的列。執行後實際輸出為何？

grid = [[0] * 3] * 3
grid[1][2] = 7

print(grid)

1. [[0, 0, 0], [0, 0, 7], [0, 0, 0]]
2. [[0, 0, 7], [0, 0, 7], [0, 0, 7]]
3. [[7, 0, 0], [7, 0, 0], [7, 0, 0]]
4. 程式會在建立 grid 時發生錯誤

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

def change(x, data):
    x = x + 5
    data[0] = data[0] + 5
    data = data + [99]

n = 10
a = [10]
change(n, a)

print(n, a)

1. 10 [10]
2. 15 [15, 99]
3. 10 [15]
4. 15 [15]

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

a = [3, 1, 2]
b = a.sort()
c = sorted(a, reverse=True)

print(a)
print(b)
print(c)

1. [1, 2, 3]
   None
   [3, 2, 1]

2. [3, 1, 2]
   [1, 2, 3]
   [3, 2, 1]

3. [1, 2, 3]
   [1, 2, 3]
   [3, 2, 1]

4. [3, 2, 1]
   None
   [1, 2, 3]

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

s = "ABCDEFG"
print(s[-2], s[1:6:2], s[::-2])

1. F BDF GECA
2. F BDF ACEG
3. G BCE GEC
4. F BDF GFEDCBA

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

def check(s):
    left = 0
    right = len(s) - 1
    count = 0

    while left < right:
        count += 1
        if s[left] != s[right]:
            return False, count
        left += 1
        right -= 1

    return True, count

print(check("LEVEL"), check("LEVER"))

1. (True, 2) (False, 1)
2. (True, 3) (False, 2)
3. (False, 2) (True, 1)
4. (True, 5) (False, 5)

下列程式要將 AAABBCCCC 壓縮成 A3B2C4。空格應填入哪一行？

s = "AAABBCCCC"
result = ""
count = 1

for i in range(1, len(s)):
    if s[i] == s[i - 1]:
        count += 1
    else:
        result += s[i - 1] + str(count)
        count = 1

____________________________
print(result)

1. result += s[0] + str(count)
2. result += s[-1] + str(count)
3. result += s[i - 1] + str(i)
4. result += str(count) + s[0]

下列 Selection Sort 執行完第一次外層迴圈，也就是 i == 0 的那一輪後，a 為何，且實際交換幾次？

a = [7, 3, 5, 2]

for i in range(len(a) - 1):
    pos = i
    for j in range(i + 1, len(a)):
        if a[j] < a[pos]:
            pos = j
    a[i], a[pos] = a[pos], a[i]

1. [3, 7, 5, 2]
2. [2, 3, 5, 7]，且第一輪發生兩次交換
3. [2, 3, 5, 7]，且第一輪發生三次交換
4. [2, 3, 5, 7]，且第一輪只在最後交換一次

下列程式將索引 3 的元素插入前方已排序區域。執行後 a 為何？

a = [2, 5, 7, 3, 9]

key = a[3]
j = 2

while j >= 0 and a[j] > key:
    a[j + 1] = a[j]
    j -= 1

a[j + 1] = key

1. [2, 5, 3, 7, 9]
2. [2, 3, 5, 7, 9]
3. [3, 2, 5, 7, 9]
4. [2, 5, 7, 9, 3]

下列程式的主要特徵是選出一個 key，把較大的元素向右搬移，再把 key 放入空出的正確位置。這是哪一種演算法？

for i in range(1, len(a)):
    key = a[i]
    j = i - 1

    while j >= 0 and a[j] > key:
        a[j + 1] = a[j]
        j -= 1

    a[j + 1] = key

1. Bubble Sort(氣泡排序)
2. Selection Sort(選擇排序)
3. Insertion Sort(插入排序)
4. Binary Search(二分搜尋)

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

a = [4, 8, 1, 6, 9, 3]
target = 9
comparisons = 0

for i in range(len(a)):
    comparisons += 1
    if a[i] == target:
        break

print(i, comparisons)

1. 4 4
2. 4 5
3. 5 5
4. 5 6

下列函式想回傳串列中的最大值，但初始化方式有問題。哪一組輸入最能測出錯誤？

def find_max(a):
    answer = 0

    for x in a:
        if x > answer:
            answer = x

    return answer

1. [1, 2, 3]
2. [0, 5, 2]
3. [-5, -2, -8]
4. [10]

下列函式要回傳已排序串列中 target 第一次出現的索引。找到目標後，空格應填什麼？

def first_pos(values, target):
    left = 0
    right = len(values) - 1
    answer = -1

    while left <= right:
        mid = (left + right) // 2

        if values[mid] == target:
            answer = mid
            __________________
        elif values[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return answer

1. left = mid + 1
2. right = mid - 1
3. return mid
4. right = mid + 1

下列程式以固定長度串列模擬 Stack。關於這組函式，下列敘述何者正確？

storage = [None] * 3
top = 0

def push(x):
    global top
    storage[top] = x
    top += 1

def pop():
    global top
    top -= 1
    return storage[top]

1. 空堆疊呼叫 pop() 時會回傳 None，且 top 仍維持 0
2. 空堆疊呼叫 pop() 時，top 會變成 -1，並讀取串列最後一格，未正確偵測下溢
3. 堆疊滿時呼叫 push()，Python 會自動擴充 storage
4. top 永遠指向目前堆疊頂端的元素

下列程式以固定長度串列模擬 Queue。依序加入 10、20、30，取出兩次，再加入 40、50。此時若再加入 60，主要問題是什麼？

Q = [None] * 5
front = 0
rear = 0

def enqueue(x):
    global rear
    Q[rear] = x
    rear += 1

def dequeue():
    global front
    x = Q[front]
    front += 1
    return x

1. 60 會自動存到索引 0，因此沒有問題
2. 雖然索引 0、1 已空出，但 rear 已到 5，再寫入會越界；函式沒有重用前端空間
3. dequeue() 會從尾端取出資料
4. Queue 中仍有五個有效元素，因此本來就不應再加入

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

a = [1, 2, 2, 2, 3]

for x in a:
    if x == 2:
        a.remove(x)

print(a)

1. [1, 3]
2. [1, 2, 3]
3. [1, 2, 2, 3]
4. 迴圈會無限執行

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

calls = 0

def check(x):
    global calls
    calls += 1
    return x > 0

result = check(0) and check(1) or check(2)

print(result, calls)

1. False 1
2. False 2
3. True 2
4. True 3

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

grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

total = 0

for i in range(len(grid)):
    for j in range(len(grid[i])):
        if i == j or i + j == len(grid) - 1:
            total += grid[i][j]

print(total)

1. 20
2. 25
3. 30
4. 35

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

a = 48
b = 18
count = 0

while b != 0:
    a, b = b, a % b
    count += 1

print(a, count)

1. 6 2
2. 6 3
3. 12 2
4. 12 3