GATE 1999

Question 1

Suppose that the expectation of a random variable X is 5. Which of the following statements is true?

A
There is a sample point at which X has the value 5.
B
There is a sample point at which X has value greater than 5.
C
There is a sample point at which X has a value greater than or equal to 5.
D
None of the above
       Engineering-Mathematics       Probability
Question 1 Explanation: 
Expectation of discrete random variable
E(X) = x1P1 + x2P2 + ... + xnPn
In question, E(X) is given as 5.
E(X) = 5, 0≤Pi≤1
P1 + P2 + ... + Pn = 1 [Probability]
Therefore, E(X) = 5 is possible only if atleast one of the xi value is greater than 5.
Question 2

The number of binary relations on a set with n elements is:

A
n2
B
2n
C
2n (2)
D
None of the above
       Engineering-Mathematics       Sets-And-Relation
Question 2 Explanation: 
In binary relation two elements are selected from a set. So total no. of pairs possible are
n×n = n2
Now, no. of binary relations possible is
2n2
Because each pair have two possibilities either chosen or not chosen.
Question 3

The  number  of  binary  strings  of  n  zeroes  and  k  ones  that  no  two  ones  are adjacent is

A
n-1Ck
B
nCk
C
nCk+1
D
None of the above
       Engineering-Mathematics       Combinatorics
Question 3 Explanation: 
Since there are n zeroes, so
XOXOXOXOXOXOX
n+1 gaps can be possible, where 1's can be placed so that no two one's are adjacent. So, no. of ways in which k 1's can be placed in n+1 gaps are,
n+1Ck
Question 4

Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state finite  automation  that  recognizes  the  language  represented  by  this  regular expression contains

A
n states
B
n + 1 states
C
n + 2 states
D
None of the above
       Theory-of-Computation       Finite-Automata
Question 4 Explanation: 
Let's draw both NFA and DFA and see which one requires less no. of state.
DFA:

So, DFA requires (n+2) state.
NFA:

So, NFA requires (n+1) state.
So, final answer will be,
min(n+1, n+2)
= n+1
Question 5

Context-free languages are closed under:

A
Union, intersection
B
Union, Kleene closure
C
Intersection, complement
D
Complement, Kleene closure
       Theory-of-Computation       Context-Free-Language
Question 5 Explanation: 
Context free languages are not closed under Intersection and complementation.
By checking the options only option B is correct.
Question 6

Let LD be the set of all languages accepted by a PDA by final state and LE the set of all languages accepted by empty stack. Which of the following is true?

A
LD = LE
B
LD ⊃ LE
C
LE = LD
D
None of the above
       Theory-of-Computation       Push-Down-Automata
Question 6 Explanation: 
For any PDA which can be accepted by final state, there is an equivalent PDA which can also be accepted by an empty stack and for any PDA which can be accepted by an empty stack, there is an equivalent PDA which can be accepted by final state.
Question 7

Which of the following expressions is not equivalent to ?

A
x NAND X
B
x NOR x
C
x NAND 1
D
x NOR 1
       Digital-Logic-Design       Logic-Gates
Question 7 Explanation: 
Question 8

Which of the following functions implements the Karnaugh map shown below?

A
B
C
D
       Digital-Logic-Design       K-Map
Question 8 Explanation: 

⇒ CD+AD = D(A+C)
Question 9

Listed below are some operating system abstractions (in the left column) and the hardware components or mechanism (in the right column) that they are abstractions of. Which of the following matching of pairs is correct?

    A. Thread                      1. Interrupt
    B. Virtual address space       2. Memory
    C. File system                 3. CPU
    D. Signal                      4. Disk 
A
(A) – 2 (B) – 4 (C) – 3 (D) - 1
B
(A) – 1 (B) – 2 (C) – 3 (D) – 4
C
(A) – 3 (B) – 2 (C) – 4 (D) - 1
D
(A) – 4 (B) – 1 (C) – 2 (D) – 3
       Operating-Systems       Match-the-Following
Question 9 Explanation: 

⇒ Threads are handled by CPU.
⇒ Virtual address is a memory type.
⇒ File system is used to manage the disk.
⇒ Interrupt is a signal.
Question 10

Which of the following disk scheduling strategies is likely to give the best through put?

