Indian Institute of Technology Madras (IIT-M) 2000 A.M.I.E.T.E Computer Science

tree. Which of the subsequent is always tree?
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) LASTPRE = LASTPOST
(d) None of the above
2.17. Consider the subsequent functions
f(n) = 3n
g (n) = 2JIog2
h(n) = n!
Which of the subsequent is true?
(a) h(n) is 0 (f(n))
(b) h(n) is 0 (g(n))
(c) g(n) is not 0 (f(n))
(d) f(n) is 0(g(n))
2.18. Let G be an undirected connected graph with distinct edge weight. Let emaxbe the edge
with maximum weight and emjn the edge with minimum weight. Which of the subsequent
statements is false?
(a) Every minimum spanning tree of G must contain emjn
(b) If emax is in a minimum spanning tree, then its removal must disconnect G
(c) No minimum spanning tree contains emax
(d) G has a unique minimum spanning tree
2.19. Lt G be an undirected graph. Consider a depth-first traversal of G, and let T be the
resulting depth-first search tree. Let u be a vertex in G and let v be the 1st new (unvisited)
vertex visited after visiting u in the traversal. Which of the subsequent statements is always
true?
(a) {u,v} must be an edge in G, and u is a descendant of v in T
(b) {u,v} must be an edge in G, and v is a descendant of u in T
(c) If {u,v} is not an edge in G then u is a leaf in T
(d) If {u,v} is not an edge in G then u and v must have the identical parent in T
2.20. The value of j at the end of the execution of the subsequent C program mt incr (mt i)
static mt count = 0;
count = count + i;
return (count);
main ()
mt i,j;
for (i = 0; i <=4; i++)
j = incr(i);
is
(a) 10
(b) 4
(c) 6
(d) 7
2.21. provided the subsequent expression grammar:
EE*FIF+EIF
F - F - I id
which of the subsequent is true?
(a) * has higher precedence than +
(b) - has higher precedence than *
(c) + and — have identical precedence
(d) + has higher precedence than *
2.22. Suppose the time to service a page fault is on the avg. 10 milliseconds, while a
memory access takes one microsecond. Then a 99.99% hit ratio outcomes in
avg. memory access time of
(a) 1.9999 milliseconds

(b) one millisecond

Earning:   Approval pending.