, Question 1
A hash table uses open addressing with linear probing and a load factor of
0.75. If the hash function is uniform and the table size is a prime number,
which of the following best describes the expected average number of probes
for an unsuccessful search?
A. O(1)
B. O(log n)
C. O(1/(1-)) where is the load factor
D. O()
Correct Answer: C - O(1/(1-)) where is the load factor
RATIONALE
For linear probing, the expected number of probes for an unsuccessful
search is approximately 0.5*(1 + 1/(1-)^2), which is O(1/(1-)) for < 1.
This is a known result from Knuth's analysis. Options A and D are
incorrect because they ignore the clustering effect; B is incorrect
because hash tables do not have logarithmic search time under linear
probing.
Question 2
In a 5-stage pipeline (IF, ID, EX, MEM, WB), a program has 20% branch
instructions. If branches are resolved in the ID stage and the pipeline uses a
predict-not-taken strategy with a 2-cycle penalty for misprediction, what is the
approximate CPI if the branch misprediction rate is 30%?
A. 1.0
B. 1.06
C. 1.12
D. 1.20
Correct Answer: C - 1.12
Page 2
, RATIONALE
CPI = base CPI + branch frequency * misprediction rate * penalty = 1
+ 0.20 * 0.30 * 2 = 1.12. Option A ignores penalties; B underestimates
by using 1 cycle penalty; D overestimates by using 5 cycles or wrong
frequency.
Question 3
Which of the following is the primary reason that TCP uses a three-way
handshake rather than a two-way handshake?
A. To ensure reliable data transfer by acknowledging every segment.
B. To prevent old duplicate connection requests from causing confusion.
C. To negotiate the maximum segment size (MSS).
D. To establish a secure encrypted channel.
Correct Answer: B - To prevent old duplicate connection requests
from causing confusion.
RATIONALE
The three-way handshake prevents old duplicate SYN segments from
causing a half-open connection, as described in RFC 793. Option A is
about reliability, not connection setup; C is a separate option
negotiation; D is handled by TLS, not TCP.
Question 4
In relational algebra, which of the following expressions is equivalent to the
natural join of relations R(A,B) and S(B,C)?
A. _{A,B,C}(_{R.B=S.B}(R × S))
B. _{A,B,C}(R × S)
C. _{R.B=S.B}(R × S)
D. _{A,C}(R × S)
Correct Answer: A - _{A,B,C}(_{R.B=S.B}(R × S))
Page 3
, RATIONALE
Natural join is a Cartesian product followed by selection on equal
attributes and projection to remove duplicate attributes. Option A
correctly performs selection on B and projects A,B,C. B lacks
selection; C lacks projection; D drops B.
Question 5
Which of the following best describes the difference between a process and a
thread in a modern operating system?
A. A process has its own address space, while threads share the address
space of their parent process.
B. A thread has its own address space, while processes share a global
address space.
C. Processes are scheduled by the kernel, while threads are scheduled by
the user-level library.
D. Processes can communicate via shared memory, while threads cannot.
Correct Answer: A - A process has its own address space, while
threads share the address space of their parent process.
RATIONALE
Threads within the same process share the same address space,
including code, data, and heap, but have separate stacks and registers.
Processes have independent address spaces. Option B reverses the
relationship; C is not universally true (kernel-level threads exist); D is
false because threads share memory by default.
Question 6
Which of the following is a key characteristic of a functional programming
language?
A. It relies heavily on mutable state and side effects.
B. It treats computation as the evaluation of mathematical functions and
avoids changing state.
Page 4
A hash table uses open addressing with linear probing and a load factor of
0.75. If the hash function is uniform and the table size is a prime number,
which of the following best describes the expected average number of probes
for an unsuccessful search?
A. O(1)
B. O(log n)
C. O(1/(1-)) where is the load factor
D. O()
Correct Answer: C - O(1/(1-)) where is the load factor
RATIONALE
For linear probing, the expected number of probes for an unsuccessful
search is approximately 0.5*(1 + 1/(1-)^2), which is O(1/(1-)) for < 1.
This is a known result from Knuth's analysis. Options A and D are
incorrect because they ignore the clustering effect; B is incorrect
because hash tables do not have logarithmic search time under linear
probing.
Question 2
In a 5-stage pipeline (IF, ID, EX, MEM, WB), a program has 20% branch
instructions. If branches are resolved in the ID stage and the pipeline uses a
predict-not-taken strategy with a 2-cycle penalty for misprediction, what is the
approximate CPI if the branch misprediction rate is 30%?
A. 1.0
B. 1.06
C. 1.12
D. 1.20
Correct Answer: C - 1.12
Page 2
, RATIONALE
CPI = base CPI + branch frequency * misprediction rate * penalty = 1
+ 0.20 * 0.30 * 2 = 1.12. Option A ignores penalties; B underestimates
by using 1 cycle penalty; D overestimates by using 5 cycles or wrong
frequency.
Question 3
Which of the following is the primary reason that TCP uses a three-way
handshake rather than a two-way handshake?
A. To ensure reliable data transfer by acknowledging every segment.
B. To prevent old duplicate connection requests from causing confusion.
C. To negotiate the maximum segment size (MSS).
D. To establish a secure encrypted channel.
Correct Answer: B - To prevent old duplicate connection requests
from causing confusion.
RATIONALE
The three-way handshake prevents old duplicate SYN segments from
causing a half-open connection, as described in RFC 793. Option A is
about reliability, not connection setup; C is a separate option
negotiation; D is handled by TLS, not TCP.
Question 4
In relational algebra, which of the following expressions is equivalent to the
natural join of relations R(A,B) and S(B,C)?
A. _{A,B,C}(_{R.B=S.B}(R × S))
B. _{A,B,C}(R × S)
C. _{R.B=S.B}(R × S)
D. _{A,C}(R × S)
Correct Answer: A - _{A,B,C}(_{R.B=S.B}(R × S))
Page 3
, RATIONALE
Natural join is a Cartesian product followed by selection on equal
attributes and projection to remove duplicate attributes. Option A
correctly performs selection on B and projects A,B,C. B lacks
selection; C lacks projection; D drops B.
Question 5
Which of the following best describes the difference between a process and a
thread in a modern operating system?
A. A process has its own address space, while threads share the address
space of their parent process.
B. A thread has its own address space, while processes share a global
address space.
C. Processes are scheduled by the kernel, while threads are scheduled by
the user-level library.
D. Processes can communicate via shared memory, while threads cannot.
Correct Answer: A - A process has its own address space, while
threads share the address space of their parent process.
RATIONALE
Threads within the same process share the same address space,
including code, data, and heap, but have separate stacks and registers.
Processes have independent address spaces. Option B reverses the
relationship; C is not universally true (kernel-level threads exist); D is
false because threads share memory by default.
Question 6
Which of the following is a key characteristic of a functional programming
language?
A. It relies heavily on mutable state and side effects.
B. It treats computation as the evaluation of mathematical functions and
avoids changing state.
Page 4
