Multiple Choice

Question 1

In 8-bit two's complement representation, the binary number 10101011 represents which decimal value?

A. 43 B. -85 C. -43 D. -84

Answer: B

Explanation: Positive numbers have identical representation in original code, one's complement, and two's complement. The most significant bit serves as the sign bit, where 0 indicates positive and 1 indicates negative.

For negative numbers:

• One's complement: invert all bits except the sign bit
• Two's complement: add 1 to the one's complement

To find the decimal value, invert the bits and add 1:

Original: 10101011 Invert: 01010100 Add 1: 01010101 = 85

Since the MSB is 1, this represents -85.

---

Question 2

What is the fundamental unit for storing data in a computer?

A. bit B. Byte C. GB D. KB

Answer: B

Explanation: A byte (8 bits) is the basic addressable unit of memory. While a bit is the smallest unit of information, bytes are the fundamental unit for data storage and addressing.

---

Question 3

Which protocol is NOT related to electronic mail?

A. POP3 B. SMTP C. WTO D. IMAP

Answer: C

Explanation: POP3 (Post Office Protocol v3) and IMAP (Internet Message Access Protocol) are protocols for retrieving emails from a mail server. SMTP (Simple Mail Transfer Protocol) handles email transmission. WTO stands for World Trade Organization and has no connection to email systems.

---

Question 4

A bitmap image with resolution 800×600 at 16-bit color depth requires how much storage space?

A. 937.5 KB B. 4218.75 KB C. 4320 KB D. 2880 KB

Answer: A

Explanation: The storage requirement is calculated as:

800 × 600 × 16 / 8 / 1024 = 937.5 KB

Each pixel at 16-bit depth uses 2 bytes. Dividing by 1024 converts bytes to kilobytes.

---

Question 5

Which was the earliest application domain for computers?

A. Numerical computation B. Artificial intelligence C. Robotics D. Process control

Answer: A

Explanation: Computers were originally developed to perform complex calculations, such as computing missile trajectory paths. Numerical computation predates all other application areas.

---

Question 6

Which of the following is NOT an object-oriented programming language?

A. C B. C++ C. Java D. C#

Answer: A Explanation: C++ (originally "C with Classes"), Java, and C# are all object-oriented languages supporting classes, objects, inheritance, and polymorphism. C is a procedural language that does not have built-in object-oriented features.

---

Question 7

What does NOI stand for in Chinese?

A. China Informatics League B. National Youth Informatics Olympiad C. China Youth Informatics Olympiad D. China Computer Association

Answer: B Explanation: NOI stands for National Olympiad in Informatics. It is China's national-level competition for high school students in competitive programming.

---

Question 8

October 1, 2017 was a Sunday. What day of the week was October 1, 1999?

A. Wednesday B. Sunday C. Friday D. Tuesday

Answer: C

Explanation: In non-leap years, 365 % 7 = 1, meaning the day advances by 1 each year. In leap years, 366 % 7 = 2, advancing by 2.

From 1999 to 2017: 18 years total, with 5 leap years and 13 common years. Total advancement: 5 × 2 + 13 × 1 = 23 days 23 % 7 = 2

Advancing 2 days from Sunday: Friday

---

Question 9

Three students A, B, and C select courses. From 4 available courses, A selects 2, while B and C each select 3. How many different selection combinations are possible?

A. 36 B. 48 C. 96 D. 192

Answer: C

Explanation: Using combinations:

• A selects 2 from 4: C(4,2) = 6
• B selects 3 from 4: C(4,3) = 4
• C selects 3 from 4: C(4,3) = 4

Total: 6 × 4 × 4 = 96

---

Question 10

Let G be a connected graph with n vertices and m edges (n ≤ m). How many edges must be removed to make G a tree?

A. m - n + 1 B. m - n C. m + n + 1 D. n - m + 1

Answer: A

Explanation: A tree with n vertices must have exactly n - 1 edges. Starting with m edges and needing n - 1 edges:

m - x = n - 1 x = m - n + 1

---

Question 11

For a given sequence {aₖ}, an inversion pair (i, j) exists if and only if i < j and aᵢ > aⱼ. How many inversion pairs exist in the sequence 1, 7, 2, 3, 5, 4?

A. 4 B. 5 C. 6 D. 7

Answer: B

Explanation: Listing all pairs where earlier elements exceed later ones:

• (7, 2), (7, 3), (7, 5), (7, 4), (5, 4)

Total: 5 inversion pairs

---

Question 12

The postfix (Reverse Polish) notation of the expression a × (b + c) × d is:

A. abcd*+* B. abc+d C. abc+d D. b+cad

Enswer: B

Explanation: Constructing the expression tree and performing postorder traversal yields: abc+d

---

Question 13

When inserting a node pointed to by s in to a linked stack with top pointer hs, which operation should be performed?

A. hs->next = s; B. s->next = hs; hs = s; C. s->next = hs->next; hs->next = s; D. s->next = hs; hs = hs->next;

Answer: B

Explanation: Push operation on a linked stack: first set the new node's next pointer to the current top, then update the top pointer to the new node.

