The GATE monk : 2016

Q. No. 1 to 25 carry 1 mark each

1. Which of the following are tautologies?

(i) [p ^ (p⇒q)] ⇒q

(ii) (p⇒q) ⇔(q’⇒p’)

(iii) [q’^(p⇒q)] ⇒p’

(a) Only (i) and (ii) are true

(b) Only (ii) and (iii) are true

(d) All are true

Ans: (D)

2. Consider the expressions given below:

E1: (0+1)*1(0+1)*1(0+1)*

E2: (0+1)*10*1(0+1)*

E3: 0*10*1(0+1)*

E4: (0+1)*10*10*

Which of the given expressions are equivalent?

(a) E1 and E2 (b) E1, E2 and E3

Ans: (D)

3. Consider the Hasse diagram given below:

The Hasse diagram represents a

(a) Poset which is not a lattice

(b) A lattice which is not complemented

(d) A Boolean algebra

Ans: (C)

4. Simplify using k-map and represent the result in SOP form

y= f(A, B, C, D) = Σ(0, 1, 2, 6, 7, 10, 14) + Σd(3, 8, 11, 15) where Σd represents don’t care conditions.

(a) A +BC (b) C’ + A’B’

Ans: (C)

5. Individual stages of data path have following latencies:

IF	ID	EX	MEM	WB
300 ps	400ps	350ps	500ps	100ps

What is the clock time of the pipelined processor?

(a) 500 ps (b) 1650 ps

Ans: (A)

6. Consider the following program:

main()

