CS GATE 2009 - Online Test
Q1. Which of the following statement (s) is/are correct regarding Bellman-Ford shortest path algorithm?
P. Always find a negative weighted cycle, if one exists.
Q. Finds whether any negative weighted cycle is reachable from the source.
Answer : Option B
Explaination / Solution:
No Explaination.
Q2. Which one of the following languages over the alphabet {0, 1} is described by the regular expression:
(0 + 1)* 0 (0 + 1)* 0(0 + 1)*?
Answer : Option C
Explaination / Solution:
No Explaination.
Q3.
Consider the program below:
#include<stdio.h>
int fun (int n, int *fp)
{
int t, f;
if ( n<= 1)
{
*fp = 1;
return 1;
}
t = fun(n - 1, fp);
f = t+ * fp;
*fp = t;
return f;
}
int main( )
{
int x = 15;
printf (“%d\n”, fun (5, &x));
return 0;
}
The value printed is
Answer : Option B
Explaination / Solution:
No Explaination.
Q4. Consider a 4 stage pipeline processor.
The number of cycle needed by the four
instructions I1,I2,I3,I4 in stages S1, S2,
S3, S4 is shown below:
What is the number of cycles needed to execute the following loop?
for (i=1 to 2) {I1; I2; I3; I4 ;}
Answer : Option B
Explaination / Solution:
No Explaination.
Q5. The essential content(s) in each entry of a page table is/are
Answer : Option B
Explaination / Solution:
No Explaination.
Q6. Which one of the following is FALSE?
Answer : Option D
Explaination / Solution:
No Explaination.
Q7. A multilevel page table is preferred in comparison to a single level page table for translating virtual
address to physical address because
Answer : Option B
Explaination / Solution:
No Explaination.
Q8. The running time of an algorithm is represented by the following recurrence relation:
Which one of the following represents the time complexity of the algorithm?
Answer : Option A
Explaination / Solution:
No Explaination.
Q9. The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using
open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash
table?
Answer : Option C
Explaination / Solution:
No Explaination.
Q10. Let R and S be relational schemes such that R={a, b, c} and S={c}. Now consider the following queries
on the database:
Where R.c = S.c
Which of the above queries are equivalent?
Answer : Option C
Explaination / Solution:
No Explaination.
