All 65 questions of GATE 2015 CS (Set 2)

We __________ our friend's birthday and we __________ how to make it up to him.

Choose the statement where the underlined word is used correctly.

Consider a function

on

The value of $x$ at which the function attains a maximum, and the maximum value of the function are:

A generic term that includes various items of clothing such as a skirt, a pair of trousers and a shirt is:

Based on the given statements, select the most appropriate option to solve the given question.

What will be the total weight of 10 poles each of same weight?

Statements:

I. One fourth of the weight of a pole is 5 kg.
II. The total weight of these poles is 160 kg more than the total weight of two poles.

Out of the following four sentences, select the most suitable sentence with respect to grammar and usage.

If the list of numbers $P,R,S,T,U$ is an arithmetic sequence, which of the following are also in arithmetic sequence?

I. $2P,2R,2S,2T,2U$
II. $P-3,R-3,S-3,T-3,U-3$
III. $P^2,R^2,S^2,T^2,U^2$

Four branches of a company are located at $M,N,O$, and $P$.

$M$ is north of $N$ at a distance of 4 km.
$P$ is south of $O$ at a distance of 2 km.
$N$ is southeast of $O$ by 1 km.

What is the distance between $M$ and $P$ in km?

If $p,q,r,s$ are distinct integers such that:

Also, a function

The same operations are valid with two-variable functions of the form $f(p,q)$.

What is the value of

In a triangle $PQR$, $PS$ is the angle bisector of $\angle QPR$ and $\angle QPS=60^\circ$. What is the length of $PS$?

In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?

Identify the correct order in which a server process must invoke the function calls accept, bind, listen, and recv according to UNIX socket API.

The larger of the two eigenvalues of the matrix

is __________.

The cardinality of the power set of

is __________.

Consider the following two statements.

Which one of the following statements follows from $S_1$ and $S_2$ as per sound inference rules of logic?

A binary tree $T$ has 20 leaves.

The number of nodes in $T$ having two children is __________.

The number of divisors of 2100 is __________.

A link has a transmission speed of $10^6$ bits/sec.

It uses data packets of size 1000 bytes each.

Assume that the acknowledgement has negligible transmission delay, and that its propagation delay is the same as the data propagation delay.

Also assume that the processing delays at nodes are negligible.

The efficiency of the stop-and-wait protocol in this setup is exactly 25%.

The value of the one-way propagation delay in milliseconds is __________.

A system has 6 identical resources and $N$ processes competing for them.

Each process can request at most 2 resources.

Which one of the following values of $N$ could lead to a deadlock?

Match the following.

A software requirements specification (SRS) document should avoid discussing which one of the following?

With reference to the B+ tree index of order 1 shown below, the minimum number of nodes, including the root node, that must be fetched in order to satisfy the following query is __________.

Query: Get all records with a search key greater than or equal to 7 and less than 15.

Consider the following C function.

int fun(int n) {
    int x = 1, k;

    if (n == 1)
        return x;

    for (k = 1; k < n; ++k)
        x = x + fun(k) * fun(n - k);

    return x;
}

The return value of fun(5) is __________.

Consider the following statements.

I. The complement of every Turing decidable language is Turing decidable.
II. There exists some language which is in NP but is not Turing decidable.
III. If $L$ is a language in NP, $L$ is Turing decidable.

Which of the above statements is/are true?

Consider two decision problems $Q_1,Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$.

Then which one of the following is consistent with the above statement?

The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence

is __________.

Which one of the following statements is NOT correct about HTTP cookies?

Consider the following function written in the C programming language.

void foo(char *a) {
    if (*a && *a != ' ') {
        foo(a + 1);
        putchar(*a);
    }
}

The output of the above function on input "ABCD EFGH" is:

Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit.

Suppose while running a program, it was observed that 80% of the processor's read requests result in a cache hit.

The average read access time in nanoseconds is __________.

Consider the following transaction involving two bank accounts $x$ and $y$.

read(x);
x := x - 50;
write(x);
read(y);
y := y + 50;
write(y);

The constraint that the sum of the accounts $x$ and $y$ should remain constant is that of:

A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways.

Assume that the TLB tag does not store any process id.

The minimum length of the TLB tag in bits is __________.

An unordered list contains $n$ distinct elements.

The number of comparisons to find an element in this list that is neither maximum nor minimum is:

Consider a complete binary tree where the left and the right subtrees of the root are max-heaps.

The lower bound for the number of operations to convert the tree to a heap is:

Consider the basic COCOMO model where $E$ is the effort applied in person-months, $D$ is the development time in chronological months, $KLOC$ is the estimated number of delivered lines of code in thousands, and $a_b,b_b,c_b,d_b$ have their usual meanings.

