GATE Computer Science Solved Paper 2017 Session I - Part 5

41.       Consider a database that has the relation schemas EMP(Empld, EinpName, Deptld), and DEPT(DeptName, DeptId). Note that the Deptld can he permitted to be NULL in the relation EMP.
Consider the following queries on the database expressed in tuple relational calculus.
Which of the above queries are safe?
(A) (I) and (II) only
(B) (I) and (III) only
(C) (II) and (III) only
(D) (I), (II) and (III)
Answer: D
42.       In a database system, unique timestamps are assigned to each transaction using Lamport’s logical clock. Let TS(T1) and TS(T2) be the timestamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2, has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database system assuming that a killed transaction is restarted with the same timestamp.

if TS(T2) < TS(T1) then
T1 is killed
else T2, waits.

Assume any transaction that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?
(A) The database system is both deadlock-free and starvation-free.
(B) The database system is deadlock-free, but not starvation-free.
(C) The database system is starvation-free, but not deadlock-free.
(D) The database system is neither deadlock-free nor starvation-free.
Answer: A
43.       Consider the following grammar:
stmt        -> if expr then expr else expr; stmt | ô
expr        -> term relop term | term
term        -> id | number
id            -> a | b | c |
number -> [0-9]
where relop is a relational operator (e.g., <,>, ...). ô refers to the empty statement, and if, then, else are terminals.
Consider a program P following the above grammar, containing ten if terminals. The number of control flow paths in P is ................ For example, the program

if e1 then e2 else e3

has 2 control flow paths. e1 -> e2 and e1 -> e3.
Answer: 1024.0
44.       In a RSA cryptosystem, a participant A uses two prime numbers p = 13 and q = 17 to generate her public and private keys. If the public key of A is 35, then the private key of A is ...............
Answer: 11.0
45.       The values of parameters for the Stop-and-Wait ARQ protocol are as given below:

Bit rate of the transmission channel = 1 Mbps.
Propagation delay from sender to receiver = 0.75 ms.
Time to process a frame = 0.25 ms.
Number of bytes in the information frame = 1980.
Number of bytes in the acknowledge frame = 20.
Number of overhead bytes in the information frame = 20.

Assume that there are no transmission errors. Then, the transmission efficiency (expressed in percentage) of the Stop-and-Wait ARQ protocol for the above parameters is ............... (correct to 2 decimal places).
Answer: 86.5 to 87.5

46.       Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below.
The following query is made on the database.
The number of rows in T2 is ....................
Answer: 4.0
47.       The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or is .................
Answer: 271.0
48.       Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1 s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is .................
Answer: 5.0
49.       Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC-relative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to the address of the next instruction in the program sequence. Consider the following instruction sequence
If the target of the branch instruction is i, then the decimal value of the Offset is ............
Answer: -16.1 to -15.9
50.    Instruction execution in a processor is divided into 5 stages. Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX), and Write Back (WB). These stages take 5, 4, 20, 10, and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementations of the processor are contemplated:
(i) a naive pipeline implementation (NP) with 5 stages and
(ii) an efficient pipeline (EP) where the OF stage is divided into stages OF1and OF2 with execution times of 12 ns and 8 ns respectively.
The speedup (correct to two decimal places) achieved by EP over NP in executing 20 independent instructions with no hazards is .................
Answer: 1.49 to 1.52
51.    Consider a 2-way set associative cache with 256 blocks and uses LRU replacement. Initially the cache is empty. Conflict misses are those misses which occur due to contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of accesses to memory blocks

(0, 128, 256, 128, 0, 128, 256, 128, 1, 129, 257, 129, 1, 129, 257, 129)

is repeated 10 times. The number of conflict misses experienced by the cache is ......................
Answer: 76.0
52.    Consider the expression (a - 1) * (((b + c) / 3) + d )). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a Ioad/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is .................
Answer: 2.0
53.    Consider the following C program.
#include <stdio.h>
include <string.h>
void printlength(char *s, char *t) {
unsigned int c = 0;
int len = ((strlen(s) - strlen(t)) > c) ? strlen(s): strlen(t);
printf(“%d\n”, len);
void main() {
char *x = “abc”;
char *y = “defgh”;
Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned int. The output of the program is ...................
Answer: 3.0
54.    A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as a direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ........... bits.
Answer: 14.0
55.    The output of executing the following C program is ...................
#include <stdio.h>
int total (int v) {
static int count = 0;
while(v) {
count += v&1;
v >>= 1;
return count;
void main() {
static int x = 0;
int i = 5;
for(; i > 0; i--) {
x = x + total (i);
printf (“%d\n”, x);
Answer: 23.0

Pages   2   3   4   5 

Post a Comment