Question 1
Which of the following software is NOT produced by Microsoft?
A. PowerPoint
B. Word
C. Excel
D. Acrobat Reader
Answer: D
Options A, B, and C are all part of Microsoft Office suite. Acrobat Reader is a PDF viewer developed by Adobe Systems.
Question 2
To represent 256 different colors using binary encoding, what is the minimum number of bits required?
A. 6
B. 7
C. 8
D. 9
Answer: C
Since 28 = 256, we need at least 8 bits to represent 256 distinct values.
Question 3
Which of the following is NOT a wireless communication technology?
A. Bluetooth
B. WiFi
C. GPRS
D. Ethernet
Answer: D
Bluetooth and WiFi are wireless technologies. GPRS is a data transmission technology used in 2G networks. Ethernet is a wired networking technology.
Question 4
Which of the following is NOT a CPU manufacturer?
A. Intel
B. AMD
C. Microsoft
D. IBM
Answer: C
Intel and AMD are well-known CPU manufacturers. Microsoft is a software company. IBM manufactures server CPUs.
Question 5
Which of the following is NOT a storage device?
A. Optical disc
B. Magnetic disk
C. Solid state drive
D. Mouse
Answer: D
A mouse is an input device, not a storage device.
Question 6
If a computer starts in lowercase input mode, and a mouse repeatedly presses keys in the following sequence: CapsLock, A, S, D, CapsLock, A, S, D, ... (cycling through this pattern), what will be the 81st character displayed on the screen?
A. A
B. S
C. D
D. a
Answer: C
The pattern repeats every 6 characters: A, S, D, a, s, d. Since 81 % 6 = 3, the 81st character corresponds to the third position, which is 'D'.
Question 7
What is the sum of binary numbers 00101100 and 00010101?
A. 00101000
B. 01000001
C. 01000100
D. 00111000
Answer: B
Perform binary addition with proper carry propagation: 00101100 + 00010101 = 01000001
Question 8
What is the octal equivalent of the binary number 0.1?
A. 0.8
B. 0.4
C. 0.2
D. 0.1
Answer: B
Convert binary 0.1 to decimal: (0.1)2 = (0.5)10
Convert decimal 0.5 to octal: (0.5)10 = (0.4)8
Question 9
What is the main difference between 32-bit and 64-bit machines?
A. Different displays
B. Different hard drive sizes
C. Different addressing space
D. Different enput methods
Answer: C
The bit count refers to the maximum number of bits the CPU can process at once, which determines the maximum memory addressing space. A 32-bit processor can address up to 232 bytes (4GB) of memory.
Question 10
Which of the following statements 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 of space characters is an empty string
Answer: A
Strings are essentially character arrays, making them a special case of linear lists. Option B is incorrect because empty strings are valid. Option C is incorrect since strings are typically stored as character arrays. Option D is incorrect because a string of spaces has non-zero length.
Question 11
Given a binary tree, if using sequential storage (where the root node has index 1, and for a node at index i, its left child is at index 2i and right child at index 2i+1), what is the maximum index among all nodes?
A. 6
B. 10
C. 12
D. 15
Answer: D
The maximum index is calculated by following the path to the deepest rightmost node using the formulas 2i for left child and 2i+1 for right child.
Question 12
Given the following code segment where s, a, b, c are integer variables and a, c are already assigned (c > 0):
result = a;
for (i = 1; i <= c; i++)
result = result + 1;
Which assignment statement is equivalent to the above code?
A. s = a + b
B. s = a + c
C. s = s + c
D. s = b + c
Answer: B
The loop adds 1 to the initial value 'a' exactly 'c' times, resulting in 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
Tracing the execution: Initially n=0, k=4. When n=3 (divisible by 3), k decrements to 3. Loop continues until n=3, which is not less than k=3, so loop exits. Output: 3,3
Question 14
Given an array L with n distinct elements forming a unimodal sequence (strictly increasing then strictly decreasing), complete the algorithm to find the peak element.
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-1] < L[k] and L[k] < L[k+1]
5. then ____
6. else ____
Options for filling blanks (a, b, c):
a. Search(k+1, n)
b. Search(1, k-1)
c. return L[k]
A. c, a, b
B. c, b, a
C. a, b, c
D. b, a, c
Answer: A
Line 2 checks if peak is found, so line 3 should return the peak (c). Line 4 checks if current position is on the left side of the peak, so search right half (a). Otherwise, search left half (b).
Question 15
A simple undirected graph G has 16 edges and each vertex has degree 2. How many vertices does G have?
A. 10
B. 12
C. 8
D. 16
Answer: D
Using the handshaking lemma: sum of degrees = 2 × number of edges. Let v be the number of vertices: v × 2 = 2 × 16, so v = 16.
Question 16
In how many ways can 7 identical apples be placed into 3 identical plates?
A. 7
B. 8
C. 21
D. 37
Answer: B
Using enumeration:
- 1 plate used: (7,0,0) → 1 way
- 2 plates used: (6,1,0), (5,2,0), (4,3,0) → 3 ways
- 3 plates used: (5,1,1), (4,2,1), (3,3,1), (3,2,2) → 4 ways
Total: 1 + 3 + 4 = 8 ways
Question 17
Given an orchard irrigation system with valves A, B, C, D (each can be open or closed), which configuration allows water to reach the trees?
A. Only B open, others closed
B. A and B open, C and D closed
C. Only A open, others closed
D. Only D open, others closed
Answer: A
Opening valve B while closing valve A creates a path for water flow. Alternatively, opening both C and D would also work.
Question 18
Based on the social network relationship diagram, Lucia wants to share a photo but doesn't want Jacob to see it. According to the sharing rules (friends of commenters can see comments), whom can Lucia share with?
A. Dana, Michael, Eve
B. Dana, Eve, Monica
C. Michael, Eve, Jacob
D. Michael, Peter, Monica
Answer: A
Lucia cannot share directly with Jacob, nor with Jacob's friends (Lena, Peter, Monica, Charles) as they would see comments. Only option A avoids these restrictions.
Question 19
Three family members need to prepare 3 dishes. Each dish requires: washing (10 min), cutting (10 min), cooking (10 min). The same step cannot be performed simultaneously for different dishes. What is the minimum total time needed?
A. 90
B. 60
C. 50
D. 40
Answer: C
Optimal schedule:
- 0-10 min: Wash dish 1
- 10-20 min: Wash dish 2, Cut dish 1
- 20-30 min: Wash dish 3, Cut dish 2, Cook dish 1
- 30-40 min: Cut dish 3, Cook dish 2
- 40-50 min: Cook dish 3
Total: 50 minutes
Question 20
Which item cannot be brought in to the NOI competition venue?
A. Pen
B. Appropriate clothing
C. USB drive
D. Pencil
Answer: C
USB drives are not allowed in competition venues as per competition rules.
Problem Solving
Question 21
On a 4×4 chessboard (non-rotatable), how many ways can you select two squares that are neither in the same row nor the same column?
Answer: 72
Select first square: 16 choices. Select second square: 9 choices (excluding the row and column of the first). Since order doesn't matter: 16 × 9 / 2 = 72.
Question 22
Given that the root of a binary tree has height 1, a binary tree with 2016 nodes has at minimum (___) leaf nodes, and its minimum height is (___).
Answer: 1, 11
Minimum leaves: A skewed tree with 2016 levels has only 1 leaf node.
Minimum height: For a complete binary tree, 2n-1 - 1 < nodes ≤ 2n - 1. Since 210 - 1 = 1023 < 2016 ≤ 211 - 1 = 2047, n = 11.
Program Reading
Question 23
Given the following program, what is the output for input: 1 2 3 4 5 6 0 7?
#include <iostream>
using namespace std;
int main() {
int maxVal, minVal, total, cnt = 0;
int val;
cin >> val;
if (val == 0)
return 0;
maxVal = minVal = total = val;
cnt++;
while (val != 0) {
cin >> val;
if (val != 0) {
total += val;
cnt++;
if (val > maxVal)
maxVal = val;
if (val < minVal)
minVal = val;
}
}
cout << maxVal << ", " << minVal << ", " << total/cnt << endl;
return 0;
}
Answer: 6, 1, 3
The loop terminates when reading 0, so the final input 7 is not processed. Final values: maxVal=6, minVal=1, total=21, cnt=6, average=3.
Question 24
What is the output of the following program?
#include <iostream>
using namespace std;
int main() {
int num = 100, result = 0;
while (num > 0) {
num--;
if (num % 8 == 1)
result++;
}
cout << result << endl;
return 0;
}
Answer: 13
The program counts numbers from 1 to 99 that give remainder 1 when divided by 8: 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97. Total: 13 numbers.
Question 25
What is the output of the folowing program?
#include <iostream>
using namespace std;
int main() {
int arr[6] = {1, 2, 3, 4, 5, 6};
int left = 0, right = 5;
int temp, idx;
while (left < right) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
for (idx = 0; idx < 6; idx++)
cout << arr[idx] << ",";
cout << endl;
return 0;
}
Answer: 6,5,4,3,2,1,
The two-pointer technique reverses the array in place. Note the trailing comma after the last element.
Question 26
What is the output of the following program?
#include <iostream>
using namespace std;
int main() {
int i, len1, len2;
string str1, str2;
str1 = "I have a dream.";
str2 = "I Have A Dream.";
len1 = str1.size();
len2 = str2.size();
for (i = 0; i < len1; i++)
if (str1[i] >= 'a' && str1[i] <= 'z')
str1[i] -= 'a' - 'A';
for (i = 0; i < len2; i++)
if (str2[i] >= 'a' && str2[i] <= 'z')
str2[i] -= 'a' - 'A';
if (str1 == str2)
cout << "=" << endl;
else if (str1 > str2)
cout << ">" << endl;
else
cout << "<" << endl;
return 0;
}
Answer: =
Both strings are converted to uppercase, resulting in "I HAVE A DREAM." for both, making them equal.
Program Completion
Questions 27-31: Reading Integers
Complete the program to read two integers within int range and output them, one per line.
#include <iostream>
using namespace std;
int readInteger() {
int value = 0;
int isNegative = 0;
char ch;
ch = cin.get();
while ((ch < '0' || ch > '9') && ch != '-')
ch = __1__; // Answer: cin.get()
if (ch == '-')
isNegative = 1;
else
__2__; // Answer: value = ch - '0'
ch = cin.get();
while (__3__) { // Answer: ch >= '0' && ch <= '9'
__4__; // Answer: value = value * 10 + ch - '0'
ch = cin.get();
}
if (isNegative == 1)
__5__; // Answer: value = -value
return value;
}
int main() {
int a, b;
a = readInteger();
b = readInteger();
cout << a << endl << b << endl;
return 0;
}
Questions 32-36: Field Trip Activity
n students participate in a field trip with total budget A. Student i has personal money M[i]. There are B bicycles (B ≥ n) available for rent with costs C[j]. Each student can only rent for themselves. Find the maximum number of students who can rent bicycles.
#include <iostream>
using namespace std;
#define MAXN 1000000
int n, B, A, M[MAXN], C[MAXN], left, right, result, mid;
bool check(int numStudents) {
int needed = 0, i, j;
i = __1__; // Answer: n - numStudents + 1
j = 1;
while (i <= n) {
if (__2__) // Answer: C[j] > M[i]
needed += C[j] - M[i];
i++;
j++;
}
return __3__; // Answer: needed <= A
}
void sort(int arr[], int l, int r) {
int i = l, j = r, pivot = arr[(l+r)/2], temp;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
i++; j--;
}
}
if (i < r) sort(arr, i, r);
if (l < j) sort(arr, l, j);
}
int main() {
int i;
cin >> n >> B >> A;
for (i = 1; i <= n; i++)
cin >> M[i];
for (i = 1; i <= B; i++)
cin >> C[i];
sort(M, 1, n);
sort(C, 1, B);
left = 0;
right = n;
while (left <= right) {
mid = (left + right) / 2;
if (__4__) { // Answer: check(mid)
result = mid;
left = mid + 1;
} else {
right = __5__; // Answer: mid - 1
}
}
cout << result << endl;
return 0;
}