Multiple Choice

Question 1 Which of the following software is NOT produced by Microsoft? A. Powerpoint B. Word C. Excel D. Acrobat Reader Answer: D Explanation: Options A, B, and C are part of Microsoft Office. Acrobat Reader is developed by Adobe.

Question 2 How many bits are minimally required to represent 256 colors in binary? A. 6 B. 7 C. 8 D. 9 Answer: C Explanation: 2^8 = 256.

Question 3 Which of the following is NOT a wireless communication technology? A. Bluetooth B. WiFi C. GPRS D. Ethernet Answer: D Explanation: Ethernet is a wired networking technology.

Question 4 Which company is NOT a CPU manufacturer? A. Intel B. AMD C. Microsoft D. IBM Answer: C Explanation: Microsoft is a software company. IBM and others listed manufacture CPUs.

Question 5 Which is NOT a storage device? A. Optical disc B. Magnetic disk C. Solid-state drive D. Mouse Answer: D Explanation: A mouse is an input device, not a storage device.

Question 6 Starting with lowercase input mode, if a user presses keys in the repeating sequence CapsLock, A, S, D, CapsLock, A, S, D..., what is the 81st character displayed? A. A B. S C. D D. a Answer: C Explanation: The output cycles through A, S, D, a, s, d every 6 keystrokes. 81 % 6 = 3, which corresponds to the third character, 'D'.

Question 7 The sum of the binary numbers 00101100 and 00010101 is: A. 00101000 B. 01000001 C. 01000100 D. 00111000 Answer: B Explanation: Binary addition yields 01000001.

Question 8 The octal number equivalent to the binary fraction 0.1 is: A. 0.8 B. 0.4 C. 0.2 D. 0.1 Answer: B Explanation: (0.1)₂ = (0.5)₁₀ = (0.4)₈.

Question 9 A key difference between a 32-bit and a 64-bit machine is: A. The display monitor B. Hard drive size C. Addressable memory space D. Input method Answer: C Explanation: The primary distinction is the size of the addressable memory space.

Question 10 Which statement about strings is correct? A. A string is a special type of linear list. B. The length of a string must be greater than zero. C. Strings cannot be represented using arrays. D. A string consisting solely of space characters is an empty string. Answer: A Explanation: A string is essentially a character array, which is a linear data structure. An empty string has zero length.

Question 11 For a given binary tree, if stored sequentially in a 1-indexed array where a node at index i has its left child at 2i and right child at 2i+1, what is the maximum array index for all nodes in the depicted tree? A. 6 B. 10 C. 12 D. 15 Answer: D Explanation: Traversing the tree structure yields a maximum index of 15.

Question 12 Given the code segment:

s = a;
for (b = 1; b <= c; b++)
    s = s + 1;

Which assignment statement is equivalent in modifying s? A. s = a + b; B. s = a + c; C. s = s + c; D. s = b + c; Answer: B Explanation: The loop adds 1 to s exactly c times, equivalent to s = a + c.

Question 13 What is the output of the following program?

#include <iostream>
using namespace std;
int main() {
    int k = 4, n = 0;
    while (n < k) {
        n++;
        if (n % 3 != 0)
            continue;
        k--;
    }
    cout << k << "," << n << endl;
    return 0;
}

A. 2,2 B. 2,3 C. 3,2 D. 3,3 Answer: D Explanation: Tracing the loop: k decrements only when n is a multiple of 3. The loop exits when n reaches 3 and k becomes 3.

Question 14 Given a unimodal array L (single peak), the following algorithm finds the peak. Fill in blanks a-c.

Search(1, n)
1. k ← ⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3.    then ____
4. else if L[k] > L[k-1] and L[k] < L[k+1]
5.    then ____
6. else ____

Options: a. Search(k+1, n) b. Search(1, k-1) c. return L[k] Correct order: A. c, a, b B. c, b, a C. a, b, c D. b, a, c Answer: A Explanation: Line 3 returns the peak when found. Line 5 searches the right half if k is on the ascending slope. Line 6 searches the left half otherwise.

Question 15 A simple undirected graph G has 16 edges, and every vertex has degree 2. How many vertices does G have? A. 10 B. 12 C. 8 D. 16 Answer: D Explanation: The sum of degrees is 2 * number_of_edges = 32. If each vertex has degree 2, the number of vertices is 32 / 2 = 16.

