Thursday, February 21, 2008

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
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
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
D The height of a B* tree is independent of the number of

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;
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) {
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

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
D none of the above

Que. 31 What is the name of O.S. system for the laptop computer called Maclite?
A Windows

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

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

No comments: