EX4

  1. Answer the following questions about the list (2,7,1,8,2)
    1. What is the length?
    2. What are all the prefixes?
    3. What are all the suffixes?
    4. What are all the sublists?
    5. How many subsequences are there?
    6. What is the head?
    7. What is the tail?
    8. How many positions are there?
  2. Repeat (1) for the character string banana.
  3. If the tail of the tail of the list L is the empty list, what is the length of L?
  4. Let L be the list (3,1,4,1,5,9)
    1. What is the value of delete (5,L)?
    2. What is the value of delete(1,L)?
    3. What is the result of popping L?
    4. What is the result of pushing 2 onto list L?
    5. What is returned if we perform lookup with the element 6 and list L?
    6. If M is the list (6,7,8), what is the value of LM (the concatenation of L and M)? What is ML?
    7. What is first(L)? What is last(L)?
    8. What is the result of retrieve (3,L)?
    9. What is the value of length(L)?
    10. What is the value of isEmpty(L)?
  5. The following method searches an array for a value. Rewrite the method using iteration rather than recursion.

public static Boolean binsearch(int x, int A[], int low, int high) {

int mid ;

if (low > high) return false;

else {

mid = (low + high) / 2;

if (x < A[mid])

return binsearch(x,A,low,mid-1);

else if (x > A[mid])

return binsearch(x,A,mid+1,high);

else

return true ; // i.e. x == A[mid]

}

}