GATE 1995

Question 1

A single instruction to clear the lower four bits of the accumulator in 8085 assembly language?

A
XRI OFH
B
ANI FOH
C
XRI FOH
D
ANI OFH
       Computer-Organization       Microprocessor
Question 1 Explanation: 
Here, we use the AND as a accumulator with immediate. F leaves the high nibble whatever it is, 0 clears the lower nibble.
→ The XOR's don't reliably clear random bits and ANI OF clears the upper nibble, not the lower nibble.
Question 2

Which of the following statements is true?

A
ROM is a Read/Write memory
B
PC points to the last instruction that was executed
C
Stack works on the principle of LIFO
D
All instructions affect the flags
       Operating-Systems       General
Question 2 Explanation: 
We know that stack works on the principle of LIFO.
Question 3

In a vectored interrupt

A
the branch address is assigned to a fixed location in memory
B
the interrupt source supplies the branch information to the processor through an interrupt vector
C
the branch address is obtained from a register in the processor
D
none of the above
       Computer-Organization       Interrupt
Question 3 Explanation: 
A vectored interrupt is a processing technique in which the interrupting device directs the processor to the appropriate interrupt service routine vector.
Question 4

In the following Pascal program segment, what is the value of X after the execution of the program segment?
X:=-10; Y:=20;
If X > Y then if X < 0 then X:=abs(X) else X:=2*X;

A
10
B
-20
C
-10
D
None
       Programming       PASCAL-Programming
Question 4 Explanation: 
X is remains unchanged. As the if condition is becomes false.
X = -10
Question 5

Merge sort uses

A
Divide and conquer strategy
B
Backtracking approach
C
Heuristic search
D
Greedy approach
       Algorithms       Sorting
Question 5 Explanation: 
Merge sort uses the divide and conquer strategy.
Question 6

The principle of locality justifies the use of

A
interrupts
B
DMA
C
Polling
D
Cache Memory
       Computer-Organization       General
Question 6 Explanation: 
The locality of reference is also known as principle of locality.
→ The things which are used more frequently those are stored in locality of reference.
→ For this purpose we use the cache memory.
Question 7

In a paged segmented scheme of memory management, the segment table itself must have a page table because

A
the segment table is often too large to fit in one page
B
each segment is spread over a number of pages
C
segment tables point to page table and not to the physical locations of the segment
D
the processor’s description base register points to a page table
E
Both A and B
       Operating-Systems       Memory-Management
Question 7 Explanation: 
The segment table is often too large to fit in one page. This is true and the segment table can be divided into pages. Thus page table for each segment table, pages are created.
Segment paging is different from paged segmentation.
Question 8

Which of the following page replacement algorithms suffers from Belady’s anamoly?

A
Optimal replacement
B
LRU
C
FIFO
D
Both (A) and (C)
       Operating-Systems       Page-Replacement-Algorithm
Question 8 Explanation: 
FIFO is suffers from Belady's Anamoly.
Question 9

In some programming languages, an identifier is permitted to be a letter following by any number of letters or digits. If L and D denote the sets of letters and digits respectively, which of the following expressions defines an identifier?

A
(L ∪ D)+
B
L(L ∪ D)*
C
(L⋅D)*
D
L⋅(L⋅D)*
       Theory-of-Computation       Regular-Expressions
Question 9 Explanation: 
Which is to be letter followed by any number of letters (or) digits
L(L ∪ D)*
Question 10

Consider a grammar with the following productions

S → a∝b|b∝c| aB
S → ∝S|b
S → ∝b b|ab
S ∝ → bd b|b 

The above grammar is:

A
Context free
B
Regular
C
Context sensitive
D
LR(k)
       Theory-of-Computation       General
Question 10 Explanation: 
S ∝→ [violates context free]
Because LHS must be single non-terminal symbol.
S ∝→ b [violates CSG]
→ Length of RHS production must be atleast same as that of LHS.
Extra information is added to the state by redefining iteams to include a terminal symbol as second component in this type of grammar.
Ex: [A → αβa]
A → αβ is a production, a is a terminal (or) right end marker $, such an object is called LR(k).
So, answer is (D) i.e., LR(k).
Question 11

What are x and y in the following macro definition?

 macro Add x,y
 Load y
 Mul x
 Store y
 end macro  
A
Variables
B
Identifiers
C
Actual parameters
D
Formal parameters
       Computer-Organization       Microprocessor
Question 11 Explanation: 
Formal arguments (or) formal parameters is a special kind of variables used in subroutine to refer to one of pieces of data provided as input to the subroutine.
Question 12

What is the distance of the following code 000000, 010101, 000111, 011001, 111111?

A
2
B
3
C
4
D
1
       Computer-Networks       Error-Detection
Question 12 Explanation: 
Distance = Minimum hamming distance = 2
010101 ⊕ 011001 = 001100
Question 13

Which of the following strings can definitely be said to be tokens without looking at the next input character while compiling a Pascal program?

 I. begin           II. program           III. <>   
A
I
B
II
C
III
D
All of the above
       Programming       Pascal Programming
Question 13 Explanation: 
Note: Out of syllabus.
Question 14

A linker is given object modules for a set of programs that were compiled separately. What information need to be included in an object module?

A
Object code
B
Relocation bits
C
Names and locations of all external symbols defined in the object module
D
Absolute addresses of internal symbols
       Compiler-Design       Run-Time-Environments
Question 14 Explanation: 
In object module it includes names and locations of all external symbols defined in the object module.
To link to external symbols it must know the location of external symbols.
Question 15

Which scheduling policy is most suitable for a time shared operating system?

A
Shortest Job First
B
Round Robin
C
First Come First Serve
D
Elevator
       Operating-Systems       CPU-Scheduling
Question 15 Explanation: 
In Round robin, we use the time quantum based on this execution can be done. Then it is said to be time shared operating system.
Question 16

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)
Question 16 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 17

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
Question 17 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 18

The probability that a number selected at random between 100 and 999 (both inclusive) will not contain the digit 7 is:

A
16/25
B
(9/10)3
C
27/75
D
18/25
       Engineering-Mathematics       Probability
Question 18 Explanation: 
Question 19

Let R be a symmetric and transitive relation on a set A. Then

A
R is reflexive and hence an equivalence relation
B
R is reflexive and hence a partial order
C
R is reflexive and hence not an equivalence relation
D
None of the above
       Engineering-Mathematics       Relations
Question 19 Explanation: 
If a relation is equivalence then it must be
i) Symmetric
ii) Reflexive
iii) Transitive
If a relation is said to be symmetric and transitive then we can't say the relation is reflexive and equivalence.
Question 20

The number of elements in he power set P (S) of the set S = {(φ), 1, (2, 3)} is:

A
2
B
4
C
8
D
None of the above
       Engineering-Mathematics       Set-Theory
Question 20 Explanation: 
S = {(φ), 1, (2, 3)}
P(S) = {φ, {{φ}}, {1}, {{2, 3}}, {{φ}, 1}, {1, {2, 3}}, {{φ}, 1, {2, 3}}}
In P(S) it contains 8 elements.
Question 21

In the interval [0, π] the equation x = cos x has

A
No solution
B
Exactly one solution
C
Exactly two solutions
D
An infinite number of solutions
       Engineering-Mathematics       Linear-Algebra
Question 21 Explanation: 

x & cos(x) are intersecting at only one point.
Question 22

If at every point of a certain curve, the slope of the tangent equals −2x/y the curve is

A
a straight line
B
a parabola
C
a circle
D
an ellipse
       Engineering-Mathematics       Lines-and-Curves
Question 22 Explanation: 
Note: Out of syllabus.
Question 23

The value of k for which 4x2 - 8xy + ky2 = 0 does not represent a pair of straight lines (both passing through the origin) is:

A
0
B
2
C
9
D
3
       Engineering-Mathematics       Straight-Lines
Question 23 Explanation: 
Note: Out of syllabus.
Question 24

The rank of the following (n + 1)×(n+1) matrix, where a is a real number is

A
1
B
2
C
n
D
Depends on the value of a
       Engineering-Mathematics       Linear-Algebra
Question 24 Explanation: 
Question 25

The minimum number of edges in a connected cyclic graph on n vertices is:

