GATE Computer Science Solved Session I 2016 - Part 2

11.       Consider the following directed graph:
The number of different topological orderings of the vertices of the graph is ..........
Answer: 6
Following are the six different topological orderings.
12.       Consider the following C program.
void f(int, short);
void main()
int i = 100;
short s = 12;
short *p = &s;
................ ;   // call to f()
Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
(A) f(s, *s)          (B) i = f(i, s)
(C) f(i, *s)           (D) f(i, *p)
Answer: D
Option (A) is wrong because we are passing *s as second argument, but s is not a pointer variable.
Option (B) is wrong because we are trying to store the value of function f(i,s) to i, but look at the function definition, it is void, it has no return type.
Option (C) is wrong because of the same reason why option (A) is wrong.
13.       The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
(A) Θ(n log n), Θ(n log n), and Θ(n2)
(B) Θ(n2), Θ(n2), and Θ(n Log n)
(C) Θ(n2), Θ(n log n), and Θ(n log n)
(D) Θ(n2), Θ(n log n), and Θ(n2)
Answer: D
14.       Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
(A) P only                      (B) Q only
(C) Neither P nor Q     (D) Both P and Q
Answer: A
15.       Consider the following C program.
void mystery(int *ptra, int *ptrb)
   int *temp;
   temp = ptrb;
   ptrb = ptra;
   ptra = temp;
int main()
    int a=2016, b=0, c=4, d=42;
    mystery(&a, &b);
    if (a < c)
       mystery(&c, &a);
    mystery(&a, &d);
    printf("%d\n", a);
The output of the program ...............
Answer: 2016
In this program the function swaps the pointers only, not the values in the pointers. So the printf function will print the original value of a, which is 2016.
If we use the below function, then it will swap the values.
void mystery(int *ptra, int *ptrb)
int temp = *ptrb;
*ptrb = *ptra;
*ptra = temp;

16.       Which of the following languages is generated by the given grammar?
S → aS|bS|ε
Answer: D
17.       Which of the following decision problems are undecidable ?
(A) I and IV only           (B) II and III only
(C) III and IV only         (D) II and IV only
Answer: C
18.       Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
(A) (0+1)*0011(0+1)*+(0+1)*1100(0+1)*
(B) (0+1)*(00(0+1)*11+11(0+1)*00)(0+1)*
(C) (0+1)*00(0+1)*+(0+1)*11(0+1)*
(D) 00(0+1)*11+11(0+1)*00
Answer: B
(B) is the correct option which covers all possible cases.
Set of all binary strings having two consecutive 0s and two consecutive 1s
Anything 00 Anything 11 Anything + Anything 11 Anything 00 Anything
After taking common term outside, (0+1)*(00(0+1)*11+11(0+1)*00)(0+1)*
(A) represents strings which either have 0011 or 1100 as substring.
(C) represents strings which either have 00 or 11 as substring.
(D) represents strings which start with 11 and end with 00 or start with 00 and end with 11
19.       Consider the following code segment.
x = u - t;
y = x * v;
x = y + w;
y = t - z;
y = x * y;
The minimum number of total variables required to convert the above code segment to static single assignment form is ................
Answer: 10
In compiler design, Static Single Assignment form (SSA) is a property of an intermediate representation, which requires that each variable is assigned exactly once, and every variable is defined before it is used.
In the given code segment, there are two assignments of the variable x and three assignments of the variable y. So we use variables x1, x2 for specifying distinct assignments of x and y1, y2 and y3 for assignment of y. So, total number of variables is 10 (x1,x2,y1,y2,y3,t,u,v,w,z).
Static Single Assignment form (SSA) of the given code segment is:
20.    Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?
(A) Shortest remaining time first
(B) Round-robin with time quantum less than the shortest CPU burst
(C) Uniform random
(D) Highest priority first with priority proportional to CPU burst length
Answer: A

Pages   2   3   4   5 

Post a Comment