GATE Sample Paper for Computer Science With Solution

May 24 • Competition Sample Papers • 3899 Views • 1 Comment on GATE Sample Paper for Computer Science With Solution

GATE Sample Paper-1 

Q.1 – Q.25 carry one mark each

1. The total size of address space in a virtual memory system is limited by

1. Length of MAR
2. Available secondary storage
3. Available main memory
4.  None of the above
5. All the above

Ans : 2

2. Let r =1(1+0)*  s=11*0 and t=1*0 are regular expressions. Which one of them is false?

1. L(s) subset of L(r) and L(s) subset of L(t)
2. L(r) subset of L(s) and L(s) subset of L(t)
3. L(s) subset of L(t) and L(s) subset of L(r)
4. L(t) subset of L(s) and L(s) subset of L(r)
5. None of the above

Ans : 2

3. The expression s[i] – ‘0’ returns

1. numeric value stored in s[i]
2. character value
3. subtracted value of the value of ASCII value of 0 and s[i]
4. none of the above

Ans : 1

4. #include<ctype.h> is used in

1. main.c
2. getop.c
3. stack.c
4. getch.c

Ans : 3

5. #define forever for( ; ; ) is

1. Gives run time error
2. Gives compilation error
3. Infinite loop
4. None of the above

Ans : 3

6. The recurrence relation  that determines the optimal execution of tower of Hanoi with p discs is

1. 2T(p-2) + 2
2. 2T(p-1) + p
3. 2T(p/2) + 1
4. 2T(p-1) + 1

Ans : 4

7. The operation that is commutative but not associative is

1. AND
2. OR
3. X-OR
4. NOR
5. NAND

Ans : 2

8. Which of the following problems is not NP-hard?

1. Hamilton circuit problem
2. 0/1 knapsack problem
3. Graph colouring problem
4. Finding bi-connected  components of a graph

Ans : 2

9.  Consider the SLR(1) AND LALR(1) parsing tables for a context free grammar. Which of the following is/are true?

1. Goto part of both may be different
2. Shift entries are identical in both
3. Reduce entries may differ
4. Error entries may be different.
5. All of the above

Ans : 4

10. Which of the regular expression equated are same?

1. r(*)= r*
2. ( r + s )* = r* + s*
3. (r* s*) =(r + s)*
4. r* s*= r* +s*
5. none

Ans : 2

11. A simple two pass assembler does the following in first pass

1. Allocate space for literals
2. Computes total length of the program
3. Builds symbol table
4. Generates code for all load and store register instructions

Ans :  1

12.  The proposition P^(~p or q) is

1. Tautology
2. Logically equivalent to p^ v
3. Logically equivalent to p or q
4. None

Ans : 1

13. The maximum number of binary trees that can be formed with three unlabeled nodes is

1. 1
2. 5
3. 4
4. 3

Ans : 3

14.  Which of the following algorithms have the highest worst case complexity?

1. Bubble sort
2. Selection sort
3. Merge sort
4. Quick sort

Ans : 1

15. Given the basic ER and relational model, which one is incorrect?

1. An attribute of an entity can have more than one value
2. An attribute can be composite
3. In row, an attribute can have exactly one value or NULL
4. In row, an attribute can have more than one value

Ans : 1

16. The PDU for application stack in the internal stack is

1. Segment
2. Datagram
3. Message
4. Frame

Ans : 3

17. Linked lists are not suitable data structures of which one of the following problems?

1. Insertion sort
2. Binary search
3. Radix sort
4. Polynomial manipulation

Ans : 4

18. The principle of locality justifies the use of

1. Interrupts
2. DMA
3. Polling
4. Cache memory

Ans : 4

19. Which of the following page replacement suffers from Belady’s  anamoly?

1. Optimal replacement
2. LRU
3. FIFO
4. Both (a) and (c)

Ans : 3

20. Which scheduling policy is suitable for a time shared operating system?

1. Shortest job first
2. First come first serve
3. Elevator
4. Round robin

