AMCAT Data Structures and Algorithms 3

Question 1

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

Accepted Answer

Radix Sort

Answer

Quick Sort

Answer

Merge Sort

Answer

Heap Sort

Question 2

The average time complexity of Quick Sort is:

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n²)

Answer

O(log 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

n

Answer

n + 1

Answer

n / 2

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 tree with maximum weight

Answer

A tree rooted at every vertex

Answer

A tree formed by DFS only

Question 5

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

Accepted Answer

Stack

Answer

Queue

Answer

Heap

Answer

Hash Table

Question 6

Dynamic programming solves optimization problems by:

Accepted Answer

Breaking problems into overlapping subproblems and storing results

Answer

Using brute force on all subsets

Answer

Always choosing the locally optimal choice

Answer

Randomly sampling the solution space