Thursday, February 21, 2008

GATE Exam Papers - (Computer Science) - Part 8

Que. 1 A relation R is defined on the set of integers as x Ry if f(x + y) is
even. Which of the following statements is true?
A R is not an equivalence relation
B R is an equivalence relation having 1 equivalence class
C R is an equivalence relation having 2 equivalence classes
D R is an equivalence relation having 3 equivalence classes

Que. 2 Let a, b, c, d be propositions. Assume that the equivalences a<-> (b
V-b) and b<->c hold. Then the truth value of the formula (a Ù b) -J. (a
Ù c) Ù d) is always
A True
B False
C Same as the truth value of b
D Same as the truth value of d

Que. 3 Consider the following relations:
R1 (a, b) if f(a + b) is even over the set of integers
R2 (a, b) if f(a + b) is odd over the set of integers
R3 (a, b) if f a.b > 0 over the set of non-zero rational numbers
R4 (a, b) iff |a - b | Which of the following statements is correct?
A R1 and R2 are equivalence relations, R3 and R4 are not
B R1 and R3 are equivalence relations, R2 and R4 are not
C R1 and R4 are equivalence relations, R2 and R3 are not
D R1, R2, R3 and R4 are all equivalence relations

Que. 4 Seven (distinct) car accidents occurred in a week. What is the probability
that they all occurred on the same day?
A (1/7)^7
B (1/7)^6
C (1/2)^7
D (7/2)^7

Que. 5 In the interval {0, (pi)} the equation x=cosx has
A no solution
B exactly one solution
C exactly two solution
D an infinite number of solution

Que. 6 In a room containing 28 people,there are 18 peoples who speaks english,15
people who speak hindi and 22 people who speak kannada.9 persons speak
both english and hindi,11 persons speak both hindi and kannada.Where as
13 persons speak both english and kannada.how many people speak all the
three languages?
A 9
B 8
C 7
D 6

Que. 7 Given the following relation instance X Y Z 1 4 2
1 5 3 1 6 3 3 2 2 Which of the following
functional dependencies are satisfied by the instance?
A XY->Z and Z ->Y
B YZ->X and Y->Z
C YZ->X and X->Z
D XZ->Y and Y->X

