Question 1

Two hosts are connected via a packet switch with 107 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 _______.

A
(1575)
B
(1576)
C
(1577)
D
(1578)
       Packet-Switching       GATE 2015 [Set-3]
Question 1 Explanation: 
Given that there is a single switch between the source and destination.
Bandwidth of the each link is 107 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)/(107 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 |x2 - 2x + 3| = 11, then possible values of |- x3 + x2 - x| include

A
2, 4
B
2, 14
C
4, 52
D
14, 52
       GATE 2014 [Set-2]
Question 2 Explanation: 
Given,
|x2 - 2x + 3| = 11, x is real
x2-2x+3 = 11
x2-2x+8 = 0
(x-4)(x+2) = 0
x = 4, -2
x2-2x+3 = -11
x2-2x+14 = 0
x is not real in this case.
|-x3+x2-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 |-x3+x2-x| include 14, 52.
Question 3

What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type A → є and A → a) to parse a string with n tokens?

A
n/2
B
n-1
C
2n-1
D
2n
       GATE 2013
Question 3 Explanation: 
Since it is given that the grammar cannot have:
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 bottom-up 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 unit-production (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

P only
B
P and R only
C
R only
D
P, Q and S only
       GATE 2013
Question 4 Explanation: 
P) True. Because every edge in cycle graph will become a vertex in new graph L(G) and every vertex of cycle graph will become an edge in new graph.
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| ≤ 3|v| - 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(β))?

A
∀x(∃z(¬β)→∀y(α))
B
∀x(∀z(β)→∃y(¬α))
C
∀x(∀y(α)→∃z(¬β))
D
∀x(∃y(¬α)→∃z(¬β))
       GATE 2013
Question 5 Explanation: 
Option A:
∀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?

A
4000
B
5000
C
4333
D
4667
       GATE 2011
Question 6 Explanation: 
Note: Out of syllabus.
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 person-months 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 person-months?

A
234.25
B
932.50
C
287.80
D
122.40
       GATE 2011
Question 7 Explanation: 
Note: Out of syllabus.
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?

A
Embed web objects from different sites into the same page
B
Refresh the page automatically after a specified interval
C
Automatically redirect to another page upon download
D
Display the client time as part of the page
       GATE 2011
Question 8 Explanation: 
Note: Out of syllabus.
Question 9

Which of the following is NOT desired in a good Software Requirement Specifications (SRS) document?

A
Functional Requirements
B
Non-Functional Requirements
C
Goals of Implementation
D
Algorithms for Software Implementation
       GATE 2011
Question 9 Explanation: 
Note: Out of syllabus.
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 non-redundant tests using equivalence class partitioning approach from input perspective for black box testing?

A
T1, T2, T3, T6
B
T1, T3, T4, T5
C
T2, T4, T5, T6
D
T2, T3, T4, T5
       GATE 2011
Question 10 Explanation: 
Note: Out of syllabus.
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 N2-N3 reduces to 2(in both directions). After the next round of updates, what will be the new distance vector at node, N3.

A
(3, 2, 0, 2, 5)
B
(3, 2, 0, 2, 6)
C
(7, 2, 0, 2, 5)
D
(7, 2, 0, 2, 6)
       GATE 2011
Question 11 Explanation: 
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?

A
19
B
21
C
20
D
10
       GATE 2010
Question 12 Explanation: 
Note: Out of syllabus.
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
A
P-3, Q-2, R-4, S-1
B
P-2, Q-3, R-1, S-4
C
P-3, Q-2, R-1, S-4
D
P-2, Q-3, R-4, S-1
       GATE 2010
Question 13 Explanation: 
Note: Out of syllabus.
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?

A
T1, T2, T3
B
T2, T4
C
T3, T4
D
T1, T2, T4
       GATE 2010
Question 14 Explanation: 
T1 covers S1
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:

A
I-II-III-IV-V
B
V-IV-III-II-I
C
I-III-V-II-IV
D
IV-II-V-III-I
       GATE 2009
Question 15 Explanation: 
Note: Out of syllabus. [Software Engineering]
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:

A
〈2, 2, 3〉 and 〈2, 3, 2〉
B
〈2, 2, 3〉 and 〈2, 2, 3〉
C
〈2, 3, 2〉 and 〈2, 3, 2〉
D
〈2, 3, 2〉 and 〈2, 2, 3〉
       GATE 2009
Question 16 Explanation: 
Note: Out of syllabus. [Web Technologies]
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.
A
II and III
B
II and III
C
I and III
D
I, II and III
       GATE 2009
Question 17 Explanation: 
Note: Out of Syllabus. [Software Engineering]
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.
A
I and II
B
II and III
C
I and III
D
I, II and III
       GATE 2009
Question 18 Explanation: 
Note: Out of syllabus. [Software Engineering]
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 , where c is the cylinder number, h is the surface number and s is the sector number. Thus, the 0th sector is addressed as <0, 0, 0>, the 1st sector as <0,0,1>, and so on.

The address of the 1039th sector is

A
〈0, 15, 31〉
B
〈0, 16, 30〉
C
〈0, 16, 31〉
D
〈0, 17, 31〉
       GATE 2009
Question 19 Explanation: 
We know in each track there are 63 sectors. And we know there is one track per surface.
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 Q1,Q2 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?

Q1 : Select e.empId
     From employee e
     Where not exists
        (Select * From employee s where s.department = “5” and s.salary >= e.salary)
Q2 : Select e.empId
     From employee e
     Where e.salary > Any
       (Select distinct salary From employee s Where s.department = “5”)
A
Q1 is the correct query
B
Q2 is the correct query
C
Both Q1 and Q2 produce the same answer
D
Neither Q1 nor Q2 is the correct query
       GATE 2007
Question 20 Explanation: 
The required output is find the employees who get higher salary than anyone in the department “5”.
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:

A
Neither a Partial Order nor an Equivalence Relation
B
A Partial Order but not a Total Order
C
A Total Order
D
An Equivalence Relation
       GATE 2006
Question 21 Explanation: 
If a relation is equivalence then it must be
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is partial order relation then it must be
i) Reflexive
ii) Anti-symmetric
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 (xv).
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

not in 2NF
B
in 2NF but not 3NF
C
in 3NF but not in 2NF
D
in both 2NF and 3NF
       GATE 1999
Question 22 Explanation: 
Since R1 ∩ R2 = ∅, so the decomposition is lossless join. 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 23

not in 2NF
B
in 2NF but not 3NF
C
in 3NF but not in 2NF
D
in both 2NF and 3NF
       GATE 1999
Question 23 Explanation: 
Since R1 ∩ R2 = ∅, so the decomposition is lossless join.
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.

A
Theory Explanation
       GATE 1999
Question 25

Let G be a finite group and H be a subgroup of G. For a∈G, define aH = {ah|h∈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.

A
Theory Explanation.
       GATE 1999
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 men-cut 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 min-cut in the graph?

(c) Prove that if a connected undirected graph G with n vertices has a min-cut of cardinality K, then G has atleast (nk/2) edges.

A
Theory Explanation.
       GATE 1999
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)

A
Theory Explanation.
       GATE 1999
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.

A
Theory Explanation.
       GATE 1999
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 1st, 2nd and 3rd smallest elements in minimum number of comparisons.

A
Theory Explanation.
       GATE 1999
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 → LL|L 
   L → LB|B 
   B → 0|1 

Write S-attributed values corresponding to each of the productions to find S.val.

A
Theory Explanation.
       GATE 1999
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 (N-1)
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.

A
Theory Explanation.
       GATE 1999
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 O-notation.

         algorithm what (n)      
             begin 
                  if n = 1 then call A 
             else begin
                   what (n-1);
                   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.

A
Theory Explanation.
       GATE 1999
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 min-heap that results from insertion of the following elements in order into an initially empty min-heap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.

A
Theory Explanation.
       GATE 1999
Question 34

An instruction pipeline consists of 4 stages: Fetch(F), Decode operand field (D), Execute (E), and Result-Write (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.

A
Theory Explanation.
       GATE 1999
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.

A
Theory Explanation.
       GATE 1999
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. 
A
Theory Explanation.
       GATE 1999
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.

A
Theory Explanation.
       GATE 1999
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?

A
Theory Explanation.
       GATE 1999
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) A0, A1, …A9(input address lines. A0 is the lest significant)
    (v) D0, D1, D2, D3(bi-directional data lines. D0 is the least significant)

A
Theory Explanation.
       GATE 1999
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 216 bytes each. The virtual address space is divided into 8 non-overlapping 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 look-aside 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.

A
Theory Explanation.
       GATE 1999
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 pseudo-code for implementing the entry and exit code to a critical region using this instruction.

(b) Consider the following solution to the producer-consumer 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.

A
Theory Explanation.
       GATE 1999
Question 42

Consider a B-tree with degree m, that is, the number of children, c, of any internal node (except the root) is such that m ≤ c ≤ 2m-1. Derive the maximum and minimum number of records in the leaf nodes for such a B-tree with height h, h≥1. (Assume that the root of a tree is at height 0.)

A
Theory Explanation.
       GATE 1999
Question 43

Consider the set of relations

EMP(Employee-no, Dept-no, Employee-name, Salary)
DEPT(Dept-no, Dept-name, 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.

A
Theory Explanation.
       GATE 1999
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).

A
Theory Explanation.
       GATE 1998
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}

A
Theory Explanation.
       GATE 1998
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.

A
Theory Explanation.
       GATE 1998
Question 47

(a) Solve the following recurrence relation:

  xn = 2xn-1 - 1, n>1
  x1 = 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.

A
Theory Explanation.
       GATE 1998
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, ice-cream) indicating what kind of ice-creams each parlor serves.
LIKES(student, ice-cream) indicating what ice-creams each parlor serves.
(Assuming that each student likes at least one ice-cream and frequents at least one parlor)
Express the following in SQL:
Print the students that frequent at least one parlor that serves some ice-cream that they like.

(b) In a computer system where the 'best-fit' 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.

A
Theory Explanation.
       GATE 1998
Question 49

(a) Find the points of local maxima and minima, if any, of the following function defined in 0 ≤ x ≤ 6.

  x3 - 6x + 9x - 15 

(b) Integrate

A
Theory Explanation.
       GATE 1998
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.

A
Theory Explanation.
       GATE 1998
Question 51

(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n-3)/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 = Rn.

