Computer Science Engineering - Online Test
Q1. An undirected graph G(V,E) contains n ( n > 2 ) nodes named v1, v2,....vn . Two nodes vi, vj are connected if and only if 0 < |i − j| ≤ 2. Each edge (vi ,vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below
The length of the path from v5 to v6 in the MST of previous question with n = 10
is
Answer : Option C
Explaination / Solution:
12 + 8 + 4 + 3 + 6 + 10 = 31
Q2. Consider the 3 process, P1, P2 and P3 shown in the table
The completion order of the 3 processes under the policies FCFS and RR2 (round robin
scheduling with CPU quantum of 2 time units) are
Answer : Option C
Explaination / Solution:
For FCFS Execution order will be order of Arrival time so it is P1,P2,P3
Next For RR with time quantum=2,the arrangement of Ready Queue will be as follows:
RQ: P1,P2,P1,P3,P2,P1,P3,P2
This RQ itself shows the order of execution on CPU(Using Gantt Chart) and here it gives the
completion order as P1,P3,P2 in Round Robin algorithm.
Q3. For the grammar below, a partial LL(1) parsing table is also presented along with the
grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty
string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The First and Follow sets for the non-terminals A and B are
Answer : Option A
Explaination / Solution:
Q4. Using public key cryptography, X adds a digital signature σ to message M, encrypts , and sends it to Y, where it is decrypted. Which one of the following sequences of keys is
used for the operations?
Answer : Option D
Explaination / Solution:
Encryption: Source has to encrypt with its p r ivate key for formin g Digital signature for Authentication. source has to encrypt the <M, σ > with Y ' s
public key to send it confidentially
Decryption: Destination Y has to decrypt first with its private key, then decrypt using source public key
Q5. A computer uses 46–bit virtual address, 32–bit physical address, and a three–level paged page
table organization. The page table base register stores the base address of the first–level table
(T1) ,which occupies exactly one page. Each entry of T1 stores the base address of a page of the
second–level table (T2) Each entry of T2 stores the base address of a page of the third–level table
(T3) Each entry of T3 stores a page table entry (PTE). The PTE is 32 bits in size. The processor
used in the computer has a 1 MB 16 way set associative virtually indexed physically tagged cache.
The cache block size is 64 bytes.
What is the size of a page in KB in this computer?
Answer : Option C
Explaination / Solution:
Let the page size be 2x Bytes. 
Then, the page offset = X bits
Now, we are using 3-level paging. First level page table is contained in one page. Each page
table entry is 32-bit.
Q6. Let ⊕ denote the Exclusive OR (XOR) operation. Let ‘1’ and ‘0’ denote the binary
constants. Consider the following Boolean expression for F over two variables P and Q.
F(P,Q) = ((1⊕P)⊕(P⊕Q))⊕((P⊕Q)⊕(Q⊕0))
The equivalent expression for F is
Answer : Option D
Explaination / Solution:
Q7. Consider a simple checkpointing protocol and the following set of operations in the log.
(Start, T4); (write, T4,y,2,3); (Start, T1); (commit,T4); (write, T1,z,5,7);
(checkpoint);
(Start,T2); (write, T2,x,1,9); (commit,T2); (start,T3), (write,T3,z,7,2);
If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo lists and the redo list?
Answer : Option A
Explaination / Solution:
As T1 & T3are not yet committed they must be undone. The transactions which are after the
latest checkpoint must be redone. So T2 must be redone. No need to redo the records which
are before last checkpoint, so T4 need not be redone.
Q8. The secant method is used to find the root of an equation f(x) = 0. It is started from
two distinct estimates xa and xb for the root. It is an iterative procedure involving
linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is
the solution. The procedure is given below. Observe that there is an expression
which is missing and is marked by? Which is the suitable expression that is to be
put in place of? So that it follows all steps of the secant method?
Initialize: xa, xb, ε, N // ε = convergence indicator
fb = f(xb)
i = 0
while (i < N and | fb | > ε) do
i = i + 1 // update counter
xt = ? // missing expression for
// intermediate value
xa= xb // reset xa
xb = xt // reset xb
fb = f(xb) // function value at new xb
end while
if |fb| > ε then // loop is terminated with i = N
write “Non-convergence”
else
write “return xb”
end if
Answer : Option D
Explaination / Solution:
Secant method direct formula
Q9. Consider a network with five nodes, N1 to N5, as shown below
The net work uses a Distance Vector Routing protocol. Once the routes have
stabilized, the distance vectors at different nodes are as following
N1 : (0, 1, 7, 8, 4)
N2 : (1, 0, 6, 7, 3)
N3 : (7, 6, 0, 2, 6)
N4 : (8, 7, 2, 0, 4)
N5 : (4, 3, 6, 4, 0)
Each distance vector is the distance of the best known path at that instance to
nodes, N1 to N5, where the distance to itself is 0. Also, all links are symmetric
and the cost is identical in both directions. In each round, all nodes exchange
their distance vectors with their respective neighbors. Then all nodes update their
distance vectors. In between two rounds, any change in cost of a link will cause
the two incident nodes to change only that entry in their distance vectors
The cost of link N2-N3 reduces to 2 in (both directions). After the next round of
updates, what will be the new distance vector at node, N3?
Answer : Option A
Explaination / Solution:
Q10. For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and | separates alternate right hand sides of productions.
S → a AbB| bAa B| ε
A → S
B → S
The appropriate entries for E1, E2, and E3 are
Answer : Option C
Explaination / Solution:
