GATE CSE 2016 Set 2

## GATE CSE

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascen

View Question
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

View Question
A complete binary min-heap is made by including each integer in $$[1,1023]$$ exactly once. The depth of a node in the he

View Question
The given diagram shows the flowchart for a recursive function $$A(n).$$ Assume that all statements, except for the recu

View Question
Let $${A_1},{A_2},{A_3},$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,\,5 \times 20,\,\,20 \times 10,$

View Question
Match the following:
.tg {border-collapse:collapse;border-spacing:0;}
.tg td{font-family:Arial, sans-serif;font-size:

View Question
Which one of the following grammars is free from $$left$$ $$recursion$$?

View Question
A student wrote two context-free grammars G1 and G2 for generating a single $$C$$-like array declaration. The dimension

View Question
In an Ethernet local area network, which one of the following statements is TRUE?

View Question
A network has a data transmission bandwidth of 20 × 106 bits per second. It uses CSMA/CD in the MAC layer. The maximum s

View Question
For the IEEE 802.11 MAC protocol for wireless communication, which of the following statements is/are TRUE?
I. At least

View Question
Consider a 128 × 103 bits/second satellite communication link with one way propagation delay of 150 milliseconds. Select

View Question
Identify the correct sequence in which the following packets are transmitted on the network by a host when a browser req

View Question
Anarkali digitally signs a message and sends it to Salim. Verification of the signature by Salim requires

View Question
A processor has $$40$$ distinct instructions and $$24$$ general purpose registers. A $$32$$-bit instruction word has an

View Question
Suppose the functions $$F$$ and $$G$$ can be computed in $$5$$ and $$3$$ nanoseconds by functional units $${U_F}$$ and $

View Question
Consider a processor with $$64$$ registers and an instruction set of size twelve. Each instruction has five distinct fie

View Question
The width of the physical address on a machine is $$40$$ bits. The width of the tag field in a $$512$$ $$KB$$ $$8$$-way

View Question
Consider a $$3$$ $$GHz$$ (gigahertz) processor with a three-stage pipeline and stage latencies $${\tau _1},{\tau _2},$$

View Question
A file system uses an in-memory cache to cache disk blocks. The miss rate of the cache is shown in the figure. The laten

View Question
Breadth First Search $$(BFS)$$ is started on a binary tree beginning from the root vertex. There is a vertex $$t$$ at a

View Question
$$N$$ items are stored in a sorted doubly linked list. For a $$delete$$ operation, a pointer is provided to the record t

View Question
Consider the following $$New-order$$ strategy for traversing a binary tree:
$$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$$ Visit

View Question
The number of ways in which the numbers $$1, 2, 3, 4, 5, 6, 7$$ can be inserted in an empty binary search tree, such tha

View Question
In an adjacency list representation of an undirected simple graph $$G = (V,E),$$ each edge $$(u, v)$$ has two adjacency

View Question
B+ Trees are considered BALANCED because

View Question
Suppose a database schedule $$S$$ involves transactions $${T_1},\,...,\,{T_n}.$$ Construct the precedence graph of $$S$$

View Question
Consider the following database schedule with two transactions, T1 and T2
S = r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X)

View Question
Consider the following database table named $$water$$_$$schemes :$$
.tg {border-collapse:collapse;border-spacing:0;bor

View Question
Consider an eight-bit ripple-carry adder for computing the sum of $$A$$ and $$B,$$ where $$A$$ and $$B$$ are integers re

View Question
Let, $${x_1} \oplus {x_2} \oplus {x_3} \oplus {x_4} = 0$$ where $${x_1},\,{x_2},\,{x_3},\,{x_4}$$ are Boolean Variables,

View Question
Let $$X$$ be the number of distinct $$16$$-bit integers in $$2’s$$ complement representation. Let $$Y$$ be the number of

View Question
Consider the system, each consisting of m linear equations in $$n$$ variables.
$$I.$$ $$\,\,\,$$ If $$m < n,$$ then

View Question
Suppose that the eigen values of matrix $$A$$ are $$1, 2, 4.$$ The determinant of $${\left( {{A^{ - 1}}} \right)^T}$$ is

View Question
Let $${A_1},\,{A_2},\,{A_3}$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,5 \times 20,\,20 \times 10,$$

View Question
Suppose that a shop has an equal number of LED bulbs of two different types. The probability of an LED bulb lasting more

View Question
Consider the following expressions:
$$\,\,\,\,\,\,\,\,\,\,\,\,\,$$ $$(i)$$ $$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,$$ false
$$\,

View Question
Let $$f(x)$$ be a polynomial and $$g\left( x \right) = f'\left( x \right)$$ be its derivative. If the degree of $$\left(

View Question
The minimum number of colours that is sufficient to vertex-colour any planar graph is _____________ .

View Question
A binary relation $$R$$ on $$N \times N$$ is defined as follows: $$(a,b)R(c,d)$$ if $$a \le c$$ or $$b \le d.$$ Consider

View Question
Consider a set $$U$$ of $$23$$ different compounds in a Chemistry lab. There is a subset $$S$$ of $$U$$ of $$9$$ compoun

View Question
Which one of the following well-formed formulae in predicate calculus is NOT valid?

View Question
The value of the expression $${13^{99}}$$ ($$mod$$ $$17$$), in the range $$0$$ to $$16,$$ is ______________ .

View Question
In which one of the following page replacement algorithms it is possible for the page fault rate to increase even when t

View Question
Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The sched

View Question
Consider a non-negative counting semaphore $$S.$$ The operation $$P(S)$$ decrements $$S,$$ and $$V(S)$$ increments $$S.$

View Question
The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression
$$${\left

View Question
Language $${L_1}$$ is defined by the grammar: $$S{}_1 \to a{S_1}b|\varepsilon $$
Language $${L_2}$$ is defined by the gr

View Question
Consider the following types of languages: $${L_1}:$$ Regular, $${L_2}:$$ Context-free, $${L_3}:$$ Recursive, $${L_4}:$$

View Question
Consider the following two statements:
$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting st

View Question
Consider the following languages:
$$$\eqalign{
& {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr

View Question
Consider the following languages.
$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \righ

View Question
## General Aptitude

The man who is now Municipal Commissioner worked as ____________________.

View Question
Find the odd one in the following group of words
mock, deride, praise, jeer

View Question
Nobody knows how the Indian cricket team is going to cope with the difficult and seamer-friendly wickets in Australia.
C

View Question
Pick the odd one from the following options.

View Question
In a quadratic function, the value of the product of the roots $$\left( {\alpha ,\beta } \right)$$ is $$4.$$ Find the va

View Question
All hill-stations have a lake. Ooty has two lakes.
Which of the statement(s) below is/are logically valid and can be inf

View Question
Among $$150$$ faculty members in an institute, $$55$$ are connected with each other through Facebook® and $$85$$ are con

View Question
Computers were invented for performing only high-end useful computations. However, it is no understatement that they hav

View Question
Choose the correct expression for $$f(x)$$ given in the graph.

View Question
In a $$2 \times 4$$ rectangle grid shown below, each cell is a rectangle. How many rectangles can be observed in the gri

View Question