21.
The solution of the recurrence relation
T(m) = T(3m/4)
+ 1 is:
(1) θ (lg m)
(2) θ (m)
(3) θ (mlg
m)
(4) θ (lglg
m)
Answer: 1
22. Consider
the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from
the array A, the depth of the heap and the right child of max-heap are ..............
and ..................
respectively.
(Root is at level 0).
(1) 3, 14
(2) 3, 10
(3) 4, 14
(4) 4, 10
Answer: 2
23. A
hash function h defined h(key)=key mod 7, with linear probing, is used to
insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6.
What will be the location of key 18?
(1) 3
(2) 4
(3) 5
(4) 6
Answer: 3
24. Which
of the following algorithms solves the single-source shortest paths?
(1) Prim’s
algorithm
(2) Floyd -
Warshall algorithm
(3)
Johnson’s algorithm
(4)
Dijkstra’s algorithm
Answer: 4
25. A
text is made up of the characters A, B, C, D, E each occurring with the probability
0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will
have the average length of:
(1) 2.4
(2) 1.87
(3) 3.0
(4) 2.15
Answer: 4
26. A
binary search tree in which every non-leaf node has non-empty left and right
subtrees is called a strictly binary tree. Such a tree with 19 leaves:
(1) cannot
have more than 37 nodes
(2) has
exactly 37 nodes
(3) has
exactly 35 nodes
(4) cannot
have more than 35 nodes
Answer: 2
27. Match
the following with respect to algorithm paradigms :
List - I
(a) The
8-Queen’s problem
(b)
Single-Source shortest paths
(c)
STRASSEN’s Matrix multiplication
(d) Optimal
binary search trees
List - II
(i) Dynamic
programming
(ii) Divide
and conquer
(iii) Greedy
approach
(iv)
Backtracking
Code:
(a) (b) (c)
(d)
(1) (iv) (i) (iii)
(ii)
(2) (iv) (iii) (i)
(ii)
(3) (iii) (iv) (ii)
(i)
(4) (iv) (iii) (ii)
(i)
Answer: 4
28. The
maximum number of comparisons needed to sort 9 items using radix sort is
(assume each item is 5 digit octal number):
(1) 45
(2) 72
(3) 360
(4) 450
Answer: 3
29. A
5-ary tree is tree in which every internal node has exactly 5 children. The
number of left nodes in such a tree with 8 internal nodes will be:
(1) 30
(2) 33
(3) 45
(4) 125
Answer: Marks to
all
30. Consider
a Boolean function of ‘n’ variables. The order of an algorithm that determines whether
the Boolean function produces a output 1 is:
(1)
Logarithmic
(2) Linear
(3)
Quadratic
(4)
Exponential
Answer: 4
31. Two
finite state machines are said to be equivalent if they:
(1) Have the
same number of edges
(2) Have the
same number of states
(3)
Recognize the same set of tokens
(4) Have the
same number of states and edges
Answer: 3
32. The
finite state machine given in figure below recognizes:
(1) any
string of odd number of a’s
(2) any
string of odd number of b’s
(3) any
string of even number of a’s and odd number of b’s
(4) any
string of odd number of a’s and odd number of b’s
Answer: 4
33. A
pushdown automata behaves like a Turing machine when the number of auxiliary
memory is:
(1) 0
(2) 1
(3) 1 or
more
(4) 2 or
more
Answer: 4
34. Pushdown
automata can recognize language generated by ................
(1) Only
context free grammar
(2) Only
regular grammar
(3) Context
free grammar or regular grammar
(4) Only
context sensitive grammar
Answer: 3
35. To
obtain a string of n Terminals from a given Chomsky normal form grammar, the
number of productions to be used is:
(1) 2n−1
(2) 2n
(3) n+1
(4) n2
Answer: 1
36. Consider
the following two Grammars:
G1
: S → SbS | a
G2
: S → aB | ab, A→GAB | a, B→ABb | b
Which of the
following option is correct?
(1) Only G1
is ambiguous
(2) Only G2
is ambiguous
(3) Both G1
and G2 are ambiguous
(4) Both G1
and G2 are not ambiguous
Answer: 3
37. Context
sensitive language can be recognized by a:
(1) Finite
state machine
(2)
Deterministic finite automata
(3)
Non-deterministic finite automata
(4) Linear
bounded automata
Answer: 4
38. The
set A={ 0n 1n 2n | n=1, 2, 3, ......... } is
an example of a grammar that is:
(1) Context
sensitive
(2) Context
free
(3) Regular
(4) None of
the above
Answer: 1
39. A
bottom-up parser generates:
(1)
Left-most derivation in reverse
(2)
Right-most derivation in reverse
(3)
Left-most derivation
(4)
Right-most derivation
Answer: 2
40. Consider
the following statements( ):
S1 : There
exists no algorithm for deciding if any two Turing machines M1 and M2 accept the
same language.
S2 : The
problem of determining whether a Turing machine halts on any input is
undecidable.
Which of the
following options is correct?
(1) Both S1
and S2 are correct
(2) Both S1
and S2 are not correct
(3) Only S1
is correct
(4) Only S2
is correct
Answer: 1
0 Comments