Andhra University 2006 B.E Information Technology COMPUTER SCIENCE

2 n + one = 0(2 n)
2 2n + one = 0(2 n)

Which of these claims are correct?

(a) I and II

(b) I and III

(c) II and III

(d) I, II and III



21. Consider the subsequent graph





Among the subsequent sequences
a b e g h f
a b f e h g
a b f h g e
a f g h b e

Which are depth 1st traversals of the above graph?

(a) I, II and IV only (b) I and IV only

(e) II, III and IV only (d) I, III and IV only

22. The usual Q (n2) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

(a) remain Q (n 2) (b) become Q (n (log n) 2)

(e) become Q (n log n) (d) become Q (n)



23. In a heap with n elements with the smallest element at the root, the seven th smallest element can be obtained in time
Q (n log n)
Q (n)
Q (log n)
Q (1)



24. Which of the subsequent statements is FALSE?

(a) In statically typed language, every variable in a program has a fixed kind

(b) In un-typed languages, values do not have any kinds

(c) In dynamically typed languages, variables have no kinds

(d) In all statically typed languages, every variable in a program is associated with values of only a single kind during the execution of the program



25. Using a larger block size in a fixed block size file system leads to
better disk throughput but poorer disk space utilization
better disk throughput and better disk space utilization
poorer disk throughput but better disk space utilization
poorer disk throughput and poorer disk space utilization



26. In a system with 32 bit virtual addresses and one KB page size, use of one-level page tables for virtual to physical address translation is not practical because of

(a) the large amount of internal fragmentation

(b) the large amount of external fragmentation

(c) the large memory overhead in maintaining page tables

Earning:   Approval pending.