GATE Exam Papers - (Computer Science) - Part 1

More than one answer can be correct.

Que. 1 Context-free languages are closed under:
A Union , intersection
B Union , Kleene closure
C Intersection, complement
D Complement, Kleene Closure

Que. 2 Let L p be the set of all languages accepted by a PDA by final
state and L E the set of all languages accepted by empty stack.
Which of the following is true?
A L D = L E
B L D É L E
C L D = L E
D None of the above

Que. 3 A grammar that is both left and right recursive for anonterminal,
is
A Ambiguous
B Unambiguous
C Information is not sufficient to decide whether it is ambiguous or
(D)None of the above
D (C)Information is not sufficient to decide whether it is ambiguous or
None of the above

Que. 4 Let S and T be languages over S = {a, b} represented by the regular expressions (a + b *) * and (a + b) *, respectively. Which of the following is true?
A S Ì T
B T Ì S
C S = T
D S Ç T = f

Que. 5 Let L denotes the language generated by the grammar S->0S0/00.
Which of the following is true?
A L = 0 +
B L is regular but not 0 +
C L is context free but not regular
D L is not context free

Que. 6 Which of the following need not necessarily be saved on a context switch
between processes?
A General purpose registers
B Translation look aside buffer
C Program counter
D All of the above

Que. 7 Given an arbitrary non-deterministic finite automaton (NFA) with
N states, the maximum number of states in an equivalent minimized
DFA is at least
A N^2
B 2^N
C 2N
D N!

Que. 8 Which one of the following regular expression over {1,1} denotes the set of all strings not containing 100 as a substring?
A 0*(1+0)*
B 0*1010*
C 0*101
D 0*(10+1)*

Que. 9 Aliasing in the context of programming languages refers to
A multiple variables having the same memory location
B multiple variables having the same value
C multiple variables having the same identifier
D multiple uses of the same variable

Que. 10 Consider the following decision problems : (PI) Does a given finite
state machine accept a given string (P2) Does a given context free grammar
generate an infinite number of stings Which of the following statements
is true?
A Both (PI) and (P2) are decidable
B Neither (PI) nor (P2) are decidable
C Only (PI) is decidable
D Only (P2) is decidable

Que. 11 Given the following expression grammar:
E->E * F | F+E | F
F-> F-F | id
Which of the following is true?
A * has higher precedence than +
B - has higher precedence than *
C + and - have same precedence
D + has higher precedence than *

Que. 12 Consider the following two statements:
S1: {(O^2n) |n>/=1} is a regu1ar language
S2: {(O^m)(1^n)(O^m+n)|m>/=l and n>/=l} is a regu1ar language
Which of the following statements is correct?
A Only S1 is correct
B Only S2 is correct
C Both S1 and S2 are correct
D None of S1 andS2 is correct

Que. 13 Which of the following statements in true?
A If a language is context free it can always be accepted by a deterministic
push-down automaton
B The union of two context free languages is context free
C The intersection of two context free languages is context free
D The complement of a context free language is context free

Que. 14 Which of the following statements is false?
A An unambiguous grammar has same leftmost and rightmost derivation
B An LL(1) parser is a top-down parser
C LALR is more powerful than SLR
D An ambiguous grammar can never be LR(k) for any k

Que. 15 Consider the following languages:
L1={w w l w (belongs) to) {a,b}*}
L2={ww^R | w (belongs) {a, b}*, w R is the reverse of w}
L3 = { 0^2i | i is an integer}
L4 = {[(O)^i]^2| i is an integer}
Which of the languages are regular?
A Only L1 and L2
B Only L2, L3, and L4
C Only L3 and L4
D Only L3

Que. 16 Context free language are closed under
A union, intesection
B union,kleene closure
C intesection,complement
D complement,kleene closure

Que. 17 Context free languages are
A closed under union
B closed under complementation
C closed under intersection
D all of the above

Que. 18 Which one is equivalent (i) (00)*(e+0) (ii) (00)* (iii) 0* (iv)
0(00)*
A (i) and (ii)
B (ii) and (iii)
C (i) and (iii)
D (iii) and (iv)

Que. 19 Type O grammer is
A (C)both and (b) above
B (C)both (a) and above
C both (a) and (b) above
D none of these

Que. 20 Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?
A 8
B 14
C 15
D 48


Que. 21 The language L={(a^k)(b^k) | k>or= 1} is
A type 3 grammer
B type 2 grammer
C type 1 grammer
D type 0 grammer

Que. 22 Recursive languages are
A a proper superset of context free languages
B always recognizable by pushdown automata
C also called type zero lanugages
D all of these

Que. 23 A grammer that is both left and right recursive for a nopn-terminal is
A ambiguous
B unambiguous
C information is not sufficient to decide whether it is ambiguous or
unambiguous
D none of the above

Que. 24 For what values of n is 10*n*log2 (n) >2*(n^2)?
A only n>/= 32
B only 0
C only 20
D only n>/=0

Que. 25 Let * be defined as x*y = x' + y.Let z = x * y .Value of z*x is
A x' + y
B x
C 0
D 1

Que. 26 Which of the following regular expressions over {0,1} denotes the set of all strings not containing
100 as a substring
A 0*(1+0)*
B 0*1010*
C 0*1*01*
D 0*(10+1)*

Que. 27 Which of the following grammer rules violate the requirements of an operator
grammer? P,Q,R are nonterminals and r,s,t are terminals. (i)
P -> Q R (ii) P -> QsR (iii) P -> e (iv)P
->Qtpr
A (i) only
B (i) and (iii) only
C (ii) and (iii) only
D (iii) and (iv) only

Que. 28 indicate which ofthe following statments are true Recursive language
are
A A proper superset of context free languages
B always recognizable by pushdown automata
C recognizable by turing machine
D also called type-0 languages

Que. 29 Which of the following is not decidable?
A Given a Turing machine M,a string s and an integer k,M accepts s
within k steps
B Equivalence of two given Turing machines
C Language Accepted by a given finite state machine is not empty
D language generated by a context free grammer is not empty

Que. 30 Regarding the power of recognition of languages,Which of the following
statments is false?
A the non-deterministic finite-state automata are equivalent to deterministic
finite state automata.
B non-deterministic push down automata are equivalent to deterministic
push down automata.
C non-deterministic Turing machines are equivalent to deterministic
to push down automata.
D non-deterministic Turing machines are equivalent to deterministic
Turing machines

Que. 31 The string 1101 does not belong to the set represented by
A 110*(0+1)
B 1(0+1)*101
C (10)*(01)*(00+11)*
D (00+(11)*0)*

Que. 32 The following grammer S->bS S->b S->aA A->bA A->aB B->bB B->aS
B->a is
A type 3 grammer
B type 2 grammer
C type 1 grammer
D type 0 grammer

Que. 33 A language accepted by a pushdown Automaton in which the stack is limited
to 10 items is best described as
A Context free
B Regular
C Deterministic Context free
D Recursive

Que. 34 Aliasing in the context of programming languages refers to
A multiple variables having the same memory location
B multiple variables having the same value
C multiple variables having the same identifier
D multiple uses of the same variable

Que. 35 If L1 is context free language and L2 is aregular language which ofthe
followingi/are false
A L1-L2 is not context free
B L1 (intersection) L2 is context free
C ~L2 is context free
D ~L1 isregular

Que. 36 consider the following regular expression :
R=(ab|abb)*bbab
Which of the following strings is NOT in the set denoted by R?
A ababab
B abbbab
C abbabbbab
D ababbabbbab

Que. 37 The following grammar S->bS S->b S->aA A->bA is
A type-3 grammer
B type-2 grammer
C type-1 grammer
D type-0 grammer

Que. 38 The smallest finite aitomaton which accepts the language {x|length of x is divisible by 3} has
A 2 states
B 3 states
C 4 states
D 5 states

Que. 39 The following production A -> ab A -> aA aAb ->
aBCb is
A type-3 grammer
B type-2 grammer
C type-1 grammer
D type-0 grammer

Que. 40 Which of the following statment is false>
A every finite subset of an non-regular set is regular
B every subset of a regular set is regular
C every finite subset of an regular set is regular
D The intersection of two regular set is regular

GATE Exam Papers - (Computer Science) - Part 2

1 Consider the following program segment for a hypothetical CPU having three user registers Rl, R2 and R3.

Instruction Operation Instruction Size (in words)
MOV Rl,5000 ; Rl ¬ Memory[5000] 2
MOV R2,(R1) ; R2 ¬ Memory[(Rl)] 1
ADD R2,R3 ; R2 ¬ R2 + R3 1
MOV 6000, R2 ; Memory[6000] ¬ R2 2
HALT ; Machine halts 1


Let the clock cycles required for various operations be as follows:
Register to/from memory transfer : 3 clock cycles
ADD with both operands in register : 1 clock cycle
Instruction fetch and decode : 2 clock cycles per word
The total number of clock cycles required to execute the program is


Options A) 29 B) 24 C) 23 D) 20

Correct Answer B

2 The order of an internal node in a B+ tree index is the maximum number of children it can have. Suppose that a child pointer takes 6 bytes, the search field value takes 14 bytes, and the block size is 512 bytes. What is the order of the internal node?
Options A) 24 B) 25 C) 26 D) 27

Correct Answer C

3 The Boolean function x, y, + xy + x, y

Options A) x, + y, B) x + y

C) x + y, D) x, + y

Correct Answer D

4 In an MxN matrix such that all non-zero entries are covered in a rows and b columns. Then the maximum number of non-zero entries, such that no two are on the same row or column, is

Options A) £ a + b B) £ max {a, b}

C) £ min {M-a, N-b} D) £ min {a, b}


Correct Answer A

5 The relation scheme Student Performance (name, courseNo, rollNo, grade) has the following functional dependencies:
name, courseNo ® grade
rollNo, courseNo ® grade
name ® rollNo
rollNo ® name
The highest normal form of this relation scheme is
Correct Answer A

6 The minimum number of page frames that must be allocated to a running process in a virtual memory environment is determined by
Options A) the instruction set architecture B) page size

C) physical memory size D) number of processes in memory

Correct Answer D

7 Consider the following program segment for a hypothetical CPU having three user registers Rl, R2 and R3.

Instruction Operation Instruction Size (in words)
MOV Rl,5000 ; Rl ¬ Memory[5000] 2
MOV R2,(R1) ; R2 ¬ Memory[(Rl)] 1
ADD R2,R3 ; R2 ¬ R2 + R3 1
MOV 6000, R2 ; Memory[6000] ¬ R2 2
HALT ; Machine halts 1


Consider that the memory is byte addressable with size 32 bits, and the program has been loaded starting from memory location 1000 (decimal). If an interrupt occurs while the CPU has been halted after executing the HALT instruction, the return address (in decimal) saved in the stack will be