Ans : 4

21. Who needs to bind ,accept and listen while using sockets?

1. Client
2. Server
3. None of the above
4. Both (a) and (b)

Ans :  2

22. The SEI approach provides ___ process maturity levels

1. 2
2. 3
3. 5
4. 7

Ans : 3

23.  Which languages necessarily need heap allocation in run-time environment?

1. 1. That support recursion
   2. That allow dynamic data structures
   3. That use dynamic scoping
   4. That use global variables

Ans : 3

24.  The 8085 microprocessor responds to the present of an interrupt

1. TRAP pin becomes “high”
2. Checking TRAP pin for “high” the end of each instruction
3. Checking TRAP pin for “high” after the execution of each instruction
4. Checking TRAP pin for “high” at regular intervals

Ans :  1

25.  The 8085 microprocessor responds to the present of an interrupt

1. TRAP pin becomes “high”
2. Checking TRAP pin for “high” the end of each instruction
3. Checking TRAP pin for “high” after the execution of each instruction
4. Checking TRAP pin for “high” at regular intervals

Ans : 1

Q.26 – Q.50 carry two marks  

26. Consider the following decision problems:

(P1) Does a given finite state machine accept a given string.

(p2) Does a  given context free grammar generate an infinte number of strings

Which of the following statements is/are true?

1. Both (P1) and (P2)
2. Only (P1)
3. Only (P2)
4. Neither (P1) nor (P2)

Ans : 3

27.  Consider the following functions

F(n)=3n

G(n)=2Jlog2

H(n)=n!

Which of the following is true?

1. H(n) is 0(f(n))
2. H(n) is 0(g(n))
3. G(n) is not 0(f(n))
4. F(n) is 0(g(n))

Ans : 2

28.  Postorder traversal of a given binary search tree, T produces the following sequence of keys

10, 9, 23, 15, 60, 29, 40

Which one of the following sequences of keys can be the result of an inorder traversal of tree T?

1. 9, 10, 15, 23, 29, 40, 60
2. 9, 10, 15, 23, 60, 40, 29
3. 29, 15, 9, 10, 23, 40, 60
4. 60, 40, 23, 10, 9, 15, 29

Ans : 1

29.   A Priority-Queue is implemented as a max-heap. Initially it has 5 elements. The level-order traversal of the heap is given below:

9, 5, 3, 1

The new elements ‘2’ and ‘8’ are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

1. 9, 8, 5, 3, 2 ,1
2. 9, 8, 2, 3, 1, 5
3. 9, 8, 1, 2, 3, 5
4. 9, 8, 3, 2, 1, 5

Ans : 1

30.  Let P, Q, R be tree atomic prepositional assertions. Let X denote (P v Q) – R and Y denotes (P – R) v (Q – R). Which one of the following is a tautology?

1. XY
2. X – Y
3. Y – X
4. -1Y –X

Ans : 4

31.  An operating system contains 3 user processors each requiring 2 units of resources R. The minimum number of units of r such that no deadlocks will ever arise is

1. 3
2. 5
3. 4
4. 6

Ans : 3

32.  Let R(a, b, c) and S(d, e, f) be two relations in which d is the foreign key of S that refers to the primary key of R. Consider the following operations:

(i)                Insert into R

(ii)             Insert into S

(iii)           Delete from S

(iv)           Delete from R

Which of the following is true about referential integrity?

1. None
2. All of the above
3. Both (i) and (iv)
4. Both (ii) and (iii)

Ans :  1

33.  Which two of the following four regular expressions are equivalent?(E being the empty string)

(i)       (00)*(E + 0)

(ii)      (00)*

(iii)      0*

(iv)      0(00)*

1. (i) and (ii)
2. (ii) and (iii)
3. (i) and (iv)
4. (iii) and (iv)

Ans : 3

34.  The grammar whose productions are

->if id then <stmt>

->if id then <stmt> else <stmt>

->id :=id

