# Programming and Data Structures (Test 4)

## Gate Exam : Cs Computer Science And Information Technology

| Home | | Gate Exam | | Cs Computer Science And Information Technology | | Programming and Data Structures |

Programming and Data Structures
| Programming and Data Structures |
Q.1
Consider the following rooted tree with the vertex labelled P as the root

The order in which the nodes are visited during an in-order traversal of the tree is
A. SQPTRWUV
B. SQPTUWRV
C. SQPTWUVR
D. SQPTRUWV
Explaination / Solution:

The In order Traversal of Ternary Tree is done as follows: Left → Root → Middle → Right So the nodes are visited in SQPTRWUV order.

Workspace
Report
Q.2
Consider the following graph:

Which of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
A. (b,e) (e,f) (a,c) (b,c) (f,g) (c,d)
B. (b,e) (e,f) (a,c) (f,g) (b,c) (c,d)
C. (b,e) (a,c) (e,f) (b,c) (f,g) (c,d)
D. (b,e) (e,f) (b,c) (a,c) (f,g) (c,d)
Explaination / Solution:
No Explaination.

Workspace
Report
Q.3
A subsequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.
We wish to find the length of the longest common subsequence (LCS) of X[m] and Y[n] as l(m, n), where an incomplete recursive definition for the function l(i, j) to compute the length of the LCS of X[m] and Y[n] is given below:
l(i, j) = 0, if either i = 0 or j = 0
= expr1, if i, j>0 and x[i - 1] = Y[j - 1]
= expr2, if i, j>0 and x[i - 1] ≠ Y[j - 1]
Which one of the following option is correct?
A. expr1 ≡ l(i - 1, j) + 1
B. expr1 ≡ I(i, j - 1)
C. expr2 ≡ max(I(i - 1, j), I(i, j - 1))
D. expr2 ≡ max(I(i - 1, j - 1), I(i, j))
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?
A. In both AST and CFG, let node, N2 be the successor of node N1. In the input program, the code corresponding to N2 is present after the code corresponding in N1.
B. For any input program, neither AST nor CFG will contain a cycle
C. The maximum number of successors of a node in an AST and a CFG depends on the input program
D. 4Each node is AST and CFG corresponds to at most one statement in the input program
Explaination / Solution:

Optional (A) is not true when CFG contains cycle Option (B) is false as CFG can contain cycle Option (D) is false as a single node can contain block of statements.

Workspace
Report
Q.5
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
A.
B.
C.
D.
Explaination / Solution:

Heap is a complete binary tree

Workspace
Report
Q.6
Which of the given options provides the increasing order of asymptotic complexityoffunctions f1,f2,fand f4?

A. f3f2f4f1
B. f3f2f1f4
C. f2f3f1f4
D. f2f3f4f1
Explaination / Solution:

Workspace
Report
Q.7
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?
A. 0
B. 1
C. n!
D.
Explaination / Solution:
No Explaination.

Workspace
Report
Q.8
An undirected graph G(V,E) contains n ( n > 2 ) nodes named v1v2,....vn . Two nodes vivj are connected if and only if 0 < |i − j| ≤ 2. Each edge (vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below
The length of the path from v5 to v6 in the MST of previous question with n = 10 is
A. 11
B. 25
C. 31
D. 41
Explaination / Solution:

12 + 8 + 4 + 3 + 6 + 10 = 31

Workspace
Report
Q.9
An operator delete (i) for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal of the element?
A. O(1)
B. O(d) but not O(1)
C. O(2d ) but not O(d)
D. O(d 2d ) but not O(2d )
Explaination / Solution:

Time complexity of heapification is O (height) =O(d)

Workspace
Report
Q.10
A. global variable but not heap.
B. heap but not global variables.
C. neither global variables nor heap.
D. Both heap and global variables