Computer Science Engineering - Online Test
Q1. Three concurrent processes X, Y, and Z execute three different code segments that access and
update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores
a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes
the P operation on semaphores c, d, and a before entering the respective code segments. After
completing the execution of its code segment, each process invokes the V operation (i.e.,
signal) on its three semaphores. All semaphores are binary semaphores initialized to one.
Which one of the following represents a deadlock-free order of invoking the P operations by
the processes?
Answer : Option B
Explaination / Solution:
Suppose X performs P(b) and preempts, Y gets chance, but cannot do its first wait i.e., P(b),
so waits for X, now Z gets the chance and performs P(a) and preempts, next X gets chance.
X cannot continue as wait on ‘a’ is done by Z already, so X waits for Z. At this time Z can
continue its operations as down on c and d. Once Z finishes, X can do its operations and so Y.
In any of execution order of X, Y, Z one process can continue and finish, such that waiting is
not circular. In options (A),(C) and (D) we can easily find circular wait, thus deadlock
Q2.
Consider the following relational schema.
Students(rollno: integer, sname: string)
Courses(courseno: integer, cname: string)
Registration(rollno: integer, courseno; integer, percent: real)
Which of the following queries are equivalent to this query in English?
“Find the distinct names of all students who score more than 90% in the course numbered 107”
(I) SELECT DISTINCT S.sname
FROM Students as S, Registration as R
WHERE R.rollno=S.rollno AND R.Courseno=107 AND R.percent>90
(II) 
(III) {T | ∃S∈ Students, ∃R∈ Registration (S.rollno = R.rollno ∧ R.courseno = 107 ∧ R.percent > 90 ∧ T.sname = S.name)}
(IV) 
Answer : Option A
Explaination / Solution:
Four queries given in SQL, RA, TRC and DRC in four statements respectively retrieve the
required information.
Q3. 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 minimum number of page colours needed to guarantee that no two synonyms map to
different sets in the processor cache of this computer?
Answer : Option C
Explaination / Solution:
As the page size is 213 Bytes and page coloring is asked so we divide cache size by page
size and group 16 pages in one set.
Number of pages in cache=1MB/8KB=128 pages
Number of set in cache=128/16=8 sets
Take any page of LAS, it will be mapped with cache on any one of these 8 sets (set
association mapping).For any two synonym to map with same set they should be colored with
same color of that respective set. So minimum we need 8 colors for this mapping.
Q4. Consider the following processors (ns stands for nanoseconds).
Assume that the pipeline registers have zero latency.
P1: Four-stage pipeline with stage latencies 1 ns, 2 ns, 2 ns, 1 ns.
P2: Four-stage pipeline with stage latencies 1 ns, 1.5 ns, 1.5 ns, 1.5 ns.
P3: Five-stage pipeline with stage latencies 0.5 ns, 1 ns, 1 ns, 0.6 ns, 1 ns.
P4: Five-stage pipeline with stage latencies 0.5 ns, 0.5 ns, 1 ns, 1 ns, 1.1 ns.
Which processor has the highest peak clock frequency?
Answer : Option C
Explaination / Solution:
Clock period (CP) = max stage delay + overhead
Q5. Which one of the following hash functions on integers will distribute keys most uniformly
over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
Answer : Option B
Explaination / Solution:
If we take first 10 elements, number of collisions taken by the hash function given by option
(B) is less when compared to others.
Q6. Consider the Boolean operator # with the following properties:
Then x # y is equivalent to
Then x # y is equivalent to
Answer : Option A
Explaination / Solution:
No Explaination.
Q7. Consider the following C program.
void f(int, short);
void main()
{
int i = 100;
short s = 12;
short *p = &s;
____________; // call to f()
}
Which one of the following expressions, when placed in the blank above, will NOT result in a
type checking error?
Answer : Option D
Explaination / Solution:
Here function f takes two arguments one is int and the other is short and its return type is void.
So, in main function ‘P’ is a pointer to short and when we call f (i,*p) there won’t be any type
checking error.
Q8. 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
After the update in the previous question, the link N1-N2 goes down. N2 will
reflect this change immediately in its distance vector as cost, ∞ . After the NEXT
ROUND of update, what will be the cost to N1 in the distance vector of N3?
Answer : Option C
Explaination / Solution:
N3 has neighbors N2 and N4
N2 has made entry ∞
N4 has the distance of 8 to N1
N3 has the distance of 2 to N4
So 2 + 8 = 10
Q9. Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic
Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.
Answer : Option C
Explaination / Solution:
(1) NTM ≅ DTM
(2) RELs are closed under union & but not complementation
(3) Turing decidable languages are recursive and recursive languages are closed under
intersection and complementation
(4) RELs are closed under union & intersection but not under complementation
Q10. A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as
follows. Each of the processes W and X reads x from memory, increments by one, stores it to
memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by
two, stores it to memory, and then terminates. Each process before reading x invokes the P
operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the
semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum
possible value of x after all processes complete execution?
Answer : Option D
Explaination / Solution:
No Explaination.