Question 16 In how many ways can 7 identical apples be placed into 3 identical boxes? A. 7 B. 8 C. 21 D. 3⁷ Answer: B Explanation: Enumreating partitions: (7,0,0), (6,1,0), (5,2,0), (4,3,0), (5,1,1), (4,2,1), (3,3,1), (3,2,2). Total 8 ways.

Question 17 Given an irrigation system diagram with valves A, B, C, D, which valve configuration(s) allow water to reach the tree? A. Open B only. B. Open A and B, close C and D. C. Open A only. D. Open D only. Answer: A Explanation: With only valve B open, water flows to the tree.

Quession 18 Based on a social network graph and sharing rules, Lucia wants to share a photo but prevent Jacob from seeing it. To which set of friends can she share? A. Dana, Michael, Eve B. Dana, Eve, Monica C. Michael, Eve, Jacob D. Michael, Peter, Monica Answer: A Explanation: Sharing to sets B, C, or D would allow the photo to reach Jacob directly or via a friend. Set A does not include Jacob or his immediate connections.

Question 19 A family of three prepares three dishes sequentially. Washing takes 10 min, cutting 10 min, cooking 10 min per dish. Different dishes cannot share the same step simultaneously. What is the minimum total time? A. 90 B. 60 C. 50 D. 40 Answer: C Explanation: An optimal pipeline schedule:

• 0-10: Wash Dish 1.
• 10-20: Wash Dish 2, Cut Dish 1.
• 20-30: Wash Dish 3, Cut Dish 2, Cook Dish 1.
• 30-40: Cut Dish 3, Cook Dish 2.
• 40-50: Cook Dish 3. Total: 50 minutes.

Question 20 Which item is NOT allowed in the NOI competition exam hall? A. Pen B. Appropriate clothing C. USB drive D. Pencil Answer: C Explanation: Electronic storage devices like USB drives are prohibited.

Problem Solving

Question 21 Choosing two squares from a 4×4 board such that they are not in the same row or column: _____ ways. Answer: 72 Explanation: First choice: 16 squares. Second choice: 9 squares not in same row/column. Since order doesn't matter, total = (16 * 9) / 2 = 72.

Question 22 For a binary tree with root height defined as 1: A tree with 2016 nodes has a minimum of _____ leaf nodes. The minimum possible height for a tree with 2016 nodes is _____. Answer: 1, 11 Explanation: A degenerate tree (linked list) has only one leaf. The minimum height for n nodes is achieved by a complete binary tree. 2¹⁰ - 1 = 1023 < 2016 ≤ 2¹¹ - 1 = 2047, so height is 11.

Program Reading

Question 23

#include <iostream>
using namespace std;
int main() {
    int max_val, min_val, total, cnt = 0;
    int input_val;
    cin >> input_val;
    if (input_val == 0) return 0;
    max_val = min_val = total = input_val;
    cnt++;
    while (input_val != 0) {
        cin >> input_val;
        if (input_val != 0) {
            total += input_val;
            cnt++;
            if (input_val > max_val) max_val = input_val;
            if (input_val < min_val) min_val = input_val;
        }
    }
    cout << max_val << ", " << min_val << ", " << total / cnt << endl;
    return 0;
}

Input: 1 2 3 4 5 6 0 7 Output: _____ Answer: 6, 1, 3 Explanation: The program stops reading at 0. It processes numbers 1 through 6. Max=6, min=1, sum=21, count=6, average=3.

Question 24

#include <iostream>
using namespace std;
int main() {
    int i = 100, x = 0, y = 0;
    while (i > 0) {
        i--;
        x = i % 8;
        if (x == 1) y++;
    }
    cout << y << endl;
    return 0;
}

Output: _____ Answer: 13 Explanation: Counts numbers from 99 down to 0 that are congruent to 1 modulo 8. There are 13 such numbers.

Question 25

#include <iostream>
using namespace std;
int main() {
    int arr[6] = {1, 2, 3, 4, 5, 6};
    int left = 0;
    int right = 5;
    int temp_val, idx;
    while (left < right) {
        temp_val = arr[left];
        arr[left] = arr[right];
        arr[right] = temp_val;
        left++;
        right--;
    }
    for (idx = 0; idx < 6; idx++)
        cout << arr[idx] << ",";
    cout << endl;
    return 0;
}

Output: _____ Answer: 6,5,4,3,2,1, Explanation: The while loop reverses the array. The output includes trailing commas.

Question 26

