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

(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) n

^{2}
Answer: 1

36. Consider
the following two Grammars:

G

_{1}: S → SbS | a
G

_{2}: S → aB | ab, A→GAB | a, B→ABb | b
Which of the
following option is correct?

(1) Only G

_{1}is ambiguous
(2) Only G

_{2}is ambiguous
(3) Both G

_{1}and G_{2}are ambiguous
(4) Both G

_{1}and G_{2}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={ 0

^{n}1^{n}2^{n}| 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