71.  The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is: 
a.  n/2 
b.  (n  1)/3 
c.  (n  1)/2 
d.  (2n + 1)/3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).(2n + 1)/3

72.  Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values: 1. Choose an i uniformly at random from 1..... n; 2. If A[i] = x then Stop else Goto 1; Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates ? 
a.  n 
b.  n  1 
c.  2n 
d.  n/2 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).n

73.  The running time of the following algorithm Procedure A(n) If n < = 2 return (1) else return (A(Image not present√nImage not present)); is best described by : 
a.  O(n) 
b.  O(log n) 
c.  O(log Log n) 
d.  O(1) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).O(log Log n)

74.  A weightbalanced tree is a binary tree in which for each node, the number of nodes in the left subtree is at least half and at most twice the number of nodes in the right subtree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following? 
a.  log2 n 
b.  log4/3 n 
c.  log3 n 
d.  log3/2 n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).log3/2 n

75.  Consider the following C function. float f(float x, int y) { float p, s; int i; for (s=1, p=1, i=1; i < y; i ++) { p*= x/i; s+=p; } return s; } For large values of y, the return value of the function f best approximates 
a.  x^y 
b.  e^x 
c.  ln(1 + x) 
d.  x^x 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).e^x

76.  Assume the following C variable declaration int *A [10], B[10][10]; Of the following expressions: I A[2] II A[2][3] III B[1] IV B[2][3] which will not give compiletime errors if used as left hand sides of assignment statements in a C program? 
a.  I, II, and IV only 
b.  II, III, and IV only 
c.  II and IV only 
d.  IV only 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).I, II, and IV only

77.  Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the inorder traversal sequence of the resultant tree ? 
a.  7 5 1 0 3 2 4 6 8 9 
b.  0 2 4 3 1 6 5 9 8 7 
c.  0 1 2 3 4 5 6 7 8 9 
d.  9 8 6 4 2 3 0 1 5 7 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).0 1 2 3 4 5 6 7 8 9

78.  Consider the following three claims 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) Which of these claims are correct ? 
a.  1 and 2 
b.  1 and 3 
c.  2 and 3 
d.  1, 2, and 3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).1 and 2

79.  Consider the following graph. Among the following sequences I) a b e g h f II) a b f e h g III) a b f h g e IV) a f g h b e Which are depth first traversals of the above graph? 
a.  I, II and IV only 
b.  I and IV only 
c.  II, III and IV only 
d.  I, III and IV only 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).I, III and IV only

80.  The unusual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where and element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will 
a.  remain Θ(n^2) 
b.  become Θ(n (log n)^2) 
c.  become Θ(n log n) 
d.  become Θ(n) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).remain Θ(n^2)