A
Farthest cylinder next
B
Nearest cylinder next
C
First come first served
D
Elevator algorithm
       Operating-Systems       Disk-Scheduling
Question 10 Explanation: 
Farthest cylinder next - Longest job first
Nearest cylinder next - SSTF
First come first served - FCFS
Elevator - SCAN
SSTF always serves the request of nearest cylinder first. Due to which the necessary movement gets reduced.
Question 11

System calls are usually invoked by using

A
a software interrupt
B
polling
C
an indirect jump
D
a privileged instruction
       Operating-Systems       System-Calls
Question 11 Explanation: 
Software interrupts are implementing device drivers (or) transitions between protected mode of operations, such as system calls.
Question 12

A sorting technique is called stable if

A
it takes O (nlog n) time
B
it maintains the relative order of occurrence of non-distinct elements
C
it uses divide and conquer paradigm
D
it takes O(n) space
       Algorithms        Sorting
Question 12 Explanation: 
Sorting techniques are said to be stable if it maintains the relative order of occurrence of non-distinct element.
Question 13

Suppose  we  want  to  arrange  the  n  numbers  stored  in any  array  such  that  all negative  values  occur  before  all  positive  ones. Minimum  number  of  exchanges required in the worst case is

A
n - 1
B
n
C
n + 1
D
None of the above
       Algorithms        Time-Complexity
Question 13 Explanation: 
Minimum no. of exchanges required in worst case will be when 1st half will contain all +ve nos and 2nd half will contain all -ve nos.
Now we will swap 1st no. with nth no. and then 2nd no. with (n-1)th no. and then 3rd no. with (n-2)th and so on. Like this we will have to do n/2 swaps in worst case.
Question 14

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:

   20, 47, 15, 8, 9, 4, 40, 30, 12, 17 

then the order of these elements after second pass of the algorithm is:

A
8, 9, 15, 20, 47, 4, 12, 17, 30, 40
B
8, 15, 20, 47, 4, 9, 30, 40, 12, 17
C
15, 20, 47, 4, 8, 9, 12, 30, 40, 17
D
4, 8, 9, 15, 20, 47, 12, 17, 30, 40
       Algorithms        Sorting
Question 14 Explanation: 
Question 15

The number of articulation points of the following graph is

A
0
B
1
C
2
D
3
       Data-Structures       Graphs
Question 15 Explanation: 
Here, vertex 2, 3, 5 are the articulation points. By removing these vertices then the graph will be disconnected.
Total no. of articulation points = 3
Question 16

If n is a power of 2, then the minimum number of multiplications needed to compute a* is

A
log2 n
B
√n
C
n-1
D
n
       Algorithms        Time-Complexity
Question 16 Explanation: 

We require 4 multiplications to calculate a16 .....(I)
→ Like that 3 multiplications requires to calculate a8 .....(II)
I, II are satisfied with the option A.
Question 17

Which of the following is the most powerful parsing method?

A
LL (1)
B
Canonical LR
C
SLR
D
LALR
       Compiler-Design       Parsers
Question 17 Explanation: 
Canonical LR is most powerful.
LR > LALR > SLR
Question 18

Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the maximum and minimum sizes of the join respectively are

A
m + n and 0
B
mn and 0
C
m + n and |m – n|
D
mn and m + n
       Database-Management-System       Relational-Algebra
Question 18 Explanation: 
For maximum:
Suppose there is no common attribute in R and S due to which natural join will act as cross product. So then in cross product total no. of tuples will be mn.
For minimum:
Suppose there is common attribute in R and S, but none of the row of R matches with rows of S then minimum no. of tuples will be 0.
Question 19

The relational algebra expression equivalent to the following tuple calculus expression:

{t| t ∈ r ∧(t[A] = 10 ∧ t[B] = 20)} is
A
σ(A=10∨B=20) (r)
B
σ(A=10) (r) ∪ σ(B=20) (r)
C
σ(A=10) (r) ∩ σ(B=20) (r)
D
σ(A=10) (r) - σ(B=20) (r)
       Database-Management-System       Relational-Algebra
Question 19 Explanation: 
The given relational algebra expression represents tuples having A=10 and B=20 which is equivalent to
σ(A=10) (r) ∩ σ(B=20) (r)
Question 20

Booth’s coding in 8 bits for the decimal number –57 is

A
0 – 100 + 1000
B
0 – 100 + 100 - 1
C
0 – 1 + 100 – 10 + 1
D
00 – 10 + 100 - 1
       Digital-Logic-Design       Number-Systems
Question 20 Explanation: 
Option-B:
Question 21

The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is

A
On2
B
O(n)
C
O(log n)
D
O(1)
       Digital-Logic-Design       Multiplexer
Question 21 Explanation: 
Total no. of gates being used for 'n' bit multiplication in an array multiplier (n*n) = (2n-1)
Total delay = 1 * 2n - 1 = O(2n - 1) = n
Question 22

The main memory of a computer has 2 cm blocks while the cache has 2c blocks. If the cache uses the set associative mapping scheme with 2 blocks per set, then block k of the main memory maps to the set

A
(k mod m) of the cache
B
(k mod c) of the cache
C
(k mod 2c) of the cache
D
(k mod 2 cm) of the cache
       Computer-Organization       Cache
Question 22 Explanation: 
No. of sets in cache = No. of blocks in cache/No. of blocks per set
= 2c/c
= c
∴ Cache set no. to which block k of main memory maps to
= (Main memory block no.) mod (Total set in cache)
= k mod c
Question 23

The Newton-Raphson method is to be used to find the root of the equation f(x)=0 where xo is the initial approximation and f' is the derivative of f. The  method converges

A
always
B
only if f is a polynomial
C
only if f(x0) < 0
D
None of the above
       Engineering-Mathematics       Newton-Raphson-Method
Question 23 Explanation: 
Note: Out of syllabus.
Question 24

Let R = (A, B, C, D, E, F) be a relation scheme with the following dependencies: C→F, E→A, EC→D, A→B. Which of the following is a key of R?

A
CD
B
EC
C
AE
D
AC
       Database-Management-System       Functional-Dependency
Question 24 Explanation: 
Let's check closure for each option,
A) (CD)+ = cdf
Not a key.
B) (EC)+ = ecdabf
Yes, it is a key.
C) (AE)+ = aeb
Not a key. D) (AC)+ = abcf
Not a key.
Question 25

Which of the following is correct?

A
B-trees are for storing data on disk and B+ trees are for main memory.
B
Range queries are faster on B* trees.
C
B-trees are for primary indexes and B* trees are for secondary indexes.
D
The height of a B* tree is independent of the number of records.
       Database-Management-System       B+-Trees
Question 25 Explanation: 
Range queries are faster on B+ trees.
Question 26

Consider two events E1 and E2 such that probability of E1, Pr[E1]=1/2, probability of E2, Pr[E2]=1/3, and probability of E1 and E2, Pr[E1 and E2]=1/5. Which of the following statement is/are True?

A
Pr[E1 or E2] is 2/3
B
Events E1 and E2 are independent
C
Events E1 and E2 are not independent
D
Pr[E1/E2] = 4/5
       Engineering-Mathematics       Probability
Question 26 Explanation: 
If Events E1 and E2 are independent
then P(E1 and E2) = P(E1) × P(E2)
But in the given equation,
P(E1 and E2) = 1/5
P(E1) × P(E2) = 1/2 × 1/3 = 1/6
So, clearly Events E1 and E2 are not independent.
Question 27

Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the number of ways they can divide the flowers amongst themselves?

A
1638
B
2100
C
2640
D
None of the above
       Engineering-Mathematics       Combinatorics
Question 27 Explanation: 
Formula for distributing n identical objects into r persons is,
n+r-1Cr-1
So for 10 roses,
10+2-1C2-1 = 11C1 = 11
For 15 sunflowers,
15+2-1C2-1 = 16C1 = 16
For 15 daffodils,
15+2-1C2-1 = 16C1 = 16
∴ The final answer is,
11×16×16 = 2816
Question 28

Let L be a set with a relation R which is transitive, anti-symmetric and reflexive and for any two elements a, b ∈ L let the least upper bound lub (a,b) and the greatest lower bound glb (a,b) exist. Which of the following is/are true?

A
L is a poset
B
L is a Boolean algebra
C
-L1 is context free
D
-L2 is regular
E
Both A and C
       Engineering-Mathematics       Sets-And-Relation
