Computer Science Engineering - Online Test
Q1. G = (V, E ) is an undirected simple graph in which each edge has a distinct weight, and e is a
particular edge of G. Which of the following statements about the minimum spanning trees
(MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
Answer : Option B
Explaination / Solution:
No Explaination.
Q2. Let X be a recursive language and Y be a recursively enumerable but not recursive language.
Let W and Z be two languages such that Y reduces to W , and Z reduces to X (reduction
means the standard many-one reduction). Which one of the following statements is TRUE?
Answer : Option C
Explaination / Solution:
No Explaination.
Q3. Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals {S,
A} and terminals {a, b}.
S → aA {print 1}
S → a {print 2}
A → Sb {print 3}
Using the above SDTS, the output printed by a bottom-up parser, for the input aab is:
Answer : Option C
Explaination / Solution:
Q4. Consider the following proposed solution for the critical section problem. There are n
processes: P0. . . Pn-1. In the code, function pmax returns an integer not smaller than any of
its arguments. For all i, t[i] is initialized to zero.
Code for Pi:
do {
c[i]=1; t[i] = pmax(t[0],. . .,t[n-1])+1; c[i]=0;
for every j = i in {0,. . .,n-1} {
while (c[j]);
while (t[j] != 0 && t[j]<=t[i]);
}
Critical Section;
t[i]=0;
Remainder Section;
} while (true);
Which one of the following is TRUE about the above solution?
Answer : Option A
Explaination / Solution:
No Explaination.
Q5. Threads of a process share
Answer : Option D
Explaination / Solution:
Threads of a process can share all resources except stack and register set.
Q6. Consider the C code fragment given below.
typedef struct node {
int data;
node* next ;
} node;
void join (node* m, node* n) {
node* p=n ;
while (p->next ! =NULL){
p = p –> next ;
}
p–> next = m;
}
Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will
Answer : Option B
Explaination / Solution:
While loop in Join Procedure moves the pointer ‘p’ to the last node of the list “n”. And at the
last statement, we are initializing the next of the last node of list n to start of list “m”.
But in some cases it may dereference to null pointer.
Q7. Consider the C struct defined below:
struct data {
int marks [100] ;
char grade;
int cnumber;
};
struct data student;
The base address of student is available in register R1. The field student.grade can be
accessed efficiently using
Answer : Option D
Explaination / Solution:
Direct access is possible with only index addressing mode.
Q8. Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of
T are :
Note: The height of a tree with a single node is 0.
Answer : Option B
Explaination / Solution:
Q9. Consider the following C code:
# include <stdio.h>
int * assignval (int *x, int val) {
*x = val;
return x;
}
void main ( ) {
int * x= malloc (sizeof (int));
if (NULL = = x) return;
x = assignval (x,0);
if(x) {
x=(int *) malloc (sizeof (int));
if (NULL = = x) return;
x = assignval (x, 10);
}
printf(“%d\n”, *x);
free (x);
}
The code suffers from which one of the following problems:
Answer : Option D
Explaination / Solution:
(A) is wrong. We don’t need to cast the result as void * is automatically and safely promoted
to any other pointer type in this case.
(B) It is discarded for obvious reason.
(C) is wrong, because dangling pointer is nothing but the pointer which is pointing to non-
existing memory (deallocated or deleted memory) which is not happening here.
(D) is the answer. When you are calling malloc second time, new location is assigned to x
and previous memory location is lost and now we don’t have no reference to that location
resulting in memory leak.
Q10. Recall that Belady’s anomaly is that the pages-fault rate may increase as the number of
allocated frames increases. Now consider the following statements:
S1: Random page replacement algorithm (where a page chosen at random is replaced)
suffers from Belady’s anomaly
S2: LRU page replacement algorithm suffers from Belady’s anomaly
Which of the following is CORRECT ?
Answer : Option B
Explaination / Solution:
Statement 1 is “TRUE”. Because there can be a case when page selected to be replaced is by
FIFO policy.
Statement 2 is “FALSE”. Because LRU page replacement algorithm does not suffers
from Belady’s Anomaly. Only FIFO page replacement algorithm suffers from Belady’s
Anomaly.
