# GATE Computer Science Solved Session I 2016 - Part 4

31.       The size of the data count register of a DMA controller is 16 bits. The processor needs to transfer a file of 29,154 kilobytes from disk to main memory. The memory is byte addressable. The minimum number of times the DMA controller needs to get the control of the system bus from the processor to transfer the file from the disk to main memory is ....................
Explanation:
Data count register gives the number of words the DMA can transfer in a single cycle. Here it is 16 bits.
Data that can be transferred in one go = 216 bytes = 64 kilobytes (in one cycle)
Given file size = 29154 kilobytes
So, the required answer is, ceil(29154/64) = 456
32.       The stage delays in a 4-stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage (with delay 800 picoseconds) is replaced with a functionally equivalent design involving two stages with respective delays 600 and 350 picoseconds. The throughput increase of the pipeline is ................ percent.
Explanation:
Throughput of 1st case T1 = 1/max delay =1/800
Throughput of 2nd case T2 = 1/max delay= 1/600
The throughput increase of the pipeline    = (T2-T1)/T1
= ( (1/600) - (1/800) ) / (1/800) * 100
= 33.33%
33.       Consider a carry lookahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is:
(A) Θ(1)
(B) Θ(Log (n))
(C) Θ(√ n)
(D) Θ(n)
Explanation:
34.       The following function computes the maximum value contained in an integer array p[] of size n (n >= 1)
int max(int *p, int n) {
int a=0, b=n-1;
while (...............) {
if (p[a] <= p[b]) { a = a+1; }
else { b = b-1; }
}
return p[a];
}
The missing loop condition is
(A) a != n
(B) b != 0
(C) b > (a + 1)
(D) b != a
35.       What will be the output of the following C program?
void count(int n) {
static int d = 1;
printf("%d ", n);
printf("%d ", d);
d++;
if(n>1) count(n-1);
printf("%d ", d);
}
void main() {
count(3);
}
(A) 3 1 2 2 1 3 4 4 4
(B) 3 1 2 1 1 1 2 2 2
(C) 3 1 2 2 1 3 4
(D) 3 1 2 1 1 1 2

36.       What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed?
a=3;
void n(x) {x = x * a; print(x);}
void m(y) {a = 1; a = y - a; n(a); print(a);}
void main() {m(a);}
(A) 6, 2               (B) 6, 6
(C) 4, 2               (D) 4, 4
37.       An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
(A) O(1)
(B) O(d) but not O(1)
(C) O(2d) but not O(d)
(D) O(d2d) but not O(2d)
38.       Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry Wij in the matrix W.
The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is .................
39.       Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is ..................
40.    G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
(A) I only
(B) II only
(C) both I and II
(D) neither I nor II