A
n - 1
B
n
C
n + 1
D
None of the above
       Engineering-Mathematics       Graph-Theory
Question 25 Explanation: 
In a normal graph number of edges required for n vertices is n-1, and in cyclic graph it is n.
In cyclic graph:
No. of edges = No. of vertices
⇒ n = n
Question 26

The capacity of a memory unit is defined by the number of words multiplied by the number of bits/word. How many separate address and data lines are needed for a memory of 4K × 16?

A
10 address, 16 data lines
B
11 address, 8 data lines
C
12 address, 16 data lines
D
12 address, 12 data lines
       Computer-Organization       Memory-Management
Question 26 Explanation: 
ROM memory size = 2m × n
m = no. of address lines
n = no. of data lines
Given, 4K × 16 = 212 × 16
Address lines = 12
Data lines = 16
Question 27

Assume that X and Y are non-zero positive integers. What does the following Pascal program segment do?

 while X <>Y do
 if X > Y then
    X := X – Y
 else
    Y := Y – X;
 write(X); 
A
Computes the LCM of two numbers
B
Divides the larger number by the smaller number
C
Computes the GCD of two numbers
D
None of the above
       Programming       PASCAL-Programming
Question 27 Explanation: 
Let X=3 and Y=5
1st pass : X=3 and Y=2
2nd pass : X=1 and Y=2
3rd pass : X=1 and Y=1
Write(X), which writes 1. Which is nothing but GCD of 3 & 5.
Question 28

What is the value of X printed by the following program?

 program COMPUTE (input, output);
    var
                  X:integer;
    procedure FIND (X:real);
                  begin
                  X:=sqrt(X);
                  end;
   begin
                  X:=2
                  Find(X)
                  Writeln(X)
   end 
A
2
B
√2
C
Run time error
D
None of the above
       Programming       Programming
Question 28 Explanation: 
Since nothing is said in question. So we will assume by default call by value.
X in the procedure FIND is a local variable. No change will be reflected in global variable X.
Question 29

What values of A, B, C and D satisfy the following simultaneous Boolean equations?

A
A = 1, B = 0, C = 0, D = 1
B
A = 1, B = 1, C = 0, D = 0
C
A = 1, B = 0, C = 1, D = 1
D
A = 1, B = 0, C = 0, D = 0
       Digital-Logic-Design       Boolean-Algebra
Question 29 Explanation: 
For verification, just put up the values and check for AND, OR operations and their outputs.
Question 30

The sequence …………… is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for …………… unit(s) of time.

A
{3,2,1),1
B
(2,1,3},0
C
{3,2,1),0
D
{1,2,3},5
       Operating-Systems       CPU-Scheduling
Question 30 Explanation: 
Here, in option (B) and (C) they have given CPU idle time is 0 which is not possible as per schedule (B) and (C).
So, (B) and (C) will be eliminated.
Now in (A) and (D):
For r(A),

So, idle time is between 0 to 1 which in case of option (A).
For option(D),

We can see there is no idle time at all, but in option given idle time is 5, which is not matching with our chart. So option (D) is eliminated.
Therefore, the correct sequence is option (A).
Question 31

The address sequence generated by tracing a particular program executing in a pure demand paging system with 100 records per page with 1 free main memory frame is recorded as follows. What is the number of page faults?

 0100, 0200, 0430, 0499, 0510, 0530, 0560, 0120, 0220, 0240, 0260, 0320, 0370 
A
13
B
8
C
7
D
10
       Operating-Systems       Page-Replacement-Algorithm
Question 31 Explanation: 
Page are fitted in frames, so first we need to determine the pages but given request are just the record request in decimal. We can assume that first page to address from 0000 to 0099 and page 2 contains records from 0100 to 0199 and so on (it is given in question that each page contains 100 records) and so on. So page request string is
01, 02, 04, 04, 05, 05, 05, 01, 02, 02, 02, 03, 03.
Clearly 7 page faults.
Question 32

If the cube roots of unity are 1, ω and ω2, then the roots of the following equation are (x - 1)3 + 8 = 0

