Ans .
A
A group is a set, G, together with an operation • (called the group law of G) that combines any two elements a and b to form another element, denoted a • b or ab. To qualify as a group, the set and operation, (G, •), must satisfy four requirements known as the group axioms: Closure For all a, b in G, the result of the operation, a • b, is also in G.b Associativity For all a, b and c in G, (a • b) • c = a • (b • c). Identity element There exists an element e in G, such that for every element a in G, the equation e • a = a • e = a holds. Such an element is unique (see below), and thus one speaks of the identity element. Inverse element For each a in G, there exists an element b in G such that a • b = b • a = e, where e is the identity element. The result of an operation may depend on the order of the operands. In other words, the result of combining element a with element b need not yield the same result as combining element b with element a; the equation a • b = b • a may not always be true. This equation always holds in the group of integers under addition, because a + b = b + a for any two integers (commutativity of addition). Groups for which the commutativity equation a • b = b • a always holds are called abelian groups
Ans .
A
Chromatic number of a graph is the minimum number of colors required to color all vertices such that no two adjacent vertices are colored with same color. Since here we have no odd cycle, we can color whole graph with only 2 colors, coloring the vertices with alternate colors. So option (A) is correct.
Ans .
B
Since the graph is simple, there must not be any self loop and parallel edges. Since the graph is connected, the degree of any vertex cannot be 0. Therefore, degree of all vertices should be be from 1 to n-1. So the degree of at least two vertices must be same.
Ans .
D
R is not symmetric as (x, y) is present, but (y, x) is not present in R. R is also not antisymmetric as both (x, z) and (z, x) are present in R.
Ans .
C
Hardware detects interrupt immediately, but CPU acts only after its current instruction. This is followed to ensure integrity of instructions.
Ans .
B
\[(1217)_{8}=(001 010 001 111)_{8} =(0010 1000 1111)=(28F)_{16}\]
Ans .
B
AB+C = (A+C)(B+C) = ((A+C)' + (B+C)')' So, '3' 2-input NOR gates are required.
Ans .
A
Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm.
Ans .
B
A page table entry must contain Page frame number. Virtual page number is typically used as index in page table to get the corresponding page frame number.
Ans .
A
selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort. Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading. This is generally the case if the items are huge but the keys are small.
Ans .
B
string generated by this language is a,b,aba,bab,aabaa,.....all this strings are odd length palindromes
Ans .
B
Bellman-ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.
Ans .
C
If a problem is both NP hard and NP, then it is NP Complete.
Ans .
C
The regular expression has two 0′s surrounded by (0+1)* which means accepted strings must have at least 2 0′s.
Ans .
D
Deterministic PDA cannot handle languages or grammars with ambiguity, but NDPDA can handle languages with ambiguity and any context-free grammar. So every nondeterministic PDA can not be converted to an equivalent deterministic PDA
Ans .
C
We need 256 Kbytes, i.e., 256 x 1024 x 8 bits. We have RAM chips of capacity 32 Kbits = 32 x 1024 bits. (256 * 1024 * 8)/(32 * 1024) = 64
Ans .
B
Regular expressions are used in lexical analysis. Pushdown automata is related to context free grammar which is related to syntax analysis. Dataflow analysis is done in code optimization. Register allocation is done in code generation.
Ans .
B
Let x is stored at location 2468 i.e. &x = 2468
(dots are use just to ensure alignment)
x = 15 fun(5, 2468)
...{t = fun(4, 2468)
.......{t = fun(3, 2468)
...........{t = fun(2,2468)
...............{t = fun(1, 2468)
...................{// x=1
........................return 1}
................t = 1
................f = 2 //1+1 //since *f_p is x
................x = t = 1
................return 2}
...........t = 2
...........f = 2+1
...........x = t = 2
...........return 3}
........t = 3
........f = 3+2
........x = t = 3
........return 5}
....t = 5
....f = 5+3
....x = t = 5
....return 8}
which implies fun (5,2468) is 8.
Ans .
A
Coupling between modules can be ranked in the order of strongest to weakest as follows:
Content Coupling >> Common Coupling >> External Coupling >> Control Coupling >> Stamp Coupling >> Data Coupling
Content Coupling: Occurs when one module modifies or relies on the internal workings of another module
Common Coupling: Occurs when two modules share the same global data
External Coupling: Occurs when two modules share an externally imposed data format or communication protocol
Control Coupling: One module controlling the flow of another, by passing it information
Stamp Coupling: Occurs when modules share a composite data structure and use only parts of it
Data coupling: Occurs when modules share data through parameters
Ans .
C
cd ab ef ij gh ab -> rowspan "2" cd -> colspan "2" 1st row closed <tr> is row <td> is data ef placed in 2nd row. gh is in same row but rowspan "2" 2nd row also closed. Move to 3rd row. Insert ij . its colspan "2".
Ans .
B
Let Xi be the probability that the face value is i.
We can say that
X1 + X2 + X3 + X4 + X5 + X6 = 1
It is given that
(X1 + X3 + X5) = 0.9*(X2 + X4 + X6)
It is also given that X2 = X4 = X6
Also given that (X4 + X6)/(X4 + X5 + X6) = 0.75
Solving the above equations, we can get X3 as 0.468
Ans .
C
An element is a generator for a cyclic group if on repeated applications of it upon itself, it can generate all elements of group. For example here : a*a = a, then (a*a)*a = a*a = a, and so on. Here we see that no matter how many times we apply a on itself, we can't generate any other element except a, so a is not a generator. Now for b, b*b = a. Then (b*b)*b = a*b = b. Then (b*b*b)*b = b*b = a, and so on. Here again we see that we can only generate a and b on repeated application of b on itself. So it is not a generator. Now for c, c*c = b. Then (c*c)*c = b*c = d. Then (c*c*c)*c = d*c = a. Then (c*c*c*c)*c = a*c = c. So we see that we have generated all elements of group. So c is a generator. For d, d*d = b. Then (d*d)*d = b*d = c. Then (d*d*d)*d = c*d = a. Then (d*d*d*d)*d = a*d = d. So we have generated all elements of group from d, so d is a generator. So c and d are generators. So option (C) is correct.
Ans .
D
This statement can be expressed as => For all X, x can be either gold or silver then the ornament X is precious => For all X, (G(X) v S(x)) => P(X).
Ans .
D
(1-tanx)/(1+tanx) = (cosx - sinx)/(cosx + sinx) Let cosx + sinx = t (-sinx + cosx)dx = dt (1/t)dt = ln t => ln(sinx + cosx) => ln(sin Π/4 + cos Π/4) => ln(1/√2 + 1/√2) => 1/2 ln 2
Ans .
B
Stage Si is allocated to instruction Ii iff
1. Eligibility: Ii must have completed Si-1 ... X time
2. Availability: Ii-1 must have released Si ... Y time
Time of allocation = Max(X,Y)
In first iteration:
I1 completes after 5th cycle
I2 completes after 10th cycle
I3 completes after 13th cycle
I4 completes after 15th cycle
In second iteration
I1 completes after 16th cycle
I2 completes after 18th cycle
I3 completes after 21th cycle
I4 completes after 23th cycle
Answer : B
Ans .
D
16 blocks and sets with 4 blocks each means there are 4 sets.So, the lower 2 bits are used for getting a set and 4-way associative means in a set only the last 4 cache accesses can be stored.
0, 255, 1, 4, 3, 8, 133, 159, 216, 129, 63, 8, 48, 32, 73, 92, 155
mod 4 gives,
0, 3, 1, 0, 3, 0, 1, 3, 0, 1, 3, 0, 0, 0, 1, 0, 3
Now for each of 0..3, the last 4accesses will be in cache.
So, {92, 32, 48, 8}, {155, 63, 159, 3}, {73, 129, 133, 1} and {}will be in cache.
So, the missing element from choice is 216.
Ans .
A
We can apply the following Deadlock Detection algorithm and see that there is no process waiting indefinitely for a resource.
Ans .
B
4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Since shortest seek time first policy is used, head will first move to 34. This move will cause 16*1 ms. After 34, head will move to 20 which will cause 14*1 ms. And so on. So cylinders are accessed in following order 34, 20, 19, 15, 10, 7, 6, 4, 2, 73 and total time will be (16 + 14 + 1 + 4 + 5 + 3 + 1 + 2 + 2 + 71)*1 = 119 ms.
Ans .
A
The above solution is a simple test-and-set solution that makes sure that deadlock doesn’t occur, but it doesn’t use any queue to avoid starvation or to have FIFO order.
Ans .
B
The size of page table may become too big to fit in contiguous space. That is why page tables are typically divided in levels.
Ans .
A
T(n) = cn + T(n/3) = cn + cn/3 + T(n/9) = cn + cn/3 + cn/9 + T(n/27) Taking the sum of infinite GP series. The value of T(n) will be less than this sum.
T(n) <= cn(1/(1-1/3)) <= 3cn/2
Therefore T(n) =\(\theta(n)\)
Ans .
B
AVL trees are binary trees with the following restrictions. 1) the height difference of the children is at most 1.
2) both children are AVL trees
Ans .
B
Answer(B) The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get \(\theta(nlogn)\)
Ans .
C
The language L1 accept strings {c, abc, abcab, aabbcab, aabbcaabb, …} and L2 accept strings {a, b, c, ab, abc, aabc, aabbc, … }. Intersection of these two languages is \(L1\cap L2\) = {\(a^{k}b^{k}c\) | k >= 0} which is context free, but not regular
Ans .
B
II is false, in recursion, compiler cannot determine the space needed for recursive calls. III is false.
Ans .
B
We have used left biasing in B+ Tree construction as biasing is important in B+ tree because all the keys have to present at the leaf nodes. In a B+ tree, insertion always happens at the leaf level, because that is where all the data resides. The nodes above the leaf level contain only keys that serve to guide the search, which may be copies of actual keys. The leaf layer is often called a 'sequence set' whereas the internal nodes make up the 'index'. When a leaf splits, a suitable separator key(which is the middle one) is copied up into the index layer.
Ans .
A
I and II describe the division operator in Relational Algebra and tuple relational calculus respectively.
Ans .
B
I is true because below is true in RSA Cryptosystem.
Encrypted-Text = (Plain-Text)e mod n
Plain-Text = (Encrypted-Text)d mod n
III is true because below is true
d-1 = e mod ϕ(n) OR
ed = 1 mod ϕ(n)
Ans .
A
The maximum packet lifetime is given to be 64 seconds in the question. Thus, a sequence number increments after every 64 seconds.
So, minimum permissible rate = 1 / 64 = 0.015 per second
Thus, option (A) is the answer.
Ans .
C
The context diagram depict the system as a single bubble. Control information should not represent in DFD.
Ans .
B
TRUE: The cyclomatic complexity of a module is the number of decisions in the module plus one,where a decision is effectively any conditional statement in the module.
TRUE: The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.
Ans .
C
The smallest division is sector. Sectors are then combined to make a track. Cylinder is formed by combining the tracks which lie on same dimension of the platters. Read write head access the disk. Head has to reach at a particular track and then wait for the rotation of the platter so that the required sector comes under it. Here, each platter has two surfaces, which is the r/w head can access the platter from the two sides, upper and lower. So,<400,16,29> will represent 400 cylinders are passed(0-399) and thus, for each cylinder 20 surfaces (10 platters * 2 surface each) and each cylinder has 63 sectors per surface. Hence we have passed 0-399 = 400 * 20 * 63 sectors + In 400th cylinder we have passed 16 surfaces(0-15) each of which again contains 63 sectors per cylinder so 16 * 63 sectors. + Now on the 16th surface we are on 29th sector. So, sector no = 400x20x63 + 16×63 + 29 = 505037
Ans .
C
(a)<0,15,31> 0th cylinder 15th surface and 31st sector So, 0 cylinders passed 0*20*63 As each cylinder has 20 surfaces and each surface has 63 sectors. + 15 surfaces passed (0-14) 15*63 As each surface has 63 sectors + We are on 31st sector So, sector no. =0*20*63+15*63+31=976 sector. Which is not equal to 1039. (b)<0,16,30> Similarly this represents, 0*20*63 + 16*63 (0-15 sectors and each sector has 63 sectors) + 30 sectors on 16th sector Sector no = 0*20*63+16*63+30=1038 sector which is not equal to 1039. (c)<0,16,31> Similarly this represents, 0*20*63 + 16*63 (0-15 sectors and each sector has 63 sectors) + 31 sectors on 16th sector Sector no = 0*20*63+16*63+31=1039 sector which is equal to 1039. Hence,option c is correct. (d)<0,17,31> Similarly this represents, 0*20*63 + 17*63 (0-16 sectors and each sector has 63 sectors) + 31 sectors on 17th sector Sector no = 0*20*63+17*63+31=1102 sector which is not equal to 1039.
Ans .
C
there are two cases for X[0..i] and Y[0..j]
1) The last characters of two strings match. The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]
2) The last characters don't match. The length of lcs is max of following two lcs values
a) LCS of X[0..i-1] and Y[0..j]
b) LCS of X[0..i] and Y[0..j-1]
Ans .
B
The value can be computed either in row major or column major order, We can swap the two loops without effecting the output.
Ans .
A
The subquery “SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’” gives pids of parts which are not blue. The bigger subquery “SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’)” gives sids of all those suppliers who have supplied blue parts. The complete query gives the names of all suppliers who have supplied a non-blue part
Ans .
A
A relation is in BCNF if for every one of its dependencies X → Y, at least one of the following conditions hold: X → Y is a trivial functional dependency (Y ⊆ X) X is a superkey for schema R Since (sname, city) forms a candidate key, there is no non-tirvial dependency X → Y where X is not a superkey
Ans .
D
Transmission delay for 1 frame = 1000/(10^6) = 1 ms Propagation time = 25 ms The sender can atmost transfer 25 frames before the first frame reaches the destination. The number of bits needed for representing 25 different frames = 5
Ans .
B
Size of sliding window = 2^5 = 32 Transmission time for a frame = 1ms Total time taken for 32 frames = 32ms The sender cannot receive acknoledgement before round trip time which is 50ms After sending 32 frames, the minimum time the sender will have to wait before starting transmission of the next frame = 50 – 32 = 18
Ans .
C
A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data. In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.
Ans .
D
For Heap trees, deletion of a node includes following two operations. 1) Replace the root with last element on the last level. 2) Starting from root, heapify the complete tree from top to bottom..