PAGES: 1 2 3 4

16. In Activity-Selection problem, each activity i has a start time s_i and a finish time f_i where s_i≤f_i. Activities i and j are compatible if:

(A) s_i≥f_j (B) s_j≥f_i

(C) s_i≥f_j or s_j≥f_i (D) s_i≥f_j and s_j≥f_i

Answer: C

17. Given two sequences X and Y:

X = <a, b, c, b, d, a, b>

Y = <b, d, c, a, b, a>

The longest common subsequence of X and Y is:

(A) <b, c, a> (B) <c, a, b>

(C) <b, c, a, a> (D) <b, c, b, a>

Answer: D

Explanation:

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

A sequence G is said to be a common subsequence of X and Y, if Z is a subsequence of both X and Y.

Here X =< a, b, c, b, d, a, b>, the sequences <b,c,a>, <c,a,b>, <b,c,b,a> are subsequences of X.

Given a second sequence of symbols Y = <b, d, c, a, b, a>, then <b,c,a>, <c,a,b>,< b,c,b,a> are common subsequences to both X and Y.

However, the longest common subsequence of X and Y is <b,c,b,a>.

18. If there are n integers to sort, each integer has d digits and each digit is in the set {1,2, …, k}, radix sort can sort the numbers in:

(A) O(d n k) (B) O(d n^k)

(C) O((d+n)k) (D) O(d(n+k))

Answer: D

19. The solution of the recurrence relation

is :

(A) O(lg n) (B) O(n)

(C) O(n lg n) (D) None of the above

Answer: D

20. Floyd-Warshall algorithm utilizes …………… to solve the all-pairs shortest paths problem on a directed graph in ……………. time.

(A) Greedy algorithm, θ(V³) (B) Greedy algorithm, θ(V² lgn)

(C) Dynamic programming, θ(V³) (D) Dynamic programming, θ(V² lgn)

Answer: C

Explanation:

Floyd-warshall algorithm uses Dynamic programming approach to solve the all-pairs shortest paths problem on a directed graph θ(V³) in time.

21. Let n=4 and (a₁, a₂, a₃, a₄) = (do, if, int, while). Let p(1:4) = (3/8, 3/8, 1/8, 1/8) and q(1:4) = (2/8, 3/8, 1/8, 1/8, 1/8) where p(i) and q(i) denotes the probability with which we search a_i and the identifier x being searched satisfy a_i < x < a_i+1 respectively. The optimal search tree is given by:

Answer: B

22. The family of context sensitive languages is …………….. under union and …………….. under reversal.

(A) closed, not closed (B) not closed, not closed

(C) closed, closed (D) not closed, closed

Answer: C

Explanation:

click on image

23. Match the following :

List – I List – II

(a) {aⁿ bⁿ|n > 0} is a deterministic (i) but not recursive language

context free language

(b) The complement of {aⁿ bⁿ aⁿ|n > 0} (ii) but not context free language

is a context free language

(c) {aⁿ bⁿ aⁿ} is context sensitive language (iii) but can not be accepted by a deterministic pushdown automation

(d) L is a recursive language (iv) but not regular

Codes :

(a) (b) (c) (d)

(A) (i) (ii) (iii) (iv)

(B) (i) (ii) (iv) (iii)

(C) (iv) (iii) (ii) (i)

(D) (iv) (iii) (i) (ii)

Answer: Marks to all

24. The language of all non-null strings of a’s can be defined by a context free grammar as

follow :

S→a S|S a| a

The word a³ can be generated by ……………. different trees.

(A) Two (B) Three

(C) Four (D) Five

Answer: C

Explanation:

25. Which one of the following non-functional quality attributes is not highly affected by the

architecture of the software ?

(A) Performance (B) Reliability

(C) Usability (D) Portability

Answer: C

26. The context free grammar given by

S→XYX

X→aX|bX|λ

Y→bbb

generates the language which is defined by regular expression:

(A) (a+b)*bbb (B) abbb(a+b)*

(C) (a+b)*(bbb)(a+b)* (D) (a+b)(bbb)(a+b)*

Answer: C

27. There are exactly ……………. different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.

(A) 64 (B) 256

(C) 1024 (D) 5832

Answer: D

Explanation:

N * N^(N*M)* 2^N (N is number of states , M is number of alphabet )

the first N is for no. of way to select initial state . Here N will be 1 because they told us X is only initial state .

N^(N*M) is for no. of transition functions from a set of N*M elements to a set of N elements. .

2^N No. of final state we can choose .

so , 1 * 3^(3*2)* 2^3 =5832

28. Given the following two languages :

L₁={aⁿbaⁿ|n>0}

L₂={aⁿbaⁿbⁿ⁺¹|n>0}

Which of the following is correct?

(A) L₁ is context free language and L₂ is not context free language

(B) L₁ is not context free language and L₂ is context free language

(C) Both L₁ and L₂ are context free languages

(D) Both L₁ and L₂ are not context free languages

Answer: A

29. Which of the following is used to make an Abstract class ?

(A) Making atleast one member function as pure virtual function

(B) Making atleast one member function as virtual function

(C) Declaring as Abstract class using virtual keyword

(D) Declaring as Abstract class using static keyword

Answer: A

30. Match the following with reference to object oriented modelling :

List – I List – II

(a) Polymorphism (i) Picking both operator and attributes with

operations appropriate to model an object

