1

### GATE CSE 2016 Set 2

In an adjacency list representation of an undirected simple graph $G = (V,E),$ each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u,$ and $[u]$ in the adjacency list of $v.$ These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If $|E| = m$ and $|V| = n,$ and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
A
$\Theta \left( {{n^2}} \right)$
B
$\Theta \left( {n + m} \right)$
C
$\Theta \left( {{m^2}} \right)$
D
$\Theta \left( {{n^4}} \right)$
2
Numerical

### GATE CSE 2016 Set 2

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 that the resulting tree has height $6,$ is _____________.

$Note:\,\,\,The\,\,height\,\,of\,\,a\,tree\,\,with\,\,a\,\,\sin gle\,\,node\,\,is\,\,0$

3

### GATE CSE 2016 Set 2

B+ Trees are considered BALANCED because
A
the lengths of the paths from the root to all leaf nodes are all equal.
B
the lengths of the paths from the root to all leaf nodes differ from each other by at most 1.
C
the number of children of any two non-leaf sibling nodes differ by at most 1.
D
the number of records in any two leaf nodes differ by at most 1.
4

### GATE CSE 2016 Set 2

Suppose a database schedule $S$ involves transactions ${T_1},\,...,\,{T_n}.$ Construct the precedence graph of $S$ with vertices representing the transactions and edges representing the conflicts. If $S$ is serializable, which one of the following orderings of the vertices of the precedence graph is guaranteed to yield a serial schedule?
A
Topological order
B
Depth-first order
C
D
Ascending order of transaction indices

### Paper Analysis of GATE CSE 2016 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization6
Data Structures5
Database Management System4
Digital Logic3
Discrete Mathematics11
Operating Systems3
Theory of Computation6
General Aptitude10