A
-1, 1 + 2ω, 1 + 2ω2
B
1, 1 - 2ω, 1 - 2ω2
C
-1, 1 - 2ω, 1 - 2ω2
D
-1, 1 + 2ω, -1 + 2ω2
       Engineering-Mathematics       Partial-Orders
Question 32 Explanation: 
Just put values of (C) in place of x. It will satisfy the equation.
Question 33

A language with string manipulation facilities uses the following operations

 head(s): first character of a string
 tail(s): all but the first character of a string
 concat(s1,s2):s1 s2
 for the string acbc what will be the output of
 concat(head(s), head(tail(tail(s)))) 
A
ac
B
bc
C
ab
D
cc
       Engineering-Mathematics       Prepositional-Logic
Question 33 Explanation: 
concat (a, head (tail (tail (acbc))))
concat (a, head (tail (cbc)))
concat (a, head (bc))
concat (a, b)
ab
Question 34

A shift reduce parser carries out the actions specified within braces immediately after reducing with the corresponding rule of grammar

S → xxW {print "1"}
S → y {print "2"}
W → Sz {print "3"} 

What is the translation of xxxxyzz using the syntax directed translation scheme described by the above rules?

A
23131
B
11233
C
11231
D
33211
       Compiler-Design       Parsers
Question 34 Explanation: 

⇒ 23131
Note SR is bottom up parser.
Question 35

A variant record in Pascal is defined by

                    type varirec      =   record
                                          number : integer;
                                          case (var1,var2) of
                                          var1: (x,y : integer);
                                          var2: (p.q.: real)
                        end
                    end   

Suppose an array of 100 records was declared on a machine which uses 4 bytes for an integer and 8 bytes for a real. How much space would the compiler have to reserve for the array?

A
2800
B
2400
C
2000
D
1200
       Programming       PASCAL-Programming
Question 35 Explanation: 
Note: Out of syllabus.
Question 36

The number of 1’s in the binary representation of
(3*4096 + 15*256 + 5*16 + 3) are:

A
8
B
8
C
10
D
12
       Digital-Logic-Design       Number-Systems
Question 36 Explanation: 
3 × 4096 = 3 × 212
= (11000000000000)2
15 × 256 = 15 × 28
= (111100000000)2
5 × 16 = 5 × 24
= (1010000)2
3 = (11)2
Hence, all binary numbers,

∴ 101's
Question 37

A unit vector perpendicular to both the vectors a = 2i - 2j + k and b = 1 + j - 2k is:

A
1/√3 (1+j+k)
B
1/3 (1+j-k)
C
1/3 (1-j-k)
D
1/√3 (1+j-k)
E
None of the above.
       Engineering-Mathematics       Vector Algebra
Question 37 Explanation: 
Dot product of two perpendicular vectors must be zero.
Question 38

A bag contains 10 white balls and 15 black balls. Two balls are drawn in succession. The probability that one of them is black and the other is white is:

A
2/3
B
4/5
C
1/2
D
2/1
       Engineering-Mathematics       Probability
Question 38 Explanation: 
Probability of first ball white and second one black is,

Probability of first ball black and second one white is,
Question 39

The iteration formula to find the square root of a positive real number b using the Newton Raphson method is

A
B
C
D
None of the above
       Engineering-Mathematics       Newton-Raphson-Method
Question 39 Explanation: 
Note: Out of syllabus.
Question 40

In a virtual memory system the address space specified by the address lines of the CUP must be __________ than the physical memory size and _______ than the secondary storage size.

A
smaller, smaller
B
smaller, larger
C
larger, smaller
D
larger, larger
       Operating-Systems       Virtual Memory
Question 40 Explanation: 
Primary memory < Virtual memory < Secondary memory.
Question 41

Let A be the set of all non-singular matrices over real number and let* be the matrix multiplication operation. Then

A
A is closed under* but < A, *> is not a semigroup
B
is a semigroup but not a monoid
C
is a monoid but not a group
D
is a group but not an abelian group
       Engineering-Mathematics       Linear-Algebra
Question 41 Explanation: 
As the matrices are non-singular so their determinant ±0. Hence, the inverse matrix always exist. But for a group to be Abelian it should follow commutative property. As matrix multiplication is not commutative, is a group but not an abelian group.
Question 42

