ALGORITHMS MCQ SHEET

1. 
Consider the following two functions. What are time complexities of the functions?

a) O(2^n) for both fun1() and fun2() b) O(n) for fun1() and O(2^n) for fun2()

c) O(2^n) for fun1() and O(n) for fun2() d) O(n) for both fun1() and fun2()

 

2. Fill in the blank: f(n) = O(g(n)) if and only if g(n) =  .

3. To sort a list with n elements, the insertion sort begins with the  element.

a) First b) Second c) Third d) Fourth

4. List obtained in third pass of selection sort for list 3, 5, 4, 1, 2 is  .

a) 1, 2, 4, 3, 5 b) 1, 2, 3, 4, 5 c) 1, 5, 4, 3, 2 d) 3, 5, 4, 1, 2

5. The complexity of Bubble sort algorithm is:

a) O(n) b) O(log n) c) O(n2) d) O(n log n)

6. The recurrence relation capturing the optimal time of the Tower of Hanoi problem with n discs is: a) T(n) = 2T(n–2)+2 b) T(n) = 2T(n–1)+n c) T(n) = 2T(n/2)+1 d) T(n) = 2T(n–1)+1

7. What does the following function do for a given Linked List with first node as head?

a) Prints all nodes of linked lists b) Prints all nodes of linked list in reverse order

c) Prints alternate nodes of Linked List d) Prints alternate nodes in reverse order

8. Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?

a) Insertion Sort b) Heap Sort c) Merge Sort d) Quick Sort

9. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is:

a) log n base 2 b) n/2 c) log n base 2 -1 d) n

10. What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.

a) O(1) and O(n) b) O(1) and O(1) c) O(n) and O(1) d) O(n) and O(n)

11. Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?

a) Possible if X is not last node. Use following two steps (a) Copy the data of next of X to X. (b) Delete next of X.

b) Possible if X is not first node. Use following two steps (a) Copy the data of next of X to X. (b)

Delete next of X

c) Possible if size of linked list is odd d) Possible if size of linked list is even

12. Suppose V is number of vertices and E is number of edges in a graph, time complexity of DFS is:

a) O(V + E) b)  O(V) c) O(E) d) None of the above

13. The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * -

The top two elements of the stack after the first * is evaluated are:

a) 6, 1 b) 5, 7 c) 3, 2 d) 1, 5

14. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is:

a) (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1) b) top1= top2 -1

c) (top1= MAXSIZE/2) or (top2 = MAXSIZE) d) top1 + top2 = MAXSIZE

15. Assume that the operators +, -, × are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, -. The postfix expression corresponding to the infix expression a + b × c - d ^ e ^ f is:

a) abc × + def ^ ^ - b) abc × + de ^ f ^ - c) ab + c × d - e ^ f ^ d) - + a × bc ^ ^ def

16. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?

a) At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)

b) The worst case time complexity for both operations will be Ω(n)

c) Worst case time complexity for both operations will be Ω(log n)

d) Both operations can be performed in O(1) time

17. 
Consider the following functions. Which of the following is true?

a) h(n) is O(f(n)) b) h(n) is O(g(n))

c) g(n) is not O(f(n)) d) f(n) is O(g(n))

18. Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

a) O(n) b) O(n Log n) c) O(n^2) d) O(n!)

19. Consider the following three claims and find Which of these claims are correct ?

1. (n + k)^m = Θ(n^m), where k and m are constants 2. 2^(n + 1) = O(2^n)

3. 2^(2n + 1) = O(2^n)

a) 1 and 2 b) 1 and 3 c) 2 and 3 d) 1, 2 and 3

20. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time:

a) Θ(n log n) b) Θ(n) c) Θ(log n) d) Θ(1)

21. Time complexity of Depth First Traversal of is

a) Θ(|V|+|E|) b) Θ(|V|) c) Θ(|E|) d) Θ(|V|*|E|)

22. From a complete graph, by removing maximum  edges, we can construct a spanning tree.

a) e-n+1 b) n-e+1 c)n+e-1 d) e-n-1

23. Consider the following functions:  f(n)  = 2^n g(n)   = n! h(n) = n^logn

Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true? a) f(n) = O(g(n)); g(n) = O(h(n)) b) f(n) = Ω(g(n)); g(n) = O(h(n))

c) g(n) = O(f(n)); h(n) = O(f(n)) d) h(n) = O(f(n)); g(n) = Ω(f(n))

24. Which of the following sorting algorithms has the lowest worst-case complexity?

a) Merge Sort b) Bubble Sort c) Quick Sort d) Selection Sort

25. Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a unction whose time complexity is θ(m). Consider the following program fragment written in a C like language:

The complexity of this program fragment is

a) Ω(n^2) b) Ω(nlog n) and O(n^2) c) θ(n) d) O(n)

Answers: 1. b) 2. g(n) = Ω(f(n)) 3. b) 4. b) 5. c) 6. d) 7. b) 8. c) 9. d) 10. a) 11. a) 12. a) 13. a) 14. b)

15. a) 16. d) 17. d) 18. c) 19. a) 20. d) 21. a) 22. a) 23. d) 24. a) 25. c)