A
Theory Explanation.
       GATE 1998
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,
({Π1234}, refines⟩

A
Theory Explanation.
       GATE 1998
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 

A
Theory Explanation.
       GATE 1998
Question 54

Let M = ({q0, q1}, {0, 1}, {z0, x}, δ, q0, z0, ∅) be a pushdown automaton where δ is given by

    δ(q0, 1, z0) = {(q0, xz0)}
    δ(q0, ε, z0) = {(q0, ε)}
    δ(q0, 1, X) = {(q0, XX)}
    δ(q1, 1, X) = {(q1, ε)}
    δ(q0, 0, X) = {(q1, X)}
    δ(q0, 0, z0) = {(q0, z0)}

(a) What is the language accepted by this PDA by empty stack?

(b) Describe informally the working of the PDA.

A
Theory Explanation.
       GATE 1998
Question 55

(a) Let G1 = (N, T, P, S1) be a CFG where,
N = {S1, A, B}, T = {a,b} and
P is given by

         S1 → aS1b             S1 → aBb
         S1 → 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 L2 = {ai bj ak bl | i, j, k, l ≥ 1, i=j or k=l} by adding not more than 5 production rule.

(c) Is L2 inherently ambiguous?

A
Theory Explanation.
       GATE 1998
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.

A
Theory Explanation.
       GATE 1998
Question 57

Design a synchronous counter to go through the following states:

  1, 4, 2, 3, 1, 4, 2, 3, 1, 4,........... 

A
Theory Explanation.
       GATE 1998
Question 58

Calculate the total time required to read 35 sectors on a 2-sided floppy disk. Assume that each track has 8 sectors and the track-to-track 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 1-sector buffer. The diskette spins at 300 RPM and initially, the head is on track 10.

A
Theory Explanation.
       GATE 1998
Question 59

For a set-associative Cache Organization, the parameters are as follows:

    tc -- Cache access tine
    tm -- 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 non-zero integer and 1 < m ≤ l.
Given the value of the hit ratio for l = 1.

A
Theory Explanation.
       GATE 1998
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  
A
Theory Explanation.
       GATE 1998
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 
A
Theory Explanation.
       GATE 1998
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.

A
Theory Explanation.
       GATE 1998
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 | ε 
A
Theory Explanation.
       GATE 1998
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.

A
Theory Explanation.
       GATE 1998
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.

A
Theory Explanation.
       GATE 1998
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 (cL,tL,sL), where cL, tL and SL 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.

A
Theory Explanation.
       GATE 1998
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?

A
Theory Explanation.
       GATE 1998
Question 68

Consider the following relational database schemes:

  COURSES(Cno, name)
  PRE-REQ(Cno, pre_Cno)
  COMPLETED(student_no, Cno) 

COURSES give the number and the name of all the available courses.
PRE-REQ gives the information about which course are pre-requisites 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 pre-requisites.

A
Theory Explanation.
       GATE 1998
Question 69

A D flip-flop is to be connected to an 8085 microprocessor chip as a 1-bit output port with a port address of FF hex. Data bit D3 should be involved in the data transfer from CPU to the flip-flop. The flip-flop should be cleared on power ON.
(a) Using only one NAND gate (fan in of 10), one NOT gate and one D flip-flop. 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 flip-flop. ON and OFF periods of the square wave should be 7 bus cycles each.

A
Theory Explanation.
       GATE 1997
Question 70

Let L = {a1, a2, ......, an} 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 a2i and a2i-1, 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 
A
Theory Explanation.
       GATE 1997
Question 71

Consider a graph whose vertices are points in the plane with integer co-ordinates (x,y) such that 1≤x≤n and 1≤y≤n, where n≥2 is an integer. Two vertices (x1,y1) and (x2,y2) are adjacent iff ∣x1−x2∣ ≤ 1 and ∣y1–y2∣ ≤1. The weight of an edge {(x1,y1),(x2,y2)} is √(x1–x2)2 + (y1–y2)2
(a) What is the weight of a minimum weight-spanning tree in this graph? Write only the answer without any explanations.
(b) What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.

A
Theory Explanation.
       GATE 1997
Question 72

Consider the following program in Pseudo-Pascal 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?

A
Theory Explanation.
       GATE 1997
Question 73

Consider the grammar

   S → bSe
   S → PQR
   P → bPc
   P → ε
   Q → cQd
   Q → ε
   R → dRe
   R → ε  

where S,P,Q,R are non-terminal 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 bi, cj, dk, em 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.

A
Theory Explanation.
       GATE 1997
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 Kth 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 Kth insertions?

A
Theory Explanation.
       GATE 1997
Question 75

Let F be the set of one-to-one 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?

A
Theory Explanation.
       GATE 1997
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 E1 ≤ E2 if ∃a,b such that a∈E1, b∈E2 and (a,b)∈R. Prove that ≤ is a partial order.

A
Theory Explanation.
       GATE 1997
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(n-1, m) + F(n, m-1);
       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).

A
Theory Explanation.
       GATE 1997
Question 78

A size-balanced 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 size-balance binary tree of height h contains at least 2h nodes.
(b) In a size-balanced binary tree of height h≤1, how many nodes are at distance h−1 from the root? Write only the answer without any explanations.

A
Theory Explanation.
       GATE 1997
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(j-1) < min then min:=j-1;
16.        sum:=sum - A[i];
17.        i:=i+1;
18. end
19. writeln (min+1);
20. end.   
A
Theory Explanation.
       GATE 1997
Question 80

Consider the following piece of 'C' code fragment that removes duplicates from an ordered list of integers.

Node  *remove-duplicates(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?

A
Theory Explanation.
       GATE 1997
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)?

A
Theory Explanation.
       GATE 1997
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.

A
Theory Explanation.
       GATE 1997
Question 83

Given that L is a language accepted by a finite state machine, show that LP and LR are also accepted by some finite state machines, where
LP = {s|ss' ∈ L, for some string s'}
LR = {s|s obtainable by reversing some string in L}

A
Theory Explanation.
       GATE 1997
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.
A
Theory Explanation.
       GATE 1997
Question 85

The language L, defined by the following grammar allows use of real or integer data in expressions and assignment statements.

    (assign-stmt):: = (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 type-specific operators (+, i), (+, r), (*, i), (*, r), (:=, i) and (:=,r).
Write a syntax directed translation scheme to convert expression and assignment strings into the post-fix form. You may assume that the name and type of a variable can be obtained by making the function calls 'give-type (id)' and 'give-name (id)' respectively.

A
Theory Explanation.
       GATE 1997
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 run-time stack. Describe the run-time 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.

A
Theory Explanation.
       GATE 1997
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.)

A
Theory Explanation.
       GATE 1997
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?

A
Theory Explanation.
       GATE 1997
Question 89

Following floating point number format is given
f is a fraction represented by a 6-bit mantissa (includes sign bit) in sign magnitude form e is a 4-bit exponent (includes sign hit) in sign magnitude form n = (f,e) = f, 2e 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)?

A
Theory Explanation.
       GATE 1997
Question 90

A concurrent system consists of 3 processes using a shared resource R in a non-preemptible 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
my-priority:integer;
my-priority:=____; /*in the range 1...3*/
repeat
    request_R(my-priority);
    P (proceed [my-priority]);
    {use shared resource R}
    release_R (my-priority);
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.

A
Theory Explanation.
       GATE 1997
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 × 103 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.

A
Theory Explanation.
       GATE 1997
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.

A
Theory Explanation.
       GATE 1997
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))

A
Theory Explanation.
       GATE 1997
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.

A
Theory Explanation.
       GATE 1996
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.

A
61 52 14 17 40 43
B
2 3 50 40 60 43
C
10 65 31 48 37 43
D
81 61 52 14 41 43
E
17 77 27 66 18 43
       GATE 1996
Question 96

A logic network has two data inputs A and B, and two control inputs C0 and C1. It implements the function F according to the following table.

Implement the circuit using one 4 to 1 Multiplexer, one 2-input Exclusive OR gate, one 2-input AND gate, one 2-input OR gate and one Inverter.

A
Theory Explanation.
       GATE 1996
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.

A
Theory Explanation.
       GATE 1996
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

A
Theory Explanation.
       GATE 1996
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.

A
Theory Explanation.
       GATE 1996
Question 100

The Fibonacci sequence {f1,f2,f3,...,fn} is defined by the following recurrence:

   fn+2 = fn+1 + fn, n ≥ 1; f2=1 : f1=1 

Prove by induction that every third element of the sequence is even.

A
Theory Explanation.
       GATE 1996
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.

A
Theory Explanation.
       GATE 1996
Question 102

Let G be a context-free 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 context-free 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.)

A
Theory Explanation.
       GATE 1996
Question 103

Given below are the transition diagrams for two finite state machine M1 and M2 recognizing languages L1 and L2 respectively.
(a) Display the transition diagram for a machine that recognizes L1.L2, obtained from transition diagrams for M1 and M2 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 (L1.L2)∗ by adding only ε transitions and no new states. (Final states are enclosed in double circles).

A
Theory Explanation.
       GATE 1996
Question 104

Let Q = ({q1,q2}, {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) δ(q1,a,Z) = {(q1,Za)}
(2) δ(q1,b,Z) = {(q1,Zb)}
(3) δ(q1,a,a) = {(.....,.....)}
(4) δ(q1,b,b) = {(.....,.....)}
(5) δ(q2,a,a) = {(q2,ϵ)}
(6) δ(q2,b,b) = {(q2,ϵ)}
(7) δ(q2,ϵ,Z) = {(q2,ϵ)} 
A
Theory Explanation.
       GATE 1996
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  
A
Theory Explanation.
       GATE 1996
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.

A
Theory Explanation.
       GATE 1996
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

A
Theory Explanation.
       GATE 1996
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?

A
Theory Explanation.
       GATE 1996
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; 
A
Theory Explanation.
       GATE 1996
Question 110

Consider the following program in pseudo-pascal syntax. What is printed by the program if parameter a in procedure test 1 is passed as
(i) call-by-reference parameter
(ii) call-by-value-result 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 
A
Theory Explanation.
       GATE 1996
Question 111

Consider the syntax-directed translation schema (SDTS) shown below:

    E → E + E  {print “+”}
    E → E ∗ E  {print “.”}
    E → id     {print id.name}
    E → (E) 

An LR-parser 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. 
A
Theory Explanation.
       GATE 1996
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: 
A
Theory Explanation.
       GATE 1996
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?

A
Theory Explanation.
       GATE 1996
Question 114

A file system with a one-level directory structure is implemented on a disk with disk block size of 4K bytes. The disk is used as follows:

 Disk-block 0: File Allocation Table, consisting of one 8-bit 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?

A
Theory Explanation.
       GATE 1996
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 flip-flops as given below.

(b) Given that the initial state of the circuit is S4, identify the set of states, which are not reachable.

A
Theory Explanation.
       GATE 1996
Question 116

A hard disk is connected to a 50 MHz processor through a DMA controller. Assume that the initial set-up 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?

A
Theory Explanation.
       GATE 1996
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?

A
Theory Explanation.
       GATE 1996
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))) 
A
Theory Explanation.
       GATE 1996
Question 119

For merging two sorted lists of sizes m and n into a sorted list of size m+n, we required comparisons of

A
O(m)
B
O(n)
C
O(m+n)
D
O(logm+logn)
       GATE 1995
Question 119 Explanation: 
In best case, no. of comparisons is Min(m,n).
In worst case, no. of comparisons is m+n-1.
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:

A
log2 n
B
n - 1
C
n
D
2n
       GATE 1995
Question 120 Explanation: 
A binary tree is a tree data structure in which each node has atmost two child nodes.
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(bA-b);
     W               :=A-B
     Z               :=A*B
 End;  
A
Theory Explanation.
       GATE 1995
Question 122

(a) Consider the following Pascal function where A and B are non-zero 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(A-1,B)+GET(A-1,B-1)
 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; 
A
Theory Explanation.
       GATE 1995
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?

A
Theory Explanation.
       GATE 1995
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.

A
Theory Explanation.
       GATE 1995
Question 125

(a) Determine the number of divisors of 600.
(b) Compute without using power series expansion

A
Theory Explanation.
       GATE 1995
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$ 
A
Theory Explanation.
       GATE 1995
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).

A
Theory Explanation.
       GATE 1995
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);  
A
Theory Explanation.
       GATE 1995
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 Lc be the complement of L over ∑*. Show that Lc is also in NP.

A
Theory Explanation.
       GATE 1995
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.

A
Theory Explanation.
       GATE 1995
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.

A
Theory Explanation.
       GATE 1995
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.

A
Theory Explanation.
       GATE 1995
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?

A
Theory Explanation.
       GATE 1995
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?

A
Theory Explanation.
       GATE 1995
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?

A
Theory Explanation.
       GATE 1995
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; 
A
Theory Explanation.
       GATE 1995
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; 
A
Theory Explanation.
       GATE 1995
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.

A
Theory Explanation.
       GATE 1995
Question 139

Let G1 and G2 be subgroups of a group G.
(a) Show that G1 ∩ G2 is also a group of G.
(b) Is G1 ∪ G2 always a subgroup of G?

A
Theory Explanation.
       GATE 1995
Question 140

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to the edge).

A
Theory Explanation.
       GATE 1995
Question 141

Prove using mathematical induction for n≥5, 2n > n2

A
Theory Explanation.
       GATE 1995
Question 142

Prove that in finite graph, the number of vertices of odd degree is always even.

A
Theory Explanation.
       GATE 1995
Question 143

(a) Find the minimum value of 3 - 4x + 2x2.
(b) Determine the number of positive integers (≤ 720) which are not divisible by any of numbers 2, 3, and 5.

A
Theory Explanation.
       GATE 1995
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 Boyce-Code Normal Form (BCNF).
(b) Determine the minimal keys of relation R.

A
Theory Explanation.
       GATE 1995
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.

A
Theory Explanation.
       GATE 1995
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:

A
XCHG and DAD B
B
XTHL and DAD H
C
PCHL and DAD D
D
XCHG and DAD H
       GATE 1995
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:

A
Theory Explanation.
       GATE 1994
Question 148

A 3-ary tree is a tree in which every internal node has exactly three children. Use induction to prove that the number of leaves in a 3-ary tree with n interval nodes is 2(n-1)+3.