The basic COCOMO equations are of the form:

Let $R$ be the relation on the set of positive integers such that $aRb$ if and only if $a$ and $b$ are distinct and have a common divisor other than 1.

Which one of the following statements about $R$ is true?

The number of states in the minimal deterministic finite automaton corresponding to the regular expression

is __________.

A computer system implements 8 kilobyte pages and a 32-bit physical address space.

Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation.

If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is __________ bits.

Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of

bytes/sec.

If the average seek time of the disk is twice the average rotational delay and the controller's transfer time is 10 times the disk transfer time, the average time, in milliseconds, to read or write a 512-byte sector of the disk is __________.

Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN.

Ethernet frames may carry data up to 1500 bytes, i.e. MTU = 1500 bytes.

Size of UDP header is 8 bytes and size of IP header is 20 bytes. There is no option field in IP header.

How many total number of IP fragments will be transmitted and what will be the contents of offset field in the last fragment?

Consider the intermediate code given below.

(1)  i = 1
(2)  j = 1
(3)  t1 = 5 * i
(4)  t2 = t1 + j
(5)  t3 = 4 * t2
(6)  t4 = t3
(7)  a[t4] = -1
(8)  j = j + 1
(9)  if j <= 5 goto (3)
(10) i = i + 1
(11) if i < 5 goto (2)

The number of nodes and edges in the control-flow graph constructed for the above code, respectively, are:

Which of the following languages is/are regular?

where $w^R$ is the reverse of string $w$.

Assume that the bandwidth for a TCP connection is 1048560 bits/sec.

Let $\alpha$ be the value of RTT in milliseconds, rounded off to the nearest integer, after which the TCP window scale option is needed.

Let $\beta$ be the maximum possible window size with window scale option.

Then the values of $\alpha$ and $\beta$ are:

Consider a simple checkpointing protocol and the following set of operations in the log.

(start, T4);
(write, T4, y, 2, 3);
(start, T1);
(commit, T4);
(write, T1, z, 5, 7);
(checkpoint);
(start, T2);
(write, T2, x, 1, 9);
(commit, T2);
(start, T3);
(write, T3, z, 7, 2);

If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo list and the redo list?

A Young tableau is a 2D array of integers increasing from left to right and from top to bottom.

Any unfilled entries are marked with $\infty$, and hence there cannot be any entry to the right of, or below, an $\infty$.

The following Young tableau consists of unique entries.

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau.

The minimum number of entries, other than 1, to be shifted to remove 1 from the given Young tableau is __________.

Consider two relations $R_1(A,B)$ with tuples $(1,5),(3,7)$ and $R_2(A,C)=(1,7),(4,9)$.

Assume that $R(A,B,C)$ is the full natural outer join of $R_1$ and $R_2$.

Consider the following tuples of the form $(A,B,C)$:

Which one of the following statements is correct?

Consider the following routing table at an IP router.

For each IP address in Group I, identify the correct choice of the next hop from Group II using the entries from the routing table above.

Group I

i. 128.96.171.92
ii. 128.96.167.151
iii. 128.96.163.151
iv. 128.96.165.121

Group II

a. Interface 0
b. Interface 1
c. R2
d. R3
e. R4

Given below are some algorithms and some algorithm design paradigms.

Match the above algorithms on the left to the corresponding design paradigm they follow.

Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB.

These partitions need to be allotted to four processes of sizes 357 KB, 210 KB, 468 KB and 491 KB in that order.

If the best fit algorithm is used, which partitions are NOT allotted to any process?

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for $i$ ranging from 0 to 2020?

Suppose you are provided with the following function declaration in the C programming language.

int partition(int a[], int n);

The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot are in the left part of the array, and all elements greater than the pivot are in the right part.

In addition, it moves the pivot so that the pivot is the last element of the left part.

The return value is the number of elements in the left part.

The following partially given function in the C programming language is used to find the $k^{th}$ smallest element in an array a[] of size $n$ using the partition function. Assume $k \le n$.

int kth_smallest(int a[], int n, int k) {
    int left_end = partition(a, n);

    if (left_end + 1 == k) {
        return a[left_end];
    }

    if (left_end + 1 > k) {
        return kth_smallest( __________ );
    }
    else {
        return kth_smallest( __________ );
    }
}

The missing argument lists are respectively:

Consider a processor with byte-addressable memory.

Assume that all registers, including Program Counter (PC) and Program Status Word (PSW), are of size 2 bytes.

A stack in the main memory is implemented from memory location $(0100)_{16}$ and it grows upward.

The stack pointer (SP) points to the top element of the stack.

The current value of SP is $(016E)_{16}$.

The CALL instruction is of two words, the first word is the op-code and the second word is the starting address of the subroutine. One word is 2 bytes.