Question 28 Explanation: 
Note: Options given are wrong.
Question 29

If L is context free language and L2 is a regular language which of the following is/are false?

A
L1 – L2 is not context free
B
L1 ∩ L2 is context free
C
~L1 is context free
D
~L2 is regular
E
Both A and C
       Theory-of-Computation       Identify-Class-Language
Question 29 Explanation: 
(A) L2 is regular language and regular language is closed under complementation. Hence ~L2 is also regular.
So L1 - L2 = L1 ∩ (~L2)
And CFL is closed under regular intersection.
So, L1 ∩ (~L2) or L1 - L2 is CFL.
So False.
(B) As we said that CFL is closed under regular intersection.
So True.
(C) CFL is not closed under complementation.
Hence False.
(D) Regular language is closed under complementation.
Hence True.
Question 30

Given the programming constructs (i) assignment (ii) for loops where the loop parameter cannot be changed within the loop (iii) if-then-else (iv) forward go to (v) arbitrary go to (vi) non-recursive procedure call (vii) recursive procedure/function call (viii) repeat loop, which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e., halting) function in the same programming language.

A
(ii), (iii), (iv)
B
(v), (vii), (viii)
C
(vi), (vii), (viii)
D
(iii), (vii), (viii)
       Programming       Programming-Constructs
Question 30 Explanation: 
Arbitrary goto, recursive call and repeat loop may enter infinite loop and the program might never terminate.
Question 31

For the schedule given below, which of the following is Correct?

1   Read A
2                               Read B
3   Write A
4                               Read A
5                               Write A
6                               Write B
7   Read B
8   Write B 
A
This schedule is serialized and can occur in a scheme using 2PL protocol
B
This schedule is serializable but cannot occur in a scheme using 2PL protocol
C
This schedule is not serialiable but can occur in a scheme using 2PL protocol
D
This schedule is not seralisable and cannot occur in a scheme using 2PL protocol.
       Database-Management-System       Transactions
Question 31 Explanation: 
Let's draw precedence graph,

Since cycle exist so not conflict serializable.
And we know that if the schedule is not serializable then it is not 2PL.
Hence correct option is (D).
Question 32

not in 2NF
B
in 2NF but not 3NF
C
in 3NF but not in 2NF
D
in both 2NF and 3NF
Question 32 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 33

not in 2NF
B
in 2NF but not 3NF
C
in 3NF but not in 2NF
D
in both 2NF and 3NF
Question 33 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 34

Consider the schema R = (S T U V) and the dependencies S → T, T → U, U → V and V → S. Let R = (R1 and R2) be a decomposition such that R1 ∩ R2 ≠ ∅ . The decomposition is

A
not in 2NF
B
in 2NF but not 3NF
C
in 3NF but not in 2NF
D
in both 2NF and 3NF
       Database-Management-System       Normalization
Question 34 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 35

Consider the circuit shown below. In a certain steady state, the line Y is at '1'. What are the possible values of A, B and C in this state?

A
A = 0, B = 0, C = 1
B
A = 0, B = 1, C = 1
C
A = 1, B = 0, C = 1
D
A = 1, B = 1, C = 1
       Database-Management-System       Logic-Gates
Question 35 Explanation: 

So the above equation is satisfied if either C=0 or A=0 and B=1.
Hence, Option (B) is correct.
Question 36

Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?

A
XOR gates, NOT gates
B
2 to 1 multiplexors
C
AND gates, XOR gates
D
Three-input gates that output (A⋅B) + C for the inputs A⋅B and C
E
Both B and C
       Database-Management-System       Boolean-Functions
Question 36 Explanation: 
(A) Not complete because, XOR can be used to make only NOT gate and NOT gate is already available. Hence not complete.
(B) 2 to 1 multiplexors is functionally complete.
(C) XOR gate can be used to make a NOT gate. So, (AND, NOT) is functionally complete.
(D) With given gates and inputs NOT gate cannot be derived.
Hence, not complete.
Question 37

A  multi-user,  multi-processing  operating  system  cannot  be  implemented  on hardware that does not support

A
Address translation
B
DMA for disk transfer
C
At least two modes of CPU execution (privileged and non-privileged)
D
Demand paging
E
Both A and C
       Operating-Systems       Virtual Memory
