One Stop GATE Forum: some Qs from CS2004..

Message

   28. What is the result of evaluating the folowing two expressions using three-digit 

floating point arithmetic with rounding ? 

(113.+ -111 ). + 7.51

113.+ (-111.+7.5 )

(a) 9.51 and 10.0 respectively (b) 10.0 and 9.51 respectively 

(c) 9.51 and 9.51 respectively (d) 10.0 and 10.0 respectively 

43. Consider the folowingC program segment 

 	  Quote: 	
		  struct CelNode

{ 

  struct CelNode *leftChild; 

  int element; 

  struct CelNode *rightChild; 

}; 

 int Dosomething(struct CelNode *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 DoSomethingwhen a pointer tothe root of a 

non-empty tree ispassed asargument is 

(a) The number of leaf nodesin the tree 

(b) The number of nodesin the tree 

(c) The number of internal nodesin the tree 

(d) The height of the tree 

54. 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, colide, and A wins 

the first backoff race. At the end of this successful transmission by A, both A and 

B attempt to transmit and colide. The probability that A wins the second backoff 

race is 

(a) 0.5  (b) 0.625 (c) 0.75 (d) 1.0 

think ans is (a) 0.5

correct/comment !

59. Which are the essential prime implicants of the folowing Boolean function? 

f(a,b,c)= a'c + ac' + b'c

(a) a'c and ac' 

(b) a'c and b'c

(c) a'c only 

(d) ac' and bc'

74. An examination paper has 150 multiple choice questions of one mark each, with

each question having four choices. Each incorect answer fetches -0.25 marks. 

Suppose  1000  students choose  all  their  answers randomly  with uniform 

probability. The sum total of the expected marks obtained by all these studentsis

(a) 0  (b) 2550 (c) 7525 (d) 9375 

75. Mala has a colouring book in which each English letter is drawn two times. She 

wants to paint eachof these 52 prints with one of k colours, such that he colour 

pairs used to colour any two letters are different. Both prints of a letter can also

be coloured with the same colour. What is the minimum value of k that satisfies

this requirement ? 

(a) 9  (b) 8 (c) 7 (d) 6 

82. Let A[1,…,n] be an aray storing a bit (1 or 0) at each location, and f(m) is a 

function whose time complexity is O(m). Consider the folowing program fragment written in a C 

like language: 

 	  Quote: 	
		  counter =0; 

  for (i =1; i <=n; i++) 

  {

   if (a ==1) 

	counter++; 

   else 

   {

	f (counter); counter =0;

   } 

  } 

The complexity of thisprogram fragment is

(a) Omega(n^2) 

(b) Omega(nlogn)  and O(n^2) 

(c) Theta(n)    

(d) o(n) 

85. A program takes as input a balanced binary search tree with n leaf nodes and 

computes the value of a function g(x) for each node x. If the cost of computing

g(x) is min(number of leaf-nodes in left-subtree of x, number of leaf-nodes in 

right-subtree of x) then the worst-case time complexity of the program is

(a) theta(n)

(b) theta(nlogn)

(c) theta(n^2)

(d) theta(n^2 logn)


One Stop GATE Forum : GATE Previous Years Test Papers - Discuss Here : CS Papers