The CALL instruction is implemented as follows:

• Store the current value of PC in the stack.
• Store the value of PSW register in the stack.
• Load the starting address of the subroutine in PC.

The content of PC just before the fetch of a CALL instruction is $(5FA0)_{16}$.

After execution of the CALL instruction, the value of the stack pointer is:

A half adder is implemented with XOR and AND gates.

A full adder is implemented with two half adders and one OR gate.

The propagation delay of an XOR gate is twice that of an AND/OR gate.

The propagation delay of an AND/OR gate is 1.2 microseconds.

A 4-bit ripple-carry binary adder is implemented by using four full adders.

The total propagation time of this 4-bit binary adder in microseconds is __________.

Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively, and $F$ denote the set of all possible functions defined from $X$ to $Y$.

Let $f$ be randomly chosen from $F$.

The probability of $f$ being one-to-one is __________.

Consider the alphabet $\Sigma=\{0,1\}$, the null or empty string $\lambda$, and the sets of strings $X_0,X_1,X_2$ generated by the corresponding non-terminals of a regular grammar.

$X_0,X_1,X_2$ are related as follows:

Which one of the following choices precisely represents the strings in $X_0$?

The secant method is used to find the root of an equation $f(x)=0$.

It is started from two distinct estimates $x_a$ and $x_b$ for the root. It is an iterative procedure involving linear interpolation to a root.

The iteration stops if $f(x_b)$ is very small and then $x_b$ is the solution. The procedure is given below.

Observe that there is an expression which is missing and is marked by ?.

Secant

Initialize: x_a, x_b, ε, N       // ε = convergence indicator
                                  // N = maximum no. of iterations

f_b = f(x_b)
i = 0

while (i < N and |f_b| > ε) do
    i = i + 1                    // update counter
    x_t = ?                      // missing expression for intermediate value

    x_a = x_b                    // reset x_a
    x_b = x_t                    // reset x_b
    f_b = f(x_b)                 // function value at new x_b
end while

if |f_b| > ε then                // loop is terminated with i = N
    write "Non-Convergence"
else
    write "return x_b"
end if

Which is the suitable expression to be put in place of ? so that it follows all steps of the secant method?

Perform the following operations on the matrix

(i) Add the third row to the second row.

(ii) Subtract the third column from the first column.

The determinant of the resultant matrix is __________.

The number of minterms after minimizing the following Boolean expression is __________.

Consider the C program below.

#include <stdio.h>
int *A, stkTop;

int stkFunc(int opcode, int val)
{
    static int size = 0, stkTop = 0;

    switch (opcode) {
        case -1: size = val; break;
        case 0:  if (stkTop < size) A[stkTop++] = val; break;
        default: if (stkTop) return A[--stkTop];
    }

    return -1;
}

int main()
{
    int B[20]; A = B; stkTop = -1;

    stkFunc(-1, 10);
    stkFunc(0, 5);
    stkFunc(0, 10);

    printf("%d\n", stkFunc(1, 0) + stkFunc(1, 0));
}

The value printed by the above program is __________.

Let

and $A$ denote the area of the region bounded by $f(x)$ and the X-axis, when $x$ varies from $-1$ to $1$.

Which of the following statements is/are TRUE?

I. $f$ is continuous in $[-1,1]$

II. $f$ is not bounded in $[-1,1]$

III. $A$ is nonzero and finite

A graph is self-complementary if it is isomorphic to its complement.

For all self-complementary graphs on $n$ vertices, $n$ is:

Which one of the following well-formed formulae is a tautology?

Which one of the following assertions concerning code inspection and code walkthrough is true?

The number of onto functions, surjective functions, from set

to set

is __________.

Consider the sequence of machine instructions given below.

MUL   R5, R0, R1
DIV   R6, R2, R3
ADD   R7, R5, R6
SUB   R8, R7, R4

In the above sequence, $R0$ to $R8$ are general purpose registers. In the instructions shown, the first register stores the result of the operation performed on the second and third registers.

This sequence of instructions is to be executed in a pipelined instruction processor with the following 4 stages:

1. Instruction Fetch and Decode (IF)
2. Operand Fetch (OF)
3. Perform Operation (PO)
4. Write back the result (WB)

The IF, OF and WB stages take 1 clock cycle each for any instruction.

The PO stage takes:

• 1 clock cycle for ADD or SUB instruction,
• 3 clock cycles for MUL instruction,
• 5 clock cycles for DIV instruction.

The pipelined processor uses operand forwarding from the PO stage to the OF stage.

The number of clock cycles taken for the execution of the above sequence of instructions is __________.

In a connected graph, a bridge is an edge whose removal disconnects a graph.

Which one of the following statements is true?