DSA Quiz 2

1.The maximum degree of any vertex in a simple graph with n vertices is Select one: a. n–1 { correct } b. n c. n+1 d. 2n–1 source :Graph Theory with Applications to Engineering and Computer Science 2.The number of edges in a 4-regular graph on 5 vertices is Select one: a. 12 b. 8 c. 14 d. 10 { correct } d-regular graph on n vertices has nd/2 edges.so either n or d should be even. Also, the largest possible value for d is n - 1, which occurs when every vertex is joined to every other vertex. 3.The numbers [23, 12, 26, 17, 6, 9] are inserted into an empty AVL tree in the given sequence. Then the rotation used to fix the AVL tree violation at node 23 is Select one: a. Double rotation- left right b. Single rotation- right right c. Double rotation- right left d. Single rotation- left left{ correct }

(LL)->single rotation left left means balancing factor is ( 2 ) and imbalance is because of 
node added to left(L) subtree of left(L) child. rotation direction is right that doesn't means right rotation 4.The numbers [15,10,25,13,9,7] are inserted into an empty AVL tree in the given sequence. Then, the AVL tree property is violated during the insertion of node Select one: a. 25 b. 7 { correct } c. 9 d. 13 5.For a tree on n vertices, the number of nodes with no ancestors is Select one: a. 1 { correct } b. n c. 0 d. 2 root node is ancester of every other node but has no ancestors 6.The number of edges on a tree with 3 nodes are Select one: a. 4 b. 5 c. 3 d. 2 { correct } tree with n nodes, the no. of edges is n-1 7.The running time of quick sort when the partition is maximally unbalanced is Select one: a. O(nlogn) b. O(n) c. O(n^2) {correct} in worst case d. None of the choices 8.In a heap data structure, the left child of the node in index 5 is in index Select one: a. 14 b. 12 c. 10 { correct } d. 8 9.Huffman tree is constructed for the following data:{A, B, C, D, E} with frequency {0.17, 0.11, 0.24, 0.33, 0.15} respectively. 1000001101 is decoded as Select one: a. CADE b. CADD c. BACE { correct } d. BAD 10.In a quick sort procedure of an array A[ 23, 12, 26, 17, 6, 9, 11, 34, 89, 40, 19], the pivot is chosen initially as the median-of-three choice. The pivot is Select one: a. 19 {correct} b. 9 c. 17 d. 6 11.G is an undirected graph with vertex set {a,b,c,d,e,f,g,h} and edge set {ab, ad, ac,cd,de, db, be, eg}, then a graph H with vertex set {a,b,c,d,e,f,g,h} and edge set {ab, ad, ac,cd, ef, eg }is a spanning subgraph of G. Select one: a. True b. False { correct } 

as number of vertives in both the graph is same but ef doesn't belong to G. 12.In a heap data structure given by the array A[1..12] where A = [23, 12, 26, 17, 6, 9, 11, 34, 89, 40, 19, 28], the first iteration of build max heap will start from the node containing the data Select one: a. 9 {correct} refer algorithm b. 28 c. 17 d. 6 13.The quick sort algorithm exploits the following design technique Select one: a. Backtracking b. Dynamic programming c. Divide and Conquer { correct } d. Greedy 14.In an undirected graph G with vertex set {a,b,c,d,e} and edge set {ab,bc, be, ce, cd, dc, de, ee}, the walk w through the edges: ab-be-ed-dc-ce is a path. Select one: a. True b. False { correct } as e vertex repeated 15.In a balanced binary search tree, the height of the tree is Select one: a. O(n^2) b. O(n) c. O(nlogn) d. O(logn) { correct } 16.For an undirected graph G with n vertices and e edges, the sum of the degrees of all the vertices is Select one: a. en b. 2n c. 2e {correct} d. ne 17.In a Max heap given by the array A[1..7] where A =[15,10,13,9,7,12,25], heap property is violated at index Select one: a. 2 b. 1 c. 4 d. 3 { correct } 18.In an undirected graph G with vertex set {a,b,c,d,e,f,g,h} and edge set {ab, af, ag,bc, ch, cg, cd,dg, gf, ge, de, ef}, the order of G is Select one: a. 8 {correct} count of no of vertices b. 7 c. 10 d. 5 19.In a heap data structure, the right child of the node in index 7 is in index Select one: a. 13 b. 14 c. 15 { correct } (2i+1) d. 12 20.In a heap data structure, the parent of the node in index 5 is in index Select one: a. 3 b. 2 {correct} floor function(i/2) c. 1 d. 4 21.Quick sort algorithm sorts Select one: a. None of the choices b. Out of place c. In place { correct } 22.In an undirected graph G with vertex set {a,b,c,d,e,f,g,h} and edge set {ab, af, ag, bc, ch, cg, cd,dg, gf, ge, de, ef}, the adjacent vertices are Select one: a. f and d b. a and h c. e and g {correct} d. c and e

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