Programming and Data Structures

Programming and Data Structures

Programming and Data Structures
| Programming and Data Structures |
Q.1
In which one of the following page replacement policies, Belady’s anomaly may occur?
A. FIFO
B. Optimal
C. LRU
D. MRU
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Q.2
Consider the basic block given below.
a = b + c 
c = a + d 
d = b + c 
e = d - b 
a = e + b
The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are
A. 6 and 6
B. 8 and 10
C. 9 and 12
D. 4 and 4
Answer : Option A
Explaination / Solution:

The given basic block can be rewritten as 

From above simplification it is visible that e is same as c and final value of a is same as d. So the final basic block can be written as follows: 

The DAG generated for the above basic block in as 

Maximum number of modes and edges in above DAG is (6,6)

Workspace
Report
Q.3
The following key values are inserted into a B+-tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+-tree is initially empty. 10, 3, 6, 8, 4, 2, 1. The maximum number of times leaf nodes would get split up as a result of these insertions is
A. 2
B. 3
C. 4
D. 5
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report
Q.4
Let G=(V, E) be a graph. Define  where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T), then 
A. |S| = 2|T|
B. |S| = |T| - 1
C. |S| = |T|
D. |S| = |T| + 1
Answer : Option D
Explaination / Solution:
No Explaination.


Workspace
Report
Q.5
Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3 -SAT reduces in polynomial time to Q2. Then which one of following is consistent with the above statement?
A. Q1 is in NP, Q2 in NP hard
B. Q2 is in NP, Q1 is NP hard
C. Both Q1 and Q2 are in NP
D. Both Q1 and Q2 are NP hard
Answer : Option A
Explaination / Solution:



Workspace
Report
Q.6
Consider the following routing table at an IP router:

For each IP address in Group I identify the correct choice of the next hop from Group II using the entries from the routing table above. 
A. i - a, ii - c, iii - e, iv - d
B. i - a, ii - d, iii - b, iv - e
C. i - b, ii - c, iii - d, iv - e
D. i - b, ii - c, iii - e, iv - d
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Q.7
The following is comment written for a C function
/* This function computes the roots of a quadratic equation
a.x^2+b.x+c=0. The function stores two real roots
in *root1 and *root2 and returns the status of validity of
roots. It handles four different kinds of cases.
(i) When coefficient a is zero irrespective of discriminant
(ii) When discriminant is positive
(iii) When discrimanant is zero
(iv) When discrimanant is negative
Only in cases (ii) and (iii), the stored roots are valid.
Otherwise 0 is stored in the roots. the function returns 0 when 
the roots are valid and -1 otherwise. 
The functin also ensures root1>=root2.
int get_QuadRoots (float a, float b, float c, float *root1, float *root2) ; 
*/
A software test engineer is assigned the job of doing black box testing. He comes up with the following test cases, many of which are redundant. 

Which one of the following options provide the set of non-redundant tests using equivalence class partitioning approach from input perspective for black box testing? 
A. T1,T2,T3,T6
B. T1,T3,T4,T5
C. T2,T4,T5,T6
D. T2,T3,T4,T5
Answer : Option C
Explaination / Solution:

T1 and T2 checking same condition a = 0 hence, any one of T1 and T2 is redundant.
T3, T4: in both case discriminant (D)= b2 − 4ac = 0 . Hence any one of it is redundant.
T5 : D>0 
T6 : D<0 

Workspace
Report
Q.8
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
A. P only
B. Q only
C. Neither P nor Q
D. Both P and Q
Answer : Option A
Explaination / Solution:
No Explaination.


Workspace
Report
Q.9
Consider a network with five nodes, N1 to N5, as shown below

The net work uses a Distance Vector Routing protocol. Once the routes have stabilized, the distance vectors at different nodes are as following
N1 : (0, 1, 7, 8, 4) 
N2 : (1, 0, 6, 7, 3) 
N3 : (7, 6, 0, 2, 6) 
N4 : (8, 7, 2, 0, 4) 
N5 : (4, 3, 6, 4, 0)
Each distance vector is the distance of the best known path at that instance to nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric and the cost is identical in both directions. In each round, all nodes exchange their distance vectors with their respective neighbors. Then all nodes update their distance vectors. In between two rounds, any change in cost of a link will cause the two incident nodes to change only that entry in their distance vectors
The cost of link N2-N3 reduces to 2 in (both directions). After the next round of updates, what will be the new distance vector at node, N3? 
A. (3. 2, 0, 2, 5)
B. (3, 2, 0, 2, 6)
C. (7, 2, 0, 2, 5)
D. (7, 2, 0, 2, 6)
Answer : Option A
Explaination / Solution:



Workspace
Report
Q.10
Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y reduces to W , and Z reduces to X (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
A. W can be recursively enumerable and Z is recursive.
B. W can be recursive and Z is recursively enumerable.
C. W is not recursively enumerable and Z is recursive.
D. W is not recursively enumerable and Z is not recursive.
Answer : Option C
Explaination / Solution:
No Explaination.


Workspace
Report


11th 1 mark 11th Key Answers UPSC GATE Solve CAT CLAT BANK UGC-NET TANCET JEE NEET AIIMS