Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order.

int ProcessArray(int *listA, int x, int n) 
{ 
      int i, j, k; 
      i = 0; 
      j = n-1; 
      do 
      { 
         k = (i+j)/2; 
         if (x <= listA[k]) 
           j = k-1; 
         if (listA[k] <= x) 
           i = k+1; 
      } 
      while (i <= j); 
      if (listA[k] == x) 
           return(k); 
      else 
           return -1; 
}

Which one of the following statements about the function ProcessArray is CORRECT?

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O( n^a log^b n + m^c log^d n ), the value of a + 10b + 100c + 1000d is _______.

Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

typedef struct treeNode* treeptr; 
Struct treeNode 
{ 
    Treeptr leftMostchild, rightSibiling; 
}; 
Int Dosomething (treeptr tree) 
{ 
    int value =0; 
    if (tree ! = NULL) { 
      If (tree -> leftMostchild = = NULL) 
          value=1; 
    else 
        value = Dosomething (tree->leftMostchild); 
        value = value + Dosometing (tree->rightsibiling); 
    } 
    return (value); 
}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

int height (treeptr n) 
  { if (n== NULL) return -1; 
  if (n-> left == NULL) 
  if (n-> right ==NULL) return 0; 
  else return B1 ;             // Box 1 
  else {h1 = height (n -> left); 
      if (n -> right == NULL) return (1 + h1); 
      else {h2 = height (n -> right); 
          return B2 ;          // Box 2 
          } 
      } 
}

The appropriate expression for the two boxes B1 and B2 are