Options A) 1007 B) 1020

C) 1024 D) 1028


Correct Answer A

8 Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
Options A) 12 B) 8
C) Less than 8 D) More than 12

Correct Answer A

9 What does the following algorithm approximate? (Assume m > 1, Î > 0).
x = m;
y-i;
while (x - y > Î)
{ x = (x + y) / 2 ;
y = m/x ;
}
print (x) ;
Options A) log m B)
m2



C) m1/2 D) m1/3

Correct Answer C

10 Consider the following C program
main ()
{ int x, y, m, n ;
scanf ("%d %d", &x, &y);
/ * Assume x > 0 and y > 0 * /
m = x; n = y ;
while ( m ! = n)
{ if (m > n)
m = m — n;
else
n = n - m ; }
printf("%d",n); }
The program computes
Options A) x + y, using repeated subtraction
B) x mod y using repeated subtraction
C) the greatest common divisor of x and y
D) the least common multiple of x and y

Correct Answer C

11 The best data structure to check whether an arithmetic expression has balanced parentheses is a
Options A) queue B) stack

C) tree D) list


Correct Answer B

12 A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8,5,3,2
Two new elements 1 and 7 are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is
Options A) 10,8,7,5,3,2,1 B) 10,8,7,2,3,1,5
C) 10,8,7,1,2,3,5 D) 10,8,7,3,2,1,5

Correct Answer D

13 Consider the following C program segment
struct CellNode {
struct CellNode *leftChild ;
int element;
struct CellNode *rightChild ;
};
int DoSomething (struct CellNode *ptr)
{
int value = 0 ; if (ptr ! = NULL)
{ if (ptr->leftChild ! = NULL)
value = 1 + DoSomething (ptr - > leftChild) ;
if (ptr - > rightChild ! = NULL)
value = max (value, 1 + DoSomething (ptr - > rightChild)) ;
}
return (value);
}

The value returned by the function DoSomething when a pointer to the root of a
non-empty tree is passed as argument is

Options A) The number of leaf nodes in the tree
B) The number of nodes in the tree
C) The number of internal nodes in the tree D) The height of the tree


Correct Answer D

14 An organization has a class B network and wishes to form subnets for 64 departments. The subnet mask would be
Options A) 255.255.0.0 B) 255.255.64.0

C) 255.255.128.0 D) 255.255.252.0

Correct Answer D

15 Suppose the round trip propagation delay for a 10 Mbps Ethernet having 48-bit jamming signal is 46.4 ms. The minimum frame size is:
Options A) 94 B) 416
C) 464 D) 512

Correct Answer C

16 Consider the following C program segment:

char p [ 20];

char * s = "string" ;

int length = strlen (s) ;

for (i = 0 ; i <>

p[ i ] = s [length - i] ;

print f ("%s", p) ;
The output of the program is

Correct Answer A

17 Consider the grammar
S ® (S) | a
Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good
Options A) n1< n1=" n3">
C) n1= n2 = n3 D) n1 ³ n3 ³ n2

Correct Answer B

18 Consider the following C function:
int f (int n)
{ static int i = 1;
if (n >= 5) return n;
n = n + i;
i ++;
return f (n);
}
The value returned by f(1) is

Options A) 5 B) 6
C) 7 D) 8

Correct Answer C

19 Consider the following code fragment:
if (fork ( ) = = 0)
{a = a + 5; print f (“%d, %d / n”, a, and a); }
else {a - 5; print f (“ %d, %d / n”, a,& a); }
Let u, v be the values printed by the parent process, and x, y be the values printed by the child process. Which one of the following is TRUE?
Options A) u = x + 10 and v = y B) u = x + 10 and v ¹ y
C) u + 10 =x and v = y D) u + 10 = x and v ¹ y

Correct Answer B

20 The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
Options A) 2 B) 3
C) 4 D) 6

Correct Answer B

GATE Exam Papers - (Computer Science) - Part 3

1 Consider the following C function
void swap (int a, int b)
{ int temp ;
temp = a ;
a = b ;
b = temp ;
}
In order to exchange the values of two variables x and y.
Options A) call swap (x, y)
B) call swap (&x, &y)

C) swap (x, y) cannot be used as it does not return any value D) swap (x, y) cannot be used as the parameters are passed by value


Your Answer (Not Answered)
Correct Answer B

2 A 5 stage pipelined CPU has the following sequence of stages:
IF - Instruction fetch from instruction memory,
RD - Instruction decode and register read,
EX - Execute: ALU operation for data and address computation,
MA - Data memory access - for write access, the register read at RD stage is used,
WB - Register write back.
Consider the following sequence of instructions:
I1 : L R0, 1oc1; R0 <= M[1oc1]
I2 : A R0, R0; R0 <= R0 + R0
I3: A R2, R0; R2 <= R2 - R0
Let each stage take one clock cycle.
What is the number of clock cycles taken to complete the above sequence of instructions starting from the fetch of I1?
Options A) 8 B) 10
C) 12 D) 15

Your Answer (Not Answered)
Correct Answer A

3 The address resolution protocol (ARP) is used for
Options A) Finding the IP address from the DNS B) Finding the IP address of the default gateway
C) Finding the IP address that corresponds to a MAC address D) Finding the MAC address that corresponds to an IP address

Your Answer (Not Answered)
Correct Answer D