(b) Inheritance (ii) Hiding implementation details of methods

from users of objects

(c) Encapsulation (iii) Using similar operations to do similar things

(d) Abstraction (iv) Create new classes from existing class

Codes :

(a) (b) (c) (d)

(A) (iv) (iii) (i) (ii)

(B) (iii) (iv) (i) (ii)

(C) (iii) (i) (ii) (iv)

(D) (iv) (iii) (ii) (i)

Answer: B

31. In CRC based design, a CRC Team consists of :

(a) one or two users representatives

(b) several programmers

(c) project co-ordinators

(d) one or two system analysts

Codes :

(A) (a) and (c) (B) (a), (b), (c) and (d)

(C) (a), (c) and (d) (D) (a), (b) and (d)

Answer: C

32. The end points of a given line are (0, 0) and (6, 18). Compute each value of y as x steps from 0 to 3, by using equation of straight line :

(A) For x=0, y=0; x=1, y=3; x=2, y=6; x=3, y=9

(B) For x=0, y=1; x=1, y=3; x=2, y=4; x=3, y=9

(C) For x=0, y=2; x=1, y=3; x=2, y=6; x=3, y=9

(D) For x=0, y=0; x=1, y=3; x=2, y=4; x=3, y=6

Answer: A

Explanation:

two end points A(0,0) and B(6,18) are given
The equation of straight line is y =mx + c where c is y intercept and m = slope of line

we know m= (y2-y1)/(x2-x1)

m=(18-0)/(6-0) m =3, y intercept c = y-mx
for y intercept we take x= x1 and y = y1
here x1 =0 and y1 =0, c = y1 – mx1
c=0
first point is x=0,y=0
second point is x step incremented by 1 so x=1
y = mx+c =3*1+0 so y=3
x=1,y=3
Third point is x step incremented by 1 so x=2
y = mx+c =3*2+0 so y=6
x=2,y=6
Fourth point is x step incremented by 1 so x=3
y = mx+c =3*3+0 so y=9
x=3,y=9
so the option is (1) i.e For x=0, y=0; x=1,y=3; x=2,y=6; x=3, y=9 is the correct answer

33. Which of the following graphic primitives are considered as the basic building blocks of

computer graphics ?

(a) Points (b) Lines (c) Polylines (d) Polygons

Codes :

(A) (a) only (B) (a) and (b)

(C) (a), (b) and (c) (D) (a), (b), (c) and (d)

Answer: B

34. Javascript and Java has similar name because ……………….. is/are true.

(a) Javascripts syntax is loosely based on Java’s syntax

(b) Javascript is stripped down version of Java

(c) Java and Javascript are originated from Island of Java

Codes :

(A) (a) only (B) (a), (b) and (c)

(C) (a) and (b) (D) (a) and (c)

Answer: A

35. Which of the following statements are true with reference to the way of describing XML

data ?

(a) XML uses DTD to describe the data

(b) XML uses XSL to describe the data

(c) XML uses a description node to describe the data

Codes :

(A) (a) only (B) (b) only

(C) (a) and (b) (D) (a) and (c)

Answer: D

36. Which of the following is/are correct with reference to Abstract class and interface ?

(a) A class can inherit only one Abstract class but may inherit several interfaces.

(b) An Abstract class can provide complete and default code but an interface has no code.

Codes :

(A) (a) is true (B) (b) is true

(C) Both (a) and (b) are true (D) Neither (a) nor (b) is true

Answer: C

37. Match the following with respect to various memory management algorithms :

List – I List – II

(a) Demand paging (i) degree of multiprogramming

(b) Segmentation (ii) working set

(c) Dynamic partitions (iii) supports user view of memory

(d) Fixed partitions (iv) compaction

Codes :

(a) (b) (c) (d)

(A) (iii) (iv) (ii) (i)

(B) (ii) (iii) (i) (iv)

(C) (iv) (iii) (ii) (i)

(D) (ii) (iii) (iv) (i)

Answer: D

38. Function of memory management unit is :

(A) Address translation (B) Memory allocation

(C) Cache management (D) All of the above

Answer: A

39. Consider a system with twelve magnetic tape drives and three processes P₁, P₂ and P₃. Process P₁ requires maximum ten tape drives, process P₂ may need as many as four tape drives and P₃ may need upto nine tape drives. Suppose that at time t₁, process P₁ is holding five tape drives, process P₂ is holding two tape drives and process P₃ is holding three tape drives. At time t₁, system is in:

(A) safe state (B) unsafe state

(C) deadlocked state (D) starvation state

Answer: B

Explanation:

At the time T1
Maximum need P1 P2 P3 is 10 4 9 respectively
Allocated P1 P2 P3 is 5 2 3 respectively
Total tape drives = 12
Available tape drives = 12-(Allocated tape drives)
= 12 – (10)=2
Need P1 P2 P3
5 2 6
So process P2 needs 2 tap drives and we have available 2.
So P2 satisfies is need at t1 After this Available becomes 4
So we can see neither P1 nor P3 need satisfies so system no longer becomes
safe and System goes to unsafe state at time t1

40. In Unix operating system, special files are used to :

(A) buffer data received in its input from where a process reads

(B) provide a mechanism to map physical device to file names

(C) store list of file names plus pointers associated with i-nodes

(D) store information entered by a user application program or utility program

Answer: B

PAGES: 1 2 3 4