computer science paper

Discussion in 'Computer Science and IT Students' started by GATE, May 19, 2006.

  1. GATE

    GATE Guest

    Which of the following is an example of spooled device?

    (a) A line printer used to print the output of a number of jobs.

    (b) A terminal used to enter input data to a running program.

    (c) A secondary storage device in a virtual memory sytem.

    (d) A graphic display device.


    * A ROM is sued to store the table for multiplication of two
    8-bit unsigned integers. The size of ROM required is

    (a) 256 ´ 16 (b) 64 K ´ 8 (c) 4 K ´ 16 (d) 64 K ´ 16

    * A critical section is a program segment

    (a) which should run in a certain specified amount of time

    (b) which avoids deadlocks

    (c) where shared resources are accessed

    (d) which must be enclosed by a pair of semaphore operations, P and V


    * Which two of the following four regular expressions are
    equivalent? (e is the empty string).

    (i) (00) * (e + 0)

    (ii) (00)*

    (iii) 0*

    (iv) 0(00)*

    (a) (i) and (ii) (b) (ii) and (iii) (c) (i) and (iii) (d) (iii) and
    (iv)


    * Which of the following statements is false?

    (a) The Halting problem of Turing machines is undecidable.

    (b) Determining whether a context-free grammar is ambiguous is
    undecidbale.

    (c) Given two arbitrary context-free grammars G1 and G2
    it is undecidable whether L(G1) = L(G2).
    (d) Given two regular grammars G1 and G2 it is undecidable
    whether L(G1) = L(G2).


    * Let L Í S* where S = {a, b}. which of the following is true?

    (a)
    (b)
    (c)
    (d)

    L = {x x has an equal number of a's and b' }s is regular

    L = { na bn n ³ }1 is regular

    L = {x x has more a's and b' }s is regular

    L = { ma bn m ,³ n ³ }1 is regular


    * Which of the following is false?

    (a)

    ≈ ’
    100n log = n log n
    « ◊

    log n = 0 (log log n)
    ∆ 100 ÷
    (b)

    (c)

    If 0 < x < y then nx

    = 0 (n )y

    (d)

    2n ¹ 0 (n )k

    * Consider the following statements:

    (i) First-in-first out types of computations are efficiently supported by
    STACKS.

    (ii) Implementing LISTS on linked lists is more efficient than
    implementing LISTS
    on an array for almost all the basic LIST operations.
    (iii) Implementing QUEUES on a circular array is more efficient than
    implementing QUEUES on a linear array with two indices.

    (iv) Last-in-first-out type of computations are efficiently supported by
    QUEUES.

    (a) (ii) and (iii) are true (b) (i) and (ii) are true

    (c) (iii) and (iv) are true (d) (ii) and (iv) are true


    * Two dice are thrown simultaneously. The probability that at least one
    of them will have 6 facing up is

    (a) 1
    36

    (b) 1
    3

    (c) 25
    36

    (d) 11
    36


    * The formula used to compute an approximation for the second
    derivative of a function f at a point X0 is.

    (a) (f 0x

    (c) (f 0x

    + h) + (f 0x
    2

    + h) + 2 (f 0x
    2h

    - h)


    ) + (f 0x




    - h)

    (b) (f 0x

    (d) (f 0x

    + h) - (f 0x
    2h

    + h) - 2 (f 0x
    2h

    - h)


    ) + (f 0x




    - h)

    * Let Ax = b be a system of linear equations where A is an
    m ´ n matrix and b is a m ´ 1 column vector and X is a n ´ 1
    column vector of unknows. Which of the following is false?

    (a) The system has a solution if and only if, both A and the augmented
    matrix [A
    b] have the same rank.
    (b) If m < n and b is the zero vector, then the system has
    infinitely many solutions.

    (c) If m = n and b is non-zero vector, then the system has a unique
    solution.
    (d) The system will have only a trivial solution when m = n,
    b is the zero vector and rank (A) = n.


    *
    An advantage of chained hash table (external hashing) over
    the open addressing scheme is

    (a) Worst case complexity of search operations is less?

    (b) Space used is less (c) Deletion is easier

    (d) None of the above



    *
    The pass numbers for each of the following activities
    (i) object code generation
    (ii) literals added to literal table
    (iii) listing printed
    (iv) address resolution of local symbols that occur in a
    two pass assembler respectively are

    (a) 1, 2, 1, 2 (b) 2, 1, 2, 1 (c) 2, 1, 1, 2 (d) 1, 2, 2, 2





    READY


    (a) a batch operating system

    BLOCKED

    (b) an operating system with a preemptive scheduler

    (c) an operating system with a non-preemptive scheduler

    (d) a uni-programmed operating system.


    * Let A and B be sets and let cA


    and cB denote the complements of the sets A and
    B. the set (a œ b) È(b-a) È(aÇb) is equal to.

    (a) A È B (b) cA È cB

    (c) A Ç B (d) cA Ç cB


    *
    Let X = {2,3,6,12,24}, Let £ be the partial order defined by
    X £ Y if x divides y. Number of edge as in the Hasse diagram of
    (X,£) is

    (a) 3 (b) 4

    (c) 9 (d) None of the above


    * Suppose X and Y are sets and


    X and


    Y are their respective cardinalities. It is
    given that there are exactly 97 functions from X to Y. from
    this one can conclude that

    (a)

    X = 1, Y = 97

    (b)

    X = 97, Y = 1

    (c)

    X = 97, Y = 97

    (d) None of the above



    * Which of the following statements is false?

    (a) The set of rational numbers is an abelian group under addition.

    (b) The set of integers in an abelian group under addition.

    (c) The set of rational numbers form an abelian group under
    multiplication.
    (d) The set of real numbers excluding zero in an abelian group under
    multiplication.

    * Number of machine cycles required for RET instruction in 8085
    microprocessor is

    (a) 1 (b) 2 (c) 3 (d) 5

    1.14 In the balanced binary tree in Fig.1.14 given below, how many nodes
    will become unbalanced when a node is inserted as a child of the node —g“?


    a

    b e
    c d f
    g


    (a) 1 (b) 3 (c) 7 (d) 8


    * Which of the following sequences denotes the post order
    traversal sequence of the tree of question 1.14?

    (a) f e g c d b a (b) g c b d a f e (c) g c d b f e a (d) f e d g c b
    a


    1.16 Relative mode of addressing is most relevant to writing

    (a) coroutines (b) position œ independent code

    (c) shareable code (d) interrupt handlers


    *
    Both‘s algorithm for integer multiplication gives worst
    performance when the multiplier pattern is

    (a) 101010 …..1010 (b) 100000 …..0001

    (c) 111111 …..1111 (d) 011111 …..1110

    2. Write in your answer book the correct or the most appropriate
    answer to the following multiple choice questions by writing the
    corresponding letter a, b, c or d against the sub-question number.

    * Which of the following is false? Read Ù as AND, Ú as OR, ~ as NOT, ‰
    as one way implication and « as two way implication.

    (a)

    (c)

    (( x ® )y Ù x ) ® y

    ( x ® ( x Ú y ))

    (b)

    (d)

    ((- x ® )y Ù (- x Ù - )y ) ® x

    (( x Ú )y « (- x ®- )y )



    * Let R denotes the set of real numbers. Let f:R´R ‰ R´R be
    a bijective function defined by f(x,y)=(x+y,x-y). the inverse function of
    f is given by

    (a)

    -1f

    ≈ ’
    ( x, )y = 1 1,
    ∆ ÷
    « x + y x - y ◊
    (b)
    -1f
    ( x, )y = ( x - ,y x + )y


    (c)

    -f 1 (


    x y =, ) x

    + y x - y ’
    ,

    1f -

    x, y = 2»


    x - y , 2

    x + y ÿ⁄
    ∆ 2 2 ÷
    (d) ( ) ( ) ( )
    « ◊


    * Let R be a non-empty relation on a collection of sets
    defined by A R B if and only if A Ç B = f. Then, (pick the true
    statement)

    (a) R is reflexive and transitive

    (b) R is symmetric and not transitive

    (c) R is an equivalence relation

    (d) R is not reflexive and not symmetric

    * For the daisy chain scheme of connecting I/O devices, which
    of the following statements is true?

    (a) It gives non-uniform priority to various devices.

    (b) It gives uniform priority to all devices.

    (c) It is only useful for connecting slow devices to a processor device.

    (d) It requires a separate interrupt pin on the processor for each
    device.


    * Consider the following floating-point number representation.


    31 24 23 0


    Exponent Mantissa

    The exponent is in 2‘s complement representation and mantissa is
    in the sign magnitude representation. The range of the
    magnitude of the normalized numbers in this representation is

    (a) 0 to 1 (b) 0.5 to 1

    (c)

    2-23

    to 0.5

    (d)

    0.5 to (1- -2 23 )



    * The probability that top and bottom cards of a randomly shuffled deck
    are both aces in

    (a) 4 ´ 4

    (b) 4 ´ 3

    (c) 4 ´ 3

    (d) 4 ´ 4
    52 52
    52 52
    52 51
    52 51


    * If L1 and L2 are context free languages and R a regular
    set, one of the languages below is not necessarily a context free
    language. Which one?

    (a) L1, L2 (b) L1 Ç L2 (c) L1 Ç R (d) L1 È L2

    *
    Which one of the following is false?
    (a) The set of all bijective functions on a finite set forms a
    group under function composition.
    (b) The set {1,2, ……., p œ1} forms a group under multiplication
    mod p where p is a prime number.
    (c) The set of all strings over a finite alphabet forms a group under
    concatenation.

    (d) A subset s ¹ f of G is a subgroup of the group <G, *>
    if and only if for any pair of elements a, b Î s, a* b-1 Î s.


    * Newton-Raphson iteration formula for finding 3


    c , where c > 0 is,


    (a)


    xn +1

    3x c
    = 2 n + 3
    3 2


    (b)

    32x c
    = n - 3
    xn +1 2
    nx 3xn

    2 3 3
    =x xn + c
    (d) x
    2x c
    = n -
    (c)
    n +1 2x3 n
    n +1 23x
    n


    »
    * The matrices q -


    q ÿ » ÿ
    and
    cos sin a 0
    … Ÿ … Ÿ commute under multiplication
    sinq
    cos q 0 b
    ⁄ ⁄


    (a) if a = b or q = np, is an integer (b) always

    (c) never (d) if a cos q ¹ b sin q



    * The minimum number of interchanges needed to convert the array

    89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70

    (a) 0 (b) 1 (c) 2 (d) 3

    * A binary search tree is generated by inserting in order the following
    integers:

    50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
    The number of nodes in the left subtree and right subtree of the root
    respectively is

    (a) (4, 7) (b) (7, 4) (c) (8, 3) (d) (3, 8)


    * Define a context free languages L £ {0,1} init (L) = {u/uv
    Î L for some n in
    {{0,1}} (in other words, init(L) is the set of prefixes of L)

    Let L {w/w is nonempty and has on equal number of 0‘s and 1‘s

    Then init (L) is

    (a) the set of all binary strings with unequal number of 0‘s and 1‘s

    (b) the set of all binary strings including the null string
    (c) the set of all binary strings with exactly one more 0‘s
    than the number of 1‘s or one more 1 than the number of 0‘s.

    (d) None of the above


    2.10. The grammar whose productions are
    ‰ if id then <stmt>
    ‰ if id then <stmt> else <stmt>
    ‰ id:=id

    is ambiguous because

    (a) the sentence

    if a then if b then c:=d
    (b) the left most and right most derivations of the sentence if a then if
    b then c:=d

    give rise top different parse trees

    (c) the sentence
    if a then if b then c:=d else c:=f has more than two parse trees

    (d) the sentence
    if a then if then c:=d else c:=f has two parse trees


    * The correct matching for the following pairs is


    (A) Activation record (1) Linking loader

    (B) Location counter (2) Garbage collection

    (C) Reference counts (3) Subroutine call

    (D) Address relocation (4) Assembler


    (a) A œ 3 B œ 4 C œ 1 D - 2 (b) A œ 4 B œ 3 C œ 1 D - 2

    (c) A œ 4 B œ 3 C œ 2 D - 1 (d) A œ 3 B œ 4 C œ 2 D - 1



    2.12. The recurrence relation

    T(1) = 2

    ≈ ’
    T(n) = 3T n + n
    ∆ ÷
    4« ◊

    Has the solution T(n) equal to

    (a) O(n) (b) O (log n)

    ≈ 3 ’
    (c) O n∆ 4 ÷
    ÷∆ (d) None of the above
    ◊«
    * The average number of key comparisons done on a successful
    sequential search in list of length n is

    (a) log n (b)

    n - 1
    2

    (c)

    n (d)
    2

    n + 1
    2



    * Quick-sort is run on two inputs shown below to sort in ascending
    order

    (i) 1,2,3 ….n

    (ii) n, n œ 1, n œ 2, …. 2, 1

    Let C1 and C2 be the number of comparisons made for the
    inputs (i) and (ii)
    respectively. Then,

    (a) C1 < C2 (b) C1 > C2 (c) C1 = C2

    (d) we cannot say anything for arbitrary n.


    * Which of the following macros can put a macro assembler into an
    infinite loop?

    (i) MACRO M1, X
    IF EQ, X: if X=0 then …. M1 X + 1

    ENDC

    IF NE, X: if X ¹ O then ……

    WORD X: address (X) is stored here
    ENDC ENDM
    (ii) MACRO M2,X IF EQ, X
    M2 X ENDC
    IF NE, X WORD X + 1
    ENDC ENDM

    (a) (ii) only (b) (i) only

    (c) both (i) and (ii) (d) None of the above



    * A solution to the Dining Philosophers Problem which avoids deadlock
    is

    (a) ensure that all philosophers pick up the left fork before the right
    fork

    (b) ensure that all philosophers pick up the right fork before the left
    fork
    (c) ensure that one particular philosopher picks up the left
    fork before the right fork, and that all other philosophers pick up the
    right fork before the left fork

    (d) None of the above

    * A 1000 Kbyte memory is managed using variable partitions but
    to compaction. It currently has two partitions of sizes 200 Kbytes
    and 260 Kbytes respectively. The smallest allocation request in Kbytes that
    could be denied is for

    (a) 151 (b) 181 (c) 231 (d) 541


    * Consider the following state table in Fig.2.23 for a
    sequential machine. The number of states in the minimized machine will
    be
    input
    x
    Present 0 1
    state
    A D0 B1

    B A0 C1

    C A0 B1

    D A1 C1

    (a) 4 (b) 3 (c) 2 (d) 1



    * A micro program control unit is required to generate a
    total of 25 control signals. Assume that during any
    microinstruction, at most two control signals are active. Minimum
    number of bits required in the control word to generate the
    required control signals will be

    (a) 2 (b) 2.5 (c) 10 (d) 12


    * Four jobs to be executed on a single processor system
    arrive at time 0+ in the order A, B, C, D. their burst CPU
    time requirements are 4, 1, 8, 1 time units respectively. The
    completion time of A under round robin scheduling with time slice
    of one time unit is

    (a) 10 (b) 4 (c) 8 (d) 9


    * Consider the circuit in Fig.2.21 which has a four fit
    binary number 3b 2b 1b 0b as
    input and a five bit binary number, 4d 3d 2d 1d 0d as output.
    ”f‘
    b3 b2 b1 b0
    (a) Binary of Hex conversion

    (b) Binary to BCD conversion

    (c) Binary to grey code conversion

    (d) Binary to radix-12 conversion.

    C out
    C in
    ”f‘
    Binary adder
    4dd3d2d1 d0

    * What is the equivalent Boolean expression in
    product-of-sums form for the
    Karnaugh map given in Fig.2.24.

    (a) BD + BD
    BA
    00 01 11 20
    CD

    (b) (B + C + )D (B + C + )D

    (c) (B + )D (B + )D

    (d) (B + )D (B + )D
    00 1 1


    10 1 1


    11 1 1


    01 1 1


    2.22. Consider the circuit in Fig.2.22 f implements

    0C

    1C Multiplex f
    2C
    3C



    A B

    (a) A BC + ABC + ABC

    (c) A Å B Å C

    (b) A + B + C

    (d) AB+BC+CA








    3. Let f be a function defined by

    x2

    (f x ) = ax2 + bx + c
    x + d



    for x £ 1 for 1 x £ 2 for x > 2
    Find the values for the constants a; b; c and d so that f
    is continuous and differentiable everywhere on the real line.




    * Let Q = (q1, q2) (a,b), (a, b, Z) d, qi, Z, f) be a
    pushdown automaton accepting by empty stack for the language
    which is the set of all nonempty even palindromes over
    the set {a,b}. Below is an incomplete specification of
    the transition d. complete the specification. The top of stack is
    assumed to be at the right end of the string representing stack
    contents.

    (1)

    d ( 1q , ,a )Z

    = ({ 1q , Za)}

    (2)

    d ( 1q , ,b

    Z ) = ({ 1q , Zb)}

    (3)

    (4)

    (5)

    (6)

    d ( 1q , ,a a) = {>> ,> }>

    d ( 1q , ,b b) = {>> ,> }>

    d ( 2q , ,a a) = ({ 2q , e )}

    d ( 2q , ,b b) = ({ 2q , e )}

    (7)

    d ( 2q , e , )Z

    = ({ 2q , e )}







    * 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 list, whose current status (page
    numbers in decimal) is

    17 1 63



    LRU page

    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.


    * The Fibonacci sequence { 1f 2, f 3, f > n }f


    is defined by the following recurrence:

    nf + 2 = nf +1 + n ,f n ³ 1; 2f = 1 1: f = 1 :

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


    » ÿ » ÿ
    10. Let A = 1a 1 1a 2 and B = 1b 1 1b 2
    … Ÿ … Ÿ be two matrices such that
    2a 1 2a 2 ⁄ 2b 1 2b 2 ⁄

    »1 0ÿ
    AB = I. Let C = A … Ÿ and CD = 1. Express the elements of D
    in terms of the

    elements of B.
    1 1⁄

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



    C1 C2 F

    0 0 A + B

    0 1 A + B

    1 0 A Å B

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



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



    C1 C2 F

    0 0 A + B

    0 1 A + B

    1 0 A Å B

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



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

    (a) Find the number of equivalence classes defined by ~

    (b) Find the number of elements in each equivalence class.



    * 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|e
    B ‰ bB ‰ e
    C ‰ d


    (e denoted the null string). Transform the grammar G to an
    equivalent context- free grammar G that has no e productions and
    no unit productions. ( A unit production is of the form x ‰ y, and y
    are non terminals).



    * A two dimensional array A[1- n] [1 œ n] of integers is partially sorted
    if

    " ,i je 1»

    - n - 1ÿ⁄

    A i» ÿ⁄ j» ÿ⁄ < A i» ÿ⁄ j»

    + 1ÿ⁄

    and

    A i» ÿ⁄ j» ÿ⁄ <

    Fill in the blanks:

    i» + 1ÿ⁄ j» ⁄ ÿ⁄

    (a) The smallest item in the array is at A [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 j ¢ j:integer; begin

    (1) i: =1; j:=A [j]:=x;

    (2) while (x > or x >) do

    (3) if A[ i + 1] [j] Ç ]j] then begin

    (4) A [j]:= A[i +1] [j]; i: =i + 1

    (5) end

    (6) else begin

    (7)

    (8) end

    (9) A [j]:=

    end




    * Let G be the directed, weighted graph shown below in Fig.4

    B
    14
    6 12
    22
    9f
    A C
    2 12

    6f


    D E
    5f

    51
    f7 1f
    F

    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 file system with a one-level directory structure is
    implemented on a disk with disk block size of 4 K 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?


    * Consider the following program that attempts to locate an
    element x in an 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;=n;

    repeat k:(i+j) div 2;
    if a [k] < x then i:=k else j:=k
    until (a⁄ =x) or (iÇ=j);

    if (a [k] = x) then

    writeln (”x is not in the array‘)

    else

    writeln (”x‘ is not in the array‘)

    end;

    * A computer system has a three level memory hierarchy, with
    access time and hit ratios as shown below:


    Level 1 (Cache memory) Level 2 (main memory) Level 3

    Access time = 50 nsec/byte Access time = 200 nsec/byte Access time = 5
    µsec/byte

    Size Hit ratio Size Hit ratio Size Hit ratio

    8 M byte 0.80 4M byte 0.98

    16 M byte 0.90 16 M byte 0.99

    260 Mbyte 1.0


    64 M byte 0.95 64 M byte 0.995



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


    * Consider the syntax-directed translation schema (SETS) 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 SDTS given above.


    * The concurrent programming constructs fork and join are as below:

    fork <label> which creates a new process executing from the specified label


    join <variable> which decrements the specified synchronization
    variable (by 1)
    and terminates the process if the new value is not 0.
    Show the precedence graph for S1, S2, S3, S4 and S5 of the
    concurrent program below.

    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 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 lock 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 size 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?


    Level 1 (Cache memory) Level 1 (Cache memory)

    Access time = 50 nsec/byte Access time = 200 nsec/byte

    Size Hit ratio Size Hit ratio

    8 Kbytes 0.80 4 Kbytes 0.98

    16 Kbytes 0.90 16 Kbytes 0.99

    64 Kbytes 0.95 64 Kbytes 0.995


    Size Hit ratio

    250 M bytes 1.0



    * A computer system uses the Banker‘s Algorithm to deal
    with deadlocks. Its current state is shown in the tables below,
    where P0, P1, P2 are processes, and R0, R1, R2 are resoures types.


    Maximum Need Current Allocation Available

    R0 R1 R2 R0 R1 R2 R0 R1 R2

    P0 4 1 2 P0 1 0 2 2 2 0

    P1 1 5 1 P1 0 3 1

    P2 1 2 3 P2 1 0 2


    (a) Show that the system can be in this state.

    (b) What will system do on a request by process P0 for one
    unit of resource type
    R1?



    * 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


    * A library relational database system uses the following schema
    USERS (User #, User Name, Home Town) BOOKS (Books # Book Title, Author
    Name) ISSUED (Book #, User #, Date)
    Explain in one English sentence, what each of the following
    relational algebra queries is designed to determine

    (a) s User #=6 (11 User #, Book Title ((USERS ISSUED) BOOKS))

    (b) s Author Name (BOOKS (s Home Town) = Delhi (USERS ISSUED)))




    * Consider the following program in pseudo-Pascal syntax. What is
    printed by the program if parameter a is 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 test 2;

    begin b: = 10 end

    procedure test 1 (a:integer);

    begin a:5;

    writeln (”point 1: ”a,b);

    test 2;

    wrote;m(”point: ”a,b);

    end;
    begin (*Example*) b:=3; test ] (b); writeln (”point 3: ”b) end


    * 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 funtion

    H(x) = (ord (x) œ ord (”a‘) + 1) mod 10

    And linear probing to resolve collisions.

    (a) Which insertions cause collisions?

    (b) Display the final hash table?


    * 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

Share This Page