This is a set of simple multiple choice questions, provided entirely for your self-assessment, and is based on the most fundamental aspects of data structure and algorithms. The level of the questions is no more than that of what one would encounter in an introductory Programming and Data Structures class in the freshman year at college.

Question 1.

Which of these is the Worst-case time complexity of Quick Sort - and cannot be expressed in lower order terms ?

(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 2.

Which of these is the worst case time complexity of Merge Sort - and cannot be expressed in lower order terms ?
(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 3.

Which of these is the average case time complexity of Merge Sort - and cannot be expressed in lower order terms ?

(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 4.

Which of these is the time complexity involved in building a heap of n elements - and cannot be expressed in lower order terms ?

(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 5.

A heap is a particular kind of a binary search tree. This statement is:
(a) True
(b) False

Question 6.

The Floyd-Warshall all-pairs shortest path algorithm for finding the shortest distances between nodes in a graph is an example of:
(a) A Dynamic Programming formulation.
(b) A Greedy Algorithm
(c) A recursion based divide and conquer technique.

Question 7.

A bitwise operation 'f' has an interesting characteristic, such that, if f(a,b) = c, it always turns out to be the case that f(b,a) = c; f(a,c) = b; f(c,a) = b; f(b,c) = a; f(c,b) = a. Which of these functions could 'f' possibly be?
(a) f(a,b) = a XOR b
(b) f(a,b) = a + b
(c) f(a,b) = a - b
(d) f(a,b) = a * b

(where a and b are the binary representations of any two non-negative integers)

Question 8.

A union find data-structure is commonly applied while implementing:
(a) A depth-first search traversal of a graph.
(b) A breadth-first search traversal of a graph.
(c) Computing the minimum spanning tree of a graph using the Kruskal algorithm.
(d) Computing the all-pairs shortest path in a graph.

Question 9.

Which of these is the worst case time complexity for looking up a key in a binary search tree - and cannot be expressed in lower order terms ?

(a) O(n)
(b) O(n log n)
(c) O(n²)
(d) O(n³)
(e) O(log n)

Question 10.

The graph algorithm which forms an essential component of the 'make' or 'ant build' used by programmers and software developers is:

(a) Flow maximization algorithm
(b) Shortest path algorithm
(c) Minimum spanning tree algorithm
(d) Bipartite matching
(e) Topological sort

Answer Format

Replace the blanks (represented by three consecutive hyphens) with the appropriate letter ('a','b','c','d' or 'e') for each of the questions. Then, hit the submit button.

Do not add any leading, trailing or intermediate spaces.
In case you are unsure about the answer, you can use the letter 'x'.
Your answer should contain ten lines, answering sequentially, all of the questions 1 to 10.

For example: (Please note that these are NOT the correct answers and this example is meant only for the purpose of explaining the format)

1:a  
2:b  
3:c  
4:d  
5:e  
6:a  
7:b  
8:x  
9:d  
10:a     

Explanation

The candidate has concluded that the correct answer the Question 1 is option 'a', the correct answer to Question 2 is option 'b' and so on. He/she does not know the answer to Question 8, hence uses the character 'x'.

Scoring

Your score is proportional to the number of answers (indicated by the letter options) identified correctly by you.