1
Numerical

### GATE CSE 2016 Set 2

Breadth First Search $(BFS)$ is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If t is the $n$-th vertex in this $BFS$ traversal, then the maximum possible value of $n$ is ___________.

2

### GATE CSE 2016 Set 2

$N$ items are stored in a sorted doubly linked list. For a $delete$ operation, a pointer is provided to the record to be deleted. For a $decrease$-$key$ operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order:
$\Theta \left( N \right),\,\,delete,\,\,O\left( {\log N} \right)\,insert,\,$ $\,O\left( {\log N} \right)\,fund, and$ $\Theta \left( N \right)\,$ $decrease$-$key.$ What is the time complexity of all these operations put together?

A
$O\left( {{{\log }^2}N} \right)$
B
$O\left( N \right)$
C
$O\left( {{N^2}} \right)$
D
$\Theta \left( {{N^2}\log N} \right)$
3

### GATE CSE 2016 Set 2

Consider the following $New-order$ strategy for traversing a binary tree:

$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$ Visit the root;
$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$ Visit the right subtree using $New-order;$
$\,\,\,\,\,\,\, \bullet \,\,\,\,\,$ Visit the left subtree using $New-order;$

The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4 * 5 - 2 ^ 6 7 * 1 + - is given by:

A
+ - 1 6 7 * 2 ^ 5 - 3 4 *
B
- + 1 * 6 7 ^ 2 - 5 * 3 4
C
- + 1 * 7 6 ^ 2 - 5 * 4 3
D
1 7 6 * + 2 5 4 3 * - ^ - New-order;
4

### 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)$

### 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