DSA QUIZ 1

1.An algorithm that requires __________ operations to complete its task on n data elements is said to have a constant runtime.

Select one:
a. 8n+2
b. 5n^2 + 3n + 13
c. 6n^2 + 7
d. 11 {correct}

2.If the array A contains the items 10 ,4, 7, 23, 67, 12, 5, what will be resultant array A after 3rd pass of Insertion sort?

Select one:
a.  67,12, 10,5,4,7,23
b.  4,7,10,23,67,12,5 {correct}
c.  10,7,4,67,23,12,5
d.  4,5,7,67,10,12,23

3.Which of the following represents the best case running time of insertion  sort?

Select one:
a. O(n) {correct}
b. O(1)
c. O(log n)
d. O(n^2)

4.The smallest element of an array index is called its

Select one:
a.   range
b.   upper bound
c.   all of these
d. lower bound {correct}

5.If a node in a BST has two children, then its inorder predecessor has

Select one:
a.  no left child
b.   no child
c.  two children
d.  no right child {correct}

EXPLANATION:
For any node, the successor is the left most element of the right subtree (if it exists). It is
given in the problem that right child exists. So the successor is the left most child in the
right subtree. Evidently, left most child cannot have a left child. (if node x has one left
child, then node x is no more the left most)
In the similar way, predecessor is the right most child in the left subtree. And rightmost
child cannot have a right child.

6.If h is any hashing function and is used to hash n keys in to a table of size m, where n<=m, the
expected number of collisions involving a particular key x is

Select one:
a. less than m
b. less than n/2.
c. less than n.
d. less than 1.{correct}

Theorem: If h is chosen from a universal class of hash functions and is used to
hash n keys into a table of size m, where n ≤ m, the expected number of collisions
involving a particular key x is less than 1.

7.A characteristic of the data, that binary search uses but the linear search ignores is the___________.

Select one:
a. Type of elements of the list
b. Maximum value in list.
c. Order of the elements of the list. {correct}
d. Length of the list.

8.What term is used to describe a  O(n) algorithm?

Select one:
a.Constant
b.Linear {correct}
c.Quadratic
d.Logarithmic

9.The searching technique that takes O(n) time to find a data is

Select one:
a.Binary Search
b.Tree Search
c.Linear Search {correct}
d.Hashing

10.Stack A has entries a, b, c (with a on  top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed on to stack B. An entry popped out of Stack B can be printed. In this arrangement, which of the following permutations of a, b, c is not possible.

Select one:
a.a,b,c
b.b,c,a
c.b,a,c
d.c,a,b {correct}

11.Which is the solution for the recurrence T (n) = 2T (n/2) + 13

Select one:
a.θ(nlg n)
b.θ(n^3)
c.None of the choices {correct}
d.θ(lg n)

solution comes out to be O(n).

12.Assume that we are running MergeSort on an array containing the following 
   values: 7,5,9,4,4,8,2,6. What does the array contain just before the last call to a merge?

Select one:
a.4,5,7,9,2,4,8,6    {correct}
b.2,4,4,5,6,7,8,9
c.2,4,4,5,6,9,7,8
d.4,5,7,9,4,8,2,6

13.One can convert a binary tree into its mirror image by traversing it in

Select one:
a.inorder
b.postorder {correct}
c.preorder
d.any order

14.The complexity of searching an element from a set of n elements using Binary search
algorithm is

Select one:
a.   O(log n) {correct}
b.   O(n)
c.   O(n log n)
d.   O(n^2)

15.Which of the following is not a dynamic data structure?

Select one:
a. Stack
b. Binary Tree
c. Linked list
d. Array {correct}

16.If the array A contains the items 100,23,90,45,2,34,8 what will be resultant array A after 3rd  pass of selection sort?

Select one:
a.   2,8,23,34,45,100,90
b.   2,8,23,45,100,34,90 {correct}
c.   2,23,45,90,100,34,8
d.   2,8,23,34,100,45,90

17.A _________ data type is a keyword of a programming language that specifies the amount of memory needed to store data and the kind of data that will be stored in that memory location
Select one:
a. abstract {correct}
b. vector
c. int
d. None of the choices

18.If sequence of operations - push(1), push(2), pop, pop, push(1), push(2), pop, push(2), pop, pop are performed on the stack, sequence of popped out values are

Select one:
a. 2,2,1,1,1
b. 2,1,2,2,1 {correct}
c. 2,1,2,1,1
d. 2,2,1,2,1

19.A technique for direct search is

Select one:
a. Linear Search
b. Binary Search
c. Tree Search
d. Hashing {correct}

20.If a node having two children is deleted from a binary tree, it is replaced by its

Select one:
a. Preorder predecessor
b. None of the choices
c. Inorder successor {correct}
d. Inorder predecessor