---

Question 14

If string S = "copyright", how many substrings does it contain?

A. 72 B. 45 C. 46 D. 36

Answer: C

Explanation: A string of length n has (1+n) × n / 2 non-empty substrings. For n = 9: 45 substrings Including the empty string: 46 total

---

Question 15

What is the binary representation of decimal 13.375?

A. 1101.011 B. 1011.011 C. 1101.101 D. 1010.01

Answer: A

Explanation:

• Integer part: 13 = 1101
• Fractional part: 0.375 = 0.25 + 0.125 = 1/4 + 1/8 = 0.011

Combined: 1101.011

---

Question 16

For the input sequence a, b, c, d, e, f, g pushed onto a stack, which of the following CANNOT be a valid output sequence?

A. a, b, c, d, e, f, g B. a, d, c, b, e, g, f C. a, d, b, c, g, f, e D. g, f, e, d, c, b, a

Answer: C

Explanation: Stack operations must maintain LIFO ordering. In option C, after outputting 'd', element 'b' appears before 'c'. This violates stack behavior since 'c' was pushed before 'b'.

---

Question 17

Given two sorted arrays A and B of length n, a merge algorithm based on element comparison requires at least how many comparisons in the worst case?

A. n² B. n log n C. 2n D. 2n - 1

Answer: D

Explanation: Merging 2n elements requires comparing elements from both arrays. In the worst case, only one element remains uncompared (the last one).

2n - 1 comparisons are necessary and sufficient.

---

Question 18

Starting from which year did the NOIP competition stop supporting Pascal?

A. 2020 B. 2021 C. 2022 D. 2023

Answer: C

Explanation: NOI (National Olympiad in Informatics) announced that Pascal support would be discontinued starting in 2022.

---

Question 19

A family has four members. What is the probability that at least two people share the same birth month? (Assume uniform distribution across months and independence)

A. 1/12 B. 1/144 C. 41/96 D. 3/4

Answer: C

Explanation: Calculate the complement (all four have different months): P(all different) = (12 × 11 × 10 × 9) / (12⁴) = 11880 / 20736 = 55/96

P(at least two same) = 1 - 55/96 = 41/96

---

Question 20

Which prestigious award is most closely related to computer science?

A. Oscar Award B. Turing Award C. Nobel Prize D. Pulitzer Prize

Answer: B

Explanation: The Turing Award is the highest recognition in computer science, equivalent to the Nobel Prize in computing.

---

Problem Solving

Question 21

A person stands at coordinates (0, 0), facing the positive x-axis. In round 1, walk 1 unit and turn right; in round 2, walk 2 units and turn right; continuing this pattern, walk n units and turn right in round n. What are the coordinates after round 2017?

Answer: 1009, 1008

Explanation: The movement pattern repeats every 4 rounds:

• Round 1: moves along +x
• Round 2: moves along -y
• Round 3: moves along -x
• Round 4: moves along +y

The sequence of positions:

• Round 0: (0, 0)
• Round 1: (1, 0)
• Round 2: (1, -2)
• Round 3: (-2, -2)
• Round 4: (-2, 2)
• Round 5: (3, 2)
• Round 6: (3, -4)

The x-coordinate increases by 1 in odd-numbered rounds (1, 3, 5, ...), while the y-coordinate pattern follows even rounds.

2017 % 4 = 1, so the position is determined by the first case in the cycle. Using the accumulated sums:

• x = 1 + 3 + 5 + ... + 2017 = 1009
• y follows the -y movements: -(2 + 4 + 6 + ... + 2016) = -1008

Final position: (1009, 1008)

---

Question 22

As shown in the diagram, there are 13 cells. Performing an operation on any cell toggles that cell and its four orthogonal neighbors (1↔0). What is the minimum number of operations required to make all cells 0?

Answer: 3

Explanation: This is a classic lights-out puzzle. Strategic placement of operations can toggle specific patterns. The minimum solution requires 3 operations, applied to the top cell, the second-from-right cell, and the center cell.

---

Program Analysis

Program 1

#include <iostream>
using namespace std;

int main() {
    int freq[256] = {0};
    string input;
    cin >> input;
    
    for (int i = 0; i < input.length(); i++)
        freq[input[i]]++;
    
    for (int i = 0; i < input.length(); i++) {
        if (freq[input[i]] == 1) {
            cout << input[i] << endl;
            return 0;
        }
    }
    cout << "no" << endl;
    return 0;
}

Question 23: Input: xyzxyw Output: ?

Answer: z

Explanation: The program counts character frequencies and outputs the first character that appears exactly once. In "xyzxyw":

• x: 2 times
• y: 2 times
• z: 1 time
• w: 1 time

The first character with frequency 1 is 'z'.

---

Program 2

#include <iostream>
using namespace std;

int compute(int total, int groups, int start) {
    int result = 0;
    if (groups == 1)
        return 1;
    
    for (int i = start; i <= total / groups; i++)
        result += compute(total - i, groups - 1, i);
    return result;
}

