# DESIGN & ANALYSIS OF ALGORITHM

1.What is the space complexity of quick search algorithm?

a. O(m+n)

b. O(mn)

c. O(n)

d. O(log n)

2.Which among the following is the language which supports classes but not polymorphism?

b. SmallTalk

c. java

d. c++

3.Which type of function among the following shows polymorphism?

a. Inline function

b. Undened functions

c. Class member functions

d. Virtual function

4.Which among the following can’t be used for polymorphism?

d. Static member functions

5.Which among the following can show polymorphism?

6.Polymorphism is possible in C language.

a. FALSE

b.

c.

d. t

7.Which among the following is not true for polymorphism?

a. It is feature of OOP

b. Increases overhead of function denition always

c. Helps in redening the same functionality

d. Ease in readability of program

8.Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?

a. 5, 3, 1, 0

b. 4, 3, 1, 0

c. 4, 2, 1, 1

d. 5, 2, 1, 1

9.What is the time complexity of uniform binary search?

a. O(n )2

b. O(n)

c. O(logn)

d. O(nlogn)

10.How can Jump Search be improved?

a. Step size should be oth

b. Begin from the kth item, where k is the step size

c. Cannot be improved

d. Start searching from the end

11.In preorder traversal of a binary tree the second step is ____________

a. traverse the right subtree

b. traverse right subtree and visit the root

c. visit the root

d. traverse the left subtree

12.An important application of binary tree is ______

a. stack implementation

b. Human coding

c. stack implementation

d. stack implementation

13.What is the minimum height for a binary search tree with 60 nodes?

a. 2

b. 1

c. 3

d. 4

14.For the expression (7-(4*5))+(9/3) which of the following is the post order tree traversal?

a. 745*-93/+

b. *745-93/+

c. *745-93/+

d. *745-93/+

15.An immediate application of a Depth First Search traversal is __________

a. implement preorder traversal

b. count the number of leaf nodes

c. perform Inorder traversal in easy way

d. count number of nodes

16.Breadth First Search traversal of a binary tree nds its application in __________

a. Cloud computing

b. Weighted graph

c. Euler path

d. Peer to peer networks

17.Which of the following data structure is required for the implementation of tree sort?

a. any ordinary tree

b. binary search tree

c. unbalanced tree

d. balanced tree

18.Tree sort is an online sorting algorithm.

a. FALSE

b.

c.

d. TRUE

19.Which of the following traversal in a binary search tree results in a sorted output?

a. post order traversal

c. n order traversal

d. pre order traversal

20.Which of the following sorting algorithm is stable?

a. Quick sort

b. Selection sort

c. Heap sort

d. Tree sort

21.Which of the following sorting algorithm uses a binary search tree?

b. odd-even sort

d. tree sort

22.Which of the following is a comparison based sort?

b. counting sort

c. pigeonhole sort

d. tree sort

23.Which of the following is not true about tree sort?

a. it requires in order traversal of BST for sorting input elements

b. it is a stable sort

c. its every implementation is adaptive

d. it is not an in place sorting algorithm

24.Which of the following sorting algorithm is not in place?

a. quick sort

b. insertion sort

c. gnome sort

d. tree sort

25.Which of the following is not an advantage of tree sort?

a. it is stable sorting algorithm

b. it is an online sorting algorithm

c. it has a low space complexity

d. it has good time complexity for balanced BST

26.Which of the following version of tree sort will have the highest worst case time complexity?

a. using splay tree as BST

b. using red black tree as BST

c. using AVL tree as BST

d. using ordinary BST

27.Strassen’s algorithm is a/an_____________ algorithm.

a. Approximation

b. Non- recursive

c. Accurate

d. Recursive

28.Strassen’s matrix multiplication algorithm follows ___________ technique.

a. Greedy technique

b. Divide and Conquer

c. Backtracking

d. Dynamic Programming

29.Running time of Strassen’s algorithm is better than the naïve Theta(n ) method

a. FALSE

b.

c.

d. Ture

30.Which of the following takes O(n) time in worst case in array implementation of stack?

a. enqueue

b. Both push and pop

c. push

d. pop

31.What is the formula to calculate the element present in second row, rst column of the product matrix?

a. M1+M3

b. M1+M7

c. M2+M4

d. M2+M4 – M5 + M7

32.How many iterating statements are involved in the naïve method of matrix multiplication?

a. 3

b. 4

c. 2

d. 1

33.Problems that can be solved in polynomial time are known as?

a. intractable

b. decision

c. complete

d. tractable

34._________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms?

a. Hard

b. Complete

c. NP

d. p

35.Problems that cannot be solved by any algorithm are called?

a. decidable problems

b. intractable problems

c. tractable problems

d. undecidable problems

36.To which class does the Euler’s circuit problem belong?

a. Partition class

b. Partition class

c. P class

d. Complete class

37.Halting problem is an example for?

a. complete problem

b. complete problem

c. complete problem

d. undecidable problem

38.How many stages of procedure does a non-deterministic algorithm consist of?

a. 2

b. 3

c. 4

d. 1

39.Which of the following problems is not NP complete?

a. Hamiltonian circuit

b. Halting problem

c. Partition problem

d. Bin packing

40.Which of the following is not type of class?

a. String Class

b. Final Class

c. Abstract Class

d. Start Class

41.What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?

a. O(n )

b. log(n)

c. O(n^3)

d. O(n ^2)

42.How many recursive calls are there in Recursive matrix multiplication through Simple Divide and conquer method

a. 8

b. 2

c. 6

d. 9

43.Which of the following is considered as the top of the stack in the linked list implementation ofthe stack?

a. every node

b. fisrt  node

c. last node

d. middle node

44.What is the time complexity of uniform binary search?

a. O(n)

b. O(n )

c. O(logn)

d. O(nlogn)

45.Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?

a. 5, 3, 1, 0

b. 4, 3, 1, 0

c. 4, 2, 1, 1

d. 5, 2, 1, 1

46.What is the space complexity of program to reverse stack recursively?

a. O(log n)

b. O(n log n)

c. O(n)

d. O(1)

47.In dynamic programming, the technique of storing the previously calculated values is called ___________

a. Storing value property

b. Saving value property

c. Memoization

d. Mapping

48.Which of the following problems should be solved using dynamic programming?

a. Binary search

b. Mergesort

c. Longest common subsequence

d. Quicksort

49.In insertion sort, the average number of comparisons required to place the 7 element into its correct position is ____

a. 4

b. 7

c. 9

d. 14