# Programming and Data Structures (Test 2)

## 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
What is the number of swaps required to sort n elements using selection sort, in the worst case?
A. θ(n)
B. θ(n log n)
C. θ(n2)
D. θ(nlog n)
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?
A.
B.
C.
D.
Explaination / Solution:
No Explaination.

Workspace
Report
Q.3
Consider the following relational schema:
Employee (empId, empName, empDept)
Customer (custId,custName, salesRepId, rating)
SalesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?
SELECT empName
FROM employee E
WHERE NOT EXISTS (SELECT custId
FROM customer C
WHERE C. salesRepId = E. empId
AND C. rating < > ‘GOOD’)

A. Names of all the employees with at least one of their customers having a ‘GOOD’ rating.
B. Names of all the employees with at most one of their customers having a ‘GOOD’ rating.
C. Names of all the employees with none of their customers having a ‘GOOD’ rating.
D. Names of all the employees with all their customers having a ‘GOOD’ rating.
Explaination / Solution:

The outer query will return the value (names of employees) for a tuple in relation E, only if inner query for that tuple will return no tuple (usage of NOT EXISTS). The inner query will run for every tuple of outer query. It selects cust-id for an employee e, if rating of customer is NOT good. Such an employee should not be selected in the output of outer query. So the query will return the names of all those employees whose all customers have GOOD rating.

Workspace
Report
Q.4
Let R be the relation on the set of positive integers such that a aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is true?
A. R is symmetric and reflexive but not transitive
B. R is reflexive but not symmetric and not transitive
C. R is transitive but not reflexive and not symmetric
D. R is symmetric but not reflexive and not transitive
Explaination / Solution:

R is not reflexive as each element can‟t be related to itself.
R is symmetric
Let a = 3, b = 6 and c = 10 then 3 and 6 have a common division other than 1
6 and 10 have a common division other than 1
but 3 &10 have no common division other than 1
3R6 and 6R10 but 3R10
R is not transitive

Workspace
Report
Q.5
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A. A tree has no bridges
B. A bridge cannot be part of a simple cycle
C. Every edge of a clique with size ≥ 3 is a bridge (A clique is any compete sub graph of a graph)
D. A graph with bridges cannot have a cycle
Explaination / Solution:

Since, every edge in a tree is bridge
(A) is false
Since, every edge in a complete graph kn (n ≥ 3) is not a bridge (c) is false
Let us consider the following graph G:
This graph has a bridge i.e., edge „e‟ and a cycle of length „3‟
(D) is false
Since, in a cycle every edge is not a bridge
(B) is true

Workspace
Report
Q.6
Consider two relations R1(A,B) with the tuples (1.5), (3,7) and R2 (A,C) = (1,7), (4,9). Assume that R(A,B,C) is the full natural outer join of R1 and R2 . Consider the following tuples of the form (A,B,C): a = (1.5,null), b = (1,null,7) c = (3,null,9), d = (4,7,null), e = (1,5,7), f = (3,7,null), g = (4,null,9). Which one of the following statements is correct?
A. R contains a,b,e,f,g but not c, d.
B. R contains all of a,b,c,d,e,f,g
C. R contains e,f,g but not a,b
D. R contains e but not f,g.
Explaination / Solution:

Workspace
Report
Q.7
Consider two binary operators '↑' and '↓' with the precedence of operator ↓ being lower than that of the operator ↑ . Operator ↑ is right associative while operator ↓, is left associative. Which one of the following represents the parse tree for expression (7 ↓ 3 ↑ 4 ↑ 3 ↓ 2)?
A.
B.
C.
D.
Explaination / Solution:

7 ↓ 3 ↑ 4 ↑ 3 ↓ 2 7 ↓ 3 ↑ (4 ↑ 3) ↓ 2 as ↑ is right associative 7 ↓ (3 ↑ (4 ↑ 3)) ↓ 2 (7 ↓ (3 ↑ (4 ↑ 3))) ↓ 2 as ↓ is left associative

Workspace
Report
Q.8
Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables a, b, c, d and e are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

A. 2
B. 9
C. 5
D. 3
Explaination / Solution:

Total 3 Registers are required minimum

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
After the update in the previous question, the link N1-N2 goes down. N2 will reflect this change immediately in its distance vector as cost, ∞ . After the NEXT ROUND of update, what will be the cost to N1 in the distance vector of N3?
A. 3
B. 9
C. 10
D.
Explaination / Solution:

N3 has neighbors N2 and N4 N2 has made entry ∞ N4 has the distance of 8 to N1 N3 has the distance of 2 to N4 So 2 + 8 = 10

Workspace
Report
Q.10
Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S, A} and terminals {a, b}.
S → aA {print 1}
S → a {print 2}
A → Sb {print 3}
Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:
A. 1 3 2
B. 2 2 3
C. 2 3 1
D. syntax error