4 Consider the following relation schema pertaining to a students database:
Student (rollno, name, address)
Enroll (rollno, courseno, coursename)
where the primary keys are shown underlined. The number of tuples in the Student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where ‘*’denotes natural join?
Options A) 8, 8 B) 120, 8

C) 960, 8 D) 960, 120


Your Answer (Not Answered)
Correct Answer C

5 Consider a direct mapped cache of size 32 KB with block size 32 bytes. The CPU generates 32 bit addresses. The number of bits needed for cache indexing and the number of tag bits are respectively
Options A) 10, 17 B) 10, 22
C) 15, 17 D) 5, 17

Your Answer (Not Answered)
Correct Answer A

6 Which one of the following is a key factor for preferring B+ -trees to binary search trees for indexing database relations?
Options A) Database relations have a large number of records B) Database relations are sorted on the primary key
C) B+ -trees require less memory than binary search trees D) Data transfer from disks is in blocks

Your Answer (Not Answered)
Correct Answer D

7 The goal of structured programming is to
Options A) have well indented programs B) be able to infer the flow of control from the compiled code
C) be able to infer the flow of control from the program text D) avoid the use of GOTO statements

Your Answer (Not Answered)
Correct Answer C

8 The tightest lower bound on the number of comparisons, in the worst ease, for comparison-based sorting is of the order of
Options A) n B) n2
C) n log n D) n log2 n

Your Answer (Not Answered)
Correct Answer B

9 Consider the following two problems on undirected graphs
a: Given G(V, E), does G have an independent set of size |V| -4?
b: Given G(V, E), does G have an independent set of size 5?
Which one of the following is TRUE?
Options A) a is in P and b is NP-complete B) a is NP-complete and b is in P
C) Both a and b are NP-complete D) Both a and b are in P

Your Answer (Not Answered)
Correct Answer C

10 Consider the languages
L1 = {wwR | w Î{0, 1}*}
L2 = {w# wR | w Î{0, 1}*}, where # is a special symbol
L3 = {ww | w Î{0, 1}*}
Which one of the following is TRUE?
Options A) L1 is a deterministic CFL B) L2 is a deterministic CFL
C) L3 is a CFL, but not a deterministic CFL D) L3 is a deterministic CFL

Your Answer (Not Answered)
Correct Answer B

11 Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
Options A) 12 B) 8
C) Less than 8 D) More than 12

Your Answer (Not Answered)
Correct Answer A

12 A and B are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both A and B attempt to transmit a frame, collide, and A wins the first backoff race. At the end of this successful transmission by A, both A and B attempt to transmit and collide. The probability that A wins the second backoff race is
Options A) 0.5 B) 0.625

C) 0.75 D) 1.0


Your Answer (Not Answered)
Correct Answer A

13 Consider the grammar
E ® E + n | E x n | n
For a sentence n + n x n, the handles in the right-sentential form of the reduction are
Options A) n, E + n and E + n x n B) n, E + n and E + E x n
C) n, n + n and n + n x n D) n, E + n and E x n

Your Answer (Not Answered)
Correct Answer D

14 Consider the grammar with the following translation rules and E as the start symbol.
E ® E1 # T {E.value = E1.value * T.value }
| T {E.value = T.value }
T ® T1 & F { T.value = T1.value + F.value }
| F {T.value = F.value}
F ® num {F.value = num.value }
Compute E. value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4.
Options A) 200 B) 180
C) 160 D) 40

Your Answer (Not Answered)
Correct Answer C

15 Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?

Options A) 2 B) 30
C) 56 D) 256

Your Answer (Not Answered)
Correct Answer D

16 Which one of the following is true for a CPU having a single interrupt request line and a single interrrupt grant line?
Options A) Neither vectored interrupt nor multiple interrupting devices are possible. B) Vectored interrupts are not possible but multiple interrupting devices are possible.
C) Vectored interrupts and multiple interrupting devices are both possible. D) Vectored interrupt is possible but multiple interrupting devices are not possible.

Your Answer (Not Answered)
Correct Answer B

17 Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold : (A ® B, BC ® D, E ® C, D ® A). What are the candidate keys of R?
Options A) AE, BE B) AE, BE, DE
C) AEH, BEH, BCH D) AEH, BEH, DEH

Your Answer (Not Answered)
Correct Answer D

18 In a network of LANs connected by bridges, packets are sent from one LAN to another through intermediate bridges. Since more than one path may exist between two LANs, packets may have to be routed through multiple bridges.

Why is the spanning tree algorithm used for bridge-routing?

Options A) For shortest path routing between LANs B) For avoiding loops in the routing paths
C) For fault tolerance D) For minimizing collisions

Your Answer (Not Answered)
Correct Answer B

19 Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?
Options A) T(n) = O(n2 ) B) T(n) = q (n log n)
C) T(n) = W (n2) D) T(n) = O(n log n)

Your Answer (Not Answered)
Correct Answer B

20 Consider the following C program segment
struct CellNode {
struct CellNode *leftChild ;
int element;
struct CellNode *rightChild ;
};
int DoSomething (struct CellNode *ptr)
{
int value = 0 ; if (ptr ! = NULL)
{ if (ptr->leftChild ! = NULL)
value = 1 + DoSomething (ptr - > leftChild) ;
if (ptr - > rightChild ! = NULL)
value = max (value, 1 + DoSomething (ptr - > rightChild)) ;
}
return (value);
}

The value returned by the function DoSomething when a pointer to the root of a
non-empty tree is passed as argument is

