Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};

int GetValue(struct CellNode *ptr)
{
  int value = 0;
  if (ptr != NULL)
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value +  GetValue(ptr->leftChild)
                   +  GetValue(ptr->rightChild);
  }
  return(value);
}

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

Question 2. 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 3. What is the best definition of a collision in a hash table?

Two entries are identical except for their keys.

Two entries with different data have the exact same key.

Two entries with different keys have the same exact hash value.

Two entries with the exact same key have different hash values.

Question 4. 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)

Question 5. Consider the following functions:
f(n) = 2^n
g(n) = n!
h(n) = n^logn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?

f(n) = O(g(n)); g(n) = O(h(n))

f(n) = Omega(g(n)); g(n) = O(h(n))

g(n) = O(f(n)); h(n) = O(f(n))

h(n) = O(f(n)); g(n) = Omega(f(n))

Question 6. Consider the function f defined below.
struct item
{
  int data;
  struct item * next;
}; 

int f(struct item *p)
{
  return (
          (p == NULL) ||
          (p->next == NULL) ||
          (( P->data <= p->next->data) && f(p->next))
         );
}

For a given linked list p, the function f returns 1 if and only if

the list is empty or has exactly one element

the elements in the list are sorted in non-decreasing order of data value

the elements in the list are sorted in non-increasing order of data value

not all elements in the list have the same data value.

Question 7. 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 8. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

n

n^2

nlogn

n(log^2)n

Question 9. 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 10. Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

T(n) <= 2T(n/5) + n

T(n) <= T(n/5) + T(4n/5) + n

T(n) <= 2T(4n/5) + n

T(n) <= 2T(n/2) + n