The solution of differential equation y'' + 3y' + 2y = 0 is of the form

A
C1ex + C2e2x
B
C1e-x + C2e3x
C
C1e-x + C2e-2x
D
C1e-2x + C22-x
       Engineering-Mathematics       Calculus
Question 42 Explanation: 
Note: Out of syllabus.
Question 43

If the proposition ¬p ⇒ ν is true, then the truth value of the proposition ¬p ∨ (p ⇒ q), where ¬ is negation, ‘∨’ is inclusive or and ⇒ is implication, is

A
true
B
multiple valued
C
false
D
cannot be determined
       Engineering-Mathematics       Prepositional-Logic
Question 43 Explanation: 
From the axiom ¬p → q, we can conclude that p ∨ q.
So, either p or q must be True.
Now,
¬p ∨ (p → q)
= ¬p ∨ (¬p ∨ q)
= ¬p ∨ q
Since nothing c an be said about the truth values of p, it implies that ¬p ∨ q can also be True or False. Hence, the value cannot be determined.
Question 44

Which of the following definitions below generates the same language as L, where L = {xnyn such that n >= 1}?

 I. E → xEy|xy
 II. xy|(x+xyy+)
 III. x+y+ 
A
I only
B
I and II
C
II and III
D
II only
       Theory-of-Computation       Regular Languages
Question 44 Explanation: 
(I) is the correct definition and the other two is wrong because the other two can have any no. of x and y. There is no such restriction over the number of both being equal.
Question 45

The postfix expression for the infix expression
A + B*(C + D)/F + D*E is:

A
AB + CD + *F/D + E*
B
ABCD + *F/DE*++
C
A *B + CD/F *DE++
D
A + *BCD/F* DE++
E
None of the above
       Algorithms       Post-fix-and-Prefix
Question 45 Explanation: 
The postfix expression will be,
A B C D + * F / + D E * +
Question 46

Which of the following statements is true?

    I. As the number of entries in a hash table increases, the number of collisions increases.
    II. Recursive programs are efficient
    III. The worst case complexity for Quicksort is O(n2)
A
I and II
B
II and III
C
I and IV
D
I and III
       Algorithms       General
Question 46 Explanation: 
Binary search using linked list is not efficient as it will not give O(log n), because we will not be able to find the mid in constant time. Finding mid in linked list takes O(n) time.
Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind iterative one in terms of performance.
Question 47

A finite state machine with the following state table has a single input x and a single out z.

If the initial state is unknown, then the shortest input sequence to reach the final state C is:

A
01
B
10
C
101
D
110
       Theory-of-Computation       Finite-State-Machine
Question 47 Explanation: 

If A is the start state, shortest sequence is 10 'or' 00 to reach C.
If B is the start state, shortest sequence is 0 to reach C.
If C is the start state, shortest sequence is 10 or 00 to reach C.
If D is the start state, shortest sequence is 0 to reach C.
∴ (B) is correct.
Question 48

Let Σ = {0,1}, L = Σ* and R = {0n1n such that n >0} then the languages L ∪ R and R are respectively

A
regular, regular
B
not regular, regular
C
regular, not regular
D
not regular, no regular
       Theory-of-Computation       regular Languages
Question 48 Explanation: 
L∪R is nothing but L itself. Because R is subset of L and hence regular. R is deterministic context free but not regular as we require a stack to keep the count of 0's to make that of 1's.
Question 49

A computer system has a 4K word cache organized in block-set-associative manner with 4 blocks per set, 64 words per block. The number of its in the SET and WORD fields of the main memory address format is:

A
15, 40
B
6, 4
C
7, 2
D
4, 6
       Computer-Organization       Cache
Question 49 Explanation: 
No. of sets = 4K/ (64×4) = 212/ 28 = 24
So we need 4 set bits.
And,
64 words per block means WORD bit is 6-bits.
So, answer is option (D).
Question 50

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

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

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

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

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

A
Theory Explanation.
Question 55

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A
Theory Explanation.
Question 70

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

A
Theory Explanation.
Question 71

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

A
Theory Explanation.
Question 72

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

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

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

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
There are 75 questions to complete.