some Qs from CS2004..
Printed From: One Stop GATE
Category: GATE Previous Years Test Papers - Discuss Here
Forum Name: CS Papers
Forum Discription: Computer Science Previous Year GATE Papers to can discussed here.
URL: http://forum.onestopgate.com/forum_posts.asp?TID=121
Printed Date: 06Feb2025 at 7:53pm
Topic: some Qs from CS2004..
Posted By: Adhiti
Subject: some Qs from CS2004..
Date Posted: 02Feb2007 at 11:36am
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)
|
Replies:
Posted By: Alok
Date Posted: 02Feb2007 at 3:56pm
Q.28
A. 9.71 and 10.0
Q.43
D. height of the tree
Q.54
A.0.5
bcoz i think previous transmission does not change the probability of
next transmission(if algorithm was given like transimission decrease
the priority of station, ans would have been different.)
Q.59
A. a'c and ac' are prime implicant
Q.82
i am not sure but ans may be
Q.74
A.expected value will be 0.
Q.82 i am not sure but ans may be
D. O(n) bcoz
| Quote: |
we are passing couter to f().
counter will be constant number at every call to f(counter) like f(12),f(1) etc. so it will take time of O(constant).
loop is iterated n times.
so time complexity would be O(n*constant)=O(n)
|
Q.85
A.theta(n)
| Quote: |
do postorder travarsal on the tree it will traverse first children then root so computaion of g(x) will be directly.
postorder takes theta(n) time
|
Expecting corrections if i am wrong anywhere
|
|