CS and IT GATE 2016 Set-2 Questions with Answer

Ques 27 Computer Network

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

Ques 28 Computer Network

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

Ques 29 Data Structure

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.

Ques 30 Data Structure

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 _____________

Ques 31 Data Structure

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?

Ques 32 Data Structure

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:

Ques 33 Data Structure

B+ Trees are considered BALANCED because

Ques 34 DBMS

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?

Ques 35 DBMS

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?

Ques 36 Design Algorithm Analysis

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______________.

Ques 37 Design Algorithm Analysis

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 ________

Ques 38 Design Algorithm Analysis

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

Ques 39 Design Algorithm Analysis

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