AMCAT Data Structures and Algorithms 3

Question 1

Which of the following is NOT a comparison-based sorting algorithm?

Accepted Answer

Radix Sort

Answer

Radix Sort sorts by individual digits without comparing elements directly, so it is non-comparison based.

Question 2

The average time complexity of Quick Sort is:

Accepted Answer

O(n log n)

Answer

Quick Sort's average case is O(n log n), though worst case (poor pivot choice) is O(n²).

Question 3

In a circular queue of size n, how many elements can actually be stored (to distinguish full from empty)?

Accepted Answer

n − 1

Answer

A circular queue typically stores at most n−1 elements to differentiate between the full and empty states.

Question 4

What is a spanning tree of a graph?

Accepted Answer

A tree that includes all vertices with the minimum number of edges

Answer

A spanning tree connects all vertices of a graph using exactly n−1 edges with no cycles.

Question 5

Which data structure is used by an operating system to manage function calls and returns?

Accepted Answer

Stack

Answer

The call stack is a stack data structure that tracks function calls, local variables, and return addresses.

AMCAT Practice Test