Que. 8 Let f(n) = (n^2)1 g n and g(n) = n (1 g n)^10 be two positive functions
of n. Which of the following statements is correct ?
A f(n) = O(g(n) and g(n)!= O(f(n))
B g(n) = O(f(n) and f(n) != O(g(n))
C f(n) != O(g(n)) and g(n) != O(f(n))
D f(n) = O(g(n)) and g(n) = O(f(n))

Que. 9 The proposition P^(~pvq) is
A A tautology
B logically equivalent to p^q
C logically equivalent to pvq
D A contradiction

Que. 10 Let A and B be real symmetric matrices of size n*n.Then which one of the
following is true?
A A(A^t)=1
B A=(A^-1)
C AB=BA
D (AB)^t=BA

Que. 11 The number of distinct simple graph with upto three nodes is
A 15
B 10
C 7
D 9

Que. 12 The Newton-Raphson method is used to find the root of the equation x^2-2=0.
if the iteration are started from -1,the iteration will
A converage to -1
B converage to [(sqrt)2]
C converage to -[(sqrt)2]
D not converage

Que. 13 What is the converse ofthe following assertion? I stay only
if you go
A I stay if you go
B if I stay then you go
C if you do not go then i donot stay
D if i do not stay then you go

Que. 14 In a room containing 28 people,there are 18 peoples who speak english,15
people who speak hindiand 22 people who speak kannada.9 persons speak
both english and hindi 11 persons speak both hindi and kannads whereas
13 persons speak both kannada and english.how many people speak all therr
languages?
A 9
B 8
C 7
D 6

Que. 15 Let L be the set of all binary strings whoes last two symbols are same.the
number of states in the minimum state determinimstc finite 0 state automaton
accepting L is
A 2
B 5
C 8
D 3

Que. 16 Which oneof the following operations is commutative but not associative?
A AND
B OR
C NAND
D EXOR

Que. 17 What is the maximum value of the function f(x)=2(x^2) -2x +6 in the interval
[0,2]?
A 6
B 10
C 12
D 5.5

Que. 18 The function
f(x,y)=(x^2)y-3xy+2y+x has
A no local extremun
B one local minimum but no local maximum
C one local maximum but no local minimum
D one local minimum and one local maximum

Que. 19 Let L be a set with a relation R which istransitive,anti
symmetric and reflexive and for any two elements a, b Î L let the
least upper bound lub (a, b) and the greatest lower bound glb
(a, b) exist. Which of the following is/are true?
A L is a poset
B L is a boolean algebra
C L is a lattice
D None of the above

Que. 20 The number of binary strings of n zeros and k ones that no two
ones are adjacent is
A n-1 C k
B n C k
C n C k+l
D None of the above


Que. 21 A polynomial p(x) satisfies the following: p (1) = p(3) = p(5) = 1
p(2) = p(4) = -1 The minimum degree of such a polynomial is
A 1
B 2
C 3
D 4

Que. 22 Suppose the adjacency relation of vertices in a graph is represented
in a table Adj(X, Y). Which of the following queries cannot be expressed
by a relational algebra expression of constant length?
A List all vertices adjacent to a given vertex
B List all vertices which have self loops
C List all vertices which belong to cycles of less than three vertices
D List all vertices reachable from a given vertex

Que. 23 Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. Then the relational algebra expression s A=a (r |X| s) is always equal to
A s A=a (r)
B r
C s A=a (r) |X| s
D none of the above

Que. 24 Let f : A->B be a function, and let E and F be subsets of A. Consider
the following statements about images. S1 :f (E(union)F)=f (E)(union)
f (F) S2 :f (E (intersection) F)=f(E)(intersection)f (F) Which of the
following is true about S1 and S2 ?
A Only S1 is correct
B Only S2 is correct
C Both S1 and S2 are correct
D None of S1 and S2 is correct

Que. 25 The proposition p <-> q means
A p if and only if q
B which is true if both p and q are true
C it is false when p is true and q is false
D all of the above

Que. 26 If A={a,b} then A+ is
A {a,b} (union) {{a,b}}
B {{a,b} (union) {a,b}}
C {a,b} (union) {a,b}}
D none of these

Que. 27 What is the number of ways to point 12 offices so that 3 of them will
be green,2 of them pink,2 of them yellow and the remaining onces white
A 166324
B 166328
C 166320
D 166322

Que. 28 The number of binary relations on a set with n elements is
A n^2
B 2^n
C 2^(n^2)
D none of these

Que. 29 Let A,B,C,D be n*n matrices,each with non-zero determinant.If ABCD=1 then
B^(-1) is
A D(-1)C(-1)A(-1)
B CDA
C ADC
D Does not necessarily exist

Que. 30 Given the following input (4322,1334,1471,1989,6171,6173,4199) ans the
following hash function x mod 10,which of the following statments 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
A (i) only
B (ii) only
C (i) and (ii) only
D (iii) or (iv)

Que. 31 In a group of 30 persons,a total of 16 take tea while 9 take tea but not
coffee. how many persons in this group take coffee but not tea?
A 27
B 20
C 25
D 11

Que. 32 The less than relation,<,on reals is
A A partical ordering since it is asymmetric and reflexive
B A partical ordering since it is antiymmetric and reflexive
C not a partical ordering it is not asymmetric and not reflexive
D not a partical ordering it is not asymmetric and reflexive
(E)none of these

Que. 33 The number of element in the power set P(S) of the set
S={(fi),1,(2,3)} is
A 2
B 4
C 8
D none of the above

Que. 34 The rank of the following (n+1)*(n+1) natrix,where a is a real number is
|1 a a^2... a^n|
|1 a a^2... a^n|
|. . . . |
|. . . . |
|. . . . |
|1 a a^2... a^n|
A 1
B 2
C n
D depend on the value of a

Que. 35 The determinant of the matrix
|6 -8 1 1|
|0 2 4 6|
|0 0 4 8|
|0 0 0 -1|
is
A 11
B -48
C 0
D -24

Que. 36 What is the maximum value of the function f(x)=2(x^2)-2x+6 in the interval
[0,2]?
A 6
B 10
C 12
D 5.5

Que. 37 The solution to the recurrence equation T(2^k)=3T[2^(k-1)]+1, T(1)=1,
is
A 2^k
B [3^(k+1)-1]/2
C [3^(log2 k)]
D [2^(log2 k)]

Que. 38 For X=4.0 the value of I in the FORTRAN 77 statment I=-2**2+5.0*X/X*3+3/4
is
A 11
B -11
C 22
D -22

Que. 39 A polynomial p(x) is such that p(0)=5, p(1)=4,P(2)=9 and p(3)=20.The minimum
degree it can have is
A 1
B 2
C 3
D 4

Que. 40 Let f(x,y,z)=x'+y'x+xz be a switching function.Which one of the following
is valid
A y'x is a prime implicant of f
B xz is a minterm of f
C xz is an implicant of f
D y is a prime implicant of f

GATE Exam Papers - (Computer Science) - Part 7

Que. 1 Comparing the time T1 taken for a single instruction on a pipelined CPU
with time T2 taken on a non pipelined but identical CPU, we can say that
A T1
B T1>=T2
C T1<>
D T1 is T2 plus the time taken for one instruction fetch cycle

Que. 2 Consider the values A = Ques0 x 10 30, B =-Ques0 x 10 30 , C= 1.0, and
the sequence X: =A+B Y: =A+C X: = X + C Y: =Y+B executed on a computer
where floating-point numbers are represented with 32 bits. The values
for X and Y will be
A X = 1.0, Y =1.0
B X = 1.0, Y = 0.0
C X = 0.0, Y = 1.0
D X = 0.0, Y = 0.0

Que. 3 What is the scope of m declared in the main program?
A PARAM,P,Q
B PARAM,P
C PARAM,Q
D P,Q
(E)none of htese

Que. 4 Where does the swap space reside ?
A RAM
B Disk
C ROM
D On-chip cache

Que. 5 Trap is which type of interrupt
A synchronous
B Asynchronous
C Hardware
D software

Que. 6 Assume that each charecter code consist of 8-bits.The number of charecters
that can be transmitted per sec. through an asynchronous serial line
at 2400 band rate,and with two stop bits,is
A 109
B 216
C 218
D 219
(E)240

Que. 7 The value of n,output by the program PARAM is:
A 0,because n is a actual perameter that corresponds to x in procedure
Q.
B 0,because n is a actual perameter to y in procedure Q.
C 1,because n is a actual perameter corresponding to x in procedure Q.
D 1,because n is a actual perameter corresponding to y in procedure
Q. (E)none of these

Que. 8 A CPU has two modes - privileged and non-privileged. In order to change
the mode from privileged to non-privileged
A a hardware interrupt is needed
B a software interrupt is needed
C a privileged instruction (which does not generate an interrupt) is needed
D a non-privileged instruction (which does not generate an interrupt) is
needed

Que. 9 The main advantage of interrupt concept is elimination of
A spooling
B pooling
C job scheduling
D blocking the currently running process

Que. 10 Which is non vector interrupt?
A INTR
B TRAP
C RST 6.5
D RST 7.5

Que. 11 Which is the most appropriate match for the items in the first column
with the items in the second column ? X Indirect Addressing I. Array
implementation Y Indexed Addressing II. Writing relocatable code Z.
Base Register Addressing III. Passing array as parameter
A (X. III), (Y, I), (Z, II)
B (X, II), (Y, III), (Z, I)
C (X, III), (Y, II), (Z, I)
D (x, I), (Y, III), (Z, II)

Que. 12 The performance of a pipelined processor suffers if
A the pipeline stages have different delays
B consecutive instructions are dependent on each other
C the pipeline stages share hardware resources
D all of the above

Que. 13 The minimum number of page frames that must be allocated to a running
process in a virtual memory environment is determined by
A the instruction set architecture
B page size
C physical memory size
D number of processes in memory

Que. 14 A certain processor supports only the immediate and the direct addressing
mods.Which of the following programming language features cannot be implemented
on this processor?
A pointers
B array
C records
D all of these

Que. 15 Ques Let m [0]….m [4] be mutexes (binary semaphores) and P [0] ... P [4]
be processes. Suppose each process P[i] executes the following : wait
(m [i]); wait (m [(i + 1) mode 4]); …….. release (m [i]) ; release (m[(i
+ 1) mod 4 ] ); This could cause
A Thrashing
B Deadlock
C Starvation, but not deadlock
D None of the above

Que. 16 A single instruction of a clear the lower four bits of the accumulator
in 8085 assembly language is?
A XIR OFH
B ANI FOH
C XIR FOH
D ANI OFH

Que. 17 Which of the following statment is true?
A ROM is read/write memory.
B PC points to the last instruction that was executed.
C stack works on the principle of LIFO
D All instructions affect the flags

Que. 18 In a page segemented scheme of memory management,the segment table
itself must have a page table because
A the segment table is often too large to fit in one page
B Each segment table is spread over a number of pages
C segment table points to page table and not to the physical
location of the segment
D none of these

Que. 19 I/O redirection
A implies changing the name of a file
B can be employed to use an existing file as input file for a program
C implies connection 2 programs through a pipe
D noneof the above

Que. 20 The sequence of two instructions that multiply the contents of the DE
resister pair by 2 and store the result in HL resister pair(in 8085 assembly
language) is
A XCHG and DAD B
B XTHL and DAD H
C PCHL and DAD D
D XCHG and DAD H


Que. 21 The address sequence generated by tracing a particular program executing
in a pure demand paging system with 100 records per page with 1 free
main memory fram is recorded as follows.What is the number of page
faults? 0100,0200,0430,0499,0510,0530,0560,0120,0220,0240,0260,0320,0370
A 13
B 7
C 8
D 10

Que. 22 A N-bit carry lookhaed adder,where N is a multiple of 4,employs IC's 74181
(4 bit ALU) and 74182(4 bit carry look ahead grnerator) the minimum
addition time using the best architecture for this adder is
A proportional to N
B proportional to log N
C constant
D none of the above

Que. 23 Dirty bit for a page in a page table
A helps avoid unnecessary writes on a paging device
B helps maintain LRU information
C allows only read on a page
D none of the above

Que. 24 Contents of A resister after the execution of the following 8085 microprocessor
program is MIV A,55H MIV C,25H ADDC DAA
A 7AH
B 80H
C 50H
D 22H

Que. 25 Each process Pi,i=1.......9 is coaded as follows
repeat
P(mutex)
{critical selection}
v(mutex)
forever
The code of P(10) is identical except that it uses v(mutex) in place of P(mutex).What is the largest
number of processes that can be inside the critical section at any moment
A 1
B 2
C 3
D none of the above

Que. 26 Let R = (a, b, c, d, e, f) be a relation scheme with the following dependencies c-->f, e-->a, ec-->d, a-->b. Which of the following is a key for R ?
A CD
B EC
C AE
D AC

Que. 27 A single instruction to clear the lower four bit of the accumulator in
8085 assembly language is
A XRI OF H
B A NI OH
C X RI FOH
D ANI OF H

Que. 28 Which of the following statment is true?
A ROM is read/write memory
B PC points to the last instruction that was executed
C Stack works on the principle of LIFO
D All instructions affect the flags.

Que. 29 Four 256*8 PROm chips are used to produce a total capacity of 1024*8 the
address bus lines are required are
A 4
B 8
C 10
D 16

Que. 30 Assume that each charecter code consist of8 bits.the number of characters
that can be transmitted per second thriugh an asynchronous serial line
at 2400 band rate and with two stop bit is
A 109
B 216
C 218
D 219

Que. 31 Virtual memory is
A simple to implement
B used on all majour commercial operating system
C useful when fast I/O devices are not available
D less efficient in utilization of memory

Que. 32 The primary quantity of a good working program in the earlier days of
software development in the 1950's and 1960's were
A maintainable
B Readable
C Fast
D On budget and within time

Que. 33 A multi-user, multi-processing operating system cannot be implemented
on hardware that does not support
A address translation
B DMA for the disk transfer
C At least two modes CPU execution
D all of these

Que. 34 Advantage of synchronous sequential circuits memory over asynchronous
once is
A faster operation
B ease to avoiding prblems due to hazards
C lower hardware requirment
D better noise immunity

Que. 35 The total size of address space in a virtual memory system is limited
by
A the length of MAR
B the available secindary storage
C the available main memory
D all of the above

Que. 36 A device employing INTR line for device interrupt puts the CALL instruction
on the data bus while
A INTA is active
B hold is active
C ready is active
D none of these

Que. 37 Which scheduling is not suffer to balady anomoly
A FCFC
B optimal page replacement
C LRU
D Round Robin

Que. 38 I/O vide rection
A implies changing the name of a file
B can be employed to use an existing files as input file for a program.
C implies connection 2 programs though a pipe.
D none of the above

Que. 39 Which of the following device should get higher priority in assigning
interrupts?
A hard disk
B printer
C keyboard
D floopy disk

Que. 40 The main difference between a CISC and RISC processor is/are that a RISC
prcessor typically
A has few ever instructions
B has fewever addressing modes
C has more registers
D all of these

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

GATE Exam Papers - (Computer Science) - Part 5

Que. 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 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