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