81.  In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time 
a.  Θ(n log n) 
b.  Θ(n) 
c.  Θ(log n) 
d.  Θ(1) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Θ(1)

82.  Which of the following statements is FALSE ? 
a.  In statically typed language, each variable in a program has a fixed type 
b.  In untyped languages, values do not have any types 
c.  In dynamically typed languages, variables have no types 
d.  In all statically typed languages, each variable in a program is associated with values of only a single type during the execution of the program 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).In dynamically typed languages, variables have no types

83.  How many perfect matchings are there in a complete graph of 6 vertices ? 
a.  15 
b.  24 
c.  30 
d.  60 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).15

84.  A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.
Delection of the smallest element Insertion of an element if it is not already present in the set Which of the following data structures can be used for this purpose? 
a.  A heap can be used but not a balanced binary search tree 
b.  A balanced binary search tree can be used but not a heap 
c.  Both balanced binary search tree and heap can be used 
d.  Neither balanced binary search tree nor heap can be used 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).A balanced binary search tree can be used but not a heap

85.  Let S be a stack of size n ≥ 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥ 1, define the stacklife of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stacklife of an element of this stack is 
a.  n (X + Y) 
b.  3Y + 2X 
c.  n (X + Y)  X 
d.  Y + 2X 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).n (X + Y)  X

86.  What is the weight of a minimum spanning tree of the following graph ? 
a.  29 
b.  31 
c.  38 
d.  41 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).31

87.  Let G (V, E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ......., vj) such that (vk, vk+1) ∈ E for all k in i through j  1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow.
Consider the following algorithm. for i = 1 to n for j = 1 to n for k = 1 to n A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ? 
a.  A[j, k] ≤ n 
b.  If A[j, k] ≥ n  1, then G has a Hamiltonian cycle 
c.  If there exists a path from j to k, A[j, k] contains the longest path lens from j to k 
d.  If there exists a path from j to k, every simple path from j to k contain most A[j, k] edges 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).If there exists a path from j to k, every simple path from j to k contain most A[j, k] edges

88.  The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.
global int i = 100, j = 5; void P(x) { int i = 10; print(x + 10); i = 200; j = 20; print(x); } main() { P(i + j); } If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are 
a.  115, 220 
b.  25, 220 
c.  25, 15 
d.  115, 105 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).115, 105

89.  The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.
global int i = 100, j = 5; void P(x) { int i = 10; print(x + 10); i = 200; j = 20; print(x); } main() { P(i + j); } If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are : 
a.  115, 220 
b.  25, 220 
c.  25, 15 
d.  115, 105 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).115, 220

90.  Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.
Class P { void f(int i) { print(i); } } Class Q subclass of P { void f(int i) { print(2*i); } } Now consider the following program fragment: P x = new Q(); Q y = new Q(); P z = new Q(); x.f(1); ((P)y).f(1); z.f(1); Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be 
a.  1 2 1 
b.  2 1 1 
c.  2 1 2 
d.  2 2 2 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).2 2 2