#include <iostream>
using namespace std;
int main() {
    int idx, len1, len2;
    string str1, str2;
    str1 = "I have a dream.";
    str2 = "I Have A Dream.";
    len1 = str1.size();
    len2 = str2.size();
    for (idx = 0; idx < len1; idx++)
        if (str1[idx] >= 'a' && str1[idx] <= 'z')
            str1[idx] -= 'a' - 'A';
    for (idx = 0; idx < len2; idx++)
        if (str2[idx] >= 'a' && str2[idx] <= 'z')
            str2[idx] -= 'a' - 'A';
    if (str1 == str2)
        cout << "=" << endl;
    else if (str1 > str2)
        cout << ">" << endl;
    else
        cout << "<" << endl;
    return 0;
}

Output: _____ Answer: = Explanation: Both strings are converted to uppercase, resulting in "I HAVE A DREAM.", so they are equal.

Program Completion

(Integer Input) Complete the program to read two integers within the int range, each on a separate line, ignoring spaces and newlines.

#include <iostream>
using namespace std;
int readint() {
    int result = 0;
    int is_negative = 0;
    char ch;
    ch = cin.get();
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = __1__;
    if (ch == '-')
        is_negative = 1;
    else
        __2__;
    ch = cin.get();
    while (__3__) {
        __4__;
        ch = cin.get();
    }
    if (is_negative == 1)
        __5__;
    return result;
}
int main() {
    int first, second;
    first = readint();
    second = readint();
    cout << first << endl << second << endl;
    return 0;
}

Question 27 Blank 1: _____ Answer: ch = cin.get() Explanation: Reads the next character to skip non-digit, non-minus characters.

Question 28 Blank 2: _____ Answer: result = ch - '0' Explanation: Converts the first digit character to its integer value.

Question 29 Blank 3: _____ Answer: ch >= '0' && ch <= '9' Explanation: Continues processing while the character is a digit.

Question 30 Blank 4: _____ Answer: result = result * 10 + (ch - '0') Explanation: Builds the integer from successive digits.

Question 31 Blank 5: _____ Answer: return -result Explanation: Returns the negative value if the flag was set.

(Outing Activity) Program uses binary search and greedy strategy to find the maximum number of students who can rent bicycles given personal money M[i], bike prices C[j], and a total school budget A.

#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], left_bound, right_bound, answer, mid;
bool feasible(int num_people) {
    int extra_cost = 0, i, j;
    i = __1__;
    j = 1;
    while (i <= n) {
        if (__2__)
            extra_cost += C[j] - M[i];
        i++;
        j++;
    }
    return __3__;
}
void sort_arr(int arr[], int low, int high) {
    int left_idx = low, right_idx = high, pivot = arr[(low + high) / 2], temp;
    while (left_idx <= right_idx) {
        while (arr[left_idx] < pivot) left_idx++;
        while (arr[right_idx] > pivot) right_idx--;
        if (left_idx <= right_idx) {
            temp = arr[left_idx]; arr[left_idx] = arr[right_idx]; arr[right_idx] = temp;
            left_idx++; right_idx--;
        }
    }
    if (left_idx < high) sort_arr(arr, left_idx, high);
    if (low < right_idx) sort_arr(arr, low, right_idx);
}
int main() {
    int idx;
    cin >> n >> B >> A;
    for (idx = 1; idx <= n; idx++)
        cin >> M[idx];
    for (idx = 1; idx <= B; idx++)
        cin >> C[idx];
    sort_arr(M, 1, n);
    sort_arr(C, 1, B);
    left_bound = 0;
    right_bound = n;
    while (left_bound <= right_bound) {
        mid = (left_bound + right_bound) / 2;
        if (__4__) {
            answer = mid;
            left_bound = mid + 1;
        } else {
            right_bound = __5__;
        }
    }
    cout << answer << endl;
    return 0;
}

Question 32 Blank 1: _____ Answer: n - num_people + 1 Explanation: Start from the num_people-th richest person (after sorting M ascending).

Question 33 Blank 2: _____ Answer: C[j] > M[i] Explanation: If the bike price exceeds the student's money, the school covers the difference.

Question 34 Blank 3: _____ Answer: extra_cost <= A Explanation: The total subsidy needed must not exceed the school budget.

Question 35 Blank 4: _____ Answer: feasible(mid) Explanation: Checks if mid students can be served.

Question 36 Blank 5: _____ Answer: mid - 1 Explanation: Standard binary search update when condition fails.