Welcome to Data Structure Quiz, Entry Level !!

Question 1. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

log 2 n

n/2

log 2 n - 1

n

Question 2. A scheme for storing binary trees in an array X is as follows. Indexing of X starts 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 n vertices the minimum size of X should be.

log2n

n

2n + 1

2^n - 1

Question 3. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

O(n)

O(nlogn)

O(n^2)

O(n^2logn)

Question 4. Level order traversal of a rooted tree can be done by starting from the root and performing

preorder traversal

in-order traversal

depth first search

breadth first search

Question 5. The problem 3-SAT and 2-SAT are

both in P

both NP complete

NP-complete and in P respectively

undecidable and NP-complete respectively

Question 6. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?

LASTIN = LASTPOST

LASTIN = LASTPRE

LASTPRE = LASTPOST

none of the above

Question 7. The time complexity of the following C function is (assume n > 0
int recursive (mt n)
{
   if (n == 1)
     return (1);
   else
     return (recursive (n-1) +  recursive (n-1));
}

0(n)

0(nlogn)

0(n^2)

0(2^n)

Question 8. What is the worst-case time for serial search finding a single item in an array?

Constant time

Logarithmic time

Linear time

Quadratic time

Question 9. Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

n(X + Y)

3Y + 2X

n(X + Y)-X

Y + 2X

Question 10. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

O(nlogn)

O(n)

O(logn)

O(1)