|
Q.1. Data
Structure and Algorithms
In a box there are random number of white and black marbles. At
a time two marbles are taken out at random and if
A) Both Black: Discard both and insert a white
B) Both White: Discard one and retain one
C) One Black and One White: Discard White and retain Black.
If initially there are nb black and nw white marbles then determine
the color of the only marble remaining at the end.
Options
1. white if nb is even
2. white if nw is odd
3. black if nb is even
4. black if nw is odd
Ans: 1
Explanation:
Here parity of black is preserved and the parity of white is neglected.
Lets consider each case
A) Both Black: Discard both and insert a white Parity of back is
preserved by discarding both, i.e if there are nb marbles then nb-2
remain. Thus if nb is even, nb-2 is also even. For nw, it becomes
nw+1 and hence parity is changed(or is not conserved).
B) Both White: Discard one and retain one Again no change to nb
and nw parity is neglected.
C) One Black and One White: Discard White and retain Black. Same
applies here also.
Thus, the color of last marble depends on nb and not on nw.
Hence, we get the following table:
| nb |
nw |
remaining |
| even |
even |
white |
| even |
odd |
white |
| odd |
even |
black |
| odd |
odd |
black |
which can be further reduce to :
| nb |
nw |
remaining |
| even |
X |
white |
| odd |
X |
black |
Q.3. Databases
Consider three tables with following number of tuples in each
S(a,b,c) = 100
R(a,d,e) = 80
T(x,d,f) = 90
Tuples in S and R with same value of attribute "a" = 60
Tuples in R and T with same value of attribute "d" = 70
Maximum and minimum number of tuples in (S left outer join R)
full outer join T is:
Options
1. 130 120
2. 150 140
3. 140 130
4. 140 120
Ans: 3
Explanation:
Consider, X = ( S left outer join R ) This will have 100
rows, with d = null for 40(100-60) rows.
X full outer join T: Here, the common values of d in
tables X and T can be between 50 and 60.
Case 1: Minimum value of common values of d between
X and T
Out of 80 values of d in R, 20 were not found in X (since X has only
60 non-null values of d). These 20 can all be the ones that were common
between S and T. In this case the common values between X and T will
be 50.
Case 2: Maximum value of common values of d between
X and T
Now assume that 20 values of d that were lost, none was common between
S and T. But this is not possible, because S has 80 tuples and 70
values are common with T. So at least 10 common values will get lost.
Thus max. value of common d's will b 60.
Now full outer join (X + T - common values of d in X and T) will be
either
100 + 90 - 50 or 100 + 90 - 60.
Thus the answer is 140,130. Hence 3
Q.4. Data Structures
- Hashing
A hash table implementation uses function of (% 7) and linear probing
to resolve collision. What is the ratio of numbers in the following
series with out collision and with collision if 7 buckets are used:
32, 56, 87, 23, 65, 26, 93
Options
1. 2,5
2. 3,4
3. 4,3
4. 5,2
Ans: 3
Explanation:
Since we're using mod 7 hash function, we've a hash table with
7 buckets numbered from 0 to 6. Any number x will be mapped
to x % 7 bucket.
Lets look at the insertion of sequence into hash table:
1. 32 is inserted into 32 % 7 = 4 i.e. 4th bucket.
2. 56 is inserted into 56 % 7 = 0 i.e. 0th bucket.
3. 87 is inserted into 87 % 7 = 3 i.e. third bucket.
3A
4. 23 is inserted into 23 % 7 = 2
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
|
23
|
87 |
32 |
|
|
5. 65 is inserted 65 % 7 = 2. Since bucket 3 also contains
23, its a collision. We'll put 65 into the next empty bucket i.e.
5
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
|
23
|
87 |
32 |
65
|
|
6. 26 is inserted into 26 % 7 = 5. However, since bucket
5 is also full, its a collision and 26 is inserted into the next empty
bucket i.e. 6.
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
|
23 |
87 |
32 |
65
|
26
|
7. 93 is inserted into 93 % 7 = 2. However, since bucket
2 is also full, its a collision and 93 is inserted into the next empty
bucket i.e. 1.
| 0 |
1 |
2 |
3 |
4 |
5 |
6 |
| 56 |
93
|
23
|
87 |
32 |
65 |
26 |
Final position of buckets will be:
| Bucket # |
Element |
Remark |
| 0 |
56 |
|
| 1 |
93 |
|
| 2 |
23 - 65 - 93 |
|
| |
65 ( move to next empty - 5) |
Collision |
| |
93 ( move to next empty - 1) |
Collision |
| 3 |
87 |
|
| 4 |
32 |
|
| 5 |
65 - 26 |
|
| |
26 (move to next empty - 6) |
Collision |
| 6 |
26 |
|
Q.5. Computer
Organization
In a certain machine data references constitute 40% of the mix,
and that the ideal CPI of the pipelined machine is 1. Assume that
the machine with structural hazards has a clock rate that is 1.05
times higher than the clock rate of machine without hazard. What
is effective speedup with pipelining without structural hazard?
Options
1. 1.05
2. 1.3
3. 1
4. none of above
Ans: 2
Explanation:
We major the average instruction time on both the machines to access
speedup/slowdown.
Avg. instruction time = CPI * clock cycle time
Since there are no stalls/hazards, the average instruction time
for ideal machine is the clock cycle times.
The average clock cycle time for the machine with 40% structural
hazard is M
= (1+0.4 x 1) x Clock cycle time ideal/1.05 = 1.3 clock cycle time
ideal
Machine without structural hazard is 1.3 times faster.
Content Provided By GateGenie.com |