Options A) The number of leaf nodes in the tree
B) The number of nodes in the tree
C) The number of internal nodes in the tree D) The height of the tree


Your Answer (Not Answered)
Correct Answer D

GATE Exam Papers - (Computer Science) - Part 4

1 What does the following algorithm approximate? (Assume m > 1, Î > 0).
x = m;
y-i;
while (x - y > Î)
{ x = (x + y) / 2 ;
y = m/x ;
}
print (x) ;
Options A) log m B)
m2



C) m1/2 D) m1/3

Your Answer (Not Answered)
Correct Answer C

2 The problems 3-SAT and 2-SAT are
Options A) both in P
B) both NP-complete

C) NP-complete and in P respectively D) undecidable and NP-complete respectively

Your Answer (Not Answered)
Correct Answer C

3 Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold : (A ® B, BC ® D, E ® C, D ® A). What are the candidate keys of R?
Options A) AE, BE B) AE, BE, DE
C) AEH, BEH, BCH D) AEH, BEH, DEH

Your Answer (Not Answered)
Correct Answer D

4 A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000,1 by 0001,..., 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit ³ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required?
Options A) 2 B) 3
C) 4 D) 5

Your Answer (Not Answered)
Correct Answer C

5 If 73x (in base-x number system) is equal to 54y (in base-y number system), the possible values of x and y are
Options A) 8, 16 B) 10, 12

C) 9, 13 D) 8, 11

Your Answer (Not Answered)
Correct Answer D

6 In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is
Options A) 4 B) 6
C) 7 D) 9

Your Answer (Not Answered)
Correct Answer D

7 Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = d1d2... dm.
int n, rev;
rev = 0;
while (n > 0) {
rev = rev * 10 + n % 10 ;
n = n/10;
}
The loop invariant condition at the end of the ith iteration is:
Options A) n = d1d2... dm-i and rev = dmdm-1….dm-i+1 B) n = dm-i+1...dm-1dm (or) rev = dm-i...d2d1
C) n ¹ rev D) n = d1d2...dm (or) rev = dm...d2d1


Your Answer (Not Answered)
Correct Answer A

8 Consider the following program segment for a hypothetical CPU having three user registers Rl, R2 and R3.

Instruction Operation Instruction Size (in words)
MOV Rl,5000 ; Rl ¬ Memory[5000] 2
MOV R2,(R1) ; R2 ¬ Memory[(Rl)] 1
ADD R2,R3 ; R2 ¬ R2 + R3 1
MOV 6000, R2 ; Memory[6000] ¬ R2 2
HALT ; Machine halts 1


Let the clock cycles required for various operations be as follows:
Register to/from memory transfer : 3 clock cycles
ADD with both operands in register : 1 clock cycle
Instruction fetch and decode : 2 clock cycles per word
The total number of clock cycles required to execute the program is


Options A) 29 B) 24
C) 23 D) 20

Your Answer (Not Answered)
Correct Answer B

9 Consider an operating system capable of loading and executing a single
sequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs ?
Options A) 50% B) 40%

C) 25% D) 0%


Your Answer (Not Answered)
Correct Answer D

10 Consider the following statements with respect to user-level threads and
kernel-supported threads
(i) Context switch is faster with kernel-supported threads
(ii) For user-level threads, a system call can block the entire process
(iii) Kernel-supported threads can be scheduled independently
(iv) User-level threads are transparent to the kernel
Which of the above statements are true?
Options A) (ii), (iii) and (iv) only B) (ii) and (iii) only

C) (i), and (iii) only D) (i) and (ii) only


Your Answer (Not Answered)
Correct Answer A

11 Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
Options A) P3 is decidable if P1 is reducible to P3 B) P3 is undecidable if P3 is reducible to P2

C) P3 is undecidable if P2 is reducible to P3
D) P3 is decidable if P3 is reducible to P2s complement

Your Answer (Not Answered)
Correct Answer A

12 Which one of the following are essential features of an object-oriented
programming language?

(i) Abstraction and encapsulation
(ii) Strictly-typedness
(iii) Type-safe property coupled with sub-type rule
(iv) Polymorphism in the presence of inheritance


Options A) (i) and (ii) only B) (i) and (iv) only
C) (i), (ii) and (iv) only D) (i), (iii) and (iv) only

Your Answer (Not Answered)
Correct Answer B

13 Consider the following relation schema pertaining to a students database:
Student (rollno, name, address)
Enroll (rollno, courseno, coursename)
where the primary keys are shown underlined. The number of tuples in the Student and Enroll tables are 120 and 8 respectively. What are the maximum and minimum number of tuples that can be present in (Student * Enroll), where ‘*’denotes natural join?
Options A) 8, 8 B) 120, 8

C) 960, 8 D) 960, 120


Your Answer (Not Answered)
Correct Answer C

14 Assume the following C variable declaration

int *A [10], B [10][10];

Of the following expressions

I A[2] II A [2] [3]

III B[l] IV B[2][3]

which will not give compile-time errors if used as left hand sides of assignment statements in a C program ?

Options A) I, II, and IV only B) II, III, and IV only
C) II and IV only D) IV only



Your Answer (Not Answered)
Correct Answer D

15 How many distinct binary search trees can be created out of 4 distinct keys?
Options A) 5 B) 14
C) 24 D) 42

Your Answer (Not Answered)
Correct Answer B

16 Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true ?
(i) 9679, 1989, 4199 hash to the same value
(ii) 1471, 6171 hash to the same value
(iii) All elements hash to the same value
(iv) Each element hashes to a different value
Options A) (i) only B) (ii) only