int main() {
    int m, n;
    cin >> m >> n;
    cout << compute(m, n, 0) << endl;
    return 0;
}

Question 24: Input: 7 3 Output: ?

Answer: 8

Explanation: This recursive function counts ways to partition m into n positive integers in non-decreasing order.

compute(7, 3, 0):

• i=0: compute(7, 2, 0) = compute(7,1,0) + compute(6,1,1) + compute(5,1,2) + compute(4,1,3) = 4
• i=1: compute(6, 2, 1) = compute(5,1,1) + compute(4,1,2) + compute(3,1,3) = 3
• i=2: compute(5, 2, 2) = compute(3,1,2) = 1

Total: 4 + 3 + 1 = 8

---

Program 3

#include <iostream>
using namespace std;

int main() {
    string bits;
    int prefix[200] = {0};
    int suffix[200] = {0};
    int len, i, zeros, answer;
    
    cin >> bits;
    len = bits.length();
    
    for (i = 1; i <= len; i++) {
        suffix[i] = bits[i - 1] - '0';
        prefix[i] = prefix[i - 1] + suffix[i];
    }
    
    answer = prefix[len];
    zeros = 0;
    
    for (i = len; i > 0; i--) {
        if (suffix[i] == 0)
            zeros++;
        if (prefix[i - 1] + zeros < answer)
            answer = prefix[i - 1] + zeros;
    }
    cout << answer << endl;
    return 0;
}

Question 25: Input: 1001101011001101101011110001 Output: ?

Answer: 11

Explanation: The program finds the minimum value of (ones in prefix) + (zeros in suffix) across all possible split points. For the given binary string, examining each split position yields a minimum of 11.

---

Program 4

#include <iostream>
using namespace std;

int main() {
    int rows, cols;
    int px = 1, py = 1;
    int vx = 1, vy = 1;
    int bounces = 0;
    
    cin >> rows >> cols;
    
    while (bounces != 2) {
        bounces = 0;
        px += vx;
        py += vy;
        
        if (px == 1 || px == rows) {
            bounces++;
            vx = -vx;
        }
        if (py == 1 || py == cols) {
            bounces++;
            vy = -vy;
        }
    }
    cout << px << " " << py << endl;
    return 0;
}

Question 26: Input 1: 4 3 → Output: ? Input 2: 2017 1014 → Output: ?

Answer: 1 3 and 2017 1

Explanation: This simulates a ball bouncing in a rectangle. The ball starts at (1,1) moving diagonally down-right. It bounces when hitting boundaries. The loop terminates when both x and y hit boundaries simultaneously.

The termination condition occurs at the LCM of (rows-1) and (cols-1). For 4×3 grid, both dimensions hit boundaries at (1,3). For 2017×1014, x reaches row 2017 while y returns to column 1.

---

Program Completion

Fast Exponentiation

Complete the program to calculate x^p mod m using divide-and-conquer.

#include <iostream>
using namespace std;

int base, power, modulus, result;

int main() {
    cin >> base >> power >> modulus;
    result = 1;
    
    while (power > 0) {
        if (power % 2 == 1)
            result = result * base % modulus;
        power /= 2;
        base = base * base % modulus;
    }
    cout << result << endl;
    return 0;
}

Question 27: Fill in blank 1 Answer: 1

Explanation: The result accumulator should initialize to 1 (multiplicative identity).

Question 28: Fill in blank 2 Answer: power > 0

Explanation: The loop continues while power remains positive.

Question 29: Fill in blank 3 Answer: result * base % modulus

Explanation: When power is odd, multiply the current base into the result before halving.

Question 30: Fill in blank 4 Answer: base * base % modulus

Explanation: Square the base and take modulo for the next iteration.

Question 31: Fill in blank 5 Answer: result

Explanation: Output the accumulated result.

---

Rope Cutting

Given n ropes with integer lengths, cut them into m rope segments of equal maximum length L.

#include <iostream>
using namespace std;

int main() {
    int n, m;
    int ropes[100];
    long total = 0;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> ropes[i];
        total += ropes[i];
    }
    
    cin >> m;
    if (total < m) {
        cout << "Failed" << endl;
        return 0;
    }
    
    int left = 1, right = 1000000;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        long count = 0;
        
        for (int i = 0; i < n; i++)
            count += ropes[i] / mid;
        
        if (count < m)
            right = mid - 1;
        else
            left = mid;
    }
    cout << left << endl;
    return 0;
}

Question 32: Fill in blank 1 Answer: total += ropes[i]

Explanation: Accumulate the sum of all rope lengths.

Question 33: Fill in blank 2 Answer: total < m

Explanation: If total length is less than m, even cutting to length 1 cannot produce m segments.

Question 34: Fill in blank 3 Answer: left < right

Explanation: Binary search terminates when left equals right.

Question 35: Fill in blank 4 Answer: (left + right + 1) / 2

Explenation: Use upper-mid to avoid infinite loops when the answer equals left.

Question 36: Fill in blank 5 Answer: count += ropes[i] / mid

Explanation: Calculate how many segments of length mid can be cut from each rope.