21.
The solution of recurrence relation:

T(n) = 2T(sqrt(n))
+ lg (n)

is

(1) O(lg (n))

(2) O(n lg (n))

(3) O(lg (n)
lg (n))

(4) O(lg (n)
lg (lg (n)))

Answer: 4

22. The
elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a
max-heap. The resultant max-heap is sorted in an array implementation as

(1) <42,40,35,25,22,30,26>

(2) <42,35,40,22,25,30,26>

(3) <42,40,35,25,22,26,30>

(4) <42,35,40,22,25,26,30>

Answer: 1

23. Consider
two sequences X and Y:

X = <0,1,2,1,3,0,1>

Y = <1,3,2,0,1,0>

The length
of longest common subsequence between X and Y is

(1) 2

(2) 3

(3) 4

(4) 5

Answer: 3

24. Consider
the following postfix expression with single digit operands:

623∗/42∗+68∗−

The top two
elements of the stack after the second ∗ is evaluated, are:

(1) 8,2

(2) 8,1

(3) 6,2

(4) 6,3

Answer: 2

25. A
binary search tree is constructed by inserting the following numbers in order:

60, 25, 72, 15,
30, 68, 101, 13, 18, 47, 70, 34

The number
of nodes in the left subtree is

(1) 5

(2) 6

(3) 7

(4) 3

Answer: 3

26. In
a ternary tree, the number of internal nodes of degree 1, 2, and 3 is 4, 3, and
3 respectively. The number of leaf nodes in the ternary tree is

(1) 9

(2) 10

(3) 11

(4) 12

Answer: 2

27. Match
List-I with List-II and choose the correct answer from the code given below:

**List I (Graph Algorithm) List II (Time Complexity)**

(a) Dijkstra’s
algorithm (i) O(E lg E)

(b) Kruskal’s
algorithm (ii) Î˜(V

^{3})
(c) Floyd-Warshall
algorithm (iii) O(V

^{2})
(d) Topological
sorting (iv) Î˜(V+E)

where V and
E are the number of vertices and edges in graph respectively.

**Code:**

(1) (a)-(i),
(b)-(iii), (c)-(ii), (d)-(iv)

(2) (a)-(iii),
(b)-(i), (c)-(ii), (d)-(iv)

(3) (a)-(i),
(b)-(iii), (c)-(iv), (d)-(ii)

(4) (a)-(iii),
(b)-(i), (c)-(iv), (d)-(ii)

Answer: 2

28. In
K-coloring of an undirected graph G=(V,E) is a function. c:V→{0,1,…,K−1} such
that c(u)≠c(v) for every edge (u,v)∈E.

Which of the
following is

**not**correct?
(1) G is
bipartite

(2) G is
2-colorable

(3) G has cycles
of odd length

(4) G has no
cycles of odd length

Answer: 3

29. Consider
a singly linked list. What is the worst case time complexity of the best-known
algorithm to delete the node a, pointer to this node is q, from the list?

(1) O(n lg n)

(2) O(n)

(3) O(lg n)

(4) O(1)

Answer: 2

30. The
second smallest of n elements can be found with ............... comparisons in
the worst case.

(1) n−1

(2) lg n

(3) n+ceil(lg
n) - 2

(4) 3n/2

Answer: 3

31. Let
r = a(a + b)*, s = aa*b
and t = a*b
be three regular expressions.

Consider the
following:

(i) L(s) ⊆ L(r) and
L(s) ⊆ L(t)

(ii) L(r) ⊆ L(s) and
L(s) ⊆ L(t)

Choose the
correct answer from the code given below:

**Code:**

(1) Only (i)
is correct

(2) Only
(ii) is correct

(3) Both (i)
and (ii) are correct

(4) Neither
(i) nor (ii) is correct

Answer: 1

32. Consider
the language L given by

L
= {2

^{nk}∣ k>0, and n is non-negative integer number}
The minimum
number of states of finite automaton which accepts the language L is

(1) n

(2) n+1

(3)

^{n(n+1)}/_{2}
(4) 2

^{n}
Answer: 2

33. The
number of substrings that can be formed from string given by

a d e f b g h
n m p

is

(1) 10

(2) 45

(3) 55

(4) 56

Answer: 4

34. Consider
the following two languages:

L1 = {x ∣ for some y with ∣y∣ = 2

^{∣}^{x}^{∣},xy ∈ L and L is regular language}
L2 = {x ∣ for some y such that ∣x∣ = ∣y∣, xy ∈ L and L is regular language}

Which one of
the following is correct?

**Code:**

(1) Only L1
is regular language

(2) Only L2
is regular language

(3) Both L1
and L2 are regular languages

(4) Both L1
and L2 are not regular languages

Answer: 3

35. Consider
the following languages:

L1 = {a

^{n+m }b^{n }a^{m }∣ n,m ≥ 0}
L2 = {a

^{n+m}b^{n+m}a^{n+m}∣ n,m ≥ 0}
Which of the
following is correct?

**Code:**

(1) Only L1
is context-free language

(2) Only L2
is context-free language

(3) Both L1
and L2 are context free languages

(4) Both L1
and L2 are not context free languages

Answer: 1

36. Consider
R to be any regular language and L1, L2 be any two context-free languages.
Which of the following is correct?

(1) L

_{1}’ is context free
(2) (L

_{1}∪ L_{2})’ – R is context free
(3) L

_{1 }∩ L_{2}is context free
(4) L

_{1}– R is context free
Answer: 4

37. Consider
the following problems:

(i) Whether
a finite state automaton halts on all inputs?

(ii) Whether
a given context free language is regular?

(iii) Whether
a Turing machine computes the product of two numbers?

Which one of
the following is correct?

**Code:**

(1) Only (i)
and (iii) are undecidable problems

(2) Only
(ii) and (iii) are undecidable problems

(3) Only (i)
and (ii) are undecidable problems

(4) (i),
(ii) and (iii) are undecidable problems

Answer: 2

38. Which
of the following problems is decidable for recursive languages (L)?

(1) Is L = Ï•?

(2) Is w ∈ L, where w
is a string?

(3) Is L = Î£*?

(4) Is L = R,
where R is a given regular set?

Answer: 2

39. Consider
the following grammar G:

S
→ A ∣ B

A
→ a ∣ c

B
→ b ∣ c

where {S, A,
B} is the set of non-terminals, {a, b, c,} is the set of terminals.

Which of the
following statement(s) is/are correct?

S1: LR(1) can parse all strings that are
generated using grammar G.

S2: LL(1) can parse all strings that are
generated using grammar G.

Choose the
correct answer from the code given below:

**Code:**

(1) Only S1

(2) Only S2

(3) Both S1
and S2

(4) Neither
S1 nor S2

Answer: 4

40. The
grammar S → (S) ∣ SS
∣ Ïµ is

**not**suitable for predictive parsing because the grammar is
(1) Right
recursive

(2) Left
recursive

(3) Ambiguous

(4) An
operator grammar

Answer: 3

## 0 Comments