{

int i=257;

int *iptr = &i;

printf(“%d%d”, *((char*)iptr, *((char*)iptr+1);

}

What should be the output of the above program?

(a) 257, 257 (b) -128, 127

Ans: (D)

7. Suppose that a code consists of the following code-words:

{ 000000, 000111, 111000, 111111}

Consider the following statements:

(i) The hamming distance of the code is 3

(ii) A single bit error can be detected

(iii) 000100 received with two bit errors can be corrected

Which of the given statement(s) is/are true?

(a) only (i)

(b) Only (i) and (ii)

(d) Only (ii) and (iii)

Ans: (B)

8. An 8-bit number with binary value 10010010 is to be encoded using an even parity hamming code. What is the binary value after encoding?

(a) 101000110010 (b) 111100110010

Ans: (B)

9. Which of the following model is not preferred when the requirements are indicating a complex system to be built?

(a) Waterfall model

(b) Evolutionary model

(d) Iterative Enhancement model

Ans: (A)

10. A shopkeeper advertises that a customer can have his/her hamburger with or without any or all of the following: catsup, mustard, mayonnaise, lettuce, tomato, onion, pickle, cheese or mushrooms. How many different kind of hamburgers orders are possible?

(a) 9! (b) 2⁹

Ans: (B)

11. Convert the following statement into symbolic form:

“Nobody can ignore her”

Where I(x) = x can ignore her

(a) (∃x)I(x) (b) ∀x[~I(x)]

Ans: (B)

12. The minimal DFA that recognizes

L= {w| w∈{0,1}* & 1<=|w| mod 5 <=3}

has how many states?

(a) 3 (b) 4

Ans: (C)

13. Consider an empty stack of integers. Let the numbers 1, 2, 3, 4, 5, 6, 7,8 to be pushed on to the stack only in the order they appeared from left to right. Let U indicate PUSH and O indicates POP operation and print the value. What will be the possible order printed if the given set of operation is UOUUOUOUUOUOOUOO?

(a) 12345678 (b) 13467582

Ans: (B)

14. Using the generator (division) polynomial x⁴+ x+ 1 for CRC, what frame will be transmitted for the data M= x⁷ + x⁵ + x³ + 1

(a) 101010011001 (b) 101010010100

Ans: (D)

15. Match the following CMM levels given in Table 1 with the characterizations given in Table 2 by using codes

Table 1 Table 2

A. Initial 1. Process Control

B. Repeatable 2. Process Definition

C. Defined 3. Adhoc Process

D. Managed 4. Basic project management

E. Optimized 5. Process measurement

A B C D E

(a) 1 2 3 4 5

(b) 3 2 4 1 5

(d) 3 5 2 4 1

Ans: (C)

16. Find the time complexity for the given program-

main ()

{

int n;

int x = 0;

while (n<1)

( x=x +1;

n= n/2;

}

Where n is a positive integer?

(a) O(n) (b) O(logn)

Ans: (C)

17. Which of the following CNF is equivalent to the given formula?

(~p) => ~(q ^~(r ∨ ~(s^u)))

(a) p^q^r∨~r∨~s

(b) p∨r∨q∨s∨~u

(d) None of these

Ans: (C)

18. The number of asymmetric relations on a set of m elements:

(a) 2 ^m(m-1)/2(b) 3^m(m-1)/2

Ans: (B)

19. Consider the following grammar G-

G: S⇒ SS|a|ε

Which of the following is true about G?

(a) L(G) is accepted by DFA

(b) G is a regular grammar

(d) L(G) is finite

Ans: (A)

20. Suppose that you collect the following timing data for a program as a function of the input size N.

N	Time
100	0.01sec
400	0.16sec
1600	3.00sec
6400	41sec
25600	656sec

Estimate the running time of program (in seconds) as a function of N.

(a) T(n)= ϴ(n) (b) T(n) = ϴ(n³)

Ans: (C)

21. Consider the following program-

main ()

{

int i= 5;

{

int i=7, j=8;

printf( “%d%d”, i, j);

}

printf(“%d%d”, i, j);

}

Which of the following is true about this program?

(a) It prints 7858 (b) It prints 5858

Ans: (C)

22. You are given a hash table with n keys and m slots with the simple uniform hashing assumption (each key is equally likely to be hashed into each slot. Collisions are resolved by chaining). Thus the probability that no key hashes into the first slot is:

(a) 1/ mⁿ (b) 1/(m-1)ⁿ

Ans: (C)

23. Consider the following program segment:

P(S1);

a++;

P(S2);

V++;

V(S2);

V(S1);

(S1, S2 are semaphores). All variables are auto. Now, consider two threads running this fragment of code simultaneously.

Which of the following statements is true?

(a) Deadlock is possible

(b) No situation where deadlock could occur

(d) None of these

Ans: (B)

24. Consider the m-way relationship R between entity sets E1, E2, ....,En. What is the minimum and maximum number of attributes that could form the key for a relation derived from R respectively?

(a) n, n+1 (b) n-1, n

Ans: (B)

25. Which one of the following is used at high load situations?

(a) Pure ALOHA

(b) Slotted ALOHA

(d) Both (a) and (b)

Ans: (C)

Q. No. 26 to 55 carry 2 marks each

26. Consider the Matrix A =

Which of the following are Eigen values of the matrix A 2 ?

(a) 1, 1, 1 (c) 1, 1, 9

(b) 2, 2, 2 (d) 9, 9, 9

Ans: (B)

27. Which of the following sets is a lattice with respect to divisibility?

(i) A 1 = { 1, 2, 4, 5, 20 }

(ii) A 2 = { 2, 4, 8, 10, 20, 40 }

(iii) A 3 = { 1, 2, 3, 4, 5, 6, 10, 15, 20, 30, 60 }

(a) Only (i) and (ii) (c) Only (ii) and (iii)

(b) Only (iii) (d) All (i), (ii), and (iii)

Ans: (D)

28. What is the running time of the following function (specified as a function of the input value l)?

void function (int l)

{

int a = 1;

int b = 1;

while (b < = l)

{

a++;

b = b + a;

printf(“*”);

}

(a) O(l log l) (c) O(l)

(b) O(√l) (d) None of these

Ans: (C)

29. Consider the given syntax directed translation

E → E 1 #T {E.Val = E 1 .Val*T.Val}

E → T {E.Val = T.Val}

T → T 1 &F {(1)}

T → F {T.Val = F.Val}

F → num {F.Val = num}

If the expression 6#11&3#18&2#4&2

Evaluate to 576. Then which of the following correctly represents (1)?

(a) T.Val = T.Val – F.Val

(b) T.Val = T.Val/F.Val

(d) T.Val = T.Val * F.Val

Ans: (A)

30. Consider the following grammar over the terminals +, - (negation operator) and id

S → E

E → E + E | -E | id

Determine the number of states (such that i 0 , i 1, i 2 ,….) in the above given LR parser

(a) 6 (c) 7

(b) 8 (d) 9

Ans: (B)

31. Consider a demand paging system with a paging disk that has an average access and transfer time of 20ms. Addresses are translated through page table in memory, with an access time of 1sec per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page table entry is in the associative memory. Assume that 80% of the accesses are in associative memory and that of the remaining 10% (or 2% of the total) causes page faults. What is the effective memory access time?

(a) 312.2sec (c) 366.8sec

(b) 538.9sec (d) None of these

Ans: (D)

32. A system has four process and five allocatable resources, the current allocation and maximum needs are as follows

What is the smallest value of x for which system is in safe state?

(a) 0 (c) 1

(b) 2 (d) More than 3

Ans: (B)

Common Data Question for Q.no 33 & 34.

Consider the following preemptive priority scheduling algorithm based on dynamically changing priorities. Larger priority implies higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate ‘a’; when its is running, its priority changes at a rate ‘b’. All processes are given a priority of zero when they enter the ready queue for the first time. The parameters a and b can be set to give many scheduling algorithms.

33. What is the algorithm that results from b>a>0

(a) FCFS

(b) LIFO

(d) No algorithm apply for the above condition

Ans: (A)

34. What is the algorithm resulting from a<b<0

(a) FCFC

(b) LIFO

(d) No algorithm apply for above condition

Ans: (B)

35. Consider the following functions:

I. f(x) = |x|

II. f(x) = x³ +6

Which of the above functions is neither one-to-one nor onto?

(a) I only (b) II only

Ans: (A)

36. In a college dance function there are 20 girls and 20 boys. Consider a match of the students into 20 girl/boy couples. Of course not all of the couples go out on the dance floor for each song. Zero or more couples may be selected for a particular song for dancing and we can call such a set of couples as a “dancing set”. Then, how many such dancing sets can there be?

(a) 20! X 2²⁰

(b) 2²⁰

(d) None of these

Ans: (A)

37. What happens if the schedule executing using Basic Timestamp Ordering protocol:

S: r1(A)r2(B)w1(C)r3(B)r3(C)w2(B)w3(A)

With TS values (T1, T2, T3) = (100, 200, 300). Which of the following is true?

(a) Roll back T1

(b) Roll back T2

(d) Roll back T1, T2 and T3

Ans: (B)

38. Consider a token ring in which there are 20 stations, and the length of the ring in a 40 Mbps token ring network is 18000 meters. The speed of propagation is 3x10⁸m/s. Each station holds the token for 10 micro-sec. Calculate the total time for a 10 byte token to go around the ring.

(a) 0.40 x 10^-4 sec

(b) 0.60 x 10^-4 sec

(d) 1.00 x 10^-4 sec

Ans: (D)

39. Consider the given below IP header without options. The header is divided into 16-bit section.

Calculate the checksum in the hexadecimal

(a) 743E

(b) 8BC1

(d) 8BB1

Ans: (D)

40. A Table T 1 in a relational database has the following rows and columns

The following sequence of SQL statements was successfully executed on table T 1

UPDATE T 1 SET Balance = Balance + 7000;

SELECT AVG(Balance) FROM T 1 ;

What is the output of the SELECT statement?

(a) 13,000

(b) 15,334

(d) None of these

Ans: (D)

41. Which of the following language is/are regular:

L 1 : the language of strings with no occurrences of the substring “010”.

L 2 : the language of strings with more occurrences of 0 than 1.

L 3 : the language of strings whose length is a multiple of 3.

L 4 : the language of strings whose number of occurrence of zero minus number of occurrences of 1 is a multiple of 3.

L 5 : the language of strings of terminals and non-terminals that can appear on the parsing stack during an LR(1) parse ( stack is read from the bottom of the stack ).

Here the alphabet is the set of terminals and non-terminals of the grammar being passed

(a) L 1, L 4 and L 5

(b) L 1, L 2 and L 4

(d) L 1, L 3, L 4 and L 5

Ans: (D)

42. A shift Reduce parser carries out the actions specified with in braces immediately after reducing the corresponding rule of grammar

A → aaB {print “x”}

A → b { print “+”}

B → Ac{ print “-“}

B→ c{print “/”}

What is the translation of aaaabcc using the syntax directed translation scheme described by the above rules.

(a) +-x-x

(b) x-x-+

(d) None of these

Ans: (A)

Common Data Question for Q. No. 43 and 44

Consider the following table TAB1

TAB1

COL1	COL2
A	10
B	20
C	30
A	10
D	40
C	30

43. Assuming that the following results are desired:

TAB

COL1	COL2
A	10
B	20
C	30
D	40

Which of the following given statements will produce the above results?

(a) SELECT UNIQUE *FROM TAB1

(b) SELECT DISTINCT *FROM TAB1

(d) SELECT DISTINCT (*) FROM TAB1

Ans: (B)

44. Assuming table TAB1 contains 100 rows. Which of the following queries will return only half of the rows available:

(a) SELECT * FROM TAB1 FIND FIRST 50 ROWS

(b) SELECT * FROM TAB1 FETCH FIRST 50 ROWS ONLY

(d) SELECT * FROM TAB1 MAXROWS 50

Ans: (B)

45. Consider the following code segment

# include <stdlib.h>;

int *f1 (void)

{

int x = 10;

return &x;

}

int *f2 (void)

{

int *ptr;

*ptr = 10;

return ptr;

}

int *f3 (void)

{

int *ptr;

ptr = malloc (size of *ptr);

return ptr;

}

Which of these function uses pointers incorrectly?

(a) f1 only

(b) f1 and f2 only

(d) f1, f2 and f3

Ans: (B)

Common Data Question 46 and 47.

Consider the following given C program

# include <stdio.h>

main ()

{

float sum = 0.0, j = 1.0, i = 2.0;

while (i/j > 0.001)

{

j = j + j;

sum = sum + i/j;

printf(“%f\n”,sum);

}

46. How many lines of output does the program produce?

(a) 0-9

(b) 10-19

(d) More than 39

Ans: (B)

47. For the C code shown above, which of the following integer that best approximates the last number printed?

(a) 0

(b) 1

(d) 3

Ans: (C)

48. The employee information of an Organization is stored in the relation :

Employee (name, sex, salary, deptname)

Consider the following SQL query:

Select deptname from Employee

Where sex = ‘M’

group by deptname

having avg (salary) > {select avg (salary) from Employee}

Output of the given query corresponds to

(A) Average salary of employee more than average salary of the organization.

(B) Average salary less than average salary of the organization.

(D) Average salary of male employees in a department is more than average salary of the organization.

Ans: (D)

49. For a database relation R(a, b, c, d) where the domains of a, b, c, d include only the atomic values. The functional dependency a → c, b → d holds in the following relation

(A) In 1NF not in 2NF

(B) In 2NF not in 3NF

(D) In 1NF

Ans: (A)

50. A pushdown automaton M = (Q, Σ, Γ, δ, q0, z, F) is set to be deterministic subject to which of the following condition(s), for every q ∈ Q, a ∈ Σ ∪ {λ} and b ∈ Γ

(s1) δ(q, a, b) contains at most one element

(s2) if δ(q, λ, b) is not empty then δ(q, c, b) must be empty for every c ∈ Σ

(A) only s1

(B) only s2

(D) neither s1 nor s2

Ans: (C)

51. For every context free grammar (G) there exists an algorithm that passes any w ∈ L(G) in number of steps proportional to

(A) ln|w|

(B) |w|

(D) |w|³

Ans: (D)

52. The simplified function in product of sums of Boolean function F(W, X, Y, Z) = Σ(0, 1, 2, 5, 8, 9, 10) is

(A) (W' + X') (Y' + Z') (X' + Z)

(B) (W' + X') (Y' + Z') (X' + Z')

(D) (W' + X') (Y + Z') (X' + Z)

Ans: (A)

53. What will be the output of the following segment of the program?

main( )

{

char *s = “hello world”;

int i = 7;

printf(“%, *s”, i, s);

}

(A) Syntax error

(B) hello w

(D) o world

54. Consider the following processes with time slice of 4 milliseconds (I/O requests are ignored):

The average turn around time of these processes will be

(A) 19.25 milliseconds

(B) 18.25 milliseconds

(D) 18.5 milliseconds

Ans: (B)

55. A job has four pages A, B, C, D and the main memory has two page frames only. The job needs to process its pages in following order:

ABACABDBACD

Assuming that a page interrupt occurs when a new page is brought in the main memory, irrespective of whether the page is swapped out or not.

The number of page interrupts in FIFO and LRU page replacement algorithms are

(A) 9 and 7

(B) 7 and 6

(D) 8 and 6

Ans: (C)

Q. No. 56 to Q. No. 60 carries 1 mark each

56. Consider given sentence having one or two idioms.

The two women are so jealous that at the drop of a hat they start insulting each other.

Which of the following best describe the meaning of the idiom?

(a) On every occasion

(b) For no reason at all

(d) Very rarely

Ans: (A)

57. Eight friends Ankit, Arjit, Ram, Mohan, Simran, Rupali, Pinki and Monu are sitting in a circle facing the centre. Ram is sitting between Pinki and Simran, Ankit is third to the left of Ram and second to the right of Monu. Rupali is sitting between Ankit and Pinki, and Ram and Mohan are not sitting opposite to each other. Who is second right to the Rupali?

(a) Mohan (c) Ram

(b) Simran (d) Arjit

Ans: (B)

58. In a class 40% of the students enrolled for Math and 70% enrolled for Hindi. If 15% of the students enrolled for both Math and Hindi, what percent of the student of the class did not enroll for either of the two subjects?

(a) 5% (c) 95%

(b) 0% (d) None of these

Ans: (A)

59. Pick the Oddman out:

(a) Wisdom; folly (c) Friendship; enmity

(b) Often; seldom (d) Loyalty; treachery

Ans: (C)

60. Fill in the blank with the appropriate word:

Value of currency was increasing which ultimately kick started ________ in economy.

(a) Deflation

(b) Depreciation

(d) None of these is appropriate word

Ans: (A)

Q. No. 61 to Q. No. 65 carries 2 marks each

61. Today is 8/10/12. Keeping this figure 81012 in mind, I have arrived at the following sequence 1, 1, 3, 10, __. Which of the following number can fill the blank?

(a) 10812 (c) 108

(b) 12 (d) 65

Ans: (D)

62. In a bike race five participants Ajay, Akhilesh, Riya, Sapna, Sumit take part. Track 1 is extreme left and track 5 is extreme right. The following conditions exist:

(i) Akhilesh and Sumit are not cycling adjacent to each other.

(ii) Sapna is not in one of the extreme tracks.

(iii) Ajay is to the left of Riya.

If Sapna is left to Ajay, then Sapna could be in

(a) Track 3 only (c) Track 2 only

(b) Track 2 or 3 (d) None of these

Ans: (B)

63. Sum of square of two numbers X and Y is less or equal to 100. How many sets of integers solutions of X and Y are possible?

(a) 299

(b) 297

(d) None of these

Ans: (D)

64. There are 6 tasks and 6 students. Task 1 cannot be assigned to either student 1 or student 2. Task 2 must be assigned to either student 3 or student 4. Every student is to be assigned a task. In how many ways can the assignment be done?

(a) 180

(b) 192

(d) 144

Ans: (D)

65. Consider two trains A and B at stations x and y with a distance of 150 km between them. A travels with a speed of 60 km/hr and B travels with a speed of 100 km/hr towards A on parallel track. A has started with a delay of 6 minutes compared to that of B. Find the distance at which the two trains will meet when measured from station y.

(a) 97.5 (b) 26.5

Ans: (A)

The GATE monk

Friday, 25 November 2016

Mock Test-2 With Answers

Blog Archive

About Me

Friday, 25 November 2016

*Mock Test-2 With Answers*

Mock Test-2 With Answers