Is ambiguous because

1. The left most derivation and right most derivations of the sentence     if a then if b then c :=d  gives rise top different parse trees.
2. The sentence   if a then if b then c:=d
3. The sentence    if a then if b then c:=d else c:=f   has more than two parse trees
4. The sentence   if a then if then c:=d else c:=f has two parse trees.

 

Ans : 3

35.  Quick sort is run on two inputs shown below to sort in ascending order

(i)                1, 2, 3……….n

(ii)             N, n-1, n-2………2, 1

Let c1 and c2 be the number of comparisons made for the inputs. Then

1. C1 < c2
2. C1 > c2
3. C1 = c2
4. Cannot be determined

Ans : 1

36.  A solution to dining philosophers problem that avoids deadlock is

1. All philosopher picks up the left fork before right fork
2. All philosophers picks up right fork before left fork
3. None of the above
4. Cannot be determined

Ans : 3

37.  What values of A, B, C, D satisfy the following Boolean equations?

A` +AB =0

AB = AC

AB + (AC)` + CD = (CD)`

1. A=1 B=0 C=0 D=1
2. A=1 B=1 C=0 D=0
3. A=1 B=0 C=1 D=1
4. A=1 B=0 C=0 D=0

Ans : 1

38.  In a virtual memory system the address space specified by the address lines of the cpu must be _____ than the physical memory size and _____ than the secondary storage

1. Smaller, smaller
2. Smaller, larger
3. Larger, smaller
4. Larger, larger

Ans : 3

39. A memory page containing a heavily used variable that was initialized very early and is in constant use is removed when

1. LRU page replacement algorithm is used
2. FIFO page replacement is used
3. LFU page replacement is used
4. None

Ans : 3

40. What is the converse of the following assertion?

I stay only if you go

1. I stay if you go
2. If a stay then you go
3. If you do not go then i do not stay
4. If i do not stay then you go

Ans : 3

41.  The string 1101 does not belong to the set represented by

1. 110*(0+ 1)
2. 1( 0 + 1)*101
3. (10)*(01)*(00 + 11)*
4. (00 + (11)*0)*

Ans : 3

42.  Type checking is done during

1. Lexical analysis
2. Syntax analysis
3. Syntax directed  translation
4. Code optimization

Ans : 1

43.  There are  five records in a database

Name	Age	Occupation	category
Rama	27	con	A
Abdul	22	engg	A
Jeniffer	28	doctor	B
Maya	32	ser	D
Dev	24	Mus	C

There is an index file associated with this and it contains the values 1, 3, 2, 5, 4. Which one of the fields is the index built from?

1. Age
2. Name
3. Occupation
4. Category

Ans : 1

44.  Consider the following statements:

S1 : there exits infinite sets A, B, C such that  A^(B U C) is finite

S2 : there exists two irrational numbers x and y such that (x +y)     is rational.

Which of the following is true?

1. Only s1
2. Only s2
3. Both s1 and s2
4. None

Ans : 4

45.  Which of the following disk scheduling strategies is likely to give the best throughput?

1. Farthest cylinder next
2. Nearest cylinder next
3. FCFS
4. Elevator algorithm

Ans : 3

46. A sorting technique is called stable if

1. It takes O(nlog n) time
2. It maintains the relative order of occurrence of non-distinct elements
3. It uses divide and conquer paradigm
4. It takes O(n) space

Ans : 2

47.  Consider two well formed formulas in prepositional logic

F1 : P=> ~P

F2 : (P=> ~P) v (~P =>P)

Which of the following is correct?

1. F1 is satisfiable , F2 is valid
2. F1 unsatisfiable, F2 is satisfiable
3. F1 is unsatisfiable, F2 is valid
4. F1 and F2 are both satisfiable

Ans : 1

48. The following C declarations

struct node{

int i:

float j;

};

struct node *s[10];

define s to be

1.  An array, each element of which is a pointer to a structure of type node
2.  A structure of 2 fields, each field being a pointer to an array of 10 elements
3. A structure of 3 fields: an integer, a float, and an array of 10 elements
4. An array, each element of which is a structure of type node

Ans : 1

49. Given the following expression grammar:

E ->E * F | F + E | F

F ->F – | id

Which of the following is true?

1. *  has higher precedence than +
2.  – has has higher precedence than *
3. + and – have same precedence
4. + has higher precedence than *

Ans : 1

50. Where does the swap space reside?

1. RAM
2. DISK
3. ROM
4. On-chip cache

Ans : 2

51. Which of the following scheduling algorithms in non-preemptive?

1. Round robin
2. First in first out
3. Multilevel queue scheduling
4. Multilevel queue scheduling with feedback

Ans : 2

Q.52 – Q.55 is common data questions ( 1 mark each)

A computer has 256 KB , 4-way set associative, write back data cache with block size 64 bytes. The processor snds 64 bit addresses to the cache controller. Each cache tag directory contains, in addition to addresses tag, 2 valid bits , 1 modified bit and 1 replacement bit.

52.  The size of the cache tag directory is

1. 136 kbites
2. 64 kbits
3. 324Kbits
4. None

Ans : 3

53.  The number of bits in the tag field of an address is

1. 11
2. 16
3. 10
4. 12

Ans : 4

Suppose the letters a, b, c, d have probabilities ½, ¼, 1/8, 1/16 respectively.

54.   Which of the following is the Huffman code for the letters a, b, c, d, e, f?

1. 0,10,110,1110
2. 11, 10, 011, 010
3. 11, 10, 01, 001
4. 110, 100, 010, 000

Ans : 4

55.  What is the average length of the correct answer of Q.76?

1. 3
2. 2.25
3. 1.9
4. None

Ans :3

Q56 – Q65 carry 2 marks each

56.  In one of the most stunning reversals in the history of marketing, the Coca-cola company in July 1985 yielded to thousands of irate consumers demanding that it should bring back the original coke formula

1. Demanding that it should
2. Demanding to it
3. And their demand to
4. Who demanded it to

Ans : 1

57.   Synonym of lineal is

1. Splenic
2. Tolerant
3. Liasise
4. Mediate

Ans : 1

58.  Synonym of abacinate

1. Blind
2. Care
3. Wisdom
4. Deaf

Ans : 1

59. Antonym of aboulic

1. Unneurotic
2. Happiness
3. Addiction
4. None of the above

Ans : 1

60. I can drive 6miles in 1hour and 20 minutes. What’s my speed in mph?

1. 7
2. 4.5
3. 9
4. None

Ans : 2

61.  The fluid contained in the bucket can fill four large bottles or seven small bottles. A full large bottle is used to fill an empty small bottle. What fraction of the fluid is left over in the large bottle when the small one is full?

1. 2/7
2. 3/7
3. 4/7
4. 5/7

Ans : 2

62.  The mean of 50 observations was 36. It was found later that an observation 48 was wrongly taken as 23. The corrected new mean is

1. 35.2
2. 36.1
3. 36.5
4. 39.1

Ans : 3

63.  One man 3 woman and 4 boys can do a piece of work in 96 hours. 2 men,8 boys, can do it in 80 hours. 2men and 3 women can do it in 120 hours. 5men 12 boys can do it it

1. 4 days
2. 5 days
3. 6 days
4. 7 days

Ans : 1

64.  Three persons are walking from place A to B. Their speeds are in the ratio 4:3:5. The time to reach B by these persons will be in the ratio

1. 4:3:5
2. 5:3:4
3. 15:9:20
4. 15:20:12

Ans : 4

65.  The rate at which a sum becomes four times itself in 15 years at S.I. will be

1. 15%
2. 17 ½%
3. 20%
4. 25%

Ans : 3

gategate paper for computer scienceGate sample Papersample paper

« Sample paper for Biotechnology ICSE CLASS 10 ACCOUNTS SAMPLE PAPER »