# Programming and Data Structures (Test 3)

## 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
Let A be a square matrix size n × n. Consider the following pseudocode. What is the expected output?
C = 100;
for i = 1 to n do
for j = 1 to n do
{
Temp = A[ i ] [ j ] + C ;
A [ i ] [ j ] = A [ j ] [ i ] ;
A [ j ] [ i ] = Temp – C ;
}
for i = 1 to n do
for j = 1 to n do
output (A[ i ] [ j ]);
A. The matrix A itself
B. Transpose of the matrix A
C. Adding 100 to the upper diagonal elements and subtracting 100 from lower diagonal elements of A
D. None of these
Explaination / Solution:

In the computation of given pseudo code for each row and column of Matrix A, each upper triangular element will be interchanged by its mirror image in the lower triangular and after that the same lower triangular element will be again re-interchanged by its mirror image in the upper triangular, resulting the final computed Matrix A same as input Matrix A.

Workspace
Report
Q.2
Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr;
Struct treeNode
{
Treeptr leftMostchild, rightSibiling;
};
Int Dosomething (treeptr tree)
{
int value =0;
if (tree ! = NULL) {
If (tree -> leftMostchild = = NULL)
else
value = Dosomething (tree->leftMostchild);
value = value + Dosometing (tree->rightsibiling);
}
return (value);
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
A. number of internal nodes in the tree.
B. height of the tree.
C. number of nodes without a right sibling in the tree.
D. number of leaf nodes in the tree.
Explaination / Solution:

The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time. Here, that condition is if (tree→leftMostchild == Null) ⇒ Which means if there is no left most child of the tree (or the sub-tree or the current nodeas called in recursion) ⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all). ⇒ Which means the node under consideration is a leaf node. ⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered. ⇒ The function returns the number of leaf nodes in the tree.

Workspace
Report
Q.3
Which one of the following array represents a binary max-heap?
A. {25, 12, 16, 13, 10, 8, 14}
B. {25, 14, 13, 16, 10, 8, 12}
C. {25, 14, 16, 13, 10, 8, 12}
D. {25, 14, 12, 13, 10, 8, 16}
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
A. 0
B. 1
C. (n-1)/2
D. n-1
Explaination / Solution:
No Explaination.

Workspace
Report
Q.5
Which one of the following assertions concerning code inspection and code walkthrough is true?
A. Code inspection is carried out once the code has been unit tested
B. Code inspection and code walkthrough are synonyms
C. Adherence to coding standards is checked during code inspection
D. Code walkthrough is usually carried out by an independent test team
Explaination / Solution:
No Explaination.

Workspace
Report
Q.6
A graph is self-complementary if it is isomorphic to its complement For all self-complementary graphs on n vertices, n is
A. A multiple of 4
B. Even
C. Odd
D. Congruent to 0 mod 4, or, 1 mod 4
Explaination / Solution:

An n vertex self complementary graph has exactly half number of edges of the complete graph i.e., n(n-1)/4 edges. Since n(n-1) must be divisible by 4 , n must be congruent to 0 or 1 module 4.

Workspace
Report
Q.7
A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
A. Both operations can be performed in O(1) time
B. At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)
C. The worst case time complexity for both operations will be Ω(n)
D. Worst case time complexity for both operations will be Ω(log n)
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 What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
A. 1/12(11n2 - 5n)
B. n- n + 1
C. 6n -11
D. 2n + 1
Explaination / Solution:
No Explaination.

Workspace
Report
Q.9
What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed?
a=3;
void n(x) {x = x * a; print(x);}
void m(y) {a = 1; a = y - a; n(a); print(a);}
void main() {m(a);}
A. 6,2
B. 6,6
C. 4,2
D. 4,4
Explaination / Solution:

Dynamic scoping looks for the definition of free variable in the reverse order of calling sequence.

Workspace
Report
Q.10
Consider the following proposed solution for the critical section problem. There are n processes: P0. . . Pn-1. In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero.
Code for Pi:
do {
c[i]=1; t[i] = pmax(t,. . .,t[n-1])+1; c[i]=0;
for every j = i in {0,. . .,n-1} {
while (c[j]);
while (t[j] != 0 && t[j]<=t[i]);
}
Critical Section;
t[i]=0;
Remainder Section;
} while (true);
Which one of the following is TRUE about the above solution?
A. At most one process can be in the critical section at any time
B. The bounded wait condition is satisfied
C. The progress condition is satisfied
D. It cannot cause a deadlock