A
Theory Explanation.
       GATE 1994
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; 
A
Theory Explanation.
       GATE 1994
Question 150

An array A contains n integers in locations A[0],A[1], …………… A[n-1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n-1. 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
A
Theory Explanation.
       GATE 1994
Question 151

A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, 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.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
Question 153

Write a program in 8085 Assembly language to Add two 16-bit unsigned BCD(8-4-2-1 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)

A
Theory Explanation.
       GATE 1994
Question 154

Find the contents of the flip-flop Q2, Q1 and Q0 in the circuit of figure, after giving four clock pulses to the clock terminal. Assume Q2Q1Q0 = 000 initially.

A
Theory Explanation.
       GATE 1994
Question 155

(a) Assume that a CPU has only two registers R1 and R2 and that only the following instruction is available XOR Ri, Rj; {Rj ← Ri ⊕ Rj, for i,j = 1,2}
Using this XOR instruction, find an instruction sequence in order to exchange the contents of the registers R1 and R2.

(b) The line p of the circuit shown in figure has stuck at 1 fault. Determine an input test to detect the fault.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
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(-).

A
Theory Explanation.
       GATE 1994
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

A
Theory Explanation.
       GATE 1994
Question 159

Every element a of some ring (R,+,0) satisfies the equation aoa = a.
Decide whether or not the ring is commutative.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
Question 162

(a) Given a set
S = {x| there is an x-block of 5's in the decimal expansion of π}
(Note: x-block 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 L1 is regular and that the language L1 ∪ L2 is regular, is the language L2 always regular? Prove your answer.

A
Theory Explanation.
       GATE 1994
Question 163

A grammar G is in Chomsky-Normal Form (CNF) if all its productions are of the form A → BC or A → a, where A, B and C, are non-terminals 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?

A
Theory Explanation.
       GATE 1994
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(n-1) + fib(n-2)
 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.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
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 + T|T        T → (E)|id 

Write a syntax directed translation to generate code using this grammar for the computer described above.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
Question 168

An array a contains n integers in non-decreasing 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.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
Question 170

(a) Draw a precedence graph for the following sequential code. The statements are numbered from S1 to S6

 S1       read n
 S2       i:=1
 S3       if i>n goto next
 S4       a(i):=i+1
 S5       i:=i+1
 S6       next : Write a(i) 

(b) Can this graph be converted to a concurrent program using parbegin-parend construct only?

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1994
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.

A
Theory Explanation.
       GATE 1993
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 non-jump instruction, what are the contents of PC after the execution of this instruction?

A
Theory Explanation.
       GATE 1993
Question 174

In the three-level memory hierarchy shown in the following table, pi denotes the probability that an access request will refer to Mi.

If a miss occurs at level Mi, a page transfer occurs from Mi+1 to Mi and the average time required for such a page swap is Ti. Calculate the average time tA required for a processor to read one word from this memory system.

A
Theory Explanation.
       GATE 1993
Question 175

The following Pascal program segments finds the largest number in a two-dimensional integer array A[0...n-1,0...n-1] 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.
A
Theory Explanation.
       GATE 1993
Question 176

Consider a singly linked list having n nodes. The data items d1, d2, ...dn are stored in these n nodes. Let X be a pointer to the j-th node (1≤j≤n) in which dj 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 d1, d2, ..., dj-1, dj, ..., dn in the order without using the header.

A
Theory Explanation.
       GATE 1993
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?

A
Theory Explanation.
       GATE 1993
Question 178

Consider the recursive algorithm given below:

 procedure bubblersort (n);
 var i,j: index; temp : item;
 begin
    for i:=1 to n-1 do
    if A[i] > A [i+1] then
 begin
    temp : A[i];
    A[i]:=A[i+1]; 
    A[i+1]:=temp
    end;
   bubblesort (n-1)
 end 

Let an 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 an in terms of an-1. Solve for an.

A
Theory Explanation.
       GATE 1993
Question 179

Prove by the principal of mathematical induction that for any binary tree, in which every non-leaf node has 2 descendants, the number of leaves in the tree is one more than the number of non-leaf nodes.

A
Theory Explanation.
       GATE 1993
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?

A
Theory Explanation.
       GATE 1993
Question 181

Show that proposition C is a logical consequence of the formula

     A ∧ (A →(B ∨ C)) ∧ (B → ~A)  

Using truth tables.

A
Theory Explanation.
       GATE 1993
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 flip-flops, and P is control input. Develop the state transition table for this controller.

A
Theory Explanation.
       GATE 1993
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  
A
Theory Explanation.
       GATE 1993
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.

A
Theory Explanation.
       GATE 1993
Question 185

Write a concurrent program using parbegin-parend and semaphores to represent the precedence constraints of the statements S1 to S6, as shown in figure below.

A
Theory Explanation.
       GATE 1993
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.

A
Theory Explanation.
       GATE 1993
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 3rd 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).

A
Theory Explanation.
       GATE 1993
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 context-free 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  
A
Theory Explanation.
       GATE 1993
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?

A
Theory Explanation.
       GATE 1993
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.

A
Theory Explanation.
       GATE 1993
Question 191

Let ({p,q{,*) be a semigroup where p * q = q. Show that:

 (a) p * q = q * p and
 (b) q * q = q 
A
Theory Explanation.
       GATE 1993
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 two-bit output (X1,X0) 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 3-bit counter using D-flip flops such that not more than one flip-flop changes state between any two consecutive states.

A
Theory Explanation.
       GATE 1992
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 write-through 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 INTR1, INTR2 and INTR3 are available with priority of INTR1 > priority of INTR2 > priority of INTR3.
Draw a schematic of the priority logic, using an interrupt mask register, in which Priority of A > Priority of B > Priority of C.

A
Theory Explanation.
       GATE 1992
Question 194

A microprocessor is capable of addressing 1 megabyte of memory with a 20-bit 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 sec-read 3µsec-write 

(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.

A
Theory Explanation.
       GATE 1992
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).

A
Theory Explanation.
       GATE 1992
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.

A
Theory Explanation.
       GATE 1992
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) FIND-ONE(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.

A
Theory Explanation.
       GATE 1992
Question 198

(a) What type of parameter passing mechanism (call-by-value, call-by-reference, call-by-name, or-by-value 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. 
A
Theory Explanation.
       GATE 1992
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 3-address 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  
A
Theory Explanation.
       GATE 1992
Question 200

(a) Draw the precedence graph for the concurrent program given below:

   S1
   parbegin
       begin
       S2:S4
       end;
       begin
       S3;
       parbegin
       S5;
       begin
          S6:S8
          End
       parend
   end;
   S7
  parend;
  S9  

(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.

A
Theory Explanation.
       GATE 1992
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.

A
Theory Explanation.
       GATE 1992
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 a2 = 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  
A
Theory Explanation.
       GATE 1992
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 a-b is a multiple of n. Show that R is an equivalence relation and finds its equivalence classes for n = 5.

A
Theory Explanation.
       GATE 1992
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.
A
Theory Explanation.
       GATE 1992
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 (a1, a2, a3) = (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.

A
Theory Explanation.
       GATE 1991
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 min-terms 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 flip-flop and AND gate is 10 ns. Also assume that the setup time for the JK inputs of the flipflops is negligible.

A
Theory Explanation.
       GATE 1991
Question 207

(a) Using D flip-flop and gates, design a parallel-in/serial-out 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 serial-in/serial-out unidirectional shift register using a 1K × 1 bit RAM with data input Din, data output Dout and control input . You may assume that availability of standard SSI and MSI components such as gates, registers and counters.

A
Theory Explanation.
       GATE 1991
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.

A
Theory Explanation.
       GATE 1991
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,

A
Theory Explanation.
       GATE 1991
Question 210

(a) Consider the following pseudo-code
(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 pseudo-code, 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. 
A
Theory Explanation.
       GATE 1991
Question 211

Consider the following grammar for arithmetic expression using binary operators – and/which are not associative:

   E → E−T|T
   T → T/F|F
   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.

A
Theory Explanation.
       GATE 1991
Question 212

Consider the following scheme for implementing a critical section in a situation with three processes and Pj and Pk.

     Pi;
     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
     non-critical 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.

A
Theory Explanation.
       GATE 1991
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.

A
Theory Explanation.
       GATE 1991
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 pseudo-code to delete an arbitrary node from such a binary tree with n nodes that preserves the structure. What is the worst-case time-complexity of your procedure?

A
Theory Explanation.
       GATE 1991
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) 
(A-universal quantifier and E-existential quantifier)
Does it have finite models?
Is it satisfiable? Is so, give a countable model for it.

A
Theory Explanation.
       GATE 1991
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.

A
Theory Explanation.
       GATE 1991
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 a1. Give a non-deterministic finite automaton that recognizes L. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?

A
Theory Explanation.
       GATE 1991
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.

A
True, True
B
True, False
C
False, True
D
False, False
       GATE 2008-IT
Question 218 Explanation: 
Note: Out of syllabus.
Question 219

Which of the following is TRUE only of XML but NOT HTML?

A
It is derived from SGML
B
It describes content and layout
C
It allows user defined tags
D
It is restricted only to be used with web browsers
       GATE 2008-IT
Question 219 Explanation: 
Note: Out of syllabus.
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
A
02, 03
B
01, 05
C
04, 06
D
02, 05
       GATE 2008-IT
Question 220 Explanation: 
Note: Out of syllabus.
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?

A
5, 5
B
4, 5
C
5, 4
D
4, 4
       GATE 2008-IT
Question 221 Explanation: 
Note: Out of syllabus.
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 algo­rithms 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 imple­mentation?

    (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.
A
S1
B
S2
C
S3
D
S4
       GATE 2008-IT
Question 222 Explanation: 
Note: Out of syllabus.
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
A
S4 and S3
B
S4 and S2
C
S3 and S1
D
S2 and S1
       GATE 2008-IT
Question 223 Explanation: 
Note: Out of syllabus.
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?

A
0
B
4
C
7
D
8
       GATE 2007-IT
Question 224 Explanation: 
0100 - Page fault, address till 199 in memory
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 mouse-click within the image and the subsequent action to be taken without additional responses from the web server.
(iii) The dots in the cgi-bin 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?

A
0
B
1
C
2
D
3
       GATE 2007-IT
Question 225 Explanation: 
Note: Out of syllabus.
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?

A
The Title and Content elements
B
The Content and TOC elements
C
The Title and TOC elements
D
The Title, Content and TOC elements
       GATE 2007-IT
Question 226 Explanation: 
Note: Out of syllabus.
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

A
0.45
B
0.63
C
0.84
D
0.95
       GATE 2007-IT
Question 227 Explanation: 
MIBF = ∑(Start of downtime - Start of uptime)/No. of failures
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

A
20
B
50
C
80
D
110
       GATE 2007-IT
Question 229

In the simplified flowchart given below, the shaded boxes represent code that is executed during a test case.

The Branch coverage is

A
3/4
B
2/3
C
1/2
D
3/8
       GATE 2007-IT
Question 229 Explanation: 
Note: Out of syllabus.
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

A
T1, T2, T8, T10
B
T1, T3, T8, T10
C
T1, T2, T3, T4, T5, T6, T7, T8, T9, T10
D
T1, T4, T5, T7, T8, T10
       GATE 2007-IT
Question 230 Explanation: 
Note: Out of syllabus.
Question 231

Consider the following pseudo-code:

 IF ((A > B) AND (C > D)) THEN
       A = A + 1
       B = B + 1
       ENDIF

The cyclomatic complexity of the pseudo-code is

A
2
B
3
C
4
D
5
       GATE 2007-IT
Question 231 Explanation: 
Note: Out of syllabus.
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.)

A
"b1 c1"
B
"b2 c3"
C
"b1 c2"
D
"b1 c3"
       GATE 2007-IT
Question 232 Explanation: 
Note: Out of syllabus.
Question 233

The cyclomatic complexity of the flow graph of a program provides

A
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once
B
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once
C
an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once
D
a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once
       GATE 2006-IT
Question 233 Explanation: 
Note: Out of syllabus.
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

A
1 or 3
B
2 or 3
C
2 or 4
D
1 or 4
       GATE 2006-IT
Question 234 Explanation: 
Note: Out of syllabus.
Question 235

A software program consists of two modules M1 and M2 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 M1is T1 with a mean time to repair (MTTR) of R1. The MTTF of M2 is T2 with an MTTR of R2. What is the availability of the overall program given that the failure and repair times are all exponentially distributed random variables?

A
B
C
D
       GATE 2006-IT
Question 235 Explanation: 
Note: Out of syllabus.
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?

A
III and IV
B
I and IV
C
II and IV
D
I, II and IV
       GATE 2006-IT
Question 236 Explanation: 
Note: Out of syllabus.
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 
A
The professor with the lowest course evaluation
B
Professors who have all their course evaluations above the university average
C
The course with the lowest evaluation
D
Courses with all evaluations above the university average
       GATE 2006-IT
Question 237 Explanation: 
Note: Out of syllabus.
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

A
60
B
63
C
66
D
69
       GATE 2006-IT
Question 238 Explanation: 
Note: Out of syllabus.
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

A
315
B
330
C
393
D
403
       GATE 2006-IT
Question 239 Explanation: 
Note: Out of syllabus.
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,

A
P1-P2-P4, 1 day
B
P1-P3-P4, 1 day
C
P1-P3-P4, 2 days
D
P1-P2-P4, 2 days
       GATE 2006-IT
Question 240 Explanation: 
Note: Out of syllabus.
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.

A
100 and 1000
B
100 and 1200
C
150 and 1200
D
200 and 2000
       GATE 2006-IT
Question 241 Explanation: 
Note: Out of syllabus.
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)?

A
6
B
4
C
3
D
2
       GATE 2005-IT
Question 242 Explanation: 
2, -3, 2, -1, 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

A
Except in case of an Operating System crash
B
Except in case of a Disk crash
C
Except in case of a power failure
D
Always, even if there is a failure of any kind
       GATE 2005-IT
Question 243 Explanation: 
Durability guarantees that once a transition has been committed, it will remain committed even in the case of a system failure.
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

A
01101011
B
011010110
C
011101100
D
0110101100
       GATE 2004-IT
Question 244 Explanation: 
In the data link layer, bits stuffing is employed then bit stuffing is done using the flag delimiter. If there is a flag of n bits then we will compare the data sequence with the flag and for every n-1 bits matched found, a bit 0 is stuffed in the data sequence.
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
Which data structure is used in breadth-first search of a graph to store nodes ?
A
Array
B
Stack
C
Queue
D
Tree
       NVS PGT CS 2017 Part-B
Question 245 Explanation: 
Queue is in breadth-first search of a graph to store nodes Use a queue to store the node and mark it as 'visited' until all its neighbours (vertices that are directly connected to it) are marked.
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
In neural network, the network capacity is defined as
A
The traffic carry capacity of the network
B
The total number of nodes in the network
C
The number of patterns that can be stored and recalled in a network
D
None of the above
       ISRO-2018
Question 246 Explanation: 
In neural network, the network capacity is defined as the number of patterns that can be stored and recalled in a network
Question 247
Cloaking is a search engine optimization (SEO) technique. During cloaking
A
Content presented to search engine spider is different from that presented to the user’s browser
B
Content present to search engine spider and browser is the same
C
Contents of the user’s requested website are changed
D
None of the above
       ISRO-2018
Question 247 Explanation: 
→ Cloaking takes a user to other sites than he or she expects by disguising those sites' true content.
→ 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
A data driven machine is one that executes an instruction if the needed data is available. The physical ordering of the code listing does not dictate the course of execution. Consider the following pseudo-code: (A) Multiply E by 0.5 to get F (B) Add A and B to get E (C) Add B with 0.5 to get D (D) Add E and F to get G (E) Add A with 10.5 to get C Assume A, B, C are already assigned values and the desired output is G. Which of the following sequence of execution is valid?
A
B, C, D, A, E
B
C, B, E, A, D
C
A, B, C, D, E
D
E, D, C, B, A
       ISRO-2018
Question 248 Explanation: 
Given data,
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
Type I Error occurs if
A
The null hypothesis is rejected even though it is true
B
The null hypothesis is accepted even though it is false
C
Both the null hypothesis as well as alternative hypotheses are rejected
D
None of the above
       HCU PHD CS 2018 June
Question 249 Explanation: 
Rejecting the null hypothesis when it is in fact true is called a Type I error.
Question 250
Armstrong’s inference rule does not determine
A
Reflexivity
B
Augmentation
C
Transitivity
D
Mutual dependency
       ISRO-2007
Question 250 Explanation: 
Armstrong inference rules refers to a set of inference rules used to infer all the functional dependencies on a relational database. It consists of the following axioms:
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
A rule in a limited entry decision table is a
A
row of the table consisting of condition entries
B
row of the table consisting of action entries
C
column of the table consisting of condition entries and corresponding action entries
D
columns of the table consisting of conditions of the stub
       ISRO-2007
Question 251 Explanation: 
A limited entry decision table is a structured way to formulate requirements and test cases when dealing with complex business rules. Using a decision table will make it easier to write requirements that cover all alternative conditions. In these tables, the upper half of the table lists the conditions being tested while the lower half lists the possible actions to be taken and each column represents a certain type of condition or rule.
Question 252
An email contains a textual birthday greeting, a picture of a cake and a song. The order is not important. What is the content-type?An email contains a textual birthday greeting, a picture of a cake and a song. The order is not important. What is the content-type?
A
Multipart/mixed
B
Multipart/parallel
C
Multipart/digest
D
Multipart/alternative
       ISRO-2007
Question 252 Explanation: 
The Multipart/parallel subtype
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
Perform window to viewport transformation for the point (20, 15). Assume that (Xwmin, Ywmin) is (0,0); (Xwmax, Ywmax) is (100,100); (Xvmin, Yvmin) is (5,5); (Xvmax, Yvmax) is (20,20). The value of x and y in the viewport is
A
x = 4 , y = 4
B
x = 3 , y = 3
C
x = 8 , y = 7.25
D
x = 3 , y = 4
       ISRO-2018
Question 253 Explanation: 

Question 254
Which of the following is mandatory attribute of < IMG > tag and < EMBED > tag ?
A
Border
B
HEIGHT
C
WIDTH
D
SRC
       NVS PGT CS 2017 Part-B
Question 254 Explanation: 
< img src= “ “ > The src attribute is required, and contains the path to the image you want to embed < embed src= “ “ >
Specifies the URL of an application to be embedded.
Question 255
A
XOR
B
NOR
C
XNOR
D
NAND
       NVS PGT CS 2017 Part-B
Question 255 Explanation: 
XOR gate ( EX-OR and pronounced as Exclusive OR) is a digital logic gate that gives a true (1 or HIGH) output when the number of true inputs is odd.
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
A
XY' + X
B
X'Y + XY'
C
XY + XY'
D
XY + X'Y'
       NVS PGT CS 2017 Part-B
Question 256 Explanation: 
XNOR gate is a digital logic gate whose function is the logical complement of the exclusive OR (XOR) gate.
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
A thread in Operating System is a
A
Task
B
Program
C
Process
D
Light weight process
       NVS PGT CS 2017 Part-B
Question 257 Explanation: 
A thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system.
Question 258
Which product metric gives the measure of the average length of words and sentence in documents?
A
SCI number
B
Cyclomatic complexity
C
LOC
D
Fog index
       ISRO-2017 May
Question 258 Explanation: 
→ In linguistics, the Gunning fog index is a readability test for English writing. The index estimates the years of formal education a person needs to understand the text on the first reading
→ 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
Type 4 JDBC driver is a driver
A
which is written in C++
B
which requires an intermediate layer
C
which communicates through Java sockets
D
which translates JDBC function calls into API not native to DBMS
       ISRO-2017 December
Question 259 Explanation: 
The JDBC type 4 driver, also known as the Direct to Database Pure Java Driver, is a database driver implementation that converts JDBC calls directly into a vendor-specific database protocol.
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 application-to-database connection; this can facilitate debugging.

Disadvantages Drivers are database specific, as different database vendors use widely different (and usually proprietary) network protocols.

Type-1 driver (or) JDBC-ODBC bridge driver
Type-2 driver (or) Native-API driver
Type-3 driver (or) Network Protocol driver
Type-4 driver (or) Thin driver
Question 260
You are playing an old-style video game in which you have to shoot down alien space- ships as they fly across the screen from left to right. Each spaceship flies across the screen at a specified height. You have an antiaircraft gun set to shoot down all space- ships at a certain height. Spaceships fly one at a time, so if your gun is set to fire at the correct height, it will shoot down the spaceship currently flying across the screen.
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.
A
Descriptive Explanation
       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 260 Explanation: 
(a) If we view h[1], . . . , h[N ] as a list of numbers, we are essentially asked to find the length of the longest descending subsequence. The recurrence is as follows:
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 First In First Out queue is a data structure supporting the operations Enque, Deque, Print. Enque(x) adds the item x to the tail of the queue. Deque removes the element at the head of the queue and returns its value. Print prints the head of the queue.
(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?
A
Descriptive Explanation
       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 261 Explanation: 
(a) Assume the queue contains 1,2,3,4,5 in order, with 1 at the head. We display below the sequence of instructions and the state of the queue whenever it changes.

(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 "01-JAN-07"
A
SELECT*, COUNT () FROM CLUB WHERE TYPE = "MONTHLY'' AND DOJ > = "01-JAN-07'';
B
SELECT FROM CLUB COUNT (*) WHERE TYPE = "MONTHLY" AND DOJ "01-JAN-07";
C
SELECT COUNT (*) FROM CLUB WHERE TYPE = "MONTHLY" OR DOJ = "01- JAN-07";
D
SELECT COUNT (*) FROM CLUB WHERE TYPE = "MONTHLY" AND DOJ > "01-JAN-07";
       NVS PGT CS 2017 Part-B
Question 262 Explanation: 
The SQL COUNT() function returns the number of rows in a table satisfying the criteria specified in the WHERE clause. It sets the number of rows or non NULL column values.
COUNT() returns 0 if there were no matching rows.
Question 263
Which is not the state of the process in OS?
A
vileged
B
Running
C
Ready
D
Blocked
       NVS PGT CS 2017 Part-B
Question 263 Explanation: 
New- The process is being created.
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
Which of the following is not a valid value of the SCROLLING attribute of the <FRAME > tag ?
A
yes
B
No
C
Auto
D
None
       NVS PGT CS 2017 Part-B
Question 264 Explanation: 
The syntax of frame tag:
< frame scrolling="auto|yes|no" >
Attribute Values
Question 265
Given two sorted lists of size m and n respectively. The number of comparisons needed in the worst case by the merge algorithm will be.
A
min (m, n)
B
max (m, n)
C
m+n-1
D
mn
       NVS PGT CS 2017 Part-B
Question 265 Explanation: 
→ To merge two lists of size m and n, we need to do m+n-1 comparisons in the worst case. Since we need to merge 2 at a time, the optimal strategy would be to take the smallest size lists first. → The reason for picking smallest two items is to carry minimum items for repetition in merging.
Question 266
Which Boolean law is represented below?
P+QR=(P+Q)(P+R)
A
De Morgan's law
B
Associative law
C
Commutative law
D
Distributive law
       NVS PGT CS 2017 Part-B
Question 266 Explanation: 
Distributive Law – This law permits the multiplying or factoring out of an expression.
A(B + C) = A.B + A.C (OR Distributive Law)
A + (B.C) = (A + B).(A + C) (AND Distributive Law)
Question 267
Which of the words below matches the regular expression a(a + b) ∗ b + b(a + b) ∗ a?
A
aba
B
bab
C
abba
D
aabb
       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 267 Explanation: 
Word should start with an a and end with b, or start with b and end with a.
Question 268
Akash, Bharani, Chetan and Deepa are invited to a party. If Bharani and Chetan attend, then Deepa will attend too. If Bharani does not attend, then Akash will not attend. If Deepa does not attend, which of the following is true?
A
Chetan does not attend
B
Akash does not attend
C
either (a) or (b)
D
none of the above
       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (15 May 2018)
Question 268 Explanation: 
If Deepa does not attend, then one of Chetan and Bharani is absent. The first case is (a). The second case is that Bharani does not attend – but it is given that Akash will not attend if Bharani does not attend. So in the second case, (b) holds. So either (a) holds or (b) holds, and hence the correct answer is (c).
Question 269
Out Of the following, which cannot be used as an identifier in C++ ?
A
Name2
B
Total
C
class
D
Derived
       NVS PGT CS 2017 Part-B
Question 269 Explanation: 
“Class” is the keyword in c++.
We can’t use keywords as identifier names.
Question 270
What does a pixel mask mean?
A
string containing only 1’s
B
string containing only 0’s
C
string containing two 0’s
D
string containing 1’s and 0’s
       ISRO CS 2014
Question 270 Explanation: 
Pixel mask: when a given image is intended to be placed over a background, the transparent areas can be specified through a binary mask.
→ 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 all-zero bits and white pixels have the all-one bits.
Question 271
The number of logical CPUs in a computer having two physical quad-core chips with hyperthreading enabled is
A
1
B
2
C
8
D
16
       ISRO CS 2014
Question 271 Explanation: 
There is only one processor chip. That chip can have one, two, four, six, or eight cores.
Currently, an 18-core 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
In this programming methodology, common functionalities are grouped together into separate independent units. The whole program is divided into several units which interact through procedure calls.
A
Random Programming
B
Modular Programming
C
.NET Programming
D
Object Oriented Programming
       NVS PGT CS 2017 Part-B
Question 272 Explanation: 
Complex program is divided into several modules.
Each module meant for a specific functionality.
Question 273
The output of a tristate buffer when the enable input in 0 is
A
Always 0
B
Always 1
C
Retains the last value when enable input was high
D
Disconnected state
       ISRO CS 2014
Question 274
The operator used to access member functions of a class from its object is
A
*
B
::
C
:
D
'
       NVS PGT CS 2017 Part-B
Question 274 Explanation: 
Scope resolution(::) operator is used to access the member functions outside the class in c++.
Question 275
A web client sends a request to a web server. The web server transmits a program to that client and is executed at the client. It creates a web document. What are such web documents called?
A
Active
B
Static
C
Dynamic
D
Passive
       ISRO CS 2014
Question 275 Explanation: 
→ Static
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
The following is a computing industry standard for the consistent encoding, representation and handling of text.
A
EBCDIC
B
Unicode
C
ASCII
D
QRcode
       NVS PGT CS 2017 Part-B
Question 276 Explanation: 
Unicode is a computing industry standard for the consistent encoding, representation, and handling of text expressed in most of the world's writing systems.
Question 277
If the maximum output voltage of a DAC is V volts and if the resolution is R bits then the weight of the most significant bit is
A
V/ (2R -1)
B
(2R-1).V/(2R -1)
C
(2R-1).V
D
V/(2R-1)
       ISRO CS 2014
Question 277 Explanation: 
→ If the maximum output voltage of a Digital to Analogue Converter is V volts and if the resolution is R bits then the weight of the most significant bit is (2R-1).V/(2R-1)
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 :

A
16 frames per second
B
19 frames per second
C
21 frames per second
D
23 frames per second
       UGC-NET CS 2018 JUNE Paper-2
Question 278 Explanation: 
Given data,
- 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 = ?
Step-1: Graphic display system = 640 * 480 =307200
Step-2: Memory required for Graphic display system = 640 * 480 * 1 = 307200
Step-3: Total screen access time = Memory required for Graphic display system * Access time of each pixel
= 307200 * 200 ns
= 61440000 ns
Step-4: Refresh rate of frame buffer per second =(10-9)/61440000
= 16.27604166 frames per second
[ Note: 10-9 = 1000000000 ]
Question 279
Which of the following statements is true for TCP protocol?
A
TCP is a connection-less unreliable protocol. [Option ID = 11080]
B
TCP is a connection-less reliable protocol. [Option ID = 11079]
C
TCP is a connection-oriented reliable protocol. [Option ID = 11077]
D
TCP is a connection-oriented unreliable protocol. [Option ID = 11078]
       DU PHD JUNE 2018
Question 279 Explanation: 
TCP is a connection-oriented reliable protocol. [Option ID = 11077]
Question 280
Copying a process from memory to disk to allow space for other processes is called:
A
Swapping
B
Demand Paging
C
Deadlock
D
Page Fault
       Nielit Scientist-B IT 4-12-2016
Question 280 Explanation: 
→ Swapping was an early virtual memory technique. An entire program would be swapped out (or rolled out) from RAM to disk, and another one would be swapped in (or rolled in). → A swapped-out program would be current but its execution would be suspended while its RAM was in use by another program.
Question 281
Find the odd one out
A
Merge Sort
B
Travelling Salesman Problem
C
Knapsack Problem
D
Optimal Binary Search Tree Problem
       Nielit Scientist-B IT 4-12-2016
Question 281 Explanation: 
Merge Sort → Divide and Conquer
Travelling Salesman Problem → Dynamic Programming
Knapsack Problem → Dynamic Programming
Optimal Binary Search Tree Problem → Dynamic Programming
Question 282
What is 2's complement of (101)​ 3​ ?
A
(010​ ) ​ 3
B
(011​ )3
C
(121​ ) ​ 3
D
(121​ ) ​ 2
       Nielit Scientist-B IT 4-12-2016
Question 282 Explanation: 
Given base is r=3. So, 2’s complement is diminished radix complement or (r-1) complement. (r-1)’s complement is 222-101= 121
Question 283
If attributes of relation schema R is member of some candidate key then this type of attributes are classified as:
A
atomic attribute
B
candidate attribute
C
non prime attribute
D
prime attribute
       Nielit Scientist-B IT 4-12-2016
Question 283 Explanation: 
→ ​ In the relational model of databases, a candidate key of a relation is a minimal superkey for that relation; that is, a set of attributes such that:
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 non-prime 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
Which of this is not a network edge device?
A
PC
B
Server
C
Smartphone
D
Switch
       Nielit Scientist-B IT 4-12-2016
Question 284 Explanation: 
● PC, Server and Smartphones are devices which are used for various purposes where as Switch is networking device.
● 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
The example of implied addressing is
A
Stack addressing
B
Indirect addressing
C
Immediate addressing
D
None of the above
       Nielit Scientist-B IT 4-12-2016
Question 285 Explanation: 
-----> Operand is (implicitly) on top of stack
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
The degree of multi programming is controlled by:
A
CPU Scheduler
B
long term Scheduler
C
Context Switching
D
Medium term Scheduler
       Nielit Scientist-B IT 4-12-2016
Question 286 Explanation: 
→ The long-term scheduler, or admission scheduler, decides which jobs or processes are to be admitted to the ready queue (in main memory); that is, when an attempt is made to execute a program, its admission to the set of currently executing processes is either authorized or delayed by the long-term scheduler. Thus, this scheduler dictates what processes are to run on a system, and the degree of concurrency to be supported at any one time – whether many or few processes are to be executed concurrently, and how the split between I/O-intensive and CPU-intensive processes is to be handled.
→ The long-term scheduler is responsible for controlling the degree of multiprogramming.
Question 287
How many addition and subtraction are required if you perform multiplication of 5(multiplicand) and -30(Multiplier) using Booth algorithm?
A
2,1
B
1,2
C
1,1
D
2,2
       Nielit Scientist-B IT 4-12-2016
Question 287 Explanation: 
Step-1: 2’s complement of 30 is=00011110
Step-2: Append 0 in LSB of 2’s complement number=000111100
Step-3: 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
Step-4: There are total 1 additions and 2 subtractions
Question 288
The decimal equivalent of the Hexadecimal number(AC7B)​ 16​ is:  
A
32564
B
44155
C
50215
D
43562
       Nielit Scientist-B IT 4-12-2016
Question 288 Explanation: 
= Ax16​ 3​ + Cx16​ 2 ​ + 7x16​ 1 ​ + Bx16​ 0
= 10x16​ 3​ +12x16​ 2​ + 7x16 + 11
= 40960 + 3072 + 112 +11
= ​ 44155
Question 289
How will you free the allocated memory?  
A
remove(var-name)
B
free(var-name)
C
delete(var-name)
D
dalloc(var-name)
       Nielit Scientist-B IT 4-12-2016
Question 289 Explanation: 
Dynamically allocated memory created with either calloc() or malloc() doesn't get freed on their own. You must explicitly use free() to release the space.
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

A
3
B
4
C
5
D
6
       UGC-NET CS 2018 DEC Paper-2
Question 290 Explanation: 
→ Here, every process requirement is 4 instances of the resource.
→ 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
What are the primary characteristics that distinguish a cell from a packet?
A
Cells are generally smaller that packets
B
Cells do not incorporate physical address
C
all cell have the same fixed length
D
packet cannot be switched
       Nielit Scientist-C 2016 march
Question 291 Explanation: 
● Frames and packets, in general, can be of variable length, depending on their contents; in contrast, a cell is most often a message that is fixed in size.
● For example, the fixed-length, 53-byte 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 AND-OR Search algorithm.

    S1 : A solution is a subtree that has a goal node at every leaf.
    S2 : OR nodes are analogous to the branching in a deterministic environment
    S3 : AND nodes are analogous to the branching in a non-deterministic environment.

Which one of the following is true referencing the above statements?

Choose the correct answer from the code given below:

Code:
A
S1- False, S2- True, S3- True
B
S1- True, S2- True, S3- True
C
S1- False, S2- True, S3- False
D
S1- True, S2- True, S3- False
       UGC-NET CS 2018 DEC Paper-2
Question 292 Explanation: 
• An and–or tree is a graphical representation of the reduction of problems (or goals) to conjunctions and disjunctions of subproblems (or subgoals).
• A solution in an AND-OR tree is a sub tree whose leaves are included in the goal set.
Question 293
Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is
A
248000
B
44000
C
19000
D
25000
       Nielit Scientist-B CS 22-07-2017
Question 293 Explanation: 


Question 294

Which homogeneous 2D matrix transforms the figure (a) on the left side to the figure (b) on the right ?

 
A
B
C
D
       UGC-NET CS 2018 DEC Paper-2
Question 294 Explanation: 
The homogeneous coordinates of the cartesian point (x,y) is (x,y,1) and the transformation Matrix is a 3x3 Matrix.
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.

A
HTTP GET request, DNS query, TCP SYN
B
DNS query, TCP SYN, HTTP GET request
C
TCP SYN, DNS query, HTTP GET request
D
DNS query, HTTP Get request, TCP SYN
       UGC-NET CS 2018 DEC Paper-2
Question 295 Explanation: 
Sequence in which the given 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:
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 semi-dynamic environment ?

A
The environment itself does not change with the passage of time but the agent’s performance score does.
B
The environment change while the agent is deliberating.
C
Even if the environment changes with the passage of time while deliberating, the performance score does not change.
D
Environment and performance score, both change simultaneously.
       UGC-NET CS 2018 DEC Paper-2
Question 296 Explanation: 
Semi- Dynamic environment :
The environment itself does not change with the passage of time but the agent’s performance score does.
Question 297
Suppose T(n)=2T(n/2)+n, T(0)=T(1)=1 which one of the following is false?
A
T(n)=O(n2)
B
T(n)=O(nlogn)
       Nielit Scientist-B CS 22-07-2017
Question 297 Explanation: 
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:
A
Statement S1 is true but statement S2 is false.
B
Statement S1 is false but statement S2 is true.
C
Neither of the statements S1 and S2 are true.
D
Both the statements S1 and S2 are true.
       UGC-NET CS 2018 DEC Paper-2
Question 298 Explanation: 
A heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.
Question 299
In the Merge sort algorithm, the time taken by the algorithm to divide an array of size n into two equal halves and many times that divide is called in overall sorting procedure is:
A
O(1) and θ(logn)
B
θ(1) and θ(logn)
C
O(logn) and θ(logn)
D
θ(logn) and O(1)
       Nielit STA [02-12-2018]
Question 299 Explanation: 
→ In the Merge sort algorithm, the time taken by the algorithm to divide an array of size n into two equal halves is O(logn)
→ 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:
A
Neither (i) nor (ii)
B
Both (i) and (ii)
C
(i) only
D
(ii) only
       UGC-NET CS 2018 DEC Paper-2
Question 300 Explanation: 
→ The Data warehouse Hadoop cluster at Facebook has become the largest known Hadoop storage cluster in the world.
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 map-reduce 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
Which of the following are context free?
A = {anbnambm | m, n>=0}
B = {anbnambn | m, n>=0}
C = {ambn | m≠2n,m, n>=0}
A
A and B only
B
A and C only
C
B and C only
D
C only
       ISRO DEC 2017 22- Soon
Question 301 Explanation: 
Statement-A: When 'a' will comes as input. We will push it on the top of stack and when 'b' will comes as input after 'a' we will pop one 'a' for each 'b'.
This way language 'A' can be accepted by the push down automat. Hence A is CFL.
Statement-B: When last 'b' i.e., bn after am comes as input then top of the stack will contain am
So we can't compare an with anbn. Hence it is not CFL
Statement-C: It is a CFL
Question 302
Let S be an NP-complete problem. Q and R are other two problems not known to be NP. Q is polynomial time reducible to S and S is polynomial time reducible to R. Which of the following statements is true?
A
R is NP-complete
B
R is NP-hard
C
Q is NP-complete
D
Q is NP-hard
       ISRO DEC 2017 22- Soon
Question 302 Explanation: 
NP-Hard- if it can be solved in polynomial time then all NP-Complete can be solved in polynomial time. If NP Hard problem is reducible to another problem in Polynomial Time, then that problem is also NP Hard which means every NP problem can be reduced to this problem in Polynomial Time.
Question 303
The number of structurally different possible binary trees with 4 nodes is
A
14
B
12
C
336
D
168
       ISRO DEC 2017 22- Soon
Question 303 Explanation: 
Finding number of binary tree, we are using catalan numbers formula

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 (x1,y1) and (x2,y2)
(2) y = y1
(3) d = f(x1+1, y1+½) // f is the implicit form of a line
(4) for x = x1 to x2
(5) do
(6)       plot (x,y)
(7)       if (d<0)
(8)       then
(9)           y = y+1
(10)         d = d+(y1 - y2) + (x2 - x1)
(11)     else
(12)         d = d+(y1 - y2)
(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 :
A
Q and R only
B
P only
C
P and Q only
D
P, Q and R
       UGC-NET CS 2018 DEC Paper-2
Question 304 Explanation: 
From the code given in question gives information that the algorithm will work if d is ever 0, So the statement R is false.
Line 10 and 12 will update the value of d , So the statement Q is true.
Question 305
Using public key cryptography, X adds a digital signature σ to a message M, encrypts (M,σ) and sends it to Y, where it is decrypted. Which one of the following sequence of keys is used for operations?
A
Encryption : X’s private key followed by Y’s private key. Decryption : X’s public key followed by Y’s public key.
B
Encryption : X’s private key followed by Y’s public key; Decryption : X’s public key followed by Y’s private key
C
Encryption : X’s private key followed by Y’s public key; Decryption : Y’s private key followed by X’s public key.
D
Encryption : X’s public key followed by Y’s private key; Decryption : Y’s public key followed by X’s private key.
       ISRO DEC 2017 22- Soon
Question 305 Explanation: 

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
Which of the following are used to generate a message digest by the network security protocols?
(P) SHA-256
(Q) AES
(R) DES
(S) MD5
A
P and S only
B
P and Q only
C
R and S only
D
P and R only
       ISRO DEC 2017 22- Soon
Question 306 Explanation: 
To generate a message digest by the network security protocols we need SHA and MD5.
→ SHA-256 and SHA-512 are novel hash functions computed with 32-bit and 64-bit 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 message-digest algorithm is a widely used hash function producing a 128-bit 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 non-cryptographic purposes, for example for determining the partition for a particular key in a partitioned database.
Question 307
In the IPv4 addressing format, the number of networks allowed under Class C addresses is
A
220
B
224
C
214
D
221
       ISRO DEC 2017 22- Soon
Question 307 Explanation: 
→ IP address belonging to class C are assigned to small-sized networks.
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:
221 = 2097152 network address
28 – 2 = 254 host address
IP addresses belonging to class C ranges from 192.0.0.x – 223.255.255.x.
Question 308
An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses available with it: 245.248.128.0/20. The ISP wants to give half of this chunk of addresses to Organization A, and a quarter to Organization B, while retaining the remaining with itself. Which of the following is a valid allocation of addresses to A and B?
A
245.248.136.0/21 and 245.248.128.0/22
B
245.248.128.0/21 and 245.248.128.0/22
C
245.248.132.0/22 and 245.248.132.0/21
D
245.248.136.0/24 and 245.248.132.0/21
       ISRO DEC 2017 22- Soon
Question 308 Explanation: 

Question 309
Assume that Source S and Destination D are connected through an intermediate router R. How many times a packet has to visit the network layer and data link layer during a transmission from S to D?
A
Network layer – 4 times, Data link layer – 4 times
B
Network layer – 4 times, Data link layer – 6 times
C
Network layer – 2 times, Data link layer – 4 times
D
Network layer – 3 times, Data link layer – 4 times
       ISRO DEC 2017 22- Soon
Question 309 Explanation: 
Source and destination are hosts. The hosts have all layers but routers have only 3 layers i.e physical,data link and network layer. The purpose of routers is to just pass on the packet between hosts or networks.
Therefore ,
Question 310
Generally TCP is reliable and UDP is not reliable. DNS which has to be reliable uses UDP because
A
UDP is slower
B
DNS servers has to keep connections
C
DNS requests are generally very small and fit well within UDP segments
D
None of these
       ISRO DEC 2017 22- Soon
Question 310 Explanation: 
→ UDP is cheap.
→ 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
Consider the set of activities related to e-mail
A : Send an e-mail from a mail client to mail server
B : Download e-mail headers from mail box and retrieve mails from server to a cache
C : Checking e-mail through a web browser
The application level protocol used for each activity in the same sequence is
A
SMTP, HTTPS, IMAP
B
SMTP, POP, IMAP
C
SMTP, IMAP, HTTPS
D
SMTP, IMAP, POP
E
None of the above
       ISRO DEC 2017 22- Soon
Question 311 Explanation: 
→ SMTP is used for connecting to outbound servers to send email while POP3 and IMAP are used to connect to incoming servers to retrieve messages.
→ POP download email headers from mailbox and retrieve mails from servers to a cache.
→ HTTPS checking email through a web browser.
Question 312
Station A uses 32 byte packets to transmit messages to Station B using a sliding window protocol. The round trip time delay between A and B is 40 ms and the bottleneck bandwidth on the path A and B is 64 kbps. What is the optimal window size that A should use?
A
5
B
10
C
40
D
80
       ISRO DEC 2017 22- Soon
Question 312 Explanation: 
Given data,
-- 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=?
Step-1: First we have to find transmission time
Transmission time= Frame size/bandwidth
= 32*8/(64) ms
= 4 ms
Step-2: 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
A two way set associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The physical address space is 4 GB. The number of bits in the TAG, SET fields are
A
20, 7
B
19, 8
C
20, 8
D
21, 9
       ISRO DEC 2017 22- Soon
Question 313 Explanation: 
2-way set associative it means 2 cache lines in one set
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 2-way set-associative cache
= 2^9 /2 = 2^8 sets => 8 set bits
Now, because it is set-associative 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
A CPU has a 32 KB direct mapped cache with 128 byte block size. Suppose A is a 2 dimensional array of size 512×512 with elements that occupy 8 bytes each. Consider the code segment
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
A
16384
B
512
C
2048
D
1024
       ISRO DEC 2017 22- Soon
Question 314 Explanation: 
→ Access A in row major order.
→ No. of cache blocks=Cache size/Block size = 32KB / 128B = 32×210B / 128B = 215 / 27 = 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
A computer with 32 bit word size uses 2s complement to represent numbers. The range of integers that can be represented by this computer is
A
–232 to 232
B
–231 to 232-1
C
–231 to 231-1
D
–231-1 to 232-1
       ISRO DEC 2017 22- Soon
Question 315 Explanation: 
Range of ‘n’ bit 2’s complement binary number is always –2(n-1) to 2(n-1)-1.
Question 316
Let M = 11111010 and N = 00001010 be two 8 bit two’s complement number. Their product in two’s complement is
A
11000100
B
10011100
C
10100101
D
11010101
       ISRO DEC 2017 22- Soon
Question 316 Explanation: 
A = 1111 1010 = -610 [2's complement number]
B = 0000 1010 = 1010 [2's complement number]
A×B = -6×10 = - 6010
⇒ -6010 = 101111002
= 110000112 (1's complement)
= 110001002 (2's complement)
Question 317
For a pipelines CPU with a single ALU, consider the following:
  1. The j + 1st instruction uses the result of jth instruction as an operand
  2. Conditional jump instruction
  3. jth and j + 1st instructions require ALU at the same time
Which one of the above causes a hazard?
A
A and B only
B
B and C only
C
B only
D
A , B and C
       ISRO DEC 2017 22- Soon
Question 317 Explanation: 
A is belongs to the Data hazard.
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
In designing a computer’s cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context?
A
Smaller block size incurs lower cache miss penalty
B
Smaller block size implies better spatial locality
C
Smaller block size implies smaller cache tag
D
Smaller block size implies lower cache hit time
       ISRO DEC 2017 22- Soon
Question 318 Explanation: 
When a cache block size is smaller, it could accommodate more number of blocks, it improves the hit ratio for cache, so the miss penalty for cache will be lowered.
Question 319
Consider an instruction of the type LW R1, 20(R2) which during execution reads a 32 bit word from memory and stores it in a 32 bit register R1. The effective address of the memory location is obtained by adding a constant 20 and contents of R2. Which of the following best reflects the addressing mode implemented by this instruction for operand in memory?
A
Immediate addressing
B
Register addressing
C
Register Indirect addressing
D
Indexed addressing
       ISRO DEC 2017 22- Soon
Question 319 Explanation: 
Here 20 will act as base and content of R2 will be index.
→ 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
A sorting technique is called stable if
A
If it takes O(n log n) time
B
It uses divide and conquer technique
C
Relative order of occurrence of non-distinct elements is maintained
D
It takes O(n) space
       ISRO DEC 2017 22- Soon
Question 320 Explanation: 
→ Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values).
→ 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
Match the following and choose the correct Solution in the order A, B, C (Bounds given may or may not be asymptotically tight)
A
q, r, p
B
p, q, r
C
q, p, r
D
r, q, p
       ISRO DEC 2017 22- Soon
Question 321 Explanation: 
Heap Construction → O(n)
Hash table construction→ O(n2)
AVL tree construction → O(logn)
Question 322
In a compact one dimensional array representation for lower triangular matrix (all elements above diagonal are zero) of size n x n, non zero elements of each row are stored one after another, starting from first row, the index of (i, j)th element in this new representation is
A
i+j
B
j+i(i-1)/2
C
i+j-1
D
i+j(j-1)/2
       ISRO DEC 2017 22- Soon
Question 322 Explanation: 
Though not mentioned in question, from options it is clear that array index starts from 1 and not 0. If we assume array index starting from 1 then, ith row contains i number of non-zero elements. Before ith row there are (i-1) rows, (1 to i-1) and in total these rows has 1+2+3......+(i-1) = i(i-1)/2 elements.
Now at ith row, the jth 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(i-1)/2
Question 323
Which of the following permutation can be obtained in the same order using a stack assuming that input is the sequence 5, 6, 7, 8, 9 in that order?
A
7, 8, 9, 5, 6
B
5, 9, 6, 7, 8
C
7, 8, 9, 6, 5
D
9, 8, 7, 5, 6
       ISRO DEC 2017 22- Soon
Question 323 Explanation: 
Push 5 Push 6 Push 7 Pop 7 Push 8 Pop 8 Push 9 Pop 9 Pop 6 Pop 5.
→ Remaining options are not possible.
Question 324
Quick sort is run on 2 inputs shown below to sort in ascending order
A.     1, 2, 3……n
B.     n, n-1, n-2 …… 1
Let C1 and C2 be the number of comparisons made for A and B respectively. Then
A
C1>C2
B
C1=C2
C
C1
D
Cannot say anything for arbitrary n
       ISRO DEC 2017 22- Soon
Question 324 Explanation: 
→ The above question is clearly specifying quicksort worst case complexity.
→ Elements are already sorted order it gives worst case complexity O(n2)
→ If all elements are having same weight, it performs worst case complexity.
Question 325
A binary search tree is used to locate the number 43. Which one of the following probe sequence is not possible?
A
61, 52, 14, 17, 40, 43
B
10, 65, 31, 48, 37, 43
C
81, 61, 52, 14, 41, 43
D
17, 77, 27, 66, 18, 43
       ISRO DEC 2017 22- Soon
Question 325 Explanation: 
Question 326
The characters of the string K R P C S N Y T J M are inserted into a hash table of size 10 using hash function
h(x) = ((ord(x) - ord(A) + 1)) mod 10
If linear probing is used to resolve collisions, then the following insertion causes collision
A
Y
B
C
C
M
D
P
       ISRO DEC 2017 22- Soon
Question 326 Explanation: 
Given information,
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
Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the reversal ordering on natural numbers i.e. 9 is assumed to be smallest and 0 is assumed to be largest. The in-order traversal of the resultant binary search tree is
A
9, 8, 6, 4, 2, 3, 0, 1, 5, 7
B
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
C
0, 2, 4, 3, 1, 6, 5, 9, 8, 7
D
9, 8, 7, 6, 5, 4, 3, 2, 1, 0
       ISRO DEC 2017 22- Soon
Question 327 Explanation: 

In order: 0 1 2 3 4 5 6 7 8 9
Question 328
A priority queue is implemented as a Max-heap. Initially it has 5 elements. The level order traversal of the heap is 10, 8, 5, 3, 2. Two new elements ‘1’ and ‘7’ are inserted into the heap in that order. The level order traversal of the heap after the insertion of the elements is
A
10, 8, 7, 5, 3, 2, 1
B
10, 8, 7, 2, 3, 1, 5
C
10, 8, 7, 1, 2, 3, 5
D
10, 8, 7, 3, 2, 1, 5
       ISRO DEC 2017 22- Soon
Question 328 Explanation: 
Max-Heap has 5 elements:

The level order traversal in this max heap final is:
10, 8, 7, 3, 2, 1, 5.
Question 329
The minimum number of stacks needed to implement a queue is
A
3
B
1
C
2
D
4
       ISRO DEC 2017 22- Soon
Question 329 Explanation: 
Minimum number of stacks of size n required to implement a queue of size n is two. With the help of two stacks we can able to implement a queue.
Question 330
A strictly binary tree with 10 leaves
A
cannot have more than 19 nodes
B
has exactly 19 nodes
C
has exactly 17 nodes
D
has exactly 20 nodes
       ISRO DEC 2017 22- Soon
Question 330 Explanation: 
→ If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one.
→ A strictly binary tree with N leaves always contains 2N – 1 nodes.
(2*10)-1 =19
Question 331
What is the maximum height of any AVL tree with 7 nodes? Assume that height of tree with single node is 0.
A
2
B
3
C
4
D
5
       ISRO DEC 2017 22- Soon
Question 331 Explanation: 
The maximum height of any AVL tree with 7 nodes is, [where root is considered as height 0]
2h-1=7
h=3
Question 332
Which one of the following property is correct for a red-black tree?
A
Every simple path from a node to a descendant leaf contains the same number of black nodes
B
If a node is red, then one children is red and another is black
C
If a node is red, then both its children are red
D
Every leaf node (sentinel node) is red
       ISRO DEC 2017 22- Soon
Question 332 Explanation: 
→ It could be from a binary search tree. The red-black tree tracks every simple path from a node to a descendant leaf that has the same number of black nodes.
→ A red black tree is a kind of self-balancing 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
The in order and pre order traversal of a binary tree are
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
A
e d b g f c a
B
e d b f g c a
C
d e b f g c a
D
d e f g b c a
       ISRO DEC 2017 22- Soon
Question 333 Explanation: 
Inorder: Left root Right
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
A virtual memory system uses FIFO page replacement policy and allocates a fixed number of frames to the process. Consider the following statements
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?
A
Both M and N are true and N is the reason for M
B
Both M and N are true and N is not the reason for M
C
Both M and N are false
D
M is false, but N is true
       ISRO DEC 2017 22- Soon
Question 334 Explanation: 
→ FIFO suffers from Belady Anomaly.
→ 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
ROWSPAN attribute cannot be used with which of the following tag ?
A
< TR *gt;
B
< TD >
C
< TH >
D
< TABLE >
E
A and D
       NVS PGT CS 2017 Part-B
Question 335 Explanation: 
ROWSPAN attribute is used for both < td > and < tr > tags.
Question 336
Consider three CPU intensive processes, which require 10, 20, 30 units and arrive at times 0, 2, 6 respectively. How many context switches are needed if shortest remaining time first is implemented? Context switch at 0 is included but context switch at end is ignored
A
1
B
2
C
3
D
4
       ISRO DEC 2017 22- Soon
Question 336 Explanation: 

Total no.of context switches is 2.
Question 337
A process executes the following code for (i = 0; i < n; i++) fork( ); The total number of child processes created are
A
n2
B
2n+1 -1
C
2n
D
2n -1
       ISRO DEC 2017 22- Soon
Question 337 Explanation: 
Fork is a system call, implements in kernel.
It is a operation where process creates a copy of itself.

1,3,7,15,31,... ⇒ 2n-1
Question 338
Consider the following scheduling

Matching the table in the order A, B, C gives
A
t, u, s
B
s, t, u
C
u, s, t
D
u, t, s
       ISRO DEC 2017 22- Soon
Question 338 Explanation: 
Gang Scheduling is a scheduling algorithm for parallel systems that schedules related threads (or) processes to run simultaneously on different processes to run simultaneously on different processes.
Rate Monotonic scheduling is a priority assignment algorithm used in Real-Time 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
A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 50 distinct pages in some order and then accesses the same 50 pages in reverse order. How many page faults will occur?
A
96
B
100
C
97
D
92
       ISRO DEC 2017 22- Soon
Question 339 Explanation: 
The first 100 accesses causes 100 page faults.
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
Which of the following is false?
A
User level threads are not scheduled by the kernel
B
Context switching between user level threads is faster than context switching between kernel level threads
C
When a user thread is blocked all other threads of its processes are blocked
D
Kernel level threads cannot utilize multiprocessor systems by splitting threads on different processors or cores
       ISRO DEC 2017 22- Soon
Question 340 Explanation: 
All are true except “Kernel level threads shares the code segment.”
Question 341
Which one of the following are essential features of object oriented language?
  1. Abstraction and encapsulation
  2. Strictly-typed
  3. Type-safe property coupled with sub-type rule
  4. Polymorphism in the presence of inheritance
A
A and B only
B
A, D and B only
C
A and D only
D
A, C and D only
       ISRO DEC 2017 22- Soon
Question 341 Explanation: 

Question 342
Which languages necessarily need heap allocation in the run time environment?
A
Those that support recursion
B
Those that use dynamic scoping
C
Those that use global variables
D
Those that allow dynamic data structures
       ISRO DEC 2017 22- Soon
Question 342 Explanation: 
→ Dynamic memory is allocated on the heap by the system.
→ So the languages which allow dynamic data structure require heap allocation at runtime.
Question 343
Consider the code segment
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
A
The code contains loop invariant computation
B
There is scope of common subexpression elimination in this code
C
There is scope of strength reduction in this code
D
There is scope of dead code elimination in this code
       ISRO DEC 2017 22- Soon
Question 343 Explanation: 
→ 4*j is a common sub-expression. So there is a scope of elimination. So B is correct.
→ 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
Consider the following table

Matching A, B, C, D in the same order gives :
A
p, q, r, s
B
q, r, s, p
C
r, s, q, p
D
r, s, p, q
       ISRO DEC 2017 22- Soon
Question 344 Explanation: 
Activation Records:
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
A counting semaphore was initialised to 7. Then 20 P (wait) operations and x V (signal) operations were completed on this semaphore. If the final value of semaphore is 5, then the value x will be
A
0
B
13
C
18
D
5
       ISRO DEC 2017 22- Soon
Question 345 Explanation: 
Counting semaphore value is 7
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
We consider the addition of two 2’s complement numbers bn-1bn-2…b0 and an-1an-2…a0. A binary adder for adding unsigned binary numbers is used to add the two numbers. The sum is denoted by cn-1cn-2…c0 and the carry-out by cout. Which one of the following options correctly identifies the overflow condition?
A
B
C
D
       ISRO DEC 2017 22- Soon
Question 346 Explanation: 
There is an overflow if
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
Consider the function
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
A
89
B
90
C
91
D
92
       ISRO DEC 2017 22- Soon
Question 347 Explanation: 
Value returned by
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
Consider the function
int func(int num)
{
int count = 0;
while(num)
{
count++;
num >>= 1;
}
return(count) ;
}
For func(435) the value returned is
A
9
B
8
C
0
D
10
       ISRO DEC 2017 22- Soon
Question 348 Explanation: 
func (435)
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
Which of the following set of components is sufficient to implement any arbitrary Boolean function?
a) XOR gates, NOT gates
b) 2 to 1 multiplexers
c) AND gates, XOR gate
d) Three-input gates that output (A.B)+C for the inputs A, B and C.
A
a and d
B
b and c
C
c
D
All a, b, c and d
       ISRO DEC 2017 22- Soon
Question 349 Explanation: 
(A) XOR and NOT gates can only make XOR and XNOR which are not functionally complete.
(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
Consider the following :

Matching A, B, C, D in the same order gives.
A
r, p, s, q
B
p, r, q, s
C
s, r, q, p
D
q, r, s, p
       ISRO DEC 2017 22- Soon
Question 350 Explanation: 
White box testing→ Condition Coverage
Black box testing→ Equivalence Class partitioning
Volume Testing→ Performance testing
Beta Testing→ System testing
Question 351
Consider the results of a medical experiment that aims to predict whether someone is going to develop myopia based on some physical measurements and heredity. In this case, the input dataset consists of the person’s medical characteristics and the target variable is binary: 1 for those who are likely to develop myopia and 0 for those who aren’t. This can be best classified as
A
Regression
B
Decision Tree
C
Clustering
D
Association Rules
       ISRO DEC 2017 22- Soon
Question 351 Explanation: 
Regression: It is a statistical analysis which is used to establish relation between a response and a predictor variable. It is mainly used in finance related applications.
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 non-similar objects to other groups.
Association Rules: It uses if-then reasoning method using the support-confidence 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
Which of the following related to snowflake schema is true?
A
Each dimension is represented by a single dimensional table
B
Maintenance efforts are less
C
Dimension tables are normalised
D
It is not an extension of star schema
       ISRO DEC 2017 22- Soon
Question 352 Explanation: 
→ A snowflake schema is a logical arrangement of tables in a multidimensional database such that the entity relationship diagram resembles a snowflake shape.
→ 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
Which of the following is not true with respect to deadlock prevention and deadlock avoidance schemes?
A
In deadlock prevention, the request for resources is always granted if resulting state is safe
B
In deadlock avoidance, the request for resources is always granted, if the resulting state is safe
C
Deadlock avoidance requires knowledge of resource requirements a priori
D
Deadlock prevention is more restrictive than deadlock avoidance
       ISRO DEC 2017 22- Soon
Question 353 Explanation: 
False: In deadlock prevention, the request for resources is always granted if resulting state is safe
→ 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
Consider a disk sequence with 100 cylinders. The request to access the cylinder occur in the following sequence : 4, 34, 10, 7, 19, 73, 2, 15, 6, 20 Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 2 ms to move from one cylinder to adjacent one and shortest seek time first policy is used?
A
190
B
238
C
233
D
276
       ISRO DEC 2017 22- Soon
Question 354 Explanation: 
The given sequence is
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
Consider the following C function
#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
A
SI
B
IT
C
TI
D
17
       ISRO DEC 2017 22- Soon
Question 355 Explanation: 
String is “ICRBCSIT17” and index numbers starts from 0.

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
If C is a skew-symmetric matrix of order n and X is n * 1 column matrix, then XTCX is a
A
scalar matrix
B
null matrix
C
unit matrix
D
matrix will all elements 1
       ISRO DEC 2017 22- Soon
Question 356 Explanation: 
→ A skew symmetric(or antisymmetric or anti metric) matrix is a square matrix whose transpose equals its negative. It satisfies the condition AT = -A

Question 357
A 32 bit adder is formed by cascading 4 bit CLA adder. The gate delays (latency) for getting the sum bits is
A
16
B
18
C
17
D
19
       ISRO DEC 2017 22- Soon
Question 357 Explanation: 
Block diagram of Carry look-ahead adder(CLA) is shown in below figure. All the data inputs A and B are available and Pi and Gi are computed simultaneously for all the CLAs.

The carry propagates the through the Carry-lookahead generators. Carry-lookahead 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
In IEEE floating point representation, the hexadecimal number 0xC0000000 corresponds to
A
-3.0
B
-1.0
C
-4.0
D
-2.0
       ISRO DEC 2017 22- Soon
Question 358 Explanation: 
Given number 0xC0000000 is in Hexadecimal format.
Question 359
Consider the following table : Faculty (facName, dept, office, rank, dateHired)

(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 Boyce-Codd Normal Form. Then Faculty is
A
Not in 3NF, in BCNF
B
In 3NF, not in BCNF
C
In 3NF, in BCNF
D
Not in 3NF, not in BCNF
       ISRO DEC 2017 22- Soon
Question 359 Explanation: 
Possible FD’S for given instance are:
FacName ➝ dept,office
Question 360
Consider the following query :
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
A
the index is only hash and clustered
B
the index is only B+tree and clustered
C
index can be hash or B+ tree and clustered or non-clustered
D
index can be hash or B+ tree and clustered
       ISRO DEC 2017 22- Soon
Question 361
The IETF standard documents are called:
A
RFC
B
RCF
C
ID
D
none of the above
       Nielit Scientist-B CS 4-12-2016
Question 361 Explanation: 
● The Internet Engineering Task Force (IETF) is an open standards organization, which develops and promotes voluntary Internet standards, in particular the standards that comprise the Internet protocol suite (TCP/IP).
● 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?

A
Lord Dalhousie
B
Warren Hastings
C
Lord Minto
D
Capt. Alexander read
       JT(IT) 2018 PART-A General Aptitude
Question 362 Explanation: 
The Ryotwari system was a land tenure system in British India, introduced by Sir Thomas Munro in 1820 based on system administered by Captain Alexander Read in the Baramahal district. It allowed the government to deal directly with the peasant (ryot) for revenue collection, and gave the peasant freedom to give up or acquire new land for cultivation. The peasant was assessed for only the lands he was cultivating.
Question 363

In which of the following states is the tuluni festival celebrated?

A
Arunachal pradesh
B
Manipur
C
Nagaland
D
Sikkim
       JT(IT) 2018 PART-A General Aptitude
Question 363 Explanation: 
The Tuluni Festival of Nagaland is commended around the second seven day stretch of the long stretch of July.The most noteworthy celebration celebrated by the Sumi Naga clan of Nagaland is the Tuluni Festival. This celebration is commended to cheer the most bounteous and productive period of the year in Nagaland. The Sumi clan in Nagaland praises the Tuluni Festival with magnificence and greatness.
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:

A
protective relay
B
circuit breaker
C
fuse
D
surge protectors
       JT(IT) 2018 PART-A General Aptitude
Question 364 Explanation: 
A fuse is an electrical safety device that operates to provide overcurrent protection of an electrical circuit. Its essential component is a metal wire or strip that melts when too much current flows through it, thereby interrupting the current. It is a sacrificial device; once a fuse has operated it is an open circuit, and it must be replaced or rewired, depending on type.
Question 365

Article 45 of the constitution of india provides provision for early childhood care and education to children below the age of:

A
6 years
B
9 years
C
12 years
D
10 years
       JT(IT) 2018 PART-A General Aptitude
Question 365 Explanation: 
Article 45 shall stand Substituted by Constitution (Eighty Sixth Amendment) Act, 2002, s. 3 (which is yet not in force, date to be notified later on) as --
"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:

A
validation of certain acts and regulations
B
equality of opportunity in matters of public employment
C
freedom to manage religious affairs
D
prohibition of trafficking in human beings
       JT(IT) 2018 PART-A General Aptitude
Question 366 Explanation: 
Freedom to manage religious affairs Subject to public order, morality and health, every religious denomination or any section thereof shall have the right
(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?

A
England
B
West Indies
C
South africa
D
Australia
       JT(IT) 2018 PART-A General Aptitude
Question 367 Explanation: 
England and the West Indies were both contesting the tournament final for a second time, having won one previous tournament each (in 2010 and 2012, respectively). West Indian captain Darren Sammy won the toss and elected to bowl, as he had done throughout the tournament. England posted a total of 155/9 from their 20 overs, with Joe Root top-scoring with 54 runs from 36 balls. For the West Indies, Carlos Brathwaite took 3/23 and Samuel Badree took 2/16, including a maiden. The West Indies subsequently reached their target with just two balls to spare. They required 19 runs from the final over, bowled by Ben Stokes, which Brathwaite reached by hitting four consecutive sixes. Marlon Samuels scored 85 not out from 66 balls – the highest score in World T20 final history – and was named the final Man of the Match for the second time. The match was played to a near-capacity crowd, with 66,000 people in attendance.
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?

A
Telangana
B
Maharashtra
C
Karnataka
D
Gujarat
       JT(IT) 2018 PART-A General Aptitude
Question 368 Explanation: 
India on Thursday signed a $346 million loan agreement with the Asian Development Bank (ADB) to finance improvement of over 400 km of state highways that will enhance connectivity and access to economic centres across 12 districts in Karnataka.
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 (KSHIP-III) 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?

A
Sri lanka
B
India
C
China
D
Bhutan
       JT(IT) 2018 PART-A General Aptitude
Question 369 Explanation: 
Bhutan Mountain Echoes Literary Festival definitely holds an important position among all Bhutan festivals. 2018 ninth edition of the literary festival, and the organiser has already announced the names of guests who are coming in to the festival. The festival is set to be held from August 23 to 25, 2018.
Question 370

______ can produce a virtual image larger than the object

A
Concave lens
B
Concave mirror
C
Convex mirror
D
Plane mirror
       JT(IT) 2018 PART-A General Aptitude
Question 370 Explanation: 
A converging lens (one that is thicker in the middle than at the edges) or a concave mirror is also capable of producing a virtual image if the object is within the focal length. Such an image will be magnified. In contrast, an object placed in front of a converging lens or concave mirror at a position beyond the focal length produces a real image. Such an image may be magnified or reduced depending on the position of the object.
Question 371

From the given options, select the word that can be formed using the letters from the given word

ALTERNATE

A
TAVERN
B
LANTERN
C
TALENT
D
TANNER
       JT(IT) 2018 PART-A General Aptitude
Question 371 Explanation: 
→ TAVERN: Here, V is not present in ALTERNATE.
→ 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

A
Resentful
B
Serene
C
Desolate
D
Sad
       JT(IT) 2018 PART-A General Aptitude
Question 372 Explanation: 
→ Serene synonyms are calm, peaceful and untroubled.
→ 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:?

A
OQSU
B
USPO
C
VSQO
D
USQO
       JT(IT) 2018 PART-A General Aptitude
Question 373 Explanation: 
Question 374

Select the option that is different from the other three options

A
117
B
78
C
60
D
52
       JT(IT) 2018 PART-A General Aptitude
Question 374 Explanation: 
Here, 117 and 78 difference is 13*3
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:

A
car
B
vehicle
C
mechanic
D
accountant
       JT(IT) 2018 PART-A General Aptitude
Question 375 Explanation: 
→ Restaurant is related to chef
→ Garage is related to mechanic
Question 376

Choose the correct options that will complete the given number series:

2, 2, 3, 8, 35, ?, 1421

A
204
B
40
C
408
D
70
       JT(IT) 2018 PART-A General Aptitude
Question 376 Explanation: 
The pattern in the serial is *1 – 1, *2 –2, *3 –3, *4 –4, *5 –5 i.e.,
3 (1st term) * 1 - 1 = 2 (2nd term)
2 (2nd term) * 2 - 2 = 2 (3rd term)
2 (3rd term) * 3 - 3 = 3 (4th 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 brother-in-law of Ruby's friends mother?How is Ruby's friend related to Nisha?

A
Niece
B
Friend
C
Cousin
D
Daughter
       JT(IT) 2018 PART-A General Aptitude
Question 377 Explanation: 
→ Nisha introduced herself as the eldest daughter of the brother-in-law of Ruby's friends mother is nothing but cousin.
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?

A
P
B
O
C
R
D
Q
       JT(IT) 2018 PART-A General Aptitude
Question 378 Explanation: 
Here, Q is already mentioned 2 position in a line.
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?

A
Tuesday
B
Wednesday
C
Friday
D
Monday
       JT(IT) 2018 PART-A General Aptitude
Question 379 Explanation: 
7th day of the month is four days after friday is Tuesday.
14th day- Tuesday
21st day- Tuesday
28th day-Tuesday
29th-wednesday
30th-thursday
31st- friday
Question 380
 
A
14
B
7
C
15
D
13
       JT(IT) 2018 PART-A General Aptitude
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?

A
Loss 8%
B
Gain 8%
C
Loss 5.50%
D
Gain 5.5%
       JT(IT) 2018 PART-A General Aptitude
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?

A
Rs.484
B
Rs.480
C
Rs.410
D
Rs.450
       JT(IT) 2018 PART-A General Aptitude
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:

A
12600
B
6300
C
8400
D
2100
       JT(IT) 2018 PART-A General Aptitude
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?

A
736/7
B
253/7
C
115
D
110
       JT(IT) 2018 PART-A General Aptitude
Question 385
   
A
20
B
1/2
C
2
D
1/20
       JT(IT) 2018 PART-A General Aptitude
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?

A
15
B
21
C
7 1/2
D
10 1/2
       JT(IT) 2018 PART-A General Aptitude
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?

A
65.5
B
64
C
65
D
64.5
       JT(IT) 2018 PART-A General Aptitude
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:

A
96
B
128
C
256
D
192
       JT(IT) 2018 PART-A General Aptitude
Question 389

Select the most appropriate antonym of the given word

AUDACITY
A
boldness
B
courage
C
timidity
D
nerve
       JT(IT) 2018 PART-A General Aptitude
Question 390

Select the wrongly spelt word

A
improbable
B
impudent
C
impression
D
impropreity
       JT(IT) 2018 PART-A General Aptitude
Question 391

Select the option which is NOT an antonym of another word by way of adding the prefix 'in-'.

A
indomitable
B
individualism
C
incompetent
D
incoherent
       JT(IT) 2018 PART-A General Aptitude
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.

A
our
B
their
C
his
D
my
       JT(IT) 2018 PART-A General Aptitude
Question 393

Select the most appropriate option to fill in the blank.

____ their clothes were proper, they didn't look smart.

A
Whether
B
Despite
C
Although
D
Because
       JT(IT) 2018 PART-A General Aptitude
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 "01-JAN-2010".
A
DELETE FROM CLUB WHERE TYPE= "ANNUAL" AND DOJ > = "01-JAN-10";
B
DELETE FROM CLUB WHERE TYPE= "ANNUAL" OR DOJ > "01-JAN-10";
C
DELETE * FROM CLUB WHERE TYPE= "ANNUAL" OR DOJ > "01-JAN-10";
D
DELETE FROM CLUB WHERE TYPE= "ANNUAL" OR DOJ > = "01-JAN-10";
       NVS PGT CS 2017 Part-B
Question 394 Explanation: 
The DELETE statement is used to delete existing records in a table.
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.

A
release of funds
B
to make progress
C
due to
D
is struggling
       JT(IT) 2018 PART-A General Aptitude
Question 396

Select the most appropriate synonym of the given word

STEALTHY
A
direct
B
daring
C
unrestricted
D
sly
       JT(IT) 2018 PART-A General Aptitude
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.

A
had taken
B
was taking
C
takes
D
is taking
       JT(IT) 2018 PART-A General Aptitude
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 :
A
SELECT SUM(MONTIIS_BETWEEN(SYSDATE, DOJ) * FEE)
FROM CLUB WHERE TYPE= "MONTHLY'
B
SELECT SUM(MONTH_BETWEEN (DOI,SYSDATE) * FEE)
FROM CLUB ;WHERE TYPE= "MONTHLY"
C
SELECT SUM(MONTH_BETWEEN (DOJ, SYSDATE) * FEE)
FROM CLUB WHERE TYPE= ''MONTHLY"
D
SELECT MONTHS_BETWEEN(SYSDATE, DOJ) • FEE
FROM CLUB WHERE TYPE= "MONTHLY''
       NVS PGT CS 2017 Part-B
Question 398 Explanation: 
We need to calculate the amount from DOJ to system date in monthly wise.
Question 399

Select the most appropriate option to fill in the blank.

This ward is meant for critically____children.