What topics are covered on Page 3 of GATE 2016 CS/IT Set 2?

Page 3 contains Questions 27 to 39. It covers Ethernet and digital signatures, BSTs, binary heaps, adjacency lists, binary-tree traversals, B+ trees, DBMS recoverability and serializability, matrix-chain multiplication, breadth-first search, linked-list complexity and Floyd-Warshall.

What does exponential backoff do in Ethernet?

The exponential backoff mechanism reduces the probability of repeated collisions when stations retransmit after a collision.

Which key is required to verify a digital signature?

A signature created by a sender is verified using that sender's public key.

Why are B+ trees considered balanced?

B+ trees are balanced because all root-to-leaf paths have the same length, so all leaf nodes occur at the same depth.

What ordering of a precedence graph gives an equivalent serial schedule?

For a conflict-serializable schedule, a topological ordering of its acyclic precedence graph gives an equivalent serial transaction order.

Which design paradigm does Floyd-Warshall use?

The Floyd-Warshall all-pairs shortest-path algorithm is based on dynamic programming.

CS and IT Gate 2016 Set-2 Questions with Answer

1 2 3 4 5

Ques 27 Gate 2016 Set-2

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

A station stops to sense the channel once it starts transmitting a frame.

The purpose of the jamming signal is to pad the frames that are smaller than the minimum frame size.

A station continues to transmit the packet even after the collision is detected.

The exponential backoff mechanism reduces the probability of collision on retransmissions

(Networking) is the correct answer.

PROCESSED

Ques 28 Gate 2016 Set-2

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

Anarkali’s public key.

Salim’s public key.

Salim’s private key.

Anarkali’s private key.

(Digital Signature) is the correct answer.

PROCESSED

Ques 29 Gate 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 single node is 0.

(a) is the correct answer.

Ques 30 Gate 2016 Set-2

A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The depth of a node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is _____________

(a) is the correct answer.

Ques 31 Gate 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?

Θ(n²)

Θ(m+n)

Θ(m²)

Θ(n⁴)

(Graph Theory) is the correct answer.

PROCESSED

Ques 32 Gate 2016 Set-2

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

Visit the root;
Visit the right subtree using New-order
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:

+ - 1 6 7 * 2 ˆ 5 - 3 4 *

- + 1 * 6 7 ˆ 2 - 5 * 3 4

- + 1 * 7 6 ˆ 2 - 5 * 4 3

1 7 6 * + 2 5 4 3 * - ˆ -

(Binary Tree) is the correct answer.

PROCESSED

Ques 33 Gate 2016 Set-2

B+ Trees are considered BALANCED because

the lengths of the paths from the root to all leaf nodes are all equal.

the lengths of the paths from the root to all leaf nodes differ from each other by at most 1.

the number of children of any two non-leaf sibling nodes differ by at most 1.

the number of records in any two leaf nodes differ by at most 1.

(B+ Tree) is the correct answer.

PROCESSED

Ques 34 Gate 2016 Set-2

Consider the following database schedule with two transactions, T₁ and T₂.

S = r₂(X); r₁(X); r₂(Y); w₁(X); r₁(Y); w₂(X); a₁; a₂;

where r_i(Z) denotes a read operation by transaction T_i on a variable Z, w_i(Z) denotes a write operation by T_i on a variable Z and a_i denotes an abort by transaction T_i . Which one of the following statements about the above schedule is TRUE?

S is non-recoverable

S is recoverable, but has a cascading abort

S does not have a cascading abort

S is strict

(Transactions) is the correct answer.

PROCESSED

Ques 35 Gate 2016 Set-2

Suppose a database schedule S involves transactions T1, ....Tn. 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?

Topological order

Depth-first order

Breadth-first order

Ascending order of transaction indices

(Transactions) is the correct answer.

PROCESSED

Ques 36 Gate 2016 Set-2

Let A₁, A₂, A₃, and A₄ be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A₁ A₂A₃A₄ using the basic matrix multiplication method is______________.

(a) is the correct answer.

Ques 37 Gate 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 ________

(a) is the correct answer.

Ques 38 Gate 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: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key What is the time complexity of all these operations put together

O(Log²N)

O(N)

O(N²)

Θ(N² Log N)

(S) is the correct answer.

Given:
A sorted doubly linked list containing N items.
Pointers are provided directly to the nodes for delete and decrease-key operations.
Sequence of operations:
- Θ(N) delete operations
- O(log N) insert operations
- O(log N) find operations
- Θ(N) decrease-key operations
To find:
The overall time complexity of all these operations put together.
Solution:
Let me analyze the time taken by each operation on a sorted doubly linked list one by one.
First, for the delete operation:
Since a direct pointer to the record to be deleted is given, we just need to update the prev and next pointers of the adjacent nodes.
Time taken for 1 delete = O(1).
Total time for Θ(N) delete operations = Θ(N) × O(1) = O(N).
Next, for the insert operation:
Since it is a linked list, we do not have random access, so we cannot do binary search. We have to scan linearly to find the correct sorted position.
Time taken for 1 insert = O(N).
Total time for O(log N) insert operations = O(log N) × O(N) = O(N log N).
Next, for the find operation:
Again, no random access, so linear search is required to find an element.
Time taken for 1 find = O(N).
Total time for O(log N) find operations = O(log N) × O(N) = O(N log N).
Now, for the decrease-key operation:
A pointer to the record is provided, but decreasing the key value means the node may no longer be in sorted order.
To restore the sorted order, we have to shift the node backwards along the list to its appropriate position.
In the worst case, shifting takes O(N) steps.
Time taken for 1 decrease-key = O(N).
Total time for Θ(N) decrease-key operations = Θ(N) × O(N) = O(N²).
Now adding up the time complexities of all operations:
Total Time = O(N) + O(N log N) + O(N log N) + O(N²)
The O(N²) term clearly dominates the entire sum.
So, the total time complexity is O(N²).
Answer:
(C) O(N²)

Ques 39 Gate 2016 Set-2

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

Greedy paradigm.

Divide-and-Conquer paradigm.

Dynamic Programming paradigm.

neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

(G) is the correct answer.

Given:
Floyd-Warshall algorithm for all-pair shortest paths computation.
To find:
The algorithm design paradigm it is based on.
Solution:
Let me recall how the Floyd-Warshall algorithm works.
It computes the shortest path between all pairs of vertices in a directed, weighted graph.
Let d^(k)[i][j] be the shortest path from vertex i to vertex j using only intermediate vertices from the set {1, 2, ..., k}.
The recurrence relation is:
d^(k)[i][j] = min(d^(k-1)[i][j], d^(k-1)[i][k] + d^(k-1)[k][j])
This shows that the problem exhibits optimal substructure and overlapping subproblems.
We build the solution bottom-up by iteratively increasing the set of allowed intermediate vertices from k = 1 to n.
Therefore, this algorithm directly uses the Dynamic Programming approach.
Answer: (C) Dynamic Programming paradigm.

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2016 Set-2 Questions with Answer

Question Options

Sign in to ExamPrev