Take this Quiz: A-Level Computer Science: Computational Thinking and Theory | Zestly

Question 1

A finite state machine has three states: S0, S1, and S2. S0 is the start state, and S2 is the only accepting state. The transitions are: from S0 on a zero go to S1; from S0 on a one go to S0; from S1 on a zero go to S1; from S1 on a one go to S2; from S2 on a zero go to S2; from S2 on a one go to S2. If the input string is one, zero, one, zero, one, which state does the machine end in and is the string accepted?

Accepted Answer

The machine ends in S2 and the string is accepted.

Answer

The machine ends in S0 and the string is rejected.

Answer

The machine ends in S2 and the string is rejected.

Answer

The machine ends in S1 and the string is rejected.

Question 2

Why is it impossible for a finite state machine to determine if a string contains an equal number of zeros and ones, given that the number of symbols is unbounded?

Accepted Answer

Because a finite state machine has a fixed number of states and cannot track an arbitrarily large count.

Answer

Because adding more states to the machine would eventually allow it to count any number of symbols.

Answer

Because the machine would require a non-deterministic approach to handle the parity of the symbols.

Answer

Because finite state machines cannot process input strings longer than their number of states.

Question 3

A software engineer breaks a large project into smaller, manageable modules. Later, the same engineer creates a simplified model of a network that ignores specific hardware latency details to focus on data flow. Which terms correctly describe these two actions?

Accepted Answer

Decomposition followed by abstraction.

Answer

Both are examples of decomposition.

Answer

Abstraction followed by decomposition.

Answer

Both are examples of abstraction.

Question 4

Algorithm A has a growth rate of order n squared, and Algorithm B has a growth rate of order n log n. For a very small input size, Algorithm A runs faster than Algorithm B. What is the most accurate conclusion regarding their performance?

Answer

Algorithm A is the better choice because it is faster for the current input size.

Answer

Algorithm B is always the better choice because its growth rate is lower.

Answer

The choice of algorithm depends solely on the constant factors involved in the implementation.

Answer

Algorithm B will eventually become more efficient as the input size increases, regardless of current performance.

Question 5

A firm finds that an algorithm with a worse order of growth finishes faster on their specific, small-scale dataset than an algorithm with a better order of growth. What does this demonstrate about computational complexity?

Answer

The firm should always choose the algorithm that finishes faster on their current data.

Answer

Order of growth is an unreliable metric for real-world performance.

Answer

Constant factors and specific input ranges can influence performance more than growth rates for small datasets.

Answer

The algorithm with the better order of growth is incorrectly classified.