Question 1 
Two hosts are connected via a packet switch with 10^{7} bits per second links. Each link has a propagation delay of 20 microseconds. The switch begins forwarding a packet 35 microseconds after it receives the same. If 10000 bits of data are to be transmitted between the two hosts using a packet size of 5000 bits, the time elapsed between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is _______.
(1575)  
(1576)  
(1577)  
(1578) 
Bandwidth of the each link is 10^{7} bits/sec.
Given that propagation delay between host to switch and switch to host is same i.e. 20 microseconds.
Given that 35 microseconds of buffering time is required by the switch.
Total data we need to send is 10000 bits.
Given that packet size is 5000 bits.
Number of packets we need to send is 10000/5000 = 2 packets.
Total time for the first packet to reach from source to switch = Transmission time + propagation time
Transmission time=(5000 bits)/(10^{7} bits/sec) = 500 microseconds
Total time between source to switch is = 500 + 20 = 520 microseconds
Time required for the packet to reach from switch to destination is = Buffer time+Transmission time + propagation time = 35 + 500 + 20 = 555 microseconds.
Total time required for the first packet to reach to destination from the source = 520 + 555 =1075 microseconds.
While transferring first packet from switch to destination source starts sending of it's second packet to switch, that means from 1055 microsecond on wards transmission of 2nd packet is started by the source.
By the time first packet is reached to the destination 2nd packet is completely available at the switch.
Time required for the 2nd packet to reach to the destination from the switch is
= transmission time + propagation time = 500+20 = 520 microseconds
Therefore total time required for the two packets to reach to destination from the source = 1055+ 520 = 1575 microseconds.
Question 2 
If x is real and x^{2}  2x + 3 = 11, then possible values of  x^{3} + x^{2}  x include
2, 4  
2, 14  
4, 52  
14, 52 
x^{2}  2x + 3 = 11, x is real
x^{2}2x+3 = 11
x^{2}2x+8 = 0
(x4)(x+2) = 0
x = 4, 2
x^{2}2x+3 = 11
x^{2}2x+14 = 0
x is not real in this case.
x^{3}+x^{2}x
when x=2
⇒ (2)^{3}+(2)^{2}(2)
= ((8) + (4) + 2 = 14
x=4
⇒ (4)^{3}+(4)^{2}(4)
= 64 + 16 4
= 52
Possible values of x^{3}+x^{2}x include 14, 52.
Question 3 
What is the maximum number of reduce moves that can be taken by a bottomup parser for a grammar with no epsilon and unitproduction (i.e., of type A → є and A → a) to parse a string with n tokens?
n/2  
n1  
2n1  
2^{n} 
1) epsilon production
2) production of the form A → a
Consider the grammar:
S → Sa  a
If we were to derive the string “aaa” whose length is 3 then the number of reduce moves that would have been required are shown below:
S → Sa
→ Saa
→ aaa
This shows us that it has three reduce moves. The string length is 3 and the number of reduce moves is also 3. So presence of such kinds of production might give us the answer “n” for maximum number of reduce moves. But these productions are not allowed as per the question.
Also note that if a grammar does not have unit production then the maximum number of reduce moves can not exceed “n” where “n” denotes the length of the string.
3) No unit productions
Consider the grammar:
S → A
A → B
B → C
C → a
If we were to derive the string “a” whose length is 1 then the number of reduce moves that would have been required are shown below:
S → A
A → B
B → C
C → a
This shows us that it has four reduce moves. The string length is 1 and the number of reduce moves is 4. So presence of such kind of productions might give us the answer “n+1” or even more, for maximum number of reduce moves. But these productions are not allowed as per the question.
Now keeping in view the above points suppose we want to parse the string “abcd”. (n = 4) using bottomup parsing where strings are parsed finding the rightmost derivation of a given string backwards. So here we are concentrating on deriving right most derivations only.
We can write the grammar which accepts this string which in accordance to the question, (i.e., with no epsilon and unitproduction (i.e., of type A → є and A → B) and no production of the form A → a) as follows:
S → aB
B → bC
C → cd
The Right Most Derivation for the above is:
S → aB (Reduction 3)
→ abC (Reduction 2)
→ abcd (Reduction 1)
We can see here the number of reductions present is 3.
We can get less number of reductions with some other grammar which also doesn’t produce unit or epsilon productions or production of the form A → a
S → abA
A → cd
The Right Most Derivation for the above is:
S → abA (Reduction 2)
→ abcd (Reduction 1)
Hence 2 reductions.
But we are interested in knowing the maximum number of reductions which comes from the 1st grammar. Hence total 3 reductions as maximum, which is (n – 1) as n = 4 here.
Question 4 
R) False. We can give counter example. Let G has 5 vertices and 9 edges which is planar graph. Assume degree of one vertex is 2 and of all others are 4. Now, L(G) has 9 vertices (because G has 9 edges) and 25 edges. But for a graph to be planar,
E ≤ 3v  6
For 9 vertices E ≤ 3 × 9  6
⇒ E ≤ 27  6
⇒ E ≤ 21. But L(G) has 25 edges and so is not planar.
As (R) is false, option (B) & (C) are eliminated.
Question 5 
Which one of the following is NOT logically equivalent to ¬∃x(∀y(α) ∧ ∀z(β))?
∀x(∃z(¬β)→∀y(α))  
∀x(∀z(β)→∃y(¬α))  
∀x(∀y(α)→∃z(¬β))  
∀x(∃y(¬α)→∃z(¬β)) 
∀x(∃z(¬β) → ∀y(α))
⇒ ∀x(¬∃z(¬β) ∨ ∀y(α))
⇒ ∀x(∀z(β)∨y(α))
⇒ ¬∃x¬(∀z(β)∨∀y(α))
⇒ ¬∃x(¬∀z(β)∧¬∀y(α))
A is Not equivalent to the given.
Option B:
∀x(∀z(β)→∃y(¬α))
⇒ ∀x(¬∀z(β)∨∃y(¬α))
⇒ ¬∃x¬(¬∀z(β)∨∃y(¬α))
⇒ ¬∃x(∀z(β)∨∀y(α))
B is Matching and equivalent to given.
Option C:
∀x(∀y(α)→∃z(¬β))
⇒ ∀x(¬∀y(α)∨∃z(¬β))
⇒ ¬∃x¬(¬∀y(α)∨∃z(¬β))
⇒ ¬∃x(∀y(α)∧z(β))
C is equivalent to the given.
Option D:
∀x(∃y(¬α)→∃z(¬β))
⇒ ∀x(¬∃y(¬α)∨∃z(β))
⇒ ∀x(∀y(α)∨∃z(β))
⇒ ¬∃x¬(∀y(α)∨∃z(β))
⇒ ¬∃x(¬∀y(α)∧¬∃z(β))
⇒ ¬∃x(¬∀y(α)∧∀z(¬β))
So D is Not equivalent to the given.
Question 6 
A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of code (LOC) developed using L2 is estimated to be twice the LOC developed with Ll. The product will have to be maintained for five years. Various parameters for the company are given in the table below.
Total cost of the project includes cost of development and maintenance. What is the LOC for L1 for which the cost of the project using L1 is equal to the cost of the project using L2?
4000  
5000  
4333  
4667 
Question 7 
A company needs to develop digital signal processing software for one of its newest inventions. The software is expected to have 40000 lines of code. The company needs to determine the effort in personmonths needed to develop this software using the basic COCOMO model. The multiplicative factor for this model is given as 2.8 for the software development on embedded systems, while the exponentiation factor is given as 1.20. What is the estimated effort in personmonths?
234.25  
932.50  
287.80  
122.40 
Question 8 
HTML (Hyper Text Markup Language) has language elements which permit certain actions other than describing the structure of the web document. Which one of the following actions is NOT supported by pure HTML (without any server or client side scripting) pages?
Embed web objects from different sites into the same page  
Refresh the page automatically after a specified interval  
Automatically redirect to another page upon download  
Display the client time as part of the page 
Question 9 
Which of the following is NOT desired in a good Software Requirement Specifications (SRS) document?
Functional Requirements  
NonFunctional Requirements  
Goals of Implementation  
Algorithms for Software Implementation 
Question 10 
The following is the comment written for a C function
/* This function computes the roots of a quadratic equation a.x^2 + b.x + c = . 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 discreminant is positive (iii) When discriminant is zero (iv) When discriminant is negative. Only in case (ii) and (iii) the stored roots are valid. Otherwise 0 is stored in roots. The function returns 0 when the roots are valid and 1 otherwise. The function 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 option provide the set of nonredundant tests using equivalence class partitioning approach from input perspective for black box testing?
T1, T2, T3, T6  
T1, T3, T4, T5  
T2, T4, T5, T6  
T2, T3, T4, T5 
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
T5 : D > 0
T6 : D < 0
Question 11 
Consider a network with five nodes, N1 to N5 as shown below.
The network 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 the 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 N2N3 reduces to 2(in both directions). After the next round of updates, what will be the new distance vector at node, N3.
(3, 2, 0, 2, 5)  
(3, 2, 0, 2, 6)  
(7, 2, 0, 2, 5)  
(7, 2, 0, 2, 6) 
Question 12 
The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side?
19  
21  
20  
10 
Question 13 
What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle?
P. Requirements Capture 1. Module Development and Integration Q. Design 2. Domain Analysis R. Implementation 3. Structural and Behavioral Modeling S. Maintenance 4. Performance Tuning
P3, Q2, R4, S1  
P2, Q3, R1, S4  
P3, Q2, R1, S4  
P2, Q3, R4, S1 
Question 14 
The following program is to be tested for statement coverage:
begin if (a== b) {S1; exit;} else if (c== d) {S2;] else {S3; exit;} S4; end
The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given. T1 : a, b, c and d are all equal T2 : a, b, c and d are all distinct T3 : a = b and c != d T4 : a != b and c = d Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?
T1, T2, T3  
T2, T4  
T3, T4  
T1, T2, T4 
T2 covers S3
T4 covers S2, S4.
Question 15 
The coupling between different modules of a software is categorized as follows:
 I. Content coupling
II. Common coupling
III. Control coupling
IV. Stamp coupling
V. Data coupling
Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows:
IIIIIIIVV  
VIVIIIIII  
IIIIVIIIV
 
IVIIVIIII 
Question 16 
Consider the HTML table definition given below:
The number of rows in each column and the number of columns in each row are:
〈2, 2, 3〉 and 〈2, 3, 2〉  
〈2, 2, 3〉 and 〈2, 2, 3〉  
〈2, 3, 2〉 and 〈2, 3, 2〉  
〈2, 3, 2〉 and 〈2, 2, 3〉 
Question 17 
Which of the following statements are TRUE?

I. The context diagram should depict the system as a single bubble.
II. External entities should be identified clearly at all levels of DFDs.
III. Control information should not be represented in a DFD.
IV. A data store can be connected either to another data store or to an external entity.
II and III  
II and III  
I and III  
I, II and III 
Question 18 
Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE?
 I. The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph.
II. 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.
III. The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.
I and II  
II and III  
I and III  
I, II and III 
Question 19 
A hard disk has 63 sectors per track, 10 platters each with 2 recording surfaces and 1000 cylinders. The address of a sector is given as a triple
The address of the 1039^{th} sector is
〈0, 15, 31〉
 
〈0, 16, 30〉  
〈0, 16, 31〉  
〈0, 17, 31〉 
From the given options we can calculate the sector numbers as
Option A  15*63+31 = 976
Option B  16*63+30 = 1038
Option C  16*63+31 = 1039
Option D  17*63+31 = 1102
Hence Option C is the answer.
Question 20 
Consider the table employee(empId, name, department, salary) and the two queries Q_{1},Q_{2} below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table?
Q_{1} : Select e.empId From employee e Where not exists (Select * From employee s where s.department = “5” and s.salary >= e.salary) Q_{2} : Select e.empId From employee e Where e.salary > Any (Select distinct salary From employee s Where s.department = “5”)
Q_{1} is the correct query  
Q_{2} is the correct query  
Both Q_{1} and Q_{2} produce the same answer  
Neither Q_{1} nor Q_{2} is the correct query 
Query 1: Results the empId's which have higher salary than anyone in the department 5.
Query 2: Results the empId's which have higher salary than atleast one employee of department 5.
Question 21 
A relation R is defined on ordered pairs of integers as follows: (x,y) R(u,v) if x < u and y > v. Then R is: Then R is:
Neither a Partial Order nor an Equivalence Relation  
A Partial Order but not a Total Order  
A Total Order  
An Equivalence Relation 
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is partial order relation then it must be
i) Reflexive
ii) Antisymmetric
iii) Transitive
If a relation is total order relation then it must be
i) Reflexive
ii) Symmetric
iii) Transitive
iv) Comparability
Given ordered pairs are (x,y)R(u,v) if (x
Here <, > are using while using these symbol between (x,y) and (y,v) then they are not satisfy the reflexive relation. If they uses (x<=u) and (y>=u) then reflexive relation can satisfies.
So, given relation cannot be a Equivalence. Total order relation or partial order relation.
Question 22 
And since every attribute is key so the decomposed relation will be in BCNF and hence in 3NF.
Question 23 
Now since all the attributes are keys, so R1 ∩ R2 will be a key of the decomposed relation.
And since every attribute is key so the decomposed relation will be in BCNF and hence in 3NF.
Question 24 
(a) Mr. X claims the following:
If a relation R is both symmetric and transitive, then R is reflexive. For this, Mr. X offers the following proof:
"From xRy, using symmetry we get yRy. Now because R is transitive, xRy and yRy together imply xRx. Therefore, R is reflexive."
Briefly point out the flaw in Mr. X's proof.
(b) Give an example of relation R which is symmetric and transitive but not reflexive.
Theory Explanation 
Question 25 
Let G be a finite group and H be a subgroup of G. For a∈G, define aH = {ahh∈H}
(a) Show that aH  H
(b) Show that for every pair of elements a, b∈G, either aH=bH or aH and bH are disjoint.
(c) Use the above to argue that the order of H must divide the order of G.
Theory Explanation. 
Question 26 
Let G be a connected, undirected graph. A cut in G is a set of edges whose removal results in 0 being broken into two or more components which are not connected with each other. The size of a cut is called its cardinality. A mencut of G is a cut in G of minimum cardinality. Consider the following graph.
(a) Which of the following sets of edges is a cut?
(i) {(A,B), (E,F), (B,D), (A,E), (A,D)}
(ii) {(B,D), (C,F), (A,B)}
(b) What is the cardinality of a mincut in the graph?
(c) Prove that if a connected undirected graph G with n vertices has a mincut of cardinality K, then G has atleast (nk/2) edges.
Theory Explanation. 
Question 27 
(a) Given that A is regular and A∪B is regular, does it follow that B is necessarily regular? Justify your answer.
(b) Given two finite automata M1, M2, outline an algorithm to decide if L(M1)⊆L(M2). (note: strict subset)
Theory Explanation. 
Question 28 
Show that the language L = {xcx x ∈ {0,1}* and c is a terminal symbol} is not context free, c is not 0 or 1.
Theory Explanation. 
Question 29 
Let A be an n×n matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree which finds 1^{st}, 2^{nd} and 3^{rd} smallest elements in minimum number of comparisons.
Theory Explanation. 
Question 30 
Let synthesized attribute val give the value of the binary number generated by S in the following grammar. For example, on output 101.101, S.val = 5.625.
S → LLL L → LBB B → 01
Write Sattributed values corresponding to each of the productions to find S.val.
Theory Explanation. 
Question 31 
Suppose we have a function HALTS which when applied to any arbitrary function f and its arguments will say TRUE if function f terminates for those arguments and FALSE otherwise. Example, Given the following function definition.
FACTORIAL (N) = IF(N=0) THEN 1 ELSE N*FACTORIAL (N1)
Then HALTS(FACTORIAL 4) = TRUE and HATS(FACTORIAL  5) = FALSE
Let us define the function FUNNY(f) = IF HALTS(ff) THEN not(ff) ELSE TRUE
(a) Show that FUNNY terminates for all functions f.
(b) Use (a) to prove (by contradiction) that it is not possible to have a function like HALTS which for arbitrary functions and inputs says whether it will terminate on that input or not.
Theory Explanation. 
Question 32 
(a) Consider the following algorithm. Assume procedure A and procedure B take O(1) and O(1/n) unit of time respectively. Derive the time complexity of the algorithm in Onotation.
algorithm what (n) begin if n = 1 then call A else begin what (n1); call B(n) end end.
(b) Write a constant time algorithm to insert a node with data D just before the node with address p of a singly linked list.
Theory Explanation. 
Question 33 
(a) In a binary tree, a nil node is defined to be a node with 2 children. Use induction on the height of the binary tree to prove that the number of full nodes plus one is equal to the number of leaves.
(b) Draw a minheap that results from insertion of the following elements in order into an initially empty minheap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.
Theory Explanation. 
Question 34 
An instruction pipeline consists of 4 stages: Fetch(F), Decode operand field (D), Execute (E), and ResultWrite (W). The five instructions in a certain instruction sequence need these stages for the different number of clock cycles as shown by the table below.
Find the number of clock cycles needed to perform the 5 instructions.
Theory Explanation. 
Question 35 
(a) Show that the formula [(~p ∨ q) ⇒ (q ⇒ p)] is not a tautology.
(b) Let A be a tautology and B be any other formula. Prove that (A ∨ B) is a tautology.
Theory Explanation. 
Question 36 
What will be the output of the following program assuming that parameter passing is
 (i) call by value
(ii) call by reference
(iii) call by copy restore
procedure P{x, y, z}; begin y:y+1; z: x+x end; begin a:= b:= 3; P(a+b, a, a); Print(a) end.
Theory Explanation. 
Question 37 
Consider the following pascal program skeleton:
program sort(...);var a,x,...; procedure readarray; var i,....; begin ...:=a... end; procedure exchange(...); begin ...:=a... ...:=x... end; procedure qsort(...); var k,v,...; function partition (...)...; var i,j,...; begin ...:=a... ...:=v... end; begin . . end; begin . . end;
Assume that at a given point in time during program execution, following procedures are active: sort, qsort(1,9), qsort(1.3), partition(1,3), exchange(1,3).
Show snapshots of the runtime stack with access links after each of the activations.
Theory Explanation. 
Question 38 
Consider the following program fragment in the assembly language of a certain hypothetical processor. The processor has three general purpose registers R1, R2 and R3. The meanings of the instructions are shown by comments (starting with 😉 after the instructions.
X: CMP R1, 0 ; Compare R1 and 0, set flags appropriately in status register JZ Z ; Jump if zero to target Z MOV R2, R1 ; Copy contents of R1 to R2 SHR R1 ; Shift right R1 by 1 bit SHL R1 ; Shift left R1 by 1 bit CMP R2, R1 ; Compare R2 and R1 and set flag in status register JZ Y ; Jump if zero to target Y INC R3 ; Increment R3 by 1; Y: SHR R1 ; Shift right R1 by 1 bit JMP X ; Jump to target X Z:...
(a) Initially R1, R2 and R3 contain the value 5, 0 and 0 respectively. What are the final values of R1 and R3 when control reaches Z?
(b) In general, if R1, R2 and R3 initially contain the values n, 0 and 0 respectively. What is the final value of R3 when control reaches Z?
Theory Explanation. 
Question 39 
Design a 2K x 8 (2048 locations, each 8 bit wide) memory system mapped at addresses (1000)_{16} to (17FF)_{16} for the 8085 processor using four 1K x 4 memory chips. Each of these chips has the following signal pins:
 (i) (Chip select, data lines are in high impedance state when it is 1)
(ii) (0 for read operation)
(iii) (0 for write operation)
(iv) A_{0}, A_{1}, …A_{9}(input address lines. A_{0} is the lest significant)
(v) D_{0}, D_{1}, D_{2}, D_{3}(bidirectional data lines. D_{0} is the least significant)
Theory Explanation. 
Question 40 
A certain computer system has the segmented paging architecture for virtual memory. The memory is byte addressable. Both virtual and physical address spaces contain 2^{16} bytes each. The virtual address space is divided into 8 nonoverlapping equal size segments. The memory management unit (MMU) has a hardware segment table, each entry of which contains the physical address of the page table for the segments. Page tables are stored in the main memory and consists of 2 byte page table entries.
(a) What is the minimum page size in bytes so that the page table for a segment requires at most one page to store it? Assume that the page size can only be a power of 2.
(b) Now suppose that the pages size is 512 bytes. It is proposed to provide a TLB (Transaction lookaside buffer) for speeding up address translation. The proposed TLB will be capable of storing page table entries for 16 recently referenced virtual pages, in a fast cache that will use the direct mapping scheme. What is the number of tag bits that will need to be associated with each cache entry?
(c) Assume that each page table entry contains (besides other information) 1 valid bit, 3 bits for page protection and 1 dirty bit. How many bits are available in page table entry for storing the aging information for the page? Assume that the page size is 512 bytes.
Theory Explanation. 
Question 41 
(a) A certain processor provides a 'test and set' instruction that is used as follows:
TEST register, flag
This instruction atomically copies flag to register and sets flag to 1. Give pseudocode for implementing the entry and exit code to a critical region using this instruction.
(b) Consider the following solution to the producerconsumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of count and assignment to count are atomic operations.
Producer: Repeat Produce an item; if count = 1 then sleep; place item in buffer. Count = 1; Wakeup(Consumer); Forever Consumer: Repeat if count = 0 then sleep; Remove item from buffer; Count = 0; Wakeup(Producer); Consume item; Forever;
Show that in this solution it is possible that both the processes are sleeping at the same time.
Theory Explanation. 
Question 42 
Consider a Btree with degree m, that is, the number of children, c, of any internal node (except the root) is such that m ≤ c ≤ 2m1. Derive the maximum and minimum number of records in the leaf nodes for such a Btree with height h, h≥1. (Assume that the root of a tree is at height 0.)
Theory Explanation. 
Question 43 
Consider the set of relations
EMP(Employeeno, Deptno, Employeename, Salary) DEPT(Deptno, Deptname, Location)
Write an SQL query to:
(a) Find all employee names who work in departments located at "Calcutta" and whose salary is greater than Rs. 50,000.
(b) Calculate, for each department number, the number of employees with a salary greater than Rs. 100,000.
Theory Explanation. 
Question 44 
(a) Two friends agree to meet at a park with the following conditions. Each will reach the park between 4:00 p.m. and 5:00 p.m. and will see if the other has already arrived. If not, they will wait for 10 minutes or the end of the hour whichever is earlier and leave. What is the probability that the two will not meet?
(b) Given a regular expression for the set of binary strings where every 0 is immediately followed by exactly k 1's and preceded by atleast k 1's (k is a fixed integer).
Theory Explanation. 
Question 45 
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language:
L = {w ∈ {0,1}*  w interpreted as a binary number (ignoring the leading zeros) is divisible by 5}
Theory Explanation. 
Question 46 
(a) The implication gate shown below, has two inputs (x and y), the output is 1 except when x=1 and y=0. Realize f = x'y + xy' using only four implication gates.
(b) Show that the implication gate is functionally complete.
Theory Explanation. 
Question 47 
(a) Solve the following recurrence relation:
x_{n} = 2x_{n1}  1, n>1 x_{1} = 2
(b) Consider the grammar
S → Aa  b A → Ac  Sd  ε
Construct an equivalent grammar with no left recursion and with minimum number of production rules.
Theory Explanation. 
Question 48 
(a) Suppose we have a database consisting of the following three relations.
FREQUENTS(student, parlor) giving the parlors each student visits.
SERVES(parlor, icecream) indicating what kind of icecreams each parlor serves.
LIKES(student, icecream) indicating what icecreams each parlor serves.
(Assuming that each student likes at least one icecream and frequents at least one parlor)
Express the following in SQL:
Print the students that frequent at least one parlor that serves some icecream that they like.
(b) In a computer system where the 'bestfit' algorithm is used for allocating 'jobs' to 'memory partitions', the following situation was encountered:
When will the 20K job complete? Note  This question was subjective type.
Theory Explanation. 
Question 49 
(a) Find the points of local maxima and minima, if any, of the following function defined in 0 ≤ x ≤ 6.
x^{3}  6x + 9x  15
(b) Integrate
Theory Explanation. 
Question 50 
Derive the expression for the number of expressions required to solve a system of linear equations in n unknowns using the Gaussian Elimination Method. Assume that one operation refers to a multiplication followed by an addition.
Theory Explanation. 
Question 51 
(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n3)/2.
(b) Let R be a binary relation on A = {a, b, c, d, e, f, g, h} represented by following two component digraph. Find the smallest integers m and n such that mm = R^{n}.
Theory Explanation. 
Question 52 
Suppose A = {a,b,c,d} and Π_{1} is the following partition of A
Π_{1} = {{a,b,c}{d}}
(a) List the ordered pairs of the equivalence relations induced by Π_{1}.
(b) Draw the graph of the above equivalence relation.
(c) Let Π_{2} = {{a},{b},{C},{d}}
Π_{3} = {{a,b,c,d}}
and Π_{4} = {{a,b},{c,d}}
Draw a Poset diagram of the poset,
({Π_{1},Π_{2},Π_{3},Π_{4}}, refines⟩
Theory Explanation. 
Question 53 
Let (A, *) be a semi group. Furthermore, for every a and b in A, if a ≠ b, then a*b ≠ b*a.
(a) Show that for every a in A
a*a = a
(b) Show that for every a, b in A
a*b*a = a
(c) Show that for every a, b, c in A
a*b*c = a*c
Theory Explanation. 
Question 54 
Let M = ({q_{0}, q_{1}}, {0, 1}, {z_{0}, x}, δ, q_{0}, z_{0}, ∅) be a pushdown automaton where δ is given by
 δ(q_{0}, 1, z_{0}) = {(q_{0}, xz_{0})}
δ(q_{0}, ε, z_{0}) = {(q_{0}, ε)}
δ(q_{0}, 1, X) = {(q_{0}, XX)}
δ(q_{1}, 1, X) = {(q_{1}, ε)}
δ(q_{0}, 0, X) = {(q_{1}, X)}
δ(q_{0}, 0, z_{0}) = {(q_{0}, z_{0})}
(a) What is the language accepted by this PDA by empty stack?
(b) Describe informally the working of the PDA.
Theory Explanation. 
Question 55 
(a) Let G_{1} = (N, T, P, S_{1}) be a CFG where,
N = {S_{1}, A, B}, T = {a,b} and
P is given by
S_{1} → aS_{1}b S_{1} → aBb S_{1} → aAb B → Bb A → aA B → b A → a
What is L(G1)?
(b) Use the grammar in part(a) to give a CFG
for L_{2} = {a^{i} b^{j} a^{k} b^{l}  i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.
(c) Is L_{2} inherently ambiguous?
Theory Explanation. 
Question 56 
(a) Draw the schematic of an 8085 based system that can be used to measure the width of a pulse. Assume that the pulse is given as a TTL compatible signal by the source which generates it.
(b) Write the 8085 Assembly Language program to measure the width of the pulse. State all your assumption clearly.
Theory Explanation. 
Question 57 
Design a synchronous counter to go through the following states:
1, 4, 2, 3, 1, 4, 2, 3, 1, 4,...........
Theory Explanation. 
Question 58 
Calculate the total time required to read 35 sectors on a 2sided floppy disk. Assume that each track has 8 sectors and the tracktotrack step time is 8 milliseconds. The first sector to be read is sector 3 on track 10. Assume that the diskette is soft stored and the controller has a 1sector buffer. The diskette spins at 300 RPM and initially, the head is on track 10.
Theory Explanation. 
Question 59 
For a setassociative Cache Organization, the parameters are as follows:
 t_{c}  Cache access tine
t_{m}  Main memory access time
l  number of sets
b  block size
k*b  set size
Calculate the hit ratio for a loop executed 100 times where the size of the loop is n * b and n= k * m is a nonzero integer and 1 < m ≤ l.
Given the value of the hit ratio for l = 1.
Theory Explanation. 
Question 60 
Let p be a pointer as shown in the figure in a single linked list.
What do the following assignment statements achieve?
 q: = p → next
p → next:= q → next
q → next:=(q → next) → next
(p → next) → next:= q
(b) Compute the postfix equivalent of the following Infix expression
3 * log(x+1)  a/2
Theory Explanation. 
Question 61 
Draw the binary tree with node labels a, b, c, d, e, f and g for which the inorder and postorder traversals result in the following sequences:
Inorder a f b c d g e Postorder a f c g e d b
Theory Explanation. 
Question 62 
(a) Derive a recurrence relation of the size of the smallest AVL tree with height h.
(b) What is the size of the smallest AVL tree with height 8.Theory Explanation. 
Question 63 
(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.
(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions
Program → begin d semi X end X → d semi X  sY Y → semi s Y  ε
Theory Explanation. 
Question 64 
Let the attribute 'val' give the value of a binary number generated by S in the following grammar:
S → L.L  L L→ LB  B B → 0  1
For example, an input 101.101 gives S.val = 5.625
Construct a syntax directed translation scheme using only synthesized attributes, to determine S.val.
Theory Explanation. 
Question 65 
(a) Four jobs are waiting to be run. Their expected run times are 6, 3, 5 and x. In what order should they be run to minimize the average response time?
(b) Write a concurrent program using par begin  par end to represent the precedence graph shown below.
Theory Explanation. 
Question 66 
(a) Free disk space can be kept track of using a free list or a bit map. Disk addresses require d bits. For a disk with 13 blocks, F of which is free, state the condition under which the free list uses less space than the bit map.
(b) Consider a disk with C cylinders, t tracks per cylinder, s sectors per track and a sector length sl. A logical file dl with fixed record length rl is stored continuously on this disk starting at location (c_{L},t_{L},s_{L}), where c_{L}, t_{L} and S_{L} are the cylinder, track and sector numbers, respectively. Derive the formula to calculate the disk address (i.e. cylinder, track and sector) of a logical record n assuming that rl=sl.
Theory Explanation. 
Question 67 
Consider the following database relations containing the attributes
Book_id Subject_Category_of_book Name_of_Author Nationality_of_Author with Book_id as the Primary Key.
(a) What is the highest normal form satisfied by this relation?
(b) Suppose the attributes Book_title and Author_address are added to the relation, and the primary key is changed to (Name_of_Author, Book_Title), what will be the highest normal form satisfied by the relation?
Theory Explanation. 
Question 68 
Consider the following relational database schemes:
COURSES(Cno, name) PREREQ(Cno, pre_Cno) COMPLETED(student_no, Cno)
COURSES give the number and the name of all the available courses.
PREREQ gives the information about which course are prerequisites for a given course.
COMPLETED indicates what courses have been completed by students.
Express the following using relational algebra:
List all the courses for which a student with student_no 2310 has completed all the prerequisites.
Theory Explanation. 
Question 69 
A D flipflop is to be connected to an 8085 microprocessor chip as a 1bit output port with a port address of FF hex. Data bit D3 should be involved in the data transfer from CPU to the flipflop. The flipflop should be cleared on power ON.
(a) Using only one NAND gate (fan in of 10), one NOT gate and one D flipflop. Draw the required interface logic circuit (only the relevant signals should be shown).
(b) Write a program to generate a square wave on the output of the flipflop. ON and OFF periods of the square wave should be 7 bus cycles each.
Theory Explanation. 
Question 70 
Let L = {a_{1}, a_{2}, ......, a_{n}} n ≥ 0 be a list whose Pascal representation is
type list = record next: ↑ list; val: integer end
The following function returns a list in which a_{2i} and a_{2i1}, 1 ≤ i ≤ [n/2] are interchanged. Complete the function by filling the boxes. Write the line number and the content of the box in your answer sheet.
1. function change (p: ↑ list): ↑ list; 2. var q.t: ↑ list; 3. begin 4. if p = nil then change := p 5. else if p ↑ next = nil then change : ▭ 6. else begin 7. q : p ↑ next; 8. ▭ := q; 9. t : q ↑ next; 10. ▭ := p; 11. ▭ := change(t) 12. end 13. end
Theory Explanation. 
Question 71 
Consider a graph whose vertices are points in the plane with integer coordinates (x,y) such that 1≤x≤n and 1≤y≤n, where n≥2 is an integer. Two vertices (x_{1},y_{1}) and (x_{2},y_{2}) are adjacent iff ∣x_{1}−x_{2}∣ ≤ 1 and ∣y_{1}–y_{2}∣ ≤1. The weight of an edge {(x_{1},y_{1}),(x_{2},y_{2})} is √(x_{1}–x_{2})^{2} + (y_{1}–y_{2})^{2}
(a) What is the weight of a minimum weightspanning tree in this graph? Write only the answer without any explanations.
(b) What is the weight of a maximum weightspanning tree in this graph? Write only the answer without any explanations.
Theory Explanation. 
Question 72 
Consider the following program in PseudoPascal syntax.
program what:var z: integer procedure recur(x): begin if x <= 40 then begin x:x+z recur(x); z:=x+10 end end(*recur*) begin(*what*) z=10; recur(z); writeln(z) end
(a) Suppose the parameter to the procedure ‘recur’ is passed by value.
i. What value is printed by program?
ii. How many times is ‘recur’ called?
(b) What value is printed by the program if the parameter is passed by reference?
Theory Explanation. 
Question 73 
Consider the grammar
S → bSe S → PQR P → bPc P → ε Q → cQd Q → ε R → dRe R → ε
where S,P,Q,R are nonterminal symbols with S being the start symbol; b,c,d,e are terminal symbols and ‘ε’ is the empty string. This grammar generates strings of the form b^{i}, c^{j}, d^{k}, e^{m} for some i,j,k,m ≥ 0.
(a) What is the condition on the values of i,j,k,m?
(b) Find the smallest string that has two parse trees.
Theory Explanation. 
Question 74 
Consider a hash table with n buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is 1/n. The hash table is initially empty and K distinct values are inserted in the table.
(a) What is the probability that bucket number 1 is empty after the K^{th} insertion?
(b) What is the probability that no collision has occurred in any of the K insertions?
(c) What is the probability that the first collision occurs at the K^{th} insertions?
Theory Explanation. 
Question 75 
Let F be the set of onetoone functions from the set {1,2,…,n} to the set {1,2,…,m}, where m≥n≥1.
(a) How many functions are members of F?
(b) How many functions f in F satisfy the property f(i) = 1 for some i, 1≤i≤n?
(c) How many functions f in F satisfy the property f(i) < f(j) for all 1≤i≤j≤n?
Theory Explanation. 
Question 76 
Let R be a reflexive and transitive relation on a set A. Define a new relation E on A as
E = {(a,b) ∣ (a,b)∈R and (b,a)∈R}
(a) Prove that E is an equivalence relation on A.
(b) Define a reason ≤ on the equivalence classes of E as E_{1} ≤ E_{2} if ∃a,b such that a∈E_{1}, b∈E_{2} and (a,b)∈R. Prove that ≤ is a partial order.
Theory Explanation. 
Question 77 
Consider the following function.
Function F (n, m: integer): integer; begin If (n <= 0) or (m <= 0) then F:=1 else F:= F(n1, m) + F(n, m1); end;
Use the recurrence relation to answer the following question. Assume that n, m are positive integers. Write only the answers without any explanation.
(a) What is the value of F(n,2)?
(b) What is the value of (n,m)?
(c) How many recursive calls are made to the function F, including the original call, when evaluating F(n,m).
Theory Explanation. 
Question 78 
A sizebalanced binary tree is a binary tree in which for every node, the difference between the number of nodes in the left and right subtree is at most 1. The distance of a node from the root is the length of the path from the root to the node. The height of a binary tree is the maximum distance of a leaf node from the root.
(a) Prove, by using induction on h, that a sizebalance binary tree of height h contains at least 2^{h} nodes.
(b) In a sizebalanced binary tree of height h≤1, how many nodes are at distance h−1 from the root? Write only the answer without any explanations.
Theory Explanation. 
Question 79 
An array A contains n≥1 positive integers in the locations A[1], A[2],... A[n]. The following program fragment prints the length of a shortest sequence of consecutive elements of A, A[i], A[i+1],...A[j] such that the sum of their values is ≥M, a given positive number. It prints ‘n+1’ if no such sequence exists. Complete the program by filling in the boxes. In each case use the simplest possible expression. Write only the line number and the contents of the box.
1. begin 2. i: +1; j:=1; 3. Sum := ▭; 4. min: n; finish:=false; 5. While not finish do 6. If ▭ then 7. if j=n then finish:=true. 8. else 9. begin 10. j:=j+1; 11. sum:=▭ 12. end 13. else 14. begin 15. If(j1) < min then min:=j1; 16. sum:=sum  A[i]; 17. i:=i+1; 18. end 19. writeln (min+1); 20. end.
Theory Explanation. 
Question 80 
Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers.
Node *removeduplicates(Node *head, int *j) { Node *t1, *t2; *j=0; t1 = head; if (t1! = NULL) t2 = t1 →next; else return head; *j = 1; if(t2 == NULL) return head; while t2 != NULL) { if (t1.val != t2.val) → (S1) { (*j)++; t1 → next = t2; t1 = t2: → (S2) } t2 = t2 → next; } t1 → next = NULL; return head; }
Assume the list contains n elements (n≥2) in the following questions.
(a) How many times is the comparison in statement S1 made?
(b) What is the minimum and the maximum number of times statements marked S2 get executed?
(c) What is the significance of the value in the integer pointed to by j when the function completes?
Theory Explanation. 
Question 81 
A B^{+}  tree of order d is a tree in which each internal node has between d and 2d key values. An internal node with M key values has M+1 children. The root (if it is an internal node) has between 1 and 2d key values. The distance of a node from the root is the length of the path from the root to the node. All leaves are at the same distance from the root. The height of the tree is the distance of a leaf from the root.
(a) What is the total number of key values in the internal nodes of a B^{+}  tree with l leaves (l≥2)?
(b) What is the maximum number of internal nodes in a B^{+}  tree of order 4 with 52 leaves?
(c) What is the minimum number of leaves in a B^{+}  tree of order d and height h(h≥1)?
Theory Explanation. 
Question 82 
Construct a finite state machine with minimum number of states, accepting all strings over {a,b} such that the number of a's is divisible by two and the number of b's is divisible by three.
Theory Explanation. 
Question 83 
Given that L is a language accepted by a finite state machine, show that L^{P} and L^{R} are also accepted by some finite state machines, where
L^{P} = {sss' ∈ L, for some string s'}
L^{R} = {ss obtainable by reversing some string in L}
Theory Explanation. 
Question 84 
A language L is a subset of Pascal with the following constructs:
 (a) Expressions involving the operators '+' and '<' only
(b) Assignment statements
(c) 'while' statements and
(d) Compound statements with the syntax 'begin...end'
Give an unambiguous grammar for L.
Theory Explanation. 
Question 85 
The language L, defined by the following grammar allows use of real or integer data in expressions and assignment statements.
(assignstmt):: = (LHS):= (E) (E) :: = (E) + (T)(T) (T) :: = (T) * (V)(V) (V) :: = id((E)) (LHS) :: = id
It is required to convert expression and assignment strings of L into postfix strings that use the typespecific operators (+, i), (+, r), (*, i), (*, r), (:=, i) and (:=,r).
Write a syntax directed translation scheme to convert expression and assignment strings into the postfix form. You may assume that the name and type of a variable can be obtained by making the function calls 'givetype (id)' and 'givename (id)' respectively.
Theory Explanation. 
Question 86 
Consider the following program fragment in Pascal:
Program Main; var X : integer; procedure A: var Y : integer; procedure B: var Z : integer; procedure C: var Z : integer; begin(* Procedure C *) : end(* Procedure C *) begin(*Procedure B*) : C; (* call to C *) A; (* call to A *) : end(*Procedure B*) begin(* Procedure A *) : B; (* call to B *) : end(* Procedure A *) begin (* Main *) : A; (* call to A *) : end(* Main *)
Assume that there are no calls to any procedures other than the ones indicated above. It is known that at some point of time during the execution of this program five activation records exist on the runtime stack. Describe the runtime stack at this point of time by clearly indicating the following: the top of the stack, the contents of the static link and dynamic link, and allocation of the local variables in each record.
Theory Explanation. 
Question 87 
Following is a state table for some finite state machine.
(a) Find the equivalence partition on the states of the machine.
(b) Give the state table for the minimal machine. (Use appropriate names for the equivalent states. For example if states X and Y are equivalent then use XY as the name for the equivalent state in the minimal machine.)
Theory Explanation. 
Question 88 
Let f = (w'+y)(x'+y)(w+x'+z)(w'+z)(x'+z)
(a) Express f as the minimal sum of products. Write only the answer.
(b) If the output line is stuck at 0, for how many input combinations will the value of f be incorrect?
Theory Explanation. 
Question 89 
Following floating point number format is given
f is a fraction represented by a 6bit mantissa (includes sign bit) in sign magnitude form e is a 4bit exponent (includes sign hit) in sign magnitude form n = (f,e) = f, 2^{e} is a floating point number.
Let A = 54.75 in decimal and
B = 9.75 in decimal.
(a) Represent A and B as floating point numbers in the above format.
(b) Show the steps involved in floating point addition of A and B.
(c) What is the percentage error (upto one position beyond decimal point) in the addition operation in (b)?
Theory Explanation. 
Question 90 
A concurrent system consists of 3 processes using a shared resource R in a nonpreemptible and mutually exclusive manner. The processes have unique priorities in the range 1.....3, 3 being the highest priority. It is required to synchronize the processes such that the resource is always allocated to the highest priority requester. The pseudo code for the system is as follows.
Shared Data mutex:semaphore = 1:/* initialized to 1*/ process[3]:semaphore = 0; /*all initialized to 0 */ R_requested [3]:boolean = false; /*all initialized to false */ busy: boolean = false; /*initialized to false */ Code for processes begin process mypriority:integer; mypriority:=____; /*in the range 1...3*/ repeat request_R(mypriority); P (proceed [mypriority]); {use shared resource R} release_R (mypriority); forever end process; Procedures procedure request_R(priority); P(mutex); if busy = true then R_requested [priority]:=true; else begin V(proceed [priority]); busy:=true; end V(mutex);
Give the pseudo code for the procedure release_R.
Theory Explanation. 
Question 91 
A program P reads and processes 1000 consecutive records from a sequential file F stored on device D without using any file system facilities. Given the following
Size of each record = 3200 bytes Access time of D = 10 msecs Data transfer rate of D = 800 × 10^{3} bytes/second CPU time to process each record = 3 msecs
What is the elapsed time of P if
(a) F contains unblocked records and P does not use buffering?
(b) F contains unblocked records and P uses one buffer (i.e., it always reads ahead into the buffer)?
(c) records of F are organized using a blocking factor of 2 (i.e., each block on D contains two records of F) and P uses one buffer?
You may assume that the CPU time needed to transfer a record from a buffer to a local variable of P is negligible.
Theory Explanation. 
Question 92 
An operating system handles requests to resources as follows.
A process (which asks for some resources, uses them for some time and then exits the system) is assigned a unique timestamp are when it starts. The timestamps are monotonically increasing with time. Let us denote the timestamp of a process P by TS(P).
When a process P requests for a resource the OS does the following:
(i) If no other process is currently holding the resource, the OS awards the resource to P.
(ii) If some process Q with TS(Q) < TS(P) is holding the resource, the OS makes P wait for the resources.
(iii) If some process Q with TS(Q) > TS(P) is holding the resource, the OS restarts Q and awards the resources to P.
(Restarting means taking back the resources held by a process, killing it and starting it again with the same timestamp)
When a process releases a resource, the process with the smallest timestamp (if any) amongst those waiting for the resource is awarded the resource.
(a) Can a deadlock ever arise? If yes, show how. If not, prove it.
(b) Can a process P ever starve? If yes, show how. If not, prove it.
Theory Explanation. 
Question 93 
Consider the following relational database schema:
EMP (eno name, age) PROJ (pno name) INVOLVED (eno, pno)
EMP contains information about employees. PROJ about projects and INVOLVED about which employees involved in which projects. The underlined attributes are the primary keys for the respective relations.
(a) What is the relational algebra expression containing one or more of {σ,π,x,u,−} which is equivalent to SQL query.
select eno from EMP, INVOLVED where EMP.eno=INVOLVED.eno and INVOLVED.pno=3
(b) State in English (in not more than 15 words).
What the following relational algebra expressions are designed to determine
(i) π_{eno}(INVOLVED) − π_{eno}((π_{eno}(INVOLVED) X π_{pno}(PROJ))−INVOLVED)
(ii) π_{age}(EMP) − π_{EageE}(EMP) x EMP))
(Note: ρ_{E}(EMP) conceptually makes a copy of EMP and names it K (ρ is called the rename operator))
Theory Explanation. 
Question 94 
Let f be a function defined by
Find the values for the constants a, b, c and d so that f is continuous and differentiable every where on the real line.
Theory Explanation. 
Question 95 
A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain.
61 52 14 17 40 43  
2 3 50 40 60 43  
10 65 31 48 37 43  
81 61 52 14 41 43  
17 77 27 66 18 43 
Question 96 
A logic network has two data inputs A and B, and two control inputs C_{0} and C_{1}. It implements the function F according to the following table.
Implement the circuit using one 4 to 1 Multiplexer, one 2input Exclusive OR gate, one 2input AND gate, one 2input OR gate and one Inverter.
Theory Explanation. 
Question 97 
An 8052 based system has an output port with address 00H. Consider the following assembly language program.
ORG 0100H MVI A, 00H LXI H, 0105H OUT 00H INR A PCHL HLT
(a) What does the program do with respect to the output port 00H?
(b) Show the wave forms at the three least significant bits of the port 00H.
Theory Explanation. 
Question 98 
A demand paged virtual memory system uses 16 bit virtual address, page size of 256 bytes, and has 1 Kbyte of main memory. LRU page replacement is implemented using a list whose current status (page number in decimal) is
For each hexadecimal address in the address sequence given below
00FF, 010D, 10FF, 11B0
indicate
(i) the new status of the list
(ii) page faults, if any, and
(iii) page replacements, if any
Theory Explanation. 
Question 99 
Let F be the collection of all functions f: {1,2,3} → {1,2,3}. If f and g ∈ F, define an equivalence relation ~ by f ~ g if and only if f(3) = g(3).
a) Find the number of equivalence classes defined by ~.
b) Find the number of elements in each equivalence class.
Theory Explanation. 
Question 100 
The Fibonacci sequence {f_{1},f_{2},f_{3},...,f_{n}} is defined by the following recurrence:
f_{n+2} = f_{n+1} + f_{n}, n ≥ 1; f_{2}=1 : f_{1}=1
Prove by induction that every third element of the sequence is even.
Theory Explanation. 
Question 101 
Let and be two matrices such that AB = I. Let and CD = 1. Express the elements of D in terms of the elements of B.
Theory Explanation. 
Question 102 
Let G be a contextfree grammar where G = ({S, A, B, C},{a,b,d},P,S) with the productions in P given below.
S → ABAC A → aA ∣ ε B → bB ∣ ε C → d
(ε denotes null string). Transform the grammar G to an equivalent contextfree grammar G' that has no ε productions and no unit productions. (A unit production is of the form x → y, and x and y are non terminals.)
Theory Explanation. 
Question 103 
Given below are the transition diagrams for two finite state machine M_{1} and M_{2} recognizing languages L_{1} and L_{2} respectively.
(a) Display the transition diagram for a machine that recognizes L_{1}.L_{2}, obtained from transition diagrams for M_{1} and M_{2} by adding only ε transitions and no new states.
(b) Modify the transition diagram obtained in part(a) obtain a transition diagram for a machine that recognizes (L_{1}.L_{2})∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).
Theory Explanation. 
Question 104 
Let Q = ({q_{1},q_{2}}, {a,b}, {a,b,Z}, δ, Z, ϕ) be a pushdown automaton accepting by empty stack for the language which is the set of all non empty even palindromes over the set {a,b}. Below is an incomplete specification of the transitions δ. Complete the specification. The top of the stack is assumed to be at the right end of the string representing stack contents.
(1) δ(q_{1},a,Z) = {(q_{1},Za)} (2) δ(q_{1},b,Z) = {(q_{1},Zb)} (3) δ(q_{1},a,a) = {(.....,.....)} (4) δ(q_{1},b,b) = {(.....,.....)} (5) δ(q_{2},a,a) = {(q_{2},ϵ)} (6) δ(q_{2},b,b) = {(q_{2},ϵ)} (7) δ(q_{2},ϵ,Z) = {(q_{2},ϵ)}
Theory Explanation. 
Question 105 
A two dimensional array A[1...n][1...n] of integers is partially sorted if
∀i, j ∈ [1...n−1], A[i][j] < A[i][j+1] and A[i][j] < A[i+1][j]
Fill in the blanks:
(a) The smallest item in the array is at A[i][j] where i=............and j=..............
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x (which is guaranteed to be smaller than any item in the last row or column) still keeping A partially sorted.
procedure insert (x: integer); var i,j: integer; begin (1) i:=1; j:=1, A[i][j]:=x; (2) while (x > ...... or x > ......) do (3) if A[i+1][j] < A[i][j] ......... then begin (4) A[i][j]:=A[i+1][j]; i:=i+1; (5) end (6) else begin (7) ............ (8) end (9) A[i][j]:= ............. end
Theory Explanation. 
Question 106 
Insert the characters of the string K R P C S N Y T J M into a hash table of size 10.
Use the hash function
h(x) = (ord(x) – ord("a") + 1) mod10
and linear probing to resolve collisions.
(a) Which insertions cause collisions?
(b) Display the final hash table.
Theory Explanation. 
Question 107 
A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v
Theory Explanation. 
Question 108 
Let G be the directed, weighted graph shown in below figure.
We are interested in the shortest paths from A.
(a) Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node A.
(b) Write down sequence of vertices in the shortest path from A to E.
(c) What is the cost of the shortest path from A to E?
Theory Explanation. 
Question 109 
Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?
var i,j,k: integer; x: integer; a:= array; [1...N] of integer; begin i:= 1; j:= N; repeat k:(i+j) div 2; if a[k] < x then i:= k else j:= k until (a[k] = x) or (i >= j); if (a[k] = x) then writeln ('x is in the array') else writeln ('x is not in the array') end;
Theory Explanation. 
Question 110 
Consider the following program in pseudopascal syntax. What is printed by the program if parameter a in procedure test 1 is passed as
(i) callbyreference parameter
(ii) callbyvalueresult parameter
program Example (input, output) var b: integer; procedure test2: begin b:=10; end procedure test1 (a:integer): begin a:=5; writeln ('point 1: ', a, b); test2; writeln ('point 2: ', a, b); end begin(*Example*) b:=3; test1(b); writeln('point3:', b); end
Theory Explanation. 
Question 111 
Consider the syntaxdirected translation schema (SDTS) shown below:
E → E + E {print “+”} E → E ∗ E {print “.”} E → id {print id.name} E → (E)
An LRparser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.
(a+b)∗(c+d), using the SDTS given above.
Theory Explanation. 
Question 112 
The concurrent programming constructs fork and join are as below:
fork
N = 2 M = 2 fork L3 fork L4 S1 L1:join N S3 L2:join M S5 L3:S2 goto L1 L4:S4 goto L2 next:
Theory Explanation. 
Question 113 
A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the table below, where P0, P1, P2 are processes, and R0, R1, R2 are resources types.
(a) Show that the system can be in this state.
(b) What will the system do on a request by process P0 for one unit of resource type R1?
Theory Explanation. 
Question 114 
A file system with a onelevel directory structure is implemented on a disk with disk block size of 4K bytes. The disk is used as follows:
Diskblock 0: File Allocation Table, consisting of one 8bit entry per date block, representing the data block address of the next date block in the file Disk block 1: Directory, with one 32 bit entry per file: Disk block 2: Data block 1; Disk block 3: Data block 2; etc.
(a) What is the maximum possible number of files?
(b) What is the maximum possible file size in blocks?
Theory Explanation. 
Question 115 
Consider the synchronous sequential circuit in the below figure.
(a) Draw a state diagram, which is implemented by the circuit. Use the following names for the states corresponding to the values of flipflops as given below.
(b) Given that the initial state of the circuit is S_{4}, identify the set of states, which are not reachable.
Theory Explanation. 
Question 116 
A hard disk is connected to a 50 MHz processor through a DMA controller. Assume that the initial setup of a DMA transfer takes 1000 clock cycles for the processor, and assume that the handling of the interrupt at DMA completion requires 500 clock cycles for the processor. The hard disk has a transfer rate of 2000 Kbytes/sec and average block transferred is 4 K bytes. What fraction of the processor time is consumed by the disk, if the disk is actively transferring 100% of the time?
Theory Explanation. 
Question 117 
A computer system has a three level memory hierarchy, with access time and hit ratios as shown below:
(a) What should be the minimum sizes of level 1 and 2 memories to achieve an average access time of less than 100 nsec?
(b) What is the average access time achieved using the chosen sizes of level 1 and level 2 memories?
Theory Explanation. 
Question 118 
A library relational database system uses the following schema
USERS (User#, UserName, HomeTown) BOOKS (Book#, BookTitle, AuthorName) ISSUED (Book#, User#, Date)
Explain in one English sentence, what each of the following relational algebra queries is designed to determine
(a) σ User #=6 (11 User #, Book Title ((USERS ISSUED) BOOKS)) (b) σ Author Name (BOOKS (σ Home Town) = Delhi (USERS ISSUED)))
Theory Explanation. 
Question 119 
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we required comparisons of
O(m)  
O(n)  
O(m+n)  
O(logm+logn) 
In worst case, no. of comparisons is m+n1.
Then we require O(m+n) comparisons to merging two sorted lists.
Question 120 
A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is:
log_{2} n  
n  1  
n  
2^{n} 
The no. of subtrees of a node is called the degree of the node. In a binary tree, all nodes have degree 0, 1 and 2.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is of degree 2.
The number of nodes of degree 2 in T is "n  1".
Question 121 
Consider the following high level program segment. Give the contents of the memory locations for variables W, X, Y and Z after the execution of the program segment. The values of the variables A and B are 5 CH and 92H, respectively. Also indicate error conditions if any.
var A, B, W, X, Y :unsigned byte; Z :unsigned integer, (each integer is represented by two bytes) begin X :=A+B Y :=abs(bAb); W :=AB Z :=A*B End;
Theory Explanation. 
Question 122 
(a) Consider the following Pascal function where A and B are nonzero positive integers. What is the value of GET(3,2)?
function GET(A,B:integer);integer; begin if B = 0 then GET:=1 else if A < B then GET:=0 else GET:=GET(A1,B)+GET(A1,B1) end ;
(b) The Pascal procedure given for computing the transpose of an N × N (N>1) matrix A of integers has an error. Find the error and correct it.
Assume that the following declaration are made in the main program
const MAXSIZE=20; type INTARR=array [1.,MAXSIZE,1..MAXSIZE] of integer; Procedure TRANSPOSE (var A: INTARR; N : integer); var I, J, TMP, integer; begin for I:=1 to NO – 1 do for J:=1 to N do begin TMP: = A[I,J]; A[I,J]:=A[J,I]; A(J,I):=TMP end end;
Theory Explanation. 
Question 123 
A computer installation has 1000k of main memory. The jobs arrive and finish in the following sequences.
Job 1 requiring 200k arrives Job 2 requiring 350k arrives Job 3 requiring 300k arrives Job 1 finishes Job 4 requiring 120k arrives Job 5 requiring 150k arrives Job 6 requiring 80k arrives
(a) Draw the memory allocation table using Best Fit and First fit algorithms.
(b) Which algorithm performs better for this sequence?
Theory Explanation. 
Question 124 
What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A, B, C? Draw all these binary trees.
Theory Explanation. 
Question 125 
(a) Determine the number of divisors of 600.
(b) Compute without using power series expansion
Theory Explanation. 
Question 126 
Construct the LL(1) table for the following grammar.
1. Expr → _Expr 2. Expr → (Expr) 3. Expr → Var Expr Tail 4. ExprTail → _Expr 5. ExprTail → λ 6. Var → Id Var Tail 7. VarTail → (Expr) 8. VarTail → λ 9. Goal → Expr$
Theory Explanation. 
Question 127 
(a) Translate the arithmetic expression a*(b+c) into syntax tree.
(b) A grammar is said to have cycles if it is the case that
A ⇒ +_{A}
Show that no grammar that has cycles can be LL(I).
Theory Explanation. 
Question 128 
(a) Using the scope rules of Pascal determine the declaration that apply to each occurrence of the names A and B in the following program segment.
procedure T(U, V, X, Y: integer); var A: record A, B : integer end; B: record B, A : integer end; begin with A do begin A:=4; B:=V end; with B do begin A:=X; B:=Y end end;
(b) Find the lexical errors in the following Pascal statement:
if A > 1, then B = 2.5A else read (C);
Theory Explanation. 
Question 129 
Let L be a language over ∑ i.e., *L ≤ ∑ . Suppose L satisfies the two conditions given below
(i) L is in NP and
(ii) For every n, there is exactly one string of length n that belongs to L.
Let L^{c} be the complement of L over ∑*. Show that L^{c} is also in NP.
Theory Explanation. 
Question 130 
Consider the following sequence of numbers
92, 37, 52, 12, 11, 25
Use bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.
Theory Explanation. 
Question 131 
Obtain the principal (canonical) conjunctive normal form of the propositional formula
(p ∧ q) V (¬q ∧ r)
Where ‘∧’ is logical and, ‘v’ is inclusive or and ¬ is negation.
Theory Explanation. 
Question 132 
If the overhead for formatting a disk is 96 bytes for 4000 byte sector,
(a) Compute the unformatted capacity of the disk for the following parameters:
Number of surfaces: 8 Outer diameter of the disk: 12 cm Inner diameter of the disk: 4 cm Inter track space: 0.1 mm Number of sectors per track: 20
(b) if the disk in (a) is rotating at 360 rpm, determine the effective data transfer rate which is defined as the number of bytes transferred per second between disk and memory.
Theory Explanation. 
Question 133 
(a) Implement a circuit having the following output expression using an inverter and NAND gate .
(b) What is the equivalent minimal Boolean expression (in sum of products form)
for the Karnaugh map given below?
Theory Explanation. 
Question 134 
The following is an 8085 assembly language program:
MVI B, OAH MVI A, 05H LXI H, IC40H CALL SUB HLT SUB CMP M RZ INX H DCR B JNZ SUB RET
(a) What does the program do?
(b) What are the contents of registers A and B initially?
(c) What are the contents of HL register pair after the execution of the program?
Theory Explanation. 
Question 135 
(a) An asynchronous serial communication controller that uses a start stop scheme for controlling the serial I/O of a system is programmed for a string of length seven bits, one parity bit (odd parity) and one step bit. The
transmission rate is 1200 bits/second.
(i) What is the complete bit stream that is transmitted for the string ‘0110101’?
(ii) How many such strings can be transmitted per second?
(b) Consider a CRT display that has a text mode display format of 80 × 25 characters with a 9 × 12 character cell. What is the size of the video buffer RAM for the display to be used in monochrome (1 bit per pixel) graphics mode?
Theory Explanation. 
Question 136 
The following is an incomplete Pascal function to convert a given decimal integer (in the range 8 to +7) into a binary integer in 2’s complement representation. Determine the expression A, B, C that complete program.
function TWOSCOMP (N:integer):integer; var RAM, EXPONENT:integer; BINARY :integer; begin if(N>=8) and (N<=+7) then begin if N<0 then N : = A; BINARY:=0; EXPONENT:=1; while N<>0 do begin REM:=N mod 2; BINARY:=BINARY + B*EXPONENT; EXPONENT:=EXPONENT*10; N := C end TWOSCOMP:=BINARY end end;
Theory Explanation. 
Question 137 
Consider the following program segment for concurrent processing using semaphore operators P and V for synchronization. Draw the precedence graph for the statements S1 to S9.
var a, b, c, d, e, f, g, h, i, j, k : semaphore; begin cobegin begin S1; V(a); V(b) end; begin P(a); S2; V(c); V(d) end; begin P(c); S4; V(c) end; begin P(d); S5; V(f) end; begin P(e); P(f); S7; V(k) end; begin P(b); S3;V(g);V(h) end; begin P(g); S6; V(i) end; begin P(h); P(i); S8; V(j) end; begin P(j); P(j); P(k); S9 end; coend end;
Theory Explanation. 
Question 138 
The head of a moving head disk with 100 tracks numbered 0 to 99 is currently serving a request at tract 55. If the queue of requests kept in FIFO order is
10, 70, 75, 23, 65
Which of the two disk scheduling algorithms FCFS (First Come First Served) and SSTF (Shortest Seek Time First) will require less head movement? Find the head movement for each of the algorithms.
Theory Explanation. 
Question 139 
Let G_{1} and G_{2} be subgroups of a group G.
(a) Show that G_{1} ∩ G_{2} is also a group of G.
(b) Is G_{1} ∪ G_{2} always a subgroup of G?
Theory Explanation. 
Question 140 
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to the edge).
Theory Explanation. 
Question 142 
Prove that in finite graph, the number of vertices of odd degree is always even.
Theory Explanation. 
Question 143 
(a) Find the minimum value of 3  4x + 2x^{2}.
(b) Determine the number of positive integers (≤ 720) which are not divisible by
any of numbers 2, 3, and 5.
Theory Explanation. 
Question 144 
(a) Consider the relation scheme R(A, B, C) with the following functional dependencies:
A, B → C, C → A
Show that the scheme R is the Third Normal Form (3NF) but not in BoyceCode Normal Form (BCNF).
(b) Determine the minimal keys of relation R.
Theory Explanation. 
Question 145 
Consider the relation scheme.
AUTHOR (ANAME, INSTITUTION, ACITY, AGE) PUBLISHER (PNAME, PCITY) BOOK (TITLE, ANAME, PNAME)
Express the following queries using (one or more of )SELECT, PROJECT, JOIN and DIVIDE operations.
(a) Get the names of all publishers.
(b) Get values of all attributes of all authors who have published a book for the
publisher with PNAME = ‘TECHNICAL PUBLISHERS’.
(c) Get the names of all authors who have published a book for any publisher located in Madras.
Theory Explanation. 
Question 146 
A sequence of two instructions that multiplies the contents of the DE register pair by 2 and stores the result in the HL register pair (in 8085 assembly language) is:
XCHG and DAD B  
XTHL and DAD H  
PCHL and DAD D  
XCHG and DAD H 
Question 147 
(a) Let * be a Boolean operation defined as
If C = A * B then evaluate and fill in the blanks:
(i) A * A = _______
(ii) C * A = _______
(b) Solve the following boolean equations for the values of A, B and C:
Theory Explanation. 
Question 148 
A 3ary tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a 3ary tree with n interval nodes is 2(n1)+3.
Theory Explanation. 
Question 149 
What function of x, n is computed by this program?
Function what (x, n:integer): integer: Var value : integer; begin value:=1 if n>0 then begin if n mod 2 = 1 then value:=value*x; value:=value*what(x*x, n div 2); end; what:value end;
Theory Explanation. 
Question 150 
An array A contains n integers in locations A[0],A[1], …………… A[n1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n1. An incomplete algorithm for doing this in linear time, without using another is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably declared.
min:=n; i=0; while _____do begin temp:=A[i]; j:=i; while _____do begin A[j]:=_____; j:=(j+K) mod n; if j
Theory Explanation. 
Question 151 
A rooted tree with 12 nodes has its nodes numbered 1 to 12 in preorder. When the tree is traversed in postorder, the nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, 1.
Reconstruct the original tree from this information, that is, find the parent of each node, and show the tree diagrammatically.
Theory Explanation. 
Question 152 
Following 7 bit single error correcting Hamming coded message is received. (figure below):
Determine if the message is correct (assuming that at most 1 bit could be corrupted). If the message contains an error find the bit which is erroneous and gives the correct message.
Theory Explanation. 
Question 153 
Write a program in 8085 Assembly language to Add two 16bit unsigned BCD(8421 Binary Coded Decimal) number. Assume the two input operands are in BC and DE Register pairs. The result should be placed in the register pair BC. (Higher order register in the register pair contains higher order digits of operand)
Theory Explanation. 
Question 154 
Find the contents of the flipflop Q_{2}, Q_{1} and Q_{0} in the circuit of figure, after giving four clock pulses to the clock terminal. Assume Q_{2}Q_{1}Q_{0} = 000 initially.
Theory Explanation. 
Question 155 
(a) Assume that a CPU has only two registers R_{1} and R_{2} and that only the following instruction is available XOR R_{i}, R_{j}; {R_{j} ← R_{i} ⊕ R_{j}, for i,j = 1,2}
Using this XOR instruction, find an instruction sequence in order to exchange
the contents of the registers R_{1} and R_{2}.
(b) The line p of the circuit shown in figure has stuck at 1 fault. Determine an input test to detect the fault.
Theory Explanation. 
Question 156 
Consider the following relational schema:
COURSES (cno, cname) STUDENTS (rollno, sname, age, year) REGISTERED FOR (cno, rollno)
(a) Write a relational algebra query to
Print the roll number of students who have registered for cno 322.
(b) Write a SQL query to
Print the age and year of the youngest student in each year.
Theory Explanation. 
Question 157 
Consider B+ − tree of order d shown in figure? (A) B^{+} − tree of order d contains between d and 2d keys in each node. (a) Draw the resulting B^{+} − tree after inserted in the figure.
(b) For a B^{+} − tree of order d with n leaf nodes, the number of nodes accessed during a search is 0().
Theory Explanation. 
Question 158 
(a) Use the patterns given to prove that
(You are not permitted to employ induction)
(b) Use the result obtained in (a) to prove that
Theory Explanation. 
Question 159 
Every element a of some ring (R,+,0) satisfies the equation aoa = a.
Decide whether or not the ring is commutative.
Theory Explanation. 
Question 160 
State whether the following statements are True or False with reasons for your answer:
(a) Coroutine is just another name for a subroutine.
(b) A two pass assembler uses its machine opcode table in the first pass of assembly.
Theory Explanation. 
Question 161 
State whether the following statements are True or False with reasons for your answer
(a) A subroutine cannot always be used to replace a macro in an assembly language program.
(b) A symbol declared as ‘external’ in assembly language is assigned an address outside the program by the assembler itself.
Theory Explanation. 
Question 162 
(a) Given a set
S = {x there is an xblock of 5's in the decimal expansion of π}
(Note: xblock is a maximal block of x successive 5’s)
Which of the following statements is true with respect to S? No reasons need to be given for the answer.
 (i) S is regular
(ii) S is recursively enumerable
(iii) S is not recursively enumerable
(iv) S is recursive
(b) Given that a language L_{1} is regular and that the language L_{1} ∪ L_{2} is regular, is the language L_{2} always regular? Prove your answer.
Theory Explanation. 
Question 163 
A grammar G is in ChomskyNormal Form (CNF) if all its productions are of the form A → BC or A → a, where A, B and C, are nonterminals and a is a terminal. Suppose G is a CFG in CNF and w is a string in L(G) of length, then how long is a derivation of w in G?
Theory Explanation. 
Question 164 
Consider the following recursive function:
function fib (1:integer);integer; begin if (n=0) or (n=1) then fib:=1 else fib:=fib(n1) + fib(n2) end;
The above function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter and passed on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack will not overflow. Give reasons for your answer.
Theory Explanation. 
Question 165 
Consider the program below:
Program main; var r:integer; procedure two; begin write (r) end; procedure one; var r:integer; begin r:=5 two; end begin r:=2; two; one; two; end.
What is printed by the above program if
(i) Static scoping is assumed for all variables;
(ii) Dynamic scoping is assumed for all variables.
Give reasons for your answer.
Theory Explanation. 
Question 166 
Suppose we have a computer with a single register and only three instructions given below:
LOAD addren ; load register ; from addren STORE addren ; store register ; at addren ADD addren ; add register to ; contents of addren ; and place the result ; in the register
Consider the following grammar:
A → id :=E E → E + TT T → (E)id
Write a syntax directed translation to generate code using this grammar for the computer described above.
Theory Explanation. 
Question 167 
An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:
V: Set of all vertices in the tree; I:=φ; While V ≠ φdo begin select a vertex u; ∈ V such that V:= V – {u}; if u is such that then 1:= I ∪ {u} end; output(I);
(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.
Theory Explanation. 
Question 168 
An array a contains n integers in nondecreasing order, A[1] ≤ A[2] ≤ ... ≤ A[n]. Describe, using Pascal like pseudo code, a linear time algorithm to find i, j, such that A[i] + A[j] = a given integer M, if such i, j exist.
Theory Explanation. 
Question 169 
A queue Q containing n items and an empty stack S are given. It is required to transfer all the items from the queue to the stack, so that the item at the front of queue is on the top of the stack, and the order of all other items is preserved. Show how this can be done in O(n) time using only a constant amount of additional storage. Note that the only operations which can be performed on the queue and stack are Delete, Insert, Push and Pop. Do not assume any implementation of the queue or stack.
Theory Explanation. 
Question 170 
(a) Draw a precedence graph for the following sequential code. The statements are numbered from S_{1} to S_{6}
S_{1} read n S_{2} i:=1 S_{3} if i>n goto next S_{4} a(i):=i+1 S_{5} i:=i+1 S_{6} next : Write a(i)
(b) Can this graph be converted to a concurrent program using parbeginparend construct only?
Theory Explanation. 
Question 171 
Consider the resource allocation graph given in the figure.
(a) Find if the system is in a deadlock state. (b) Otherwise, find a safe sequence.
Theory Explanation. 
Question 172 
Assume that only half adders are available in your laboratory. Show that any binary Boolean function can be implemented using half adders only.
Theory Explanation. 
Question 173 
The instruction format of a CPU is:
Mode and RegR together specify the operand. RegR specifies a CPU register and Mode specifies an addressing mode. In particular, Mode = 2 specifies that ‘the register RegR contains the address of the operand, after fetching the operand, the contents of RegR are incremented by 1’.
An instruction at memory location 2000 specifies Mode = 2 and the RegR refers to program counter (PC).
(a) What is the address of the operand?
(b) Assuming that this is a nonjump instruction, what are the contents of PC after the execution of this instruction?
Theory Explanation. 
Question 174 
In the threelevel memory hierarchy shown in the following table, p_{i} denotes the probability that an access request will refer to M_{i}.
If a miss occurs at level M_{i}, a page transfer occurs from M_{i+1} to M_{i} and the average time required for such a page swap is T_{i}. Calculate the average time t_{A} required for a processor to read one word from this memory system.
Theory Explanation. 
Question 175 
The following Pascal program segments finds the largest number in a twodimensional integer array A[0...n1,0...n1] using a single loop. Fill up the boxes to complete the program and write against in your answer book. Assume that max is a variable to store the largest value and i,j are the indices to the array.
begin max:= , i:=0,j:=0; while do begin if A[i,j]>max then max:=A[i,j] if then j:=j+1 else begin j:=0; i:= end end end.
Theory Explanation. 
Question 176 
Consider a singly linked list having n nodes. The data items d_{1}, d_{2}, ...d_{n} are stored in these n nodes. Let X be a pointer to the jth node (1≤j≤n) in which d_{j} is stored. A new data item d stored in node with address Y is t be inserted. Give an algorithm to insert d into the list to obtain a list having items d_{1}, d_{2}, ..., d_{j1}, d_{j}, ..., d_{n} in the order without using the header.
Theory Explanation. 
Question 177 
An ISAM (indexed sequential) file consists of records of size 64 bytes each, including key field of size 14 bytes. An address of a disk block takes 2 bytes. If the disk block size is 512 bytes and there are 16 K records, compute the size of the data and index areas in terms of number of blocks. How many levels of tree do you have for the index?
Theory Explanation. 
Question 178 
Consider the recursive algorithm given below:
procedure bubblersort (n); var i,j: index; temp : item; begin for i:=1 to n1 do if A[i] > A [i+1] then begin temp : A[i]; A[i]:=A[i+1]; A[i+1]:=temp end; bubblesort (n1) end
Let a_{n} be the number of times the ‘if…then….’ Statement gets executed when the algorithm is run with value n. Set up the recurrence relation by defining a_{n} in terms of a_{n1}. Solve for a_{n}.
Theory Explanation. 
Question 179 
Prove by the principal of mathematical induction that for any binary tree, in which every nonleaf node has 2 descendants, the number of leaves in the tree is one more than the number of nonleaf nodes.
Theory Explanation. 
Question 180 
Out of a group of 21 persons, 9 eat vegetables, 10 eat fish and 7 eat eggs : 5 persons eat all three. How many persons eat at least two out the three dishes?
Theory Explanation. 
Question 181 
Show that proposition C is a logical consequence of the formula
A ∧ (A →(B ∨ C)) ∧ (B → ~A)
Using truth tables.
Theory Explanation. 
Question 182 
A control algorithm is implemented by the NAND – gate circuitry given in figure below, which A and B are state variable implemented by D flipflops, and P is control input. Develop the state transition table for this controller.
Theory Explanation. 
Question 183 
Given that the following is an 8085 program segment:
(a) Identify the function performed by it, and
(b) List the roles of the registers used and the address referred to by it.
LHLD 5000 MVI B, 5 GET: IN 20 MOV M, A INX H DCR B JNZ GET
Theory Explanation. 
Question 184 
The following page addresses, in the given sequence, were generated by a program:
1 2 3 4 1 3 5 2 1 5 4 3 2 3
This program is run on a demand paged virtual memory system, with main memory size equal to 4 pages. Indicate the page references for which page faults occurs for the following page replacement algorithms.
(a) LRU (b) FIFO
Assume that the main memory is empty initially.
Theory Explanation. 
Question 185 
Write a concurrent program using parbeginparend and semaphores to represent the precedence constraints of the statements S_{1} to S_{6}, as shown in figure below.
Theory Explanation. 
Question 186 
The following relations are used to store data about students, courses, enrollment of students in courses and teachers of courses. Attributes for primary key in each relation are marked by ‘*’.
Students (rollno*, sname, saddr) courses (cno*, cname) enroll(rollno*, cno*,grade) teach(tno*,tname,cao*)
(cno is course number, cname is course name, tno is teacher number, tname is teacher name, sname is student name, etc.)
Write a SQL query for retrieving roll number and name of students who got A grade in at least one course taught by teacher named Ramesh for the above relational database.
Theory Explanation. 
Question 187 
The following relations are used to store data about students, courses, enrollment of students in courses and teachers of courses. Attributes for primary key in each relation are marked by ‘*’.
Students (rollno*, sname, saddr) courses (cno*, cname) enroll(rollno*, cno*,grade) teach(tno*,tname,cao*)
(cno is course number, cname is course name, tno is teacher number, tname is teacher name, sname is student name, etc.)
For the relational database given above, the following functional dependencies hold:
rollno → sname,sdaddr cno → cname tno → tname rollno, cno → grade
(a) Is the database in 3^{rd} normal form (3NF)?
(b) If yes, prove that it is in 3 NF. If not, normalize, the relations so that they
are in 3 NF (without proving).
Theory Explanation. 
Question 188 
A simple Pascal like language has only three statements.
(i) assignment statement e.g. x:=expression
(ii) loop construct e.g. for i:=expression to expression do statement.
(iii) sequencing e.g. begin statement ;…; statement end
(a) Write a contextfree grammar (CFG) for statements in the above language. Assume that expression has already been defined. Do not use optional
parentheses and * operator in CFG.
(b) Show the parse tree for the following statement:
for j:=2 to 10 do begin x:=expr1; y:=expr2 end
Theory Explanation. 
Question 189 
A stack is used to pass parameters to procedures in a procedure call.
(a) If a procedure P has two parameters as described in procedure definition:
procedure P (var x :integer; y: integer); and if P is called by ; P(a,b)
State precisely in a sentence what is pushed on stack for parameters a and b.
(b) In the generated code for the body of procedure P, how will the addressing of formal parameters x and y differ?
Theory Explanation. 
Question 190 
Draw the state transition of a deterministic finite state automaton which accepts all strings from the alphabet {a,b}, such that no string has 3 consecutive occurrences of the letter b.
Theory Explanation. 
Question 191 
Let ({p,q{,*) be a semigroup where p * q = q. Show that:
(a) p * q = q * p and (b) q * q = q
Theory Explanation. 
Question 192 
(a) Consider addition in two’s complement arithmetic. A carry from the most significant but does not always correspond to an overflow. Explain what is the condition for overflow in two’s complement arithmetic.
(b) A priority encoder accepts three input signals (A, B and C) and produce a twobit output (X_{1},X_{0}) corresponding to the highest priority active input signal. Assume A has the highest priority followed by B and C has the lowest priority. If none of the inputs are active the output should be 00. design the priority encoder using 4:1 multiplexers as the main components.
(c) Design a 3bit counter using Dflip flops such that not more than one flipflop changes state between any two consecutive states.
Theory Explanation. 
Question 193 
(a) The access times of the main memory and the Cache memory, in a computer system, are 500 n sec and 50 n sec, respectively. It is estimated that 80% of the main memory request are for read the rest for write. The hit ratio for the read access only is 0.9 and a writethrough policy (where both main and cache memories are updated simultaneously) is used. Determine the average time of the main memory.
(b) Three devices A, B and C are corrected to the bus of a computer, input/output transfers for all three devices use interrupt control. Three interrupt request lines INTR_{1}, INTR_{2} and INTR_{3} are available with priority of INTR_{1} > priority of INTR_{2} > priority of INTR_{3}.
Draw a schematic of the priority logic, using an interrupt mask register, in which Priority of A > Priority of B > Priority of C.
Theory Explanation. 
Question 194 
A microprocessor is capable of addressing 1 megabyte of memory with a 20bit address bus. The system to be designed requires 256 K bytes of RAM, 256 K bytes of EPROM, 16 I/O devices (memory mapped I/O) and 1 K byte of EERAM (electrically erasable RAM).
(a) Design a memory map (to reduce decoding logic) and show the decoding logic if the components available are:
Type Size Speed RAM 6 K × 8 140 n sec EPROM 256 K × 8 150 n sec EERAM 256 × 8 500 n secread 3µsecwrite
(b) The micro processor is operating at 12.5 mHz and provides time equivalent to two clock cycles for memory read and write. Assuming control signals similar to 8085, design the extra logic required for interfacing EERAM.
Theory Explanation. 
Question 195 
Consider the function F(n) for which the pseudo code is given below:
Function F(n) begin F1 ← 1 if(n=1) then F ← 3 else For i = 1 to n do begin C ← 0 For j = 1 to F(n – 1) do begin C ← C + 1 end F1 = F1 * C end F = F1 end [n is a positive integer greater than zero]
(a) Derive a recurrence relation for F(n)
(b) Solve the recurrence relation for a closed form solutions of F(n).
Theory Explanation. 
Question 196 
Let T be a Depth First Tree of a undirected graph G. An array P indexed by vertices of G is given. P[V] is the parent of vertex V, in T. Parent of the root is the root itself.
Give a method for finding and printing the cycle formed if the edge (u,v) of G not in T (i.e., e ∈ G − T) is now added to T.
Time taken by your method must be proportional to the length of the cycle.
Describe the algorithm in a PASCAL – like language. Assume that the variables have been suitably declared.
Theory Explanation. 
Question 197 
Suggest a data structure for representing a subnet S of integers from 1 to n. Following operations on the set S are to be performed in constant time (independent of cardinality of S).
(i) MEMBER(X): Check whether X is the set S or not (ii) FINDONE(S): If S is not empty, return one element of the set S (any arbitrary element will do) (iii) ADD(X): Add integer x to set S (iv) DELETE(X): Delete integer x from S.
Give pictorial examples of your data structure. Give routines for these operations in an English like language. You may assume that the data structure has been suitably initialized. Clearly state your assumptions regarding initialization.
Theory Explanation. 
Question 198 
(a) What type of parameter passing mechanism (callbyvalue, callbyreference, callbyname, orbyvalue result) is the following sequence of actions truing to implement for a procedure call P(A[i]) where P(i:integer) is a procedure and A is an integer array?
1. Create a new local variable, say z. 2. Assign to z the value of A[i]. 3. Execute the body of P using z for A[i] 4. Set A[i] to z.
Is the implementation correct? Explain and correct it if necessary. You are supposed to make only small changes.
(b) Show the activation records and the display structure just after the procedures called at lines marked x and y have started their execution. Be sure to indicate which of the two procedures named A you are referring to.
Program Test; Procedure A; Procedure B; Procedure A; …… end a; begin y:A; end B; begin B; end A; begin x:A; end Test.
Theory Explanation. 
Question 199 
(a) Write syntax directed definitions (semantic rules) for the following grammar to add the type of each identifier to its entry in the symbol table during semantic analysis. Rewriting the grammar is not permitted and semantic rules are to be added to the ends of productions only.
D → TL; T → int T → real L → L, id L → id
(b) Write 3address intermediate code (quadruples) for the following boolean expression in the sequence as it would be generated by a compiler. Partial evaluation of Boolean expressions is not permitted. Assume the usual rules of precedence of the operators.
(a + b) > (c + d) or a > c and b < d
Theory Explanation. 
Question 200 
(a) Draw the precedence graph for the concurrent program given below:
S_{1} parbegin begin S_{2}:S_{4} end; begin S_{3}; parbegin S_{5}; begin S_{6}:S_{8} End parend end; S_{7} parend; S_{9}
(b) Let the page reference and the working set window be c c d b c e c e a d and 4, respectively. The initial working set at time t = 0 contains the pages {a, d, e}, where a was referenced at time t = 0, d was referenced at time t = 1, and e was referend at time t = 2. determine the total number of page faults and the average number of page frames used by computing the working set at each reference.
Theory Explanation. 
Question 201 
(a) How is redundancy reduced in the following models?
(i) Hierarchical (ii) Network (iii) Relational
Write a one line answer in each case.
(b) Suppose we have a database consisting of the following three relations:
FREQUENTS (CUSTOMER, HOTEL) SERVES (HOTEL, SNACKS) LIKES (CUSTOMER, SNACKS)
The first indicates the hotels each customer visits, the second tells which snacks each hotel serves and the last indicates which snacks are liked by each customer. Express the following query in relational algebra: print the hotels that serve a snack that customer Rama likes.
Theory Explanation. 
Question 202 
(a) If G is a group of even order, then show that there exists an element a ≠ e, the identity in g, such that a^{2} = e
(b) Consider the set of integers {1,2,3, 4,6,8,12,24} together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?
(i) group (ii) ring (iii) field (iv) lattice
Theory Explanation. 
Question 203 
(a) Uses Modus ponens (A, A →= B) or resolution to show that the following set is inconsistent:
(1) Q(x) → P(x)V ~ R(a) (2) R(a) ~ Q(a) (3) Q(a) (4) ~ P(y)
Where x and y are universally quantified variables, a is a constant and P, Q, R are monadic predicates.
(b) Let S be the set of all integers and let n > 1 be a fixed integer. Define for a, b ∈ S, a R biff ab is a multiple of n. Show that R is an equivalence relation and finds its equivalence classes for n = 5.
Theory Explanation. 
Question 204 
Which of the following three statements are true? Prove your answer.
 (i) The union of two recursive languages is recursive.
(ii) The language {O"n is a prime} is not regular.
(iii) Regular languages are closed under infinite union.
Theory Explanation. 
Question 205 
Give short answers to the following questions:
(i) Convert the following Pascal statement to a single assignment statement:
if x > 5 they y:=true else y:=false;(ii) Convert the Pascal statement repeat S until B; into an equivalent Pascal statement that uses the while construct.
(iii) Obtain the optimal binary search tree with equal probabilities for the identifier set (a_{1}, a_{2}, a_{3}) = (if, stop, while)
(iv) If a finite axiom system A for a theory is complete and consistent, then is every subsystem of A complete and consistent? Explain briefly.
Theory Explanation. 
Question 206 
(a) Analyse the circuit in figure and complete the following table:
(b) Find the minimum sum of products form of the logic function.
f(A,B,C,D) = ∑m(0,2,8,10,15) + ∑d(3,11,12,14)Where m and d denote the minterms and don’t cares respectively.
(c) Find the maximum clock frequency at which the counter in figure, can be operated. Assume that the propagation delay through each flipflop and AND gate is 10 ns. Also assume that the setup time for the JK inputs of the flipflops is negligible.
Theory Explanation. 
Question 207 
(a) Using D flipflop and gates, design a parallelin/serialout shift register that shifts data from left to right with the following input lines:
 (i) Clock CLK
(ii) Three parallel data inputs A, B, C
(iii) Serial input S
(iv) Control input .
(b) Design a 1024 bit serialin/serialout unidirectional shift register using a 1K × 1 bit RAM with data input D_{in}, data output D_{out} and control input . You may assume that availability of standard SSI and MSI components such as gates, registers and counters.
Theory Explanation. 
Question 208 
It is required to design a hardwired controller to handle the fetch cycle of a single address of an indexed instruction should be derived in the fetch cycle itself. Assume that the lower order 8 bits of an instruction constitute the operand field.
(a) Give the register transfer sequence for realizing the above instruction fetch cycle.
(b) Draw the logic schematic of the hardwired controller including the date path.
Theory Explanation. 
Question 209 
(a) Consider an 8085 based system operating with the following specification:
Crystal frequency : 6 MHz ROM map : 0000 through 07FF RAM map : 1000 through 17 FF: ROM requires one wait state. RAM requires no wait state.
Determine the instruction cycle time for each of the following instructions:
(i) ORI A, 22 (ii) DCR M
Assume the following initial conditions of the CPU registers (in hex) for each of the instructions:
A = 55, B = AA, C = F7, D = 10, H = 10, L = FF, PC = 0200, SP = 17FO.
(b) Developing an output port interface (draw a block schematic) for an 8085 based system with a demultiplexed address bus which incorporates a handshake protocol as per the timing diagram given in figure. The interface should include a status input port at I/O address 40H which reads the INTERRUPT and BUFFFULL signals through the most significant bit and the least significant bit, respectively. The output data port is at the same I/O address 40H and is activated by a write operation. Assume the availability of SSI and MSI level components only.
Write a short program segment which performs a 200 H byte programmed I/O data transfer to the device from memory address 3400 H,
Theory Explanation. 
Question 210 
(a) Consider the following pseudocode
(all data items are of type integer):
Procedure P (a, b, c); a:=2; c:=a+b; end {P} begin x:=1 y:=5; z:=100; P(x,x*y,z); Write (‘x=’,x,z=’,z) end:Determine its output, if the parameters are passed to the procedure P by (i) value, (ii) reference and (iii) name.
(b) For the following pseudocode, indicate the output, if
(i) static scope rules and (ii) dynamic scope rules are used
Var, a, b : integer; Procedure P; a:=5; b:=10 end {P}; procedure Q; var a, b : integer; P; end {Q}; begin a:=1; b:=2; Q; Write (‘a =’, a, ‘b=’,b) end.
Theory Explanation. 
Question 211 
Consider the following grammar for arithmetic expression using binary operators – and/which are not associative:
E → E−TT T → T/FF F → (E)id(E is the start symbol)
(a) Is this grammar unambiguous? If so, what is the relative precedence between – and/if not, give an unambiguous grammar that gives/precedence over 
(b) Does the grammar allow expressions with redundant parentheses as in (id/id) or in id(id/id)? If so, convert the grammar into one which does not generate expressions with redundant parentheses. Do this with minimum number of changes to the given production rules and adding at most one more production rule.
Theory Explanation. 
Question 212 
Consider the following scheme for implementing a critical section in a situation with three processes and P_{j} and P_{k}.
P_{i}; repeat flag [i]:=true; while flag [j] or flag [k] do case turn of j : if flag [j] then begin flag [i]:=false; while turn ≠ i do skip; flag [i] : true end; k : if flag [k] then begin flag [i]:=false, while turn ≠ i do skip; flag [i]:=true end end critical section if turn = i then turn:=j; flag [i]:=false noncritical section until false;
(a) Does the scheme ensure mutual exclusion in the critical section? Briefly explain.
(b) Is there a situation in which a waiting process can never enter the critical
section? If so, explain and suggest modifications to the code to solve this problem.
Theory Explanation. 
Question 213 
Suppose, a database consists of the following relations:
SUPPLIER (SCODE, SNAME, CITY) PART (PCODE, PNAME, PDESC, CITY) PROJECTS (PRCODE, PRNAME, CITY) SPRR (SCODE, PCODE, PRCODE, QJY)
(a) Write SQL programs corresponding to the following queries:
(i) Print PCODE value for parts supplied to any project in DELHI by a supplier in DELHI.
(ii) Print all triples (CITY, PCODE, CITY), such that a supplier in the first city supplies the specified part to a project in the second city, but do not print triples in which the two CITY values are the same.
(b) Write algebraic solutions to the following:
(i) Get SCODE values for suppliers who supply to both projects PR1 and PR2.
(ii) Get PRCODE values for projects supplied by at least one supplier not in the same city.
Theory Explanation. 
Question 214 
Consider the binary tree in Figure:
(a) What structure is represented by the binary tree?
(b) Give the different steps for deleting the node with key 5 so that the structure is preserved.
(c) Outline a procedure in pseudocode to delete an arbitrary node from such a binary tree with n nodes that preserves the structure. What is the worstcase timecomplexity of your procedure?
Theory Explanation. 
Question 215 
(a) Show that the product of the least common multiple and the greatest common divisor of two positive integers a and b is a*b.
(b) Consider the following first order formula:
(Ax)(Ey)R(x,y)∧(Ax)(Ay)(R(x,y) → ~R(y,x)) ∧(Ax)(Ay)(Az)(R(x,y)∧R(y,z) → R(x,z)) ∧(Ax) ~R(x,x)(Auniversal quantifier and Eexistential quantifier)
Does it have finite models?
Is it satisfiable? Is so, give a countable model for it.
Theory Explanation. 
Question 216 
(a) Find the number of binary strings w of length 2n with an equal number os 1’s and 0’s, and the property that every prefix and w has atleast as many 0’s as 1’s.
(b) Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has at least two vertices.
Theory Explanation. 
Question 217 
(a) Show that Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class or regular languages.
(b) Let L be the language of all binary strings in which the third symbol from the right is a_{1}. Give a nondeterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
Theory Explanation. 
Question 218 
Find if the following statements in the context of software testing are TRUE or FALSE.
(S1) Statement coverage cannot guarantee execution of loops in a program under test.
(S2) Use of independent path testing criterion guarantees execution of each loop in a program under test more than once.
True, True  
True, False  
False, True  
False, False 
Question 219 
Which of the following is TRUE only of XML but NOT HTML?
It is derived from SGML  
It describes content and layout  
It allows user defined tags  
It is restricted only to be used with web browsers 
Question 220 
Which of the following are NOT considered when computing function points for a software project?
 (O1) External inputs and outputs
(O2) Programming language to be used for the implementation
(O3) User interactions
(O4) External interfaces
(O5) Number of programmers in the software project
(O6) Files used by the system
02, 03  
01, 05  
04, 06  
02, 05 
Question 221 
A software project plan has identified ten tasks with each having dependencies as given in the following table:
Task Depends On T1  T2 T1 T3 T1 T4 T1 T5 T2 T6 T3 T7 T3, T4 T8 T4 T9 T5, T7, T8 T10 T6, T9
Answer the following questions:
(Q1) What is the maximum number of tasks that can be done concurrently?
(Q2) What is the minimum time required to complete the project, assuming that each task requires one time unit and there is no restriction on the number of tasks that can be done in parallel?
5, 5  
4, 5  
5, 4  
4, 4 
Question 222 
A software engineer is required to implement two sets of algorithms for a single set of matrix operations in an object oriented programming language; the two sets of algorithms are to provide precisions of 10^{3} and 10^{6}, respectively. She decides to implement two classes, Low Precision Matrix and High Precision Matrix, providing precisions 10^{3} and 10^{6} respectively. Which one of the following is the best alternative for the implementation?
 (S1) The two classes should be kept independent.
(S2) Low Precision Matrix should be derived from High Precision Matrix.
(S3) High Precision Matrix should be derived from Low Precision Matrix.
(S4) One class should be derived from the other; the hierarchy is immaterial.
S1  
S2  
S3  
S4 
Question 223 
Which of the following requirement specifications can be validated?
 (S1) If the system fails during any operation, there should not be any loss of data
(S2) The system must provide reasonable performance even under maximum load conditions
(S3) The software executable must be deployable under MS Windows 95, 2000 and XP
(S4) User interface windows must fit on a standard monitor's screen
S4 and S3  
S4 and S2  
S3 and S1  
S2 and S1 
Question 224 
The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 bytes per page is
0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0410.Suppose that the memory can store only one page and if x is the address which causes a page fault then the bytes from addresses x to x + 99 are loaded on to the memory. How many page faults will occur?
0  
4  
7  
8 
0200  Page fault, address till 299 in memory
0430  Page fault, address till 529 in memory
0499  No page fault
0510  No page fault
0530  Page fault, address till 629 in memory
0560  No page fault.
0120  Page fault, address till 219 in memory
0220  Page fault, address till 319 in memory
0240  No page fault
0260  No page fault
0320  Page fault, address till 419 in memory
0410  No page fault
So, total page faults = 7.
Question 225 
Given below are HTML lines,
With reference to the HTML lines given above, consider the following statements.
(i) Clicking on the point <80, 75> does not have any effect.
(ii) The web browser can identify the area applicable to the mouseclick within the image and the subsequent action to be taken without additional responses from the web server.
(iii) The dots in the cgibin URL will be resolved by the web browser before it is sent to the web server.
(iv) The "fd.html" request when sent to the web server will result in a GET request.
Exactly how many of the statements given above are correct?
0  
1  
2  
3 
Question 226 
Consider the XML document fragment given below:
Consider the XPath expression: *[not (self)::TOC]
What would be the result of the given XPath expression when the current node is Book?
The Title and Content elements  
The Content and TOC elements  
The Title and TOC elements  
The Title, Content and TOC elements

Question 227 
The following table shoes the time between failures for a software system
The reliability of the system for one hour of operation assuming an exponential model is
0.45  
0.63  
0.84  
0.95 
MIBF = (6+4+8+5+6)/5 = 29/5
The probability or reliability that the product will work for a defined period of time without failure is given by
R(T) = exp(T/MTBF); T = 1 hour
R(1) = e^{(1/(29/5))} = e^{(5/29)} = 0.84
Question 228 
Given the following algorithm for sorting an array X of N numbers:
SUBROUTINE SORT(X,N) IF(N < 2) RETURN FOR(i=2 TO N INCREMENT BY 1) FOR(j=1 TO i INCREMENT BY 1) IF (X[i] > X[j]) CONTINUE TEMP X[i] X[i] = X[j] X[j] = TEMP END FOR END FOR END SUBROUTINE
A good approximation of Halstead's estimated program length is
20  
50  
80  
110 
Question 229 
In the simplified flowchart given below, the shaded boxes represent code that is executed during a test case.
The Branch coverage is
3/4  
2/3  
1/2  
3/8 
Question 230 
Consider the CPM activity chart where an arc connecting two milestones is labeled with a task identifier and the time taken in days. For example in order to go from A to B, task T1 takes 180 days. A dashed line depicts an additional dependency that is equivalent to a zero time task.
The set of activities that lie on the critical path are
T1, T2, T8, T10  
T1, T3, T8, T10  
T1, T2, T3, T4, T5, T6, T7, T8, T9, T10  
T1, T4, T5, T7, T8, T10 
Question 231 
Consider the following pseudocode:
IF ((A > B) AND (C > D)) THEN A = A + 1 B = B + 1 ENDIF
The cyclomatic complexity of the pseudocode is
2  
3  
4  
5 
Question 232 
The contents of the text file t1.txt containing four lines are as follows:
a1 b1 a2 b2 a3 b2 a4 b1
The contents of the text file t2.txt containing five lines are as follows:
a1 c1 a2 c2 a3 c3 a4 c3 a5 c4
Consider the following Bourne shell script:
awk  F''' {Print S1, S2} ' t1.txt  while read a b ; do awk v aV = Sa  v bV = Sb  F'' 'aV = = S1 (print aV, bV, S2 )'t2.txt done
Which one of the following strings will NOT be present in the output generated when the above script in run? (Note that the given strings may be substrings of a printed line.)
"b1 c1"  
"b2 c3"  
"b1 c2"  
"b1 c3" 
Question 233 
The cyclomatic complexity of the flow graph of a program provides
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once  
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once  
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once  
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once 
Question 234 
With respect to software testing, consider a flow graph G with one connected component. Let E be the number of edges, N be the number of nodes, and P be the number of predicate nodes of G. Consider the following four expressions:
1. E  N + P
2. E  N + 2
3. P + 2
4. P + 1
The cyclomatic complexity of G is given by
1 or 3  
2 or 3  
2 or 4  
1 or 4 
Question 235 
A software program consists of two modules M_{1} and M_{2} that can fail independently, but never simultaneously. The program is considered to have failed if any of these modules fails. Both the modules are ‘repairable’ and so the program starts working again as soon as the repair is done. Assume that the mean time to failure (MTTF) of M_{1}is T_{1} with a mean time to repair (MTTR) of R_{1}. The MTTF of M_{2} is T_{2} with an MTTR of R_{2}. What is the availability of the overall program given that the failure and repair times are all exponentially distributed random variables?
Question 236 
Consider the following structure chart diagram. The boxes have function names embedded in them, while the variables are indicated along the arcs.
Given below are a set of statements relevant to the above diagram.
I. F3 and F6 can be in the same module.
II. F4 and F6 can be in the same module.
III. A4 is both an output and a control variable.
IV. It is incorrect to pass A1 as data and use it as a control variable.
Which combination of these statements is TRUE?
III and IV  
I and IV  
II and IV  
I, II and IV 
Question 237 
Consider the following XML DTD describing course information in a university:
<!ELEMENT Univ (Course+, Prof+)> <!ELEMENT Course (Title, Eval*)> <!ATTLIST Course Number ID #REQUIRED Instructor IDREF #IMPLIED> <!ELEMENT Title (#PCDATA)> <!ELEMENT Eval (#PCDATA)> <!ATTLIST Eval Score CDATA #REQUIRED> <!ELEMENT Prof EMPTY> <!ATTLIST Prof Name ID #REQUIRED Teaches IDREF #IMPLIED>
What is returned by the following XQuery?
let $as := //@Score for $c in /Univ/Course[Eval] let $cs := $c/Eval?@Score where min($cs) > avg($as) return $c
The professor with the lowest course evaluation  
Professors who have all their course evaluations above the university average  
The course with the lowest evaluation  
Courses with all evaluations above the university average 
Question 238 
Consider the following program module:
void swap(float* A1, float* A2) { float temp; if (*A1 = = *A2) return; temp = *A1; *A1 = *A2; *A2 = temp; return; }
The program volume for the above module using Halstead's method is
60  
63  
66  
69 
Question 239 
Consider the following program module:
void swap(float* A1, float* A2) { float temp; if (*A1 = = *A2) return; temp = *A1; *A1 = *A2; *A2 = temp; return; }
The program effort for the above module using Halstead's method is
315  
330  
393  
403 
Question 240 
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19).
The critical path for the above project and the slack of P2 are, respectively,
P1P2P4, 1 day  
P1P3P4, 1 day  
P1P3P4, 2 days  
P1P2P4, 2 days 
Question 241 
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19).
The costs (in Rupees per day) of crashing the expected phase completion times for the four phases, respectively, are 100, 2000, 50, and 1000. Assume that the expected phase completion times of the phases cannot be crashed below their respective most likely completion times. The minimum and the maximum amounts (in Rupees) that can be spent on crashing so that ALL paths are critical are, respectively.
100 and 1000  
100 and 1200  
150 and 1200  
200 and 2000 
Question 242 
A function f defined on stacks of integers satisfies the following properties.
f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, 3, 2, 1, 2 in order from bottom to top, what is f(S)?
6  
4  
3  
2 
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,3)) = max(2,0) + (3) = 2  3 = 1
f(push(1,2)) = max(1,0) + 2 = 0 + 2 = 2
f(push(2,1)) = max(2,0)+ (1) = 2  1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
Question 243 
Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database by a successful transaction persist
Except in case of an Operating System crash  
Except in case of a Disk crash  
Except in case of a power failure  
Always, even if there is a failure of any kind 
Question 244 
In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit stuffing is employed, the transmitter sends the data sequence 01110110 as
01101011  
011010110  
011101100  
0110101100 
Thus using the above logic,
Delimiter flag: 0111
Data sequence: 01110110
So, for a flag of 4 bits we will compare data sequence with a pattern of 3 bits, i.e., 011.
0 1 1 0 1 0 1 1 0 0
In the above pattern the underlined bits are found matched. Hence, 0 in italics is stuffed. Thus resulting in the data sequence as 0110101100 which is option (D).
Question 245 
Array  
Stack  
Queue  
Tree 
The queue follows the First In First Out (FIFO) queuing method, and therefore, the neighbours of the node will be visited in the order in which they were inserted in the node i.e. the node that was inserted first will be visited first, and so on.
Question 246 
The traffic carry capacity of the network  
The total number of nodes in the network  
The number of patterns that can be stored and recalled in a network  
None of the above 
Question 247 
Content presented to search engine spider is different from that presented to the user’s browser  
Content present to search engine spider and browser is the same  
Contents of the user’s requested website are changed  
None of the above 
→ During cloaking, the search engine spider and the browser are presented with different content for the same Web page.
→ HTTP header information or IP addresses assist in sending the wrong Web pages.
→ Searchers will then access websites that contain information they simply were not seeking, including pornographic sites.
→ Website directories also offer up their share of cloaking techniques.
Question 248 
B, C, D, A, E  
C, B, E, A, D  
A, B, C, D, E  
E, D, C, B, A 
A) F= E * 0.5
B) E=A+B
C) D=B+0.5
D) G=E+F
E) C=A+10.5
It is given A, B, C are already assigned values, so we can perform any of B or C or E first but not A. so option(c) is incorrect .
Option(a) is incorrect because we can't perform operation D before operation A.
Option(d) is incorrect because we can't perform operation D before operation A.
Hence option(b) is only correct.
Question 249 
The null hypothesis is rejected even though it is true  
The null hypothesis is accepted even though it is false  
Both the null hypothesis as well as alternative hypotheses are rejected  
None of the above 
Question 250 
Reflexivity  
Augmentation  
Transitivity  
Mutual dependency 
Axiom of Reflexivity:
This axiom states: if Y is a subset of X, then X determines Y
Axiom of Augmentation:
The axiom of augmentation, also known as a partial dependency, states if X determines Y, then XZ determines YZ, for any Z
Axiom of Transitivity:
The axiom of transitivity says if X determines Y, and Y determines Z, then X must also determine Z.
Question 251 
row of the table consisting of condition entries  
row of the table consisting of action entries  
column of the table consisting of condition entries and corresponding action entries  
columns of the table consisting of conditions of the stub 
Question 252 
Multipart/mixed  
Multipart/parallel  
Multipart/digest  
Multipart/alternative 
This document defines a "parallel" subtype of the multipart Content Type. This type is syntactically identical to multipart/mixed, but the semantics are different. In particular, in a parallel entity, the order of body parts is not significant.
Question 253 
x = 4 , y = 4  
x = 3 , y = 3  
x = 8 , y = 7.25  
x = 3 , y = 4 
Question 254 
Border  
HEIGHT  
WIDTH  
SRC 
Specifies the URL of an application to be embedded.
Question 255 
XOR  
NOR  
XNOR  
NAND 
An XOR gate implements an exclusive or; that is, a true output results if one, and only one, of the inputs to the gate is true.
If both inputs are false (0/LOW) or both are true, a false output results
The diagram gives Boolean expression X.Y+ X'Y
Question 256 
XY' + X  
X'Y + XY'  
XY + XY'  
XY + X'Y' 
A high output (1) results if both of the inputs to the gate are the same. If one but not both inputs are high (1), a low output (0) results.
Question 257 
Task  
Program  
Process  
Light weight process 
Question 258 
SCI number  
Cyclomatic complexity  
LOC  
Fog index 
→ FOG index gives the average length of words and sentences in a document. The Fog Index is a readability test which predicts whether a document is easy to read or if it is difficult to read.
Question 259 
which is written in C++  
which requires an intermediate layer  
which communicates through Java sockets  
which translates JDBC function calls into API not native to DBMS 
Written completely in Java, type 4 drivers are thus platform independent. They install inside the Java Virtual Machine of the client. This provides better performance than the type 1 and type 2 drivers as it does not have the overhead of conversion of calls into ODBC or database API calls. Unlike the type 3 drivers, it does not need associated software to work.
As the database protocol is vendor specific, the JDBC client requires separate drivers, usually vendor supplied, to connect to different types of databases.
Advantages Completely implemented in Java to achieve platform independence.
These drivers don't translate the requests into an intermediary format (such as ODBC).
The client application connects directly to the database server. No translation or middleware layers are used, improving performance.
The JVM can manage all aspects of the applicationtodatabase connection; this can facilitate debugging.
Disadvantages Drivers are database specific, as different database vendors use widely different (and usually proprietary) network protocols.
Type1 driver (or) JDBCODBC bridge driver
Type2 driver (or) NativeAPI driver
Type3 driver (or) Network Protocol driver
Type4 driver (or) Thin driver
Question 260 
You can set the initial height at which the gun fires. As the game progresses, you can reset the height, but only to a lower value. You are given in advance the height at which each spaceship flies. There are N spaceships numbered 1, 2, . . . , N in the order in which they fly across the screen. For 1 ≤ i ≤ N , h[i] denotes the height at which spaceship i flies.
(a) Let V [i] denote the maximum number of spaceships from i, i+1, . . . , N that you can shoot down with a single gun. Write a recurrence for V [i] and describe a strategy to compute V [i] using dynamic programming. What is the space and time complexity of your solution?
(b) Describe an algorithm to compute the minimum number of guns required to shoot down all the spaceships. Each gun can be initialized separately to a firing height and each gun can be separately reset to a lower value.
Descriptive Explanation 
V [N ] = 1
V [i] = 1 + max{V [j]  j > i and h[i] ⩾ h[j]}
The dynamic programming algorithm maintains an array V of size N , to be filled in from V [N ] to V [1]. Computing the value of V [i] takes O(N ) time, since it involves potentially examining all entries from V [i + 1] to V [N ]. Thus the time taken overall is O(N ^{2} ). The space required is O(N ).
(b) The above algorithm can be modified to produce not just the length of the longest descending subsequence, but the subsequence itself. Once we do this, we delete these entries from the h list and find the longest descending subsequence now. We repeat this process till the original h list has been decomposed into disjoint descending subsequences. Since each of these subsequences can be handled by one gun, the minimum number of guns required to shoot down all the spaceships is the number of disjoint subsequences computed above.
Question 261 
(a) You are given a queue containing 5 elements. Using a single additional temporary variable X, write down a sequence of statements each being one of Enque, Deque, Print so that the output of the program results in the 5 elements of the queue being printed in reverse order.
(b) If the queue had n elements to begin with, how many statements would you need to print the queue in reverse order?
Descriptive Explanation 
(b) Each time we do an X = Deque followed by an Enque(X), we move the element at the head to the tail. Repeating these two statements n − 1 times moves the last element to the head, while preserving the order among the rest of the list. Issuing a Print instruction now prints the current head of the list (which was originally the last element).
Thus we need 2(n − 1) + 1 instructions to move the last element to the head and print it. At this point, the last element is what was originally the last but one element. If we now repeat the above block of 2(n − 1) + 1 instructions, we print the second last element of the original queue, while bringing the last two elements of the original queue to the head.
Extending this logic, we see that if repeat the block of code n times, we end up printing the queue in reverse. The number of statements required is n(2n − 1).
Question 262 
Based on table "CLUB", which SQL query will help us to know the number of "MONTHLY" members, who joined the club after "01JAN07"
SELECT*, COUNT () FROM CLUB WHERE TYPE = "MONTHLY'' AND DOJ > = "01JAN07'';  
SELECT FROM CLUB COUNT (*) WHERE TYPE = "MONTHLY" AND DOJ "01JAN07";  
SELECT COUNT (*) FROM CLUB WHERE TYPE = "MONTHLY" OR DOJ = "01 JAN07";  
SELECT COUNT (*) FROM CLUB WHERE TYPE = "MONTHLY" AND DOJ > "01JAN07"; 
COUNT() returns 0 if there were no matching rows.
Question 263 
vileged  
Running  
Ready  
Blocked 
Ready The process is waiting to be assigned to a processor.
Running Instructions are being executed.
Waiting The process is waiting for some event to occur(such as an I/O completion or reception of a signal).
Terminated The process has completed its execution.
Question 264 
yes  
No  
Auto  
None 
< frame scrolling="autoyesno" >
Attribute Values
Question 265 
min (m, n)  
max (m, n)  
m+n1  
mn 
Question 266 
P+QR=(P+Q)(P+R)
De Morgan's law  
Associative law  
Commutative law  
Distributive law 
A(B + C) = A.B + A.C (OR Distributive Law)
A + (B.C) = (A + B).(A + C) (AND Distributive Law)
Question 267 
aba  
bab  
abba  
aabb 
Question 268 
Chetan does not attend  
Akash does not attend  
either (a) or (b)  
none of the above 
Question 269 
Name2  
Total  
class  
Derived 
We can’t use keywords as identifier names.
Question 270 
string containing only 1’s  
string containing only 0’s  
string containing two 0’s  
string containing 1’s and 0’s 
→ This way, for each intended image there are actually two bitmaps:
1. Actual image, in which the unused areas are given a pixel value with all bits set to 0s.
2. Additional mask, in which the correspondent image areas are given a pixel value of all bits set to 0s and the surrounding areas a value of all bits set to 1s.
In the sample at right, black pixels have the allzero bits and white pixels have the allone bits.
Question 271 
1  
2  
8  
16 
Currently, an 18core processor is the best you can get in consumer PCs.
Each “core” is the part of the chip that does the processing work. Essentially, each core is a central processing unit (CPU).
From the given information , there are two quad core chips are available
So, total number of physical CPUs = 2*4 = 8
Each CPU has two logical CPU in hyper threading
So, 8 physical CPU have 2*8 = 16 logical CPU.
Question 272 
Random Programming  
Modular Programming  
.NET Programming  
Object Oriented Programming 
Each module meant for a specific functionality.
Question 273 
Always 0  
Always 1  
Retains the last value when enable input was high  
Disconnected state 
Question 274 
*  
::  
:  
' 
Question 275 
Active  
Static  
Dynamic  
Passive 
A static web document resides in a file that it is associated with a web server. The author of a static document determines the contents at the time the document is written. Because the contents do not change, each request for a static document results in exactly the same response.
→ Dynamic:
A dynamic web document does not exist in a predefined form. When a request arrives the web server runs an application program that creates the document. The server returns the output of the program as a response to the browser that requested the document. Because a fresh document is created for each request, the contents of a dynamic document can vary from one request to another.
→ Active:
An active web document consists of a computer program that the server sends to the browser and that the browser must run locally. When it runs, the active document program can interact with the user and change the display continuously.
Question 276 
EBCDIC  
Unicode  
ASCII  
QRcode 
Question 277 
V/ (2^{R} 1)  
(2^{R1}).V/(2^{R} 1)  
(2^{R1}).V  
V/(2^{R1}) 
Question 278 
A graphic display system has a frame buffer that is 640 pixels wide, 480 pixels high and 1 bit of color depth. If the access time for each pixel on the average is 200 nanoseconds, then the refresh rate of this frame buffer is approximately :
16 frames per second  
19 frames per second  
21 frames per second  
23 frames per second

 Width (or) wide = 640 pixels
 Height (or) High = 480 pixels
 Color depth =1 bit/pixel
 Access time of each pixel on the average = 200ns
 Refresh rate of frame buffer = ?
Step1: Graphic display system = 640 * 480 =307200
Step2: Memory required for Graphic display system = 640 * 480 * 1 = 307200
Step3: Total screen access time = Memory required for Graphic display system * Access time of each pixel
= 307200 * 200 ns
= 61440000 ns
Step4: Refresh rate of frame buffer per second =(10^{9})/61440000
= 16.27604166 frames per second
[ Note: 10^{9} = 1000000000 ]
Question 279 
TCP is a connectionless unreliable protocol. [Option ID = 11080]  
TCP is a connectionless reliable protocol. [Option ID = 11079]  
TCP is a connectionoriented reliable protocol. [Option ID = 11077]  
TCP is a connectionoriented unreliable protocol. [Option ID = 11078] 
Question 280 
Swapping  
Demand Paging  
Deadlock  
Page Fault 
Question 281 
Merge Sort  
Travelling Salesman Problem  
Knapsack Problem  
Optimal Binary Search Tree Problem 
Travelling Salesman Problem → Dynamic Programming
Knapsack Problem → Dynamic Programming
Optimal Binary Search Tree Problem → Dynamic Programming
Question 282 
(010 ) _{ 3}  
(011 )_{3}  
(121 ) _{ 3}  
(121 )_{ 2} 
Question 283 
atomic attribute  
candidate attribute  
non prime attribute  
prime attribute 
1. the relation does not have two distinct tuples (i.e. rows or records in common database language) with the same values for these attributes (which means that the set of attributes is a superkey)
2. there is no proper subset of these attributes for which (1) holds (which means that the set is minimal).
● Candidate keys are also variously referred to as primary keys, secondary keys or alternate keys.
● The constituent attributes are called prime attributes. Conversely, an attribute that does not occur in ANY candidate key is called a nonprime attribute.
Ex: AB, BC, CD are candidate keys of R(ABCD). In the FDs set one attribute may not be part of all the FDs.
Question 284 
PC  
Server  
Smartphone  
Switch 
● A network switch (also called switching hub, bridging hub, officially MAC bridge) is a computer networking device that connects devices on a computer network by using packet switching to receive, process, and forward data to the destination device.
Question 285 
Stack addressing  
Indirect addressing  
Immediate addressing  
None of the above 
e.g. ADD Pop top two items from stack and add
> The stack mode of addressing is a form of implied addressing,the machine instructions need not include a memory reference but implicitly operate on top of stack.
Question 286 
CPU Scheduler  
long term Scheduler  
Context Switching  
Medium term Scheduler 
→ The longterm scheduler is responsible for controlling the degree of multiprogramming.
Question 287 
2,1  
1,2  
1,1  
2,2 
Step2: Append 0 in LSB of 2’s complement number=000111100
Step3: Use the following codes. Procedure starts with LSB
(00→ 0)
(11→ 0)
(01→ +1)
(10→ 1)
1 1 1 0 0 0 0 1 0
0 0 1 0 0 0 +1 1
Step4: There are total 1 additions and 2 subtractions
Question 288 
32564  
44155  
50215  
43562 
= 10x16^{ 3} +12x16 ^{2} + 7x16 + 11
= 40960 + 3072 + 112 +11
= 44155
Question 289 
remove(varname)  
free(varname)  
delete(varname)  
dalloc(varname) 
Syntax of free()
free(ptr);
This statement frees the space allocated in the memory pointed by ptr.
Question 290 
Suppose a system has 12 instances of some resources with n processes competing for that resource. Each process may require 4 instances of the resource. The maximum value of n for which the system never enters into deadlock is
3  
4  
5  
6 
→ If we allocates 3 instance( one instance less than the requirement of each process) of the resource and to one process we allocate its minimum requirement then in that way with limited available instance of resource, without entering into deadlock we can fulfill requirement of maximum number of processes.
→ Now in question it is given that we have 12 instance then using above strategy we can allocate resources to 3 process without entering into deadlock.
Question 291 
Cells are generally smaller that packets  
Cells do not incorporate physical address  
all cell have the same fixed length  
packet cannot be switched 
● For example, the fixedlength, 53byte messages sent in Asynchronous Transfer Mode (ATM) are called cells. Like frames, cells usually are used by technologies operating at the lower layers of the OSI model.
Question 292 
Consider the following statements related to ANDOR Search algorithm.
 S_{1} : A solution is a subtree that has a goal node at every leaf.
S_{2} : OR nodes are analogous to the branching in a deterministic environment
S_{3} : AND nodes are analogous to the branching in a nondeterministic environment.
Which one of the following is true referencing the above statements?
Choose the correct answer from the code given below:
Code:S_{1} False, S_{2} True, S_{3} True
 
S_{1} True, S_{2} True, S_{3} True  
S_{1} False, S_{2} True, S_{3} False
 
S_{1} True, S_{2} True, S_{3} False

• A solution in an ANDOR tree is a sub tree whose leaves are included in the goal set.
Question 293 
248000  
44000  
19000  
25000 
Question 294 
Which homogeneous 2D matrix transforms the figure (a) on the left side to the figure (b) on the right ?
The image in figure a is translated (by 1 unit in x axis), scaled (2 units in y axis) and rotated (90 degrees counterclockwise) to figure in b.
Question 295 
Identify the correct sequence in which the following packets are transmitted on the network by a host when a browser requests a web page from a remote server, assuming that the host has been restarted.
HTTP GET request, DNS query, TCP SYN
 
DNS query, TCP SYN, HTTP GET request  
TCP SYN, DNS query, HTTP GET request
 
DNS query, HTTP Get request, TCP SYN 
Step 1: DNS query is sent to Domain name server to convert the Domain name into it’s IP address.
Step 2: TCP SYN request packet is sent by sender to establish a connection for data transmission.
Step 3: HTTP GET request is used to request data from a specified IP address.
Question 296 
Which of the following is true for semidynamic environment ?
The environment itself does not change with the passage of time but the agent’s performance score does.
 
The environment change while the agent is deliberating.
 
Even if the environment changes with the passage of time while deliberating, the performance score does not change.
 
Environment and performance score, both change simultaneously.

The environment itself does not change with the passage of time but the agent’s performance score does.
Question 297 
T(n)=O(n^{2})  
T(n)=O(nlogn) 
Question 298 
Consider the following statements
 S1: A heuristic is admissible if it never overestimates the cost to reach the goal
S2: A heuristic is monotonous if it follows triangle inequality property.
Which one of the following is true referencing the above statements?
Choose the correct answer from the code given below:
Code:Statement S1 is true but statement S2 is false.  
Statement S1 is false but statement S2 is true.
 
Neither of the statements S1 and S2 are true.  
Both the statements S1 and S2 are true.

Question 299 
O(1) and θ(logn)  
θ(1) and θ(logn)  
O(logn) and θ(logn)  
θ(logn) and O(1) 
→ many times that divide is called in overall sorting procedure is O(logn)
Question 300 
Which of the following statement/s is/are true ?

(i) Facebook has the world’s largest Hadoop cluster.
(ii) Hadoop 2.0 allows live stream processing of real time data
Choose the correct answer from the code given below :
Code:Neither (i) nor (ii)  
Both (i) and (ii)
 
(i) only
 
(ii) only

Here are some of the details about this single HDFS cluster:
1. 21 PB of storage in a single HDFS cluster
2. 2000 machines
3. 12 TB per machine (a few machines have 24 TB each)
4. 1200 machines with 8 cores each + 800 machines with 16 cores each
5. 32 GB of RAM per machine
6. 15 mapreduce tasks per machine
That's a total of more than 21 PB of configured storage capacity! This is larger than the previously known Yahoo!'s cluster of 14 PB.
→ Hadoop 2.0 allows live stream processing of real time data.
Question 301 
A = {a^{n}b^{n}a^{m}b^{m } m, n>=0}
B = {a^{n}b^{n}a^{m}b^{n}  m, n>=0}
C = {a^{m}b^{n}  m≠2n,m, n>=0}
A and B only  
A and C only  
B and C only  
C only 
This way language 'A' can be accepted by the push down automat. Hence A is CFL.
StatementB: When last 'b' i.e., b^{n} after a^{m} comes as input then top of the stack will contain a^{m}
So we can't compare a^{n} with a^{n}b^{n}. Hence it is not CFL
StatementC: It is a CFL
Question 302 
R is NPcomplete  
R is NPhard  
Q is NPcomplete  
Q is NPhard 
Question 303 
14  
12  
336  
168 
Here, n=4.
Total number of binary trees are 14.
Question 304 
Consider the midpoint (or Bresenham) algorithm for rasterizing lines given below :
(1) Input (x_{1},y_{1}) and (x_{2},y_{2}) (2) y = y_{1} (3) d = f(x_{1}+1, y_{1}+½) // f is the implicit form of a line (4) for x = x_{1} to x_{2} (5) do (6) plot (x,y) (7) if (d<0) (8) then (9) y = y+1 (10) d = d+(y_{1}  y_{2}) + (x_{2}  x_{1}) (11) else (12) d = d+(y_{1}  y_{2}) (13) end (14) end
Which statements are true ?
 P: For a line with slope m>1, we should change the outer loop in line (4) to be over y.
Q: Lines (10) and (12) update the decision variable d through an incremental evaluation of the line equation f.
R: The algorithm fails if d is ever 0.
Choose the correct answer from the code given below :
Code :Q and R only  
P only
 
P and Q only  
P, Q and R

Line 10 and 12 will update the value of d , So the statement Q is true.
Question 305 
Encryption : X’s private key followed by Y’s private key. Decryption : X’s public key followed by Y’s public key.  
Encryption : X’s private key followed by Y’s public key; Decryption : X’s public key followed by Y’s private key  
Encryption : X’s private key followed by Y’s public key; Decryption : Y’s private key followed by X’s public key.  
Encryption : X’s public key followed by Y’s private key; Decryption : Y’s public key followed by X’s private key. 
Encryption: Source has to encrypt with its private key for forming Digital signature for Authentication. Source has to encrypt the (M, σ) with Y’s public key to send it confidentially. Decryption: Destination Y has to decrypt first with its private key, then decrypt using source public key.
Question 306 
(P) SHA256
(Q) AES
(R) DES
(S) MD5
P and S only  
P and Q only  
R and S only  
P and R only 
→ SHA256 and SHA512 are novel hash functions computed with 32bit and 64bit words, respectively. They use different shift amounts and additive constants, but their structures are otherwise virtually identical, differing only in the number of rounds.
→ The MD5 messagedigest algorithm is a widely used hash function producing a 128bit hash value. Although MD5 was initially designed to be used as a cryptographic hash function, it has been found to suffer from extensive vulnerabilities. It can still be used as a checksum to verify data integrity, but only against unintentional corruption. It remains suitable for other noncryptographic purposes, for example for determining the partition for a particular key in a partitioned database.
Question 307 
2^{20}  
2^{24}  
2^{14}  
2^{21} 
The network ID is 24 bits long.
The host ID is 8 bits long.
→ The higher order bits of the first octet of IP addresses of class C are always set to 110. The remaining 21 bits are used to determine network ID.
→ The 8 bits of host ID is used to determine the host in any network. The default subnet mask for class C is 255.255.255.x. Class C has a total of:
2^{21} = 2097152 network address
2^{8} – 2 = 254 host address
IP addresses belonging to class C ranges from 192.0.0.x – 223.255.255.x.
Question 308 
245.248.136.0/21 and 245.248.128.0/22  
245.248.128.0/21 and 245.248.128.0/22  
245.248.132.0/22 and 245.248.132.0/21  
245.248.136.0/24 and 245.248.132.0/21 
Question 309 
Network layer – 4 times, Data link layer – 4 times  
Network layer – 4 times, Data link layer – 6 times  
Network layer – 2 times, Data link layer – 4 times  
Network layer – 3 times, Data link layer – 4 times 
Therefore ,
Question 310 
UDP is slower  
DNS servers has to keep connections  
DNS requests are generally very small and fit well within UDP segments  
None of these 
→ UDP itself is not reliable, but higher level protocols  as DNS  may maintain reliability, e.g. by repeating the UDP datagram in the case of no response.
→ But the last is not the case for DNS. DNS itself uses sometimes besides UDP (as its primary protocol) the reliable Transmission Control Protocol (TCP).
→ The last is used when the response data size exceeds 512 bytes, and for tasks which require the reliable delivery (e.g. zone transfers).
→ UDP is much faster. TCP is slow as it requires 3 way handshake. The load on DNS servers is also an important factor. DNS servers (since they use UDP) don’t have keep connections.
→ DNS requests are generally very small and fit well within UDP segments.
→ UDP is not reliable, but reliability can added on application layer. An application can use UDP and can be reliable by using timeout and resend at application layer.
Question 311 
A : Send an email from a mail client to mail server
B : Download email headers from mail box and retrieve mails from server to a cache
C : Checking email through a web browser
The application level protocol used for each activity in the same sequence is
SMTP, HTTPS, IMAP  
SMTP, POP, IMAP  
SMTP, IMAP, HTTPS  
SMTP, IMAP, POP  
None of the above 
→ POP download email headers from mailbox and retrieve mails from servers to a cache.
→ HTTPS checking email through a web browser.
Question 312 
5  
10  
40  
80 
 Round trip delay between A and B = 40ms
 Station A using frame size = 32 bytes. 32 bytes=32*8 bits
 Bottleneck bandwidth on the path A and B = 64kbps
 Window size=?
Step1: First we have to find transmission time
Transmission time= Frame size/bandwidth
= 32*8/(64) ms
= 4 ms
Step2: We have to find window size.
Standard Utilization formula is = n/(1+2a)
where ‘a’ is Propagation time / transmission time
= n/(1+2a)
= n/(1+40/4)
= n/11
Maximum utilization is ‘n’ = 11
Question 313 
20, 7  
19, 8  
20, 8  
21, 9 
Physical Address =4GB
Cache Size =16KB
Block Size = 8 words = 8* 32 bits = 256 bits = 32 Bytes  because 1 word =32 bits
No.of cache lines /blocks = 16KB/ 32 B = 2^14/ 2^5= 2^9 i.e 512 lines
No of sets = No of cache lines / 2  because it is 2way setassociative cache
= 2^9 /2 = 2^8 sets => 8 set bits
Now, because it is setassociative cache memory physical address generated by CPU is divided into 3 parts  first part indicate number of tag bits.
Second part indicates no of bits required to address each set.
Third part indicates  no. of bits for block offset.
Let suppose tag bits = X
Therefore , we get
X+8+5 = 32 => X= 19 are the tag bits
Question 314 
for (i =0; i < 512; i++)
{
for (j =0; j < 512; j++)
{
x += A[i][j];
}
}
Assuming that array is stored in order A[0][0], A[0][1], A[0][2]……, the number of cache misses is
16384  
512  
2048  
1024 
→ No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×2^{10}B / 128B = 2^{15} / 2^{7} = 256
→ No. of array elements in each block = Block size / Element size = 128B / 8B =16
→ Total misses for (P1)=Array size * No. of array elements / No. of cache blocks = (512×512) * 16 / 256=16384
Question 315 
–2^{32} to 2^{32}  
–2^{31} to 2^{32}1  
–2^{31} to 2^{31}1  
–2^{31}1 to 2^{32}1 
Question 316 
11000100  
10011100  
10100101  
11010101 
B = 0000 1010 = 10_{10} [2's complement number]
A×B = 6×10 =  60_{10}
⇒ 60_{10} = 10111100_{2}
= 11000011_{2} (1's complement)
= 11000100_{2} (2's complement)
Question 317 
 The j + 1st instruction uses the result of jth instruction as an operand
 Conditional jump instruction
 jth and j + 1st instructions require ALU at the same time
A and B only  
B and C only  
B only  
A , B and C 
B is belongs to the Control hazard.
C is belongs to the Structural hazard.
→ Hazards are the problems with the instruction pipeline in CPU micro architectures.
Question 318 
Smaller block size incurs lower cache miss penalty  
Smaller block size implies better spatial locality  
Smaller block size implies smaller cache tag  
Smaller block size implies lower cache hit time 
Question 319 
Immediate addressing
 
Register addressing  
Register Indirect addressing  
Indexed addressing 
→ Addresses have two parts: the number of an index register and a constant. The address of the operand is the sum of the constant and the contents of the index register. It contains indexed (direct) addressing, indexed immediate addressing and indexed indirect addressing.
Question 320 
If it takes O(n log n) time  
It uses divide and conquer technique  
Relative order of occurrence of nondistinct elements is maintained  
It takes O(n) space 
→ That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
Question 321 
q, r, p  
p, q, r  
q, p, r  
r, q, p 
Hash table construction→ O(n^{2})
AVL tree construction → O(logn)
Question 322 
i+j  
j+i(i1)/2
 
i+j1  
i+j(j1)/2 
Now at i^{th} row, the j^{th} element will be at j position.
So the index of (i, j)^{th} element of lower triangular matrix in this new representation is
j = i(i1)/2
Question 323 
7, 8, 9, 5, 6  
5, 9, 6, 7, 8  
7, 8, 9, 6, 5  
9, 8, 7, 5, 6 
→ Remaining options are not possible.
Question 324 
A. 1, 2, 3……n
B. n, n1, n2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then
C1>C2  
C1=C2  
C1  
Cannot say anything for arbitrary n 
→ Elements are already sorted order it gives worst case complexity O(n^{2})
→ If all elements are having same weight, it performs worst case complexity.
Question 325 
61, 52, 14, 17, 40, 43  
10, 65, 31, 48, 37, 43  
81, 61, 52, 14, 41, 43  
17, 77, 27, 66, 18, 43 
Question 326 
h(x) = ((ord(x)  ord(A) + 1)) mod 10
If linear probing is used to resolve collisions, then the following insertion causes collision
Y  
C  
M  
P

Hash table size=10 and index starts from 0 to 9.
String=K R P C S N Y T J M
hash function = h(x) = ((ord(x) – ord(A) + 1)) mod 10
Question 327 
9, 8, 6, 4, 2, 3, 0, 1, 5, 7  
0, 1, 2, 3, 4, 5, 6, 7, 8, 9  
0, 2, 4, 3, 1, 6, 5, 9, 8, 7  
9, 8, 7, 6, 5, 4, 3, 2, 1, 0 
In order: 0 1 2 3 4 5 6 7 8 9
Question 328 
10, 8, 7, 5, 3, 2, 1  
10, 8, 7, 2, 3, 1, 5  
10, 8, 7, 1, 2, 3, 5  
10, 8, 7, 3, 2, 1, 5 
The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 329 
3  
1  
2  
4 
Question 330 
cannot have more than 19 nodes  
has exactly 19 nodes  
has exactly 17 nodes  
has exactly 20 nodes 
→ A strictly binary tree with N leaves always contains 2N – 1 nodes.
(2*10)1 =19
Question 331 
2  
3  
4  
5 
2^{h}1=7
h=3
Question 332 
Every simple path from a node to a descendant leaf contains the same number of black nodes  
If a node is red, then one children is red and another is black  
If a node is red, then both its children are red  
Every leaf node (sentinel node) is red 
→ A red black tree is a kind of selfbalancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node.
→ These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
→ Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case.
→ When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.
→ The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.
Question 333 
d b e a f c g
and
a b d e c f g
respectively. The post order traversal of a binary tree is
e d b g f c a  
e d b f g c a  
d e b f g c a  
d e f g b c a 
Pre order: Root Left Right
Post order: Left Right Root
Inorder: d b e a f c g
Pre order: a b d e c f g
Post order: d e b f g c a
Question 334 
M : Increasing the number of page frames allocated to a process sometimes increases the page fault rate
N : Some programs do not exhibit locality of reference
Which one of the following is true?
Both M and N are true and N is the reason for M  
Both M and N are true and N is not the reason for M  
Both M and N are false  
M is false, but N is true 
→ Belady Anomaly states that when number of page frames. Increases then increase the page fault rate.
M is True:
→ Locality of reference states that it’s a phenomenon in which the same values of related storage locations are frequently accessed depending on the memory access pattern.
N is also True:
→ Q is not the reason for P, because Belady Anomaly not depends on the locality of reference.
Question 335 
< TR *gt;  
< TD >  
< TH >  
< TABLE >  
A and D 
Question 336 
1  
2  
3  
4 
Total no.of context switches is 2.
Question 337 
n^{2}  
2^{n+1} 1  
2^{n}  
2^{n} 1 
It is a operation where process creates a copy of itself.
1,3,7,15,31,... ⇒ 2^{n}1
Question 338 
Matching the table in the order A, B, C gives
t, u, s  
s, t, u  
u, s, t  
u, t, s 
Rate Monotonic scheduling is a priority assignment algorithm used in RealTime operating systems (RTOS) with a static priority scheduling class.
Fair scheduling is a process of distributing the CPU usage equally among system users or groups and which is guarantee scheduling process.
Question 339 
96  
100  
97  
92 
Page 1 …….. Page 100 causes 100 faults.
Now, when they are accesses in reverse order page 100, 99, 98, 97 are already present. So we get 96 page faults. So, total of 196 page faults.
Question 340 
User level threads are not scheduled by the kernel  
Context switching between user level threads is faster than context switching between kernel level threads  
When a user thread is blocked all other threads of its processes are blocked  
Kernel level threads cannot utilize multiprocessor systems by splitting threads on different processors or cores 
Question 341 
 Abstraction and encapsulation
 Strictlytyped
 Typesafe property coupled with subtype rule
 Polymorphism in the presence of inheritance
A and B only  
A, D and B only  
A and D only  
A, C and D only 
Question 342 
Those that support recursion  
Those that use dynamic scoping  
Those that use global variables  
Those that allow dynamic data structures 
→ So the languages which allow dynamic data structure require heap allocation at runtime.
Question 343 
int i, j, x, y, m, n;
n=20;
for (i = 0, i < n; i++)
{
for (j = 0; j < n; j++)
{
if (i % 2)
{
x + = ((4*j) + 5*i);
y += (7 + 4*j);
}
}
m = x + y;
Which one of the following is false
The code contains loop invariant computation  
There is scope of common subexpression elimination in this code  
There is scope of strength reduction in this code  
There is scope of dead code elimination in this code 
→ 5*i can be moved out of inner loop. So can be i%2, here loop invariant computation can be done, so option A is correct.
→ 4*i, 5*j can also be replaced so there is a scope of strength reduction. So C is true.
→ But there is no dead code to eliminate, we can replace the variable representation only.
Question 344 
Matching A, B, C, D in the same order gives :
p, q, r, s  
q, r, s, p  
r, s, q, p  
r, s, p, q 
An activation record is another name for Stack Frame. It's the data structure that composes a call stack. It is generally composed of:
1)Locals to the callee
2)Return address to the caller
3)Parameters of the callee
The Call Stack is thus composed of any number of activation records that get added to the stack as new subroutines are added, and removed from the stack (usually) as they return.
The actual structure and order of elements is platform and even implementation defined.
Assembler :
A computer program which translates assembly language to machine language.
It maintains a location counter to assign storage addresses to each instruction of our program.
Reference counter :
→ Reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object, block of memory, disk space or other resource.
→ Tracks for each object, counts the number of references made by it and when the count reaches zero, the object becomes inaccessible and gets destroyed.
A linking loader generally performs the reallocation of code.
Question 345 
0  
13  
18  
5 
After 20 P operations value of semaphore = 7 – 20 = 13
After ‘x’ V operations value of S=5, So 13 + xV = 5 and S = 18 .
Question 346 
1. The sign bits are same i.e MSB bits are same.
2. Carry_in ≠ Carry_out.
In option B, the MSB are equal.
Question 347 
int fun(x: integer)
{
If x > 100
then
fun = x – 10;
else
fun = fun(fun(x + 11));
}
For the input x = 95, the function will return
89  
90  
91  
92 
fun(95) = fun(fun(106))
= fun(96)
= fun(fun(107))
= fun(97)
= fun(fun(108))
= fun(98)
= fun(fun(109))
= fun(99)
= fun(110)
= fun(100)
= fun(fun(111))
= fun(101)
= 91
Question 348 
int func(int num)
{
int count = 0;
while(num)
{
count++;
num >>= 1;
}
return(count) ;
}
For func(435) the value returned is
9  
8  
0  
10 
count = 0 Shift right of 1, which means the number gets half.
while (num)
{
Shift left of 1, which means, the number gets doubled.
count++;
num>>=1;
}
return (count); 435/2 = 217/2 = 108/2 = 54/2 = 27/2 = 13/2 = 6/2 = 3/2 = 1/2 = 0
Count: 1, 2, 3, 4, 5, 6, 7, 8, 9. Χ
(or)
(435)_{10} = (110110011)_{2}
The given program counts total number of bits in binary representation and fails when while (num) becomes all zeroes.
Question 349 
a) XOR gates, NOT gates
b) 2 to 1 multiplexers
c) AND gates, XOR gate
d) Threeinput gates that output (A.B)+C for the inputs A, B and C.
a and d  
b and c  
c  
All a, b, c and d 
(B) 2×1 multiplexer is functionally complete provided we have external 1 and 0 available.
(C) XOR can be used to make a NOT gate (a⊕1=a') and (AND, NOT) is functionally complete. Again this required external 1.
(D) We cannot derive NOT gate here. So not functionally complete.
Hence, options (B) and (C) are true provided external 1 and 0 are available.
Question 350 
Matching A, B, C, D in the same order gives.
r, p, s, q  
p, r, q, s  
s, r, q, p  
q, r, s, p 
Black box testing→ Equivalence Class partitioning
Volume Testing→ Performance testing
Beta Testing→ System testing
Question 351 
Regression  
Decision Tree  
Clustering  
Association Rules 
Decision Tree: Decision tree is a computational method which works on descriptive data and records the observations of each object to reach to a result.
Clustering: It is a method of grouping more similar objects in a group and the nonsimilar objects to other groups.
Association Rules: It uses ifthen reasoning method using the supportconfidence technique to give a result.
According to the question Decision Tree is the most suitable technique that can be used to get best result of the experiment.
Question 352 
Each dimension is represented by a single dimensional table  
Maintenance efforts are less  
Dimension tables are normalised  
It is not an extension of star schema 
→ The snowflake schema is represented by centralized fact tables which are connected to multiple dimensions.
→ "Snowflaking" is a method of normalizing the dimension tables in a star schema.
→ When it is completely normalized along all the dimension tables, the resultant structure resembles a snowflake with the fact table in the middle.
→ The principle behind snowflaking is normalization of the dimension tables by removing low cardinality attributes and forming separate tables.
Question 353 
In deadlock prevention, the request for resources is always granted if resulting state is safe  
In deadlock avoidance, the request for resources is always granted, if the resulting state is safe  
Deadlock avoidance requires knowledge of resource requirements a priori  
Deadlock prevention is more restrictive than deadlock avoidance 
→ Deadlock prevention algorithms are used in concurrent programming when multiple processes must acquire more than one shared resource.
→ A deadlock prevention algorithm organizes resource usage by each process to ensure that at least one process is always able to get all the resources it needs.
Question 354 
190  
238  
233  
276 
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73
⇒ 2 ms to move from one cylinder to adjacent one
⇒ (16*2)+(14*2)+(1*2)+(4*2)+(5*2)+(3*2)+(1*2)+(2*2)+(2*2)+(71*2)
⇒ 32+28+2+8+10+6+2+4+4+142
⇒ 238 ms
Question 355 
#include <stdio.h>
int main(void)
{
char c[ ] = "ICRBCSIT17";
char *p=c;
printf("%s", c+2[p] – 6[p] – 1);
return 0;
}
The output of the program is
SI  
IT  
TI  
17 
Pointer(p) is pointing to character array c[ ].
Index location 2[p] =’R’ and 6[p] =’I’
‘R’‘I’ = 9 and c+2[p]–6[p]–1
= c+9–1
= c+8
It will print 17.
Question 356 
scalar matrix  
null matrix  
unit matrix  
matrix will all elements 1 
Question 357 
16  
18  
17  
19 
The carry propagates the through the Carrylookahead generators. Carrylookahead generator which produces carry takes 2 Units of time.
So time delay= (3 units for carry C1 of CLA1)+ (7 * 2 units for carries C2 to C7 of CLA2 to CLA7)+ (3 Units for carry and also sum of CLA8).
Note: For CLAs 1 to 7, it takes an extra 1 unit of time to produce Sum which overlaps with time required for carrie's of next CLAs.
Question 358 
3.0  
1.0  
4.0  
2.0 
Question 359 
(Assume that no faculty member within a single department has same name. Each faculty member has only one office identified in office. 3NF refers to third normal form and BCNF refers to BoyceCodd Normal Form. Then Faculty is
Not in 3NF, in BCNF  
In 3NF, not in BCNF  
In 3NF, in BCNF  
Not in 3NF, not in BCNF 
FacName ➝ dept,office
Question 360 
SELECT E.eno, COUNT(*)
FROM Employees E
GROUP BY E.eno
If an index on eno is available, the query can be Solutioned by scanning only the index if
the index is only hash and clustered
 
the index is only B+tree and clustered  
index can be hash or B+ tree and clustered or nonclustered  
index can be hash or B+ tree and clustered 
Question 361 
RFC  
RCF  
ID  
none of the above 
● A Request for Comments (RFC) is a type of publication from the technology community. RFCs may come from many bodies including from the Internet Engineering Task Force (IETF), the Internet Research Task Force (IRTF), the Internet Architecture Board (IAB) or from independent authors
Question 362 
Who among the following devised the ryotwari system during the british rule in india?
Lord Dalhousie
 
Warren Hastings  
Lord Minto
 
Capt. Alexander read

Question 363 
In which of the following states is the tuluni festival celebrated?
Arunachal pradesh
 
Manipur
 
Nagaland
 
Sikkim

Amid the Tuluni Festival there are petitions and contributions that are given to Litsaba, who is the god of productivity who gives life and insurance to the crops. During the Tuluni Festival in Nagaland , a flagon is made with the leaf of plantain, to serve the rice lager. Tuluni is the name of this wine is devoured by the Sumi clan. "anni' is another name for 'Tuluni' which means the period of plenteous harvests.
Question 364 
Among the various electrical safety device in the options, the one based on the heating effect of electric current is the:
protective relay  
circuit breaker
 
fuse  
surge protectors 
Question 365 
Article 45 of the constitution of india provides provision for early childhood care and education to children below the age of:
6 years
 
9 years
 
12 years
 
10 years 
"45 . Provision for early childhood care and education to children below the age of six years  The State shall endeavour to provide early childhood care and education for all children until they complete the age of six years."
Question 366 
Article 26 of the constitution of india deals with:
validation of certain acts and regulations
 
equality of opportunity in matters of public employment  
freedom to manage religious affairs  
prohibition of trafficking in human beings 
(a) to establish and maintain institutions for religious and charitable purposes
(b) to manage its own affairs in matters of religion
(c) to own and acquire movable and immovable property
(d) to administer such property in accordance with law
Question 367 
Which team won the ICC world twenty20 2016(Men's) tournament?
England
 
West Indies
 
South africa
 
Australia

1. West Indies won the toss and elected to field.
2. Marlon Samuels (WI) made the highest score in a World T20 final.
3. West Indies became the first team to win both the men's and women's World Twenty20s on the same day, with the women defeating Australia by 8 wickets.
Question 368 
The asian development bank(ADB) has approved a USD 346 million loan for road improvements in which of the following states?
Telangana
 
Maharashtra
 
Karnataka
 
Gujarat 
This would be in addition to an ongoing road improvement project financed by the ADB with a loan of $315 million which involves upgradation of about 615 km of state roads.
The loan agreement for the Karnataka State Highways Improvement III Project (KSHIPIII) was signed between Sameer Kumar Khare, Joint Secretary in the Finance Ministry and Kenichi Yokoyama, Country Director of ADB’s India Resident Mission.
Kenichi Yokoyama said the new loan will continue ADB support to the Karnataka government's statewide road improvement programme, and will also help improve road safety.
Question 369 
In which country was the ninth edition of the mountain echoes literature festival held in august 2018?
Sri lanka
 
India
 
China  
Bhutan 
Question 370 
______ can produce a virtual image larger than the object
Concave lens  
Concave mirror  
Convex mirror
 
Plane mirror

Question 371 
From the given options, select the word that can be formed using the letters from the given word
ALTERNATE
TAVERN  
LANTERN
 
TALENT
 
TANNER

→ LANTERN: Here, N appears 2 times but actual given word having only one ‘N’ letter.
→ TALENT: It is completely formed in given word ALTERNATE.
→ TANNER: Here, N appears 2 times but actual given word having only one ‘N’ letter.
Question 372 
Select the option that is different from the other three options
Resentful  
Serene  
Desolate
 
Sad

→ Resentful, Desolate and Sad are same category.
Question 373 
Select the options that is related to the third term in the same way as the second term is related to the first term
CEGI:XVTR::FHJL:?
OQSU  
USPO
 
VSQO
 
USQO 
Question 374 
Select the option that is different from the other three options
117  
78  
60  
52 
78 and 52 difference is 13*2
52 and 39 difference is 13*1
So, 60 is the odd one because difference is 13.
Actual difference is 39, 52, 78, 117.
Question 375 
'Restaurant' is related to 'chef; in the same way as 'garage' is related to:
car  
vehicle
 
mechanic  
accountant

→ Garage is related to mechanic
Question 376 
Choose the correct options that will complete the given number series:
2, 2, 3, 8, 35, ?, 1421
204  
40  
408  
70 
3 (1^{st} term) * 1  1 = 2 (2^{nd} term)
2 (2^{nd} term) * 2  2 = 2 (3^{rd} term)
2 (3^{rd} term) * 3  3 = 3 (4^{th} term) and so on…
Going by this pattern the next number in the series will be 35 * 6 – 6 = 204
Question 377 
Ruby met Nisha at a party. Nisha introduced herself as the eldest daughter of the brotherinlaw of Ruby's friends mother?How is Ruby's friend related to Nisha?
Niece
 
Friend  
Cousin  
Daughter

Question 378 
Five children are standing in a single file line in ascending order of their heights. Q is second in line. P and R are taller than O. N is taller than P but shorter than R. P is the middle of the line. Who is at end of the line?
P  
O  
R  
Q 
P is middle means 3rd position.
N is taller than P means but shorter than R means 4th position.
O is shorter than P and R means 1st position.
R is end of the line.
O, Q, P, N, R
Question 379 
If the seventh day of the month is four days after friday, what day will it be on the thirty first day of the month?
Tuesday
 
Wednesday
 
Friday  
Monday

14th day Tuesday
21st day Tuesday
28th dayTuesday
29thwednesday
30ththursday
31st friday
Question 381 
Abhi bought an article and sold it at a loss of 10%. If he had bought it for 20% less and sold it for Rs.121 more, he would have had a profit of 40%. If he decides to sell it for Rs.506, what will he percentage gain/loss be?
Loss 8%  
Gain 8%
 
Loss 5.50%
 
Gain 5.5%

Question 382 
A shopkeeper sold an article for Rs.494 after giving a discount of 18% on its marked proce. had he NOT given the discount, he would have earned a profit of 25% on the cost price. What is the cost price(in Rs) of the article?
Rs.484
 
Rs.480  
Rs.410
 
Rs.450

Question 383 
In folding the HCF of two numbers by the division method, the quotients are 1 and 6 respectively. If the HCF of the two numbers in 300, then their LCM will be:
12600
 
6300
 
8400  
2100

Question 384 
Of three numbers, the first is 7 times the second and is also 4 times the third. If the average of the three numbers is 299/7 , what is the sum of the first and the third number?
736/7
 
253/7  
115  
110 
Question 386 
A vessel contains a solution of A and B in the ratio 5:7. If 4 1/2L of the solution is replaced by the sme quality of A, then their ratio becomes 9:7. How much(in liters) of liquid B was there in the bucket initially?
15  
21  
7 1/2  
10 1/2 
Question 387 
There are eleven numbers whose average is 64. The first number is 4 more than second but 10 less than the third. The average of the numbers from the fourth to the seventh is 62.5, and the average of the remaining numbers is 65.5. What is the average of the second and the third number?
65.5
 
64  
65  
64.5 
Question 388 
A bag contains coins of Rs.1, 50 paise and 25 paise in the ratio 4:3:8. If the total amount in the bag is Rs.240, then the number of 50 paise coins is:
96  
128  
256  
192 
Question 389 
Select the most appropriate antonym of the given word
AUDACITYboldness
 
courage
 
timidity  
nerve 
Question 390 
Select the wrongly spelt word
improbable
 
impudent
 
impression
 
impropreity

Question 391 
Select the option which is NOT an antonym of another word by way of adding the prefix 'in'.
indomitable
 
individualism  
incompetent
 
incoherent

Question 392 
Select the most appropriate option to fill in the blank.
Divyanshu didn't like to work at a corporate. He wants to start____ own business.
our
 
their
 
his  
my

Question 393 
Select the most appropriate option to fill in the blank.
____ their clothes were proper, they didn't look smart.
Whether
 
Despite  
Although  
Because 
Question 394 
Based on table CLUB, which of the following SQL statement will delete the information of those members, who are either ANNUAL members or those who are having DOJ on or after "01JAN2010".
DELETE FROM CLUB WHERE TYPE= "ANNUAL" AND DOJ > = "01JAN10";  
DELETE FROM CLUB WHERE TYPE= "ANNUAL" OR DOJ > "01JAN10";  
DELETE * FROM CLUB WHERE TYPE= "ANNUAL" OR DOJ > "01JAN10";  
DELETE FROM CLUB WHERE TYPE= "ANNUAL" OR DOJ > = "01JAN10"; 
DELETE Syntax:
DELETE FROM table_name WHERE condition;
Question 395 
In the following sentence, four words or phrases have been underlined. one of them is incorrect. Choose the incorrect word or phrase from the given options.
Most of the projects is struggling to make progress due to various like land acquisition, forest clearance or release of funds from the government.
release of funds
 
to make progress
 
due to
 
is struggling

Question 396 
Select the most appropriate synonym of the given word
STEALTHYdirect
 
daring
 
unrestricted
 
sly

Question 397 
Select the most appropriate option to fill in the blank.
Usually she has milk, but today she____hot herbal tea because she has a sore throat.
had taken
 
was taking
 
takes
 
is taking

Question 398 
Based on table CLUB, find out the most appropriate SQL statement from the following to display the total amount of FEE collected from monthly members till date :
SELECT SUM(MONTIIS_BETWEEN(SYSDATE, DOJ) * FEE) FROM CLUB WHERE TYPE= "MONTHLY'  
SELECT SUM(MONTH_BETWEEN (DOI,SYSDATE) * FEE) FROM CLUB ;WHERE TYPE= "MONTHLY"  
SELECT SUM(MONTH_BETWEEN (DOJ, SYSDATE) * FEE) FROM CLUB WHERE TYPE= ''MONTHLY"  
SELECT MONTHS_BETWEEN(SYSDATE, DOJ) • FEE FROM CLUB WHERE TYPE= "MONTHLY'' 
Question 399 
Select the most appropriate option to fill in the blank.
This ward is meant for critically____children.