Data structures and algorithms practice set 1

Question 1

What is the time complexity of binary search on a sorted array of n elements?

Accepted Answer

O(log n)

Question 2

Which data structure follows Last In, First Out (LIFO)?

Accepted Answer

Stack

Question 3

What is the worst-case time complexity of quicksort?

Accepted Answer

O(n²)

Question 4

Which traversal of a binary search tree gives the keys in sorted order?

Accepted Answer

In-order

Question 5

What is the average time to look up a key in a hash table?

Accepted Answer

O(1)

Question 6

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

Accepted Answer

Dijkstra's algorithm

Question 7

Breadth-first search (BFS) uses which data structure?

Accepted Answer

Queue

Question 8

How many edges does a tree with n nodes have?

Accepted Answer

n − 1

Question 9

Which sorting algorithm is stable and always O(n log n)?

Accepted Answer

Merge sort

Question 10

Accessing the i-th element of an array takes:

Accepted Answer

O(1)

Question 11

Inserting at the head of a singly linked list takes:

Accepted Answer

O(1)

Question 12

In a max-heap, the largest element is:

Accepted Answer

At the root

Question 13

What is the time complexity of this code?
for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    count++;

Accepted Answer

O(n²)

Question 14

Which technique stores results of subproblems to avoid recomputation?

Accepted Answer

Dynamic programming

Question 15

The minimum number of comparisons to find the largest of n numbers is:

Accepted Answer

n − 1

How do you want to practise?