Question 37 Explanation: 
Address translation and atleast two modes of CPU execution (Privileged and non-privileged) are needed to implement multiuser and multiprocessing operating system, because address translation provides memory protection which ensures that a given process does not interfere with another, and we need privileged and non-privileged instruction, so that user and OS interconnects properly.
Question 38

Which of the following is/are advantage of virtual memory?

A
Faster access to memory on an average.
B
Processes can be given protected address spaces.
C
Linker can assign addresses independent of where the program will be loaded in physical memory.
D
Programs larger than the physical memory size can be run.
E
Both B and D
       Operating-Systems       Virtual Mem
Question 38 Explanation: 
A) False. Because in virtual memory concept address translation is required due to which access is slow.
B) True. Because in virtual memory concept of address translation provides protected address space so that one process do not interfere the other process.
C) False.
D) True.
Question 39

Which  of  the  following  actions  is/are  typically  not  performed  by  the  operating system when switching context from process A to process B?

A
Saving current register values and restoring saved register values for process B.
B
Changing address translation tables.
C
Swapping out the memory image of process A to the disk.
D
Invalidating the translation look-aside buffer.
       Operating-Systems       Context-Switching
Question 39 Explanation: 
A) True.
B) True.
C) False, because swapping is done when the process is suspended and not during context switching.
D) True, Invalidation of TLB is necessary because, if the TLB is not invalidated then the new process might end up using the translation of old process. Note that Invalidation of TLB is necessary but saving and reuse of TLB is not necessary.
Question 40

Consider the following program in a language that has dynamic seeping.

   var x: real;
   procedure show:
       begin print(x);end;
   procedure small;
       var x: real;
           begin x: = 0.125; show; end;
   begin x:=0.25
       show; small
       end. 

Then the output of the program is:

A
0.125 0.125
B
0.25 0.25
C
0.25 0.125
D
0.125 0.25
       Operating-Systems       Dynamic-Scoping
Question 40 Explanation: 
Note: Out of syllabus.
Question 41

The number of tokens in the Fortran statement DO 10 I = 1.25 is

A
3
B
4
C
5
D
None of the above
       Compiler-Design       Compile
Question 41 Explanation: 
DO → 1
10 → 2
I → 3
= → 4
1.25 → 5
Question 42

A grammar that is both left and right recursive for a non-terminal, is

A
Ambiguous
B
Unambiguous
C
Information is not sufficient to decide whether it is ambiguous or unambiguous
D
None of the above
       Theory-of-Computation       Grammar
Question 42 Explanation: 
If a grammar is both left and right recursion, then grammar may or may not be ambiguous.
Question 43

The number of full and half-adders required to add 16-bit numbers is

A
8 half-adders, 8 full-adders
B
1 half-adder, 15 full-adders
C
16 half-adders, 0 full-adders
D
4 half-adders, 12 full-adders
       Digital-Logic-Design       Adder
Question 43 Explanation: 
For Least Significant Bit we do not need a full adder since initially carry is not present.
But for rest of bits we need full address since carry from previous addition has to be included into the addition operation.
So, in total 1 half adder and 15 full adders are required.
Question 44

Zero has two representations in

A
Sign magnitude
B
1’s complement
C
2’s complement
D
None of the above
E
Both A and B
       Digital-Logic-Design       Number-Systems
Question 44 Explanation: 
Sign magnitude:
+0 = 0000
-0 = 1000
1's complement:
+0 = 0000
-0 = 1111
Question 45

Raid configurations of the disks are used to provide

A
Fault-tolerance
B
High speed
C
High data density
D
None of the above
       Computer-Organization       RAID
Question 45 Explanation: 
Raid is a way of storing the same data in different places on multiple hard disks to protect data in the case of drive failure.
So, we can say that RAID is used to provide fault tolerance.
Question 46

Arrange the following configuration for CPU in decreasing order of operating speeds: Hard wired control, vertical microprogramming, horizontal microprogramming.

A
Hard wired control, vertical micro-programming, horizontal micro- programming.
B
Hard wired control, horizontal micro-programming, vertical micro- programming.
C
Horizontal micro-programming, vertical micro-programming, Hard wired control.
D
Vertical micro-programming, horizontal micro-programming, hard wired control.
       Computer-Organization       Micro-Programming
