Uttar Pradesh Technical University (UPTU) 2006 B.Tech Computer Science Information Technology GATE - Question Paper

(A) 400
(B) 500
(C) 600
(D) 700
10. In a binary max heap containing n numbers, the smallest element can be obtained in time
(A) 0(n)
(B) O(logn)
(C) 0(loglogn)
(D) 0(1)
11. Consider a weighted complete graph Gon the vertex set {v1,v2 ,v} such that the weight of
the edge (v,,v) is 2i-j. The weight of a minimum spanning tree of G is:
(A) n—i
(B) 2n—2
(C)
(D) 2
12. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in
linear time, the data structure to be used is:
(A) Queue
(B) Stack
(C) Heap
(D) B-Tree
13. A scheme for storing binary trees in an array X is as follows. Indexing of X begins at 1
instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored

in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on nvertices
the minimum size of X should be
(A) log2 n
(B) n
(C) 2n+1
(D) 2—1
14. Which 1 of the subsequent in place sorting algorithms needs the minimum number of
swaps?
(A) Quick sort
(B) Insertion sort
(C) Selection sort
(D) Heap sort
15. Consider the subsequent C-program fragment in which i,j and nare integer variables.
for (i = n,j = 0; i >0; i 1= 2,j +=i);
Let val(j)denote the value stored in the variable jafter termination of the for loop. Which one
of the subsequent is true?
(A) val(j) = 8(logn)
(B) vaI(j)=8(fi)
(C) val(j)=8(n)
(D) val(j)= 8(nlogn)
16. Let S be an NP-complete issue and Q and R be 2 other issues not known to be in
NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which 1 of
the subsequent statements is true?
(A) R is NP-complete
(B) R is NP-hard
(C) Q is NP-complete
(D) Q is NP-hard
17. An element in an array X is called a leader if it is greater than all elements to the right of
it in X. The best algorithm to obtain all leaders in an array
(A) Solves it in linear time using a left to right pass of the array

Earning:   Approval pending.