Computer Science Engineering - Online Test
Q1. Consider the directed graph shown in the figure below. There are multiple shortest paths
between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm?
Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly
shorter path to v is discovered.
Answer : Option D
Explaination / Solution:
No Explaination.
Q2. A 5-stage pipelined processor has Instruction Fetch (IF), Instruction Decode (ID),
Operand Fetch (OF), Perform Operation (PO) and Write Operand (WO) stages.
The IF, ID, OF and WO stages take 1 clock cycle each for any instruction. The PO
stage takes 1 clock cycle for ADD and SUB instructions, 3 clock cycles for MUL
instruction, and 6 clock cycles for DIV instruction respectively. Operand
forwarding is used in the pipeline. What is the number of clock cycles needed to
execute the following sequence of instructions?
Answer : Option A
Explaination / Solution:
No Explaination.
Q3. Which one of the following problems is undecidable?
Answer : Option A
Explaination / Solution:
There were algorithms to find the membership of CFG (using CYK algorithm) and finiteness
of CFG (using CNF graph) and emptiness. But there is no algorithm for ambiguity of CFG,
so it is undecidable.
Q4. Consider the following transaction involving two bank account x and y.
read (x) ; x : = x – 50; write (x) ; read (y); y : = y + 50 ; write (y)
The constraint that the sum of the accounts x and y should remain constant is that of
Answer : Option B
Explaination / Solution:
The consistency property ensures that the database remains in a consistent state before the
(start of the transaction and after the transaction is over. Here sum of the accounts x & y
should remain same before & after execution of the given transactions which refers to the
consistency of the sum.
Q5. Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths
submitted at the same time to a computer system. Which one of the following process
scheduling algorithms would minimize the average waiting time in the ready queue?
Answer : Option A
Explaination / Solution:
SRTF is pre emptive SJF which produces less average waiting time.
Q6. A computer network uses polynomials over GF(2) for error checking with 8 bits as
information bits and uses x3 + x + 1 as the generator polynomial to generate the check bits. In
this network, the message 01011011 is transmitted as
Answer : Option C
Explaination / Solution:
Q7. A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort
algorithm. The worst case running time of this computation is
Answer : Option B
Explaination / Solution:
The height of the recursion tree using merge sort is logn and n2
comparisons are done at each
level, where at most n pairs of strings are compared at each level and n comparisons are
required to compare any two strings, So the worst case running time is O(n2 log n)
Q8. 
Here wr is the reverse of the string w. Which of these languages are deterministic Contextfree
languages?
Consider the following languages over the alphabet Σ = {0,1,c}
Answer : Option C
Explaination / Solution:
For the languages L1 and L2 we can have deterministic push down automata, so they are
DCFL’s, but for L3 only non-deterministic PDA possible. So the language L3 is not a
deterministic CFL.
Q9. Consider the following two statements.
S1 : if a candidate is known to be corrupt, then he will not be elected
S2 : if a candidate is kind, he will be elected
Which one of the following statements follows from S1 and S2 per sound interference rules of
logic?
Answer : Option C
Explaination / Solution:
Let P: candidate known to be corrupt
q: candidate will be elected
r: candidate is kind
S1 = p ⟶ ~ q
= q ⟶~p
S2 = r ⟶ q
i.e., If a person is kind, he is not known to be corrupt
Option is C
Q10. A multithreaded program P executes with x number of threads and uses y number of locks for
ensuring mutual exclusion while operating on shared memory locations. All locks in the
program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l
without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes
available. The minimum value of x and the minimum value of y together for which execution
of P can result in a deadlock are:
Answer : Option C
Explaination / Solution:
As per given question, there 'x' number of threads and 'y' number of locks for ensuring mutual exclusion while operating on shared memory locations
Option (A): x=1;y=2
Means that 1 thread and 2 locks clearly showing that no deadlock situation
Option (B): x=2;y=1
Means that 2 threads and 1 lock → No deadlock situation
After usage of lock by 1 thread, it can release that lock and then 2nd thread can be used that lock. So no deadlock
Option(C):x=2;y=2
Means that 2 threads and 2 locks→Deadlock can arise
Both threads can hold 1 lock and can wait for release of another lock
Option(D) x=1; y=1
Means that 1 thread and 1 lock →No deadlock situation