Question 46 Explanation: 
Hardwired control involves only hardware which is definitely faster than microprogramming approach.
Now between horizontal and vertical microprogramming, the signals in vertical microprogramming are in encoded form which has to be decoded first using decoder. So, horizontal microprogramming is faster than vertical microprogramming.
Question 47

The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:

A
165
B
90
C
75
D
65
       Algorithms        Greedy-Algorithm
Question 47 Explanation: 
Always merge two files with minimum no. of records.
10, 20, 15, 5, 25
Merge 5 & 10:
5+10 = 15 movements
Now the list is
15, 20, 15, 25
Merge 15 & 15:
15+15 = 30 movements
Now the list is
30, 20, 25
Merge 20 & 25:
20+25 = 45 movements
Now the list is
30, 45
Merge 30 & 45:
30+45 = 75 movements
∴ Total no. of movements
= 15+30+45+75
= 165
Question 48

If T1 = O(1), give the correct matching for the following pairs:

   (M) Tn = Tn−1 + n          (U) Tn = O(n)
   (N) Tn = Tn/2 + n          (V) Tn = O(nlogn)
   (O) Tn = Tn/2 + nlogn      (W) T = O(n2)
   (P) Tn = Tn−1 + logn       (X) Tn = O(log2n) 
A
M – W N – V O – U P - X
B
M – W N – U O – X P - V
C
M – V N – W O – X P - U
D
None of the above
       Algorithms        Time-Complexity
Question 48 Explanation: 
(M) T(n) = Sum of first n natural nos. = n(n+1)/2 = O(n2)
(N) Apply Master's theorem
T(n) = θ(n) = O(n)
(O) Apply Master's theorem
T(n) = θ(n logn) = O(n logn)
(P) Here we are adding the log of firstn natural numbers.
So,
Tn = log1 + log2 + log3 + ... + logn
= log (1×2×...n)
= log(n!)
= θ(n logn)
Question 49

The main differences(s) between a CISC and A RISC processor is/are that a RISC processor typically

A
has fewer instructions
B
has fewer addressing modes
C
has more registers
D
is easier to implement using hard-wired control logic
E
All the above
       Computer-Organization       CISC-and-RISC
Question 49 Explanation: 
All are properties of RISC processor.
Question 50

A certain processor supports only the immediate and the direct addressing modes. Which of the following programming language features cannot be implemented on this processor?

A
Pointers
B
Arrays
C
Records
D
Recursive procedures with local variable
E
All the above
       Computer-Organization       Addressing-Modes
Question 50 Explanation: 
A) Cannot be implemented because pointers need indirect addressing mode.
B) Cannot be implemented because arrays need Register indexing.
C) Records also needs pointers which needs indirect addressing modes, so this also cannot be implemented.
D) Recursive procedures needs stack, and so it needs stack pointers which in turn needs indirect addressing. So this also cannot be implemented.
Question 51

Consider the following C function definition.

int Trial (int a, int b, int c)
{
    if ((a >= b) && (c < b) return b;
    else if (a >= b) return Trial(a, c, b);
    else return Trial(b, a, c);
} 

The function Trial:

A
Finds the maximum of a, b, and c
B
Finds the minimum of a, b and c
C
Finds the middle number of a, b, c
D
None of the above
       Programming       C-Programming
Question 51 Explanation: 
Try for (3,2,2), it will go for infinite loop.
Question 52

Which of the following is/are correct?

A
An SQL query automatically eliminates duplicates
B
An SQL query will not work if there are no indexes on the relations
C
SQL permits attribute names to be repeated in the same relation
D
None of the above
       Database-Management-System       SQL
Question 52 Explanation: 
→ SQL won't remove duplicates like relational algebra projection, we have to remove it explicitly by distinct.
→ If there are no indexes on the relation SQL, then also it works.
→ SQL does not permit 2 attributes to have same name in a relation.
Question 53

(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
Question 54

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.
Question 55

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.
Question 56

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

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.
Question 58

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.
Question 59

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.
Question 60

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.
Question 61

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

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

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.
Question 64

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

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.
Question 66

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.
Question 67

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.
Question 68

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.
Question 69

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.
Question 70

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

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.
Question 72

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.
There are 72 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com
error: Content is protected !!