C) (i) and (ii) only D) (iii) or (iv)

Your Answer (Not Answered)
Correct Answer C

17 Packets of the same session may be routed through different paths in
Options A) TCP, but not UDP B) TCP and UDP

C) UDP, but not TCP D) Neither TCP, nor UDP


Your Answer (Not Answered)
Correct Answer B

18 The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
Options A) 2 B) 3
C) 4 D) 6

Your Answer (Not Answered)
Correct Answer B

19 Postorder traversal of a given binary search tree, T produces the following sequence of keys
10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29
Which one of the following sequences of keys can be the result of an inorder traversal of the tree T?
Options A) 9, 10, 15, 22, 23, 25, 27, 29, 40, 50, 60, 95 B) 9, 10, 15, 22, 40, 50, 60, 95, 23, 25, 27, 29
C) 29, 15, 9, 10, 25, 22, 23, 27, 40, 60, 50, 95
D) 95, 50, 60, 40, 27, 23, 22, 25, 10, 9, 15, 29

Your Answer (Not Answered)
Correct Answer A

20 Let f: B ® C and g: A ® B be two functions and let h = f o g. Given that h is an onto function. Which one of the following is TRUE?
Options A) f and g should both be onto functions. B) f should be onto but g need not be onto
C) g should be onto but f need not be onto D) both f and g need not be onto

Your Answer (Not Answered)
Correct Answer B

GATE Exam Papers - (Computer Science) - Part 5

ue. 1 Determinimg all possible decompositions of sequential machines requires...............
time in N,where N is the number of states.
A logarithmic
B linear
C N log(N)
D exponential

Que. 2 The following sequence of operations is performed on a stack
PUSH(10),PUSH(20),POP,PUSH(10)PUSH(20),POP,POP,POP,PUSH(20),POP
the sequence of values popped out is
A 20,10,20,10,20
B 20,20,10,10,20
C 10,20,20,10,20
D 20,20,10,20,10

Que. 3 A sorting technique is called stable if
A it takes 0 (n log n) time
B it maintains the relative order of occurrence of non-distinct
elements
C it uses divide and conquer paradigm
D it takes 0 (n) space.

Que. 4 Which of the following is correct?
A B-trees are for storing data on disk and B* trees are for
main memory.
B Range queries are faster on B* trees.
C B-trees are for primary indexes and B* trees are for secondary
indexes.
D The height of a B* tree is independent of the number of
records.

Que. 5 A certain processor supports only the immediate and the direct
addressing modes. Which of the following programming language features
cannot be implemented on this processor?
A Pointers
B Arrays
C Records
D Recursive procedures with local variable

Que. 6 The problems 3-SAT and 2-SAT are
A both P
B both NP
C NP complete and in P respectively
D undecidable and NP complete respectively

Que. 7 In SQL, relations can contain null values, and comparisons with null
values are treated as unknown. Suppose all comparisons with a null value
are treated as false. Which of the following pairs is not equivalent?
A x = 5 not (not (x = 5 ) )
B x= 5 x> 4 and x <>
C x (not equal) 5 not (x = 5)
D None of the above

Que. 8 consider the following C function:
int f(int n)
{
static int i=1;
if(n>=50) return n;
n=n+1;
i++;
return f(n);
}
The value returned by f(1) is
A 5
B 6
C 7
D 8

Que. 9 The time complexity of the following C function is
int recursive(int n) {
if(n==1)
return(1);
else
return(recursive (n-1)+recursive(n-1));
}
A O(n)
B O(n log n)
C O(n^2)
D O(2^n)

Que. 10 What does the following code do? var a,b:integer;
begin a:=a+b; b:=a-b; a:=a-b; end;
A exchangs a and b
B doubles a and stores in b
C doubles b and stores in a
D leaves a and b unchanged

Que. 11 In the index allocation scheme of block to file,the maximum possible size
ofthe file depends on
A the size ofthe blocks,and the size of the address of the blocks.
B the number of blocks used for the index, and the size of the block.
C the size of the blocks,the number of blocks used for the index,and
the size ofthe address ofthe blocks.
D none of these

Que. 12 indicate which ofthe following statments are true The number of rooted
binary trees with n nodes is,
A equal to number of ways of multiplying (n+1) matrices
B equal to number of ways of arrenging n out of 2n distinct elements
C equal to 1/(n+1)=(2n/2)
D equal to n!

Que. 13 What does the following code do? var a,b:integer begin a:=a+b;
b:=a-b; a:=a-b; end;
A exchanges a and b
B doubles a and store in b
C doubles b and store in a
D leaves a and b unchanged
(E)none of these

Que. 14 A part of the system software,which under all circumstances must reside
in the main memory,is
A text editor
B assembler
C linker
D loader
(E)none of these

Que. 15 Listed below are some operating system abstractions (in the left
column) and the hardware components (in the right column)?
A (d) -4, (B)-1, (C)-2, (D)-3
B (d) (A)-4, -1, (C)-2, (D)-3
C (d) (A)-4, (B)-1, -2, (D)-3
D (A)-4, (B)-1, (C)-2, -3

Que. 16 Which of the following disk scheduling strategies is likely to
give the best through put?
A Farthest cylinder next
B Nearest cylinder next
C First come first served
D Elevator algorithm

Que. 17 Let s be a sorted array of n integers. Let t (n) denote the time taken
for the most efficient algorithm to determine if there are two elements
with sum less than 1000 in s. Which of the following statements is true?
A t (n) is 0 (1)
B n
C n log 2 n
D t (n) = (n/2)

Que. 18 A top down parser generates
A right most derivation
B left most derivation
C right most derivation in reverse
D left most derivation in reverse

Que. 19 The root directory if a disk should be placed
A At a fixed address in the main memory
B At a fixed location on the disk
C anywhere on the disk
D At a fixed location on the system disk (E)anywhere on
the system disk

Que. 20 conisder a system having m resources of the same type.These resources
are shared by 3 processes A,B and C,which have peak demands of 3,4
and 6 respectively.For what value of m deadlock will not occure?
A 7
B 10
C 13
D 15


Que. 21 A linker is given object modules for a set of programs that wer compiled
separately.What information need not be included in an object module?
A Object code
B Relocation bits
C Names and locations of all external symbols defined in the
object module
D Absolute address of internal symbols

Que. 22 A binary tree T has a leaf nodes.The number of nodes of degree 2 in
T is
A log2 n
B n-1
C n
D 2^n

Que. 23 What is the value of A,B,C and D satisfy the following simultaneous
boolean equation A'+AB=0,AB=AC,AB+AC'+CD=C'D'
A A=1,B=0,C=0,D=1
B A=1,B=1,C=0,D=0
C A=1,B=0,C=1,D=1
D A=1,B=0,C=0,D=0

Que. 24 A binary search tree contains the value 1,2,3,4,5,6,7,8.The tree is traversed
in pre-order and the value are printed out.Which of the following
sequence is a valid output?
A 5 3 1 2 4 7 8 6
B 5 3 1 2 6 4 8 7
C 5 3 2 4 1 6 7 8
D 5 3 1 2 4 7 8 6

Que. 25 A computer has 6 Tape drivers,with n processes competing for them.Each
process may need two drivers.What is the maximum value of n for the system
to be deadlock free?
A 6
B 5
C 4
D 3

Que. 26 Banker's algorithm for resource allocation deals with
A deadlock preventation
B deadlock avoidance
C deadlock recvery
D mutual exclusion

Que. 27 Suppose the domain set of an attribute consists of signed four digit numbers.What
is the % of reduction in storage space of this attribute if it is stored
as an integer rather than in character form?
A 80%
B 20%
C 60%
D 40%

Que. 28 The function of the syntax phase is
A to recognize the major constructs of the language and to call the
appropriate action routine
B to build a literal table
C to build a uniform symbol table
D to parse the source program into the basic elements or tokens of the
language

Que. 29 Abstruct class used in
A Virtual function
B pure virtual function
C member function
D none of these

Que. 30 QUEL is the query language in the system
A ingers. QUEL based on the relation calculus
B Codsyl.QUEL
C SQL.QUEL
D none of the above

Que. 31 What is the name of O.S. system for the laptop computer called Maclite?
A Windows
B DOS
C MS-DOS
D OZ

Que. 32 Queues serve a major role in
A simulation of recursion
B simulation of motion of subatomic particle
C simulation of arbitary linked list
D simulation of limited resources allocation

Que. 33 The results returned by functions under value result and referance parameter
passing conventions
A Donor differ
B differ in presence of loops
C differ in all cases
D may differ in the presence of exceptions

Que. 34 Storage mapping is done by
A loader
B linker
C editor
D compiler

Que. 35 If n is a power of 2, then the minimum number of multiplications needed
to computer a^n is
A log2 n
B [(sqrt)n]
C n-1
D n

Que. 36 Which of the following is most powerful parsing method?
A LL(1)
B Canonical LR
C SLR
D LALR

Que. 37 How many comparisons are required to sort an array of length 5 if a straight
selection sort is used and the array is already sorted in the opposite order?
A 0
B 1
C 10
D 20

Que. 38 For marging two sorted lists of sizes m and n into a sorted list of size
m+n we require comparisons of
A O(m)
B O(n)
C O(m+n)
D O(log m + log n)

Que. 39 The parsing technique that avoides back traacking is
A top down parsing
B recursive descent parsing
C predictive parsing
D both b and c above

Que. 40 Let L be the set of binary strings whose last two symbols are same.The
number ofstates in the minimum state deterministic finite state automation
accepting L is
A 2
B 5
C 8
D 3

GATE Exam Papers - (Computer Science) - Part 6

Que. 1 in serial communication employing 8 data bits,a parity bit and 2 stop
bits, the minimum band rate required to sustain a transfer rate of 300
charecters per secound is
A 2400 band
B 19200 band
C 3300 band
D 1200 band

Que. 2 the ASCII code is for inforation interchange by a binary code for
A numbers only
B alphabets only
C alpha numerics and other common
D none of these

Que. 3 Traffic light on road are example of
A close loop system
B open loop system
C both open loop and close loop
D open loop but can be made close loop

Que. 4 how many address lines are needed to address each memory location in a
2048*4 memory chip?
A 10
B 11
C 8
D 12

Que. 5 which code is used in Baudot system?
A five unit
B seven unit
C morse
D ASCII

Que. 6 the advantage of the self correcting code is
A it is a weighted code
B it has even parity
C it is easy to decode electronically
D all of these

Que. 7 The number -34 is represented in Excess-3 BCD code is
A 1,1001 1000
B 0,1001 1001
C 1,0110 0011
D 0,0110 0111

Que. 8 which of the following is not a charecteristic of rise processor design?
A one instruction per cycle
B registor to registor operations only
C simple address modes
D registor to memory operations only

Que. 9 The octal representation of an integer is (342)8 if this were to be treated
as an eight bit integer in an 8085 based computer its decimal equivalent is
A 226
B -98
C 76
D -30

Que. 10 A storage medium with cannot support both direct access and sequential
access application is
A magnetic drup
B hard disk
C magnetic tape
D floopy drive

Que. 11 The majour disadvantage of magnetic tapes is
A cost
B unreliability of stored data
C slow data recording
D data is to be accessed sequentially

Que. 12 In time division multiplexing
A time is doubled betwen bits and byte
B time slicing at CPU level takes place
C total time available in the channel is divided between several
users and each users is alloted a time slice
D none of these

Que. 13 The number of full and half-adders required to add 16-bit numbers
is
A 8 half-adders, 8 full-adders
B 1 half-adder, 15 full-adders
C 16 half-adders, 0 full-adders
D 4 half-adders, 12 full-adders

Que. 14 The simultaneous equations on the Boolean variables x, y, z and w, x+y+z=l
xy =0 xz+w = l x+[(complement)z w] =0 have the following solution
for x, y, z and w, respectively.
A 0 1 0 0
B 1 1 0 1
C 1 0 1 1
D 1 0 0 0

Que. 15 The 2's complement representation of (-539) 10 in hexadecimal is
A ABE
(BDBC
B wx'y'+xy+xz
C DE5
D 9E7

Que. 16 How many gates are needed for 3-bit up counter using standard binary and
using T flip-flop?Assume unlimited fan-in
A 4
B 3
C 2
D 1

Que. 17 A boolean function x'y'+xy+x'y is equivalent to
A x'+y'
B x+y
C x+y'
D x'+y

Que. 18 In an SR latch by crossing coupling two NAND gates if both S and R inputs
are set to 0 then it will result in
A Q=0, Q'=1
B Q=1, Q'=0
C Q=1, Q'=1
D indeterminate state

Que. 19 In 2's complement addition overflow
A is flagged whenever there is carry from sign bit addition
B cannot occur when positive values added to the negative value
C is flagged whenever there is carry from sign bit solution
D none of the above

Que. 20 the minimum number of NAND gates required to implement the boolean function
A+AB+ABC=
A 0
B 1
C 4
D 7


Que. 21 an R-S latch is a
A combinatorial ckt
B synchronous sequential ckt
C 1-bit memory arrangement
D one clock delay element

Que. 22 Ques 25. in an 8085 microprocessor system the RST instruction will cause
an interrupt
A only if an interrupt service routine is not being executed
B only if a bit in the intreeupt mask is made 0
C only if interrupts have been enabled by an EI INSTRUCTION
D NONE OF THE ABOVE

Que. 23 the minimum number of two input NAND gate required to iomplement the boolean
function _ Z=ABC,ASSUME that A,Band C are available is
A 2
B 3
C 5
D 6

Que. 24 The threshold level for logic 1 in the TTL family is
A only voltage above 2.5V
B any voltage between 0.8V and 5.0V
C any voltage below 5.0V
D any voltage below V(cc) but above 2.8V

Que. 25 the binary fraction 0.0111 in decimal form is equal to
A 0.4375
B 0.6225
C 0.8325
D 0.1105

Que. 26 in order to add 1111+1101, we required
A one FA,one HA
B three FA
C three FA,one HA
D none of these

Que. 27 A system has a word length of 4-bits.If in this system -ve numbers are
represented by their Two's compliment,then the range of numbers that can
be represented by the word length is
A -8 to +8
B -7 to +7
C -16 to +16
D none of these

Que. 28 The decimal value 0.25
A is equivalent to binary value 0.1
B is equivalent to the binary value 0.01
C is equivalent to the binary value 0.00111
D cannot be represented precisely in binary

Que. 29 How many boolean functions of 3 variables are there?
A 16
B 64
C 256
D 512

Que. 30 The number of 1s in the binary representation of (3*4096+15*256+5*16+3)
are
A 8
B 9
C 10
D 12

Que. 31 The threshold level for logic 1 in the TTL family is
A any voltage above 2.5v
B any voltage between 0.8v and 5.0v
C any voltage below 5.0v
D any voltage below V(cc) but above 2.8v

Que. 32 In order to add 1111+1101, we required
A one FA,one HA
B three FA
C three FA,one HA
D none of these

Que. 33 The number of different boolean function of 4 variables are
A 2^16
B 16^2
C 4^2
D 16^4

Que. 34 A carry look ahead adder is frequently used for addition because, it
A is faster
B more accurate
C used fewer gates
D costs less

Que. 35 The 2's complement representation of the decimal value 15 is
A 1111
B 11111
C 111111
D 10001

Que. 36 Sign extension is a step in
A Floating point multiplication
B Signed 16 bit integer addition
C Arithmetic left shift
D Converting a signed integer from one size to another.

Que. 37 Zero has two representation in
A sign magnitude
B 1's complement
C 2's complement
D none of the above

Que. 38 how many address lines are needed to address each memory location in a
2048*4 memory chip?
A 10
B 11
C 8
D 12

Que. 39 which code is used in Baudot system?
A five unit
B seven unit
C morse
D ASCII

Que. 40 If a counter having 10FFs is initally at 0,what count will if hold after
2060 pulses.
A 000 000 1100
B 000 001 1100
C 000 001 1000
D 000 000 1110