Searching

Question

Linear search is ...

Data Structures and ADTs

Question

A stueue is a hybrid of a stack and a queue. It is a list in which new entries may be placed at either the head or the tail, but entries are always removed from the head. Which of the following would be the best data structure for a stueue?

Question

Suppose we have the following set of key values:

      Able, Baker, Charlie, Delta, Echo

Analysis of Algorithms and Big-oh

Question

An O(log n) binary search in a linked list of n elements ...

Question

When is the complexity of search in a binary search tree O(n) and not O(log n)?
(where n is the number of nodes in the tree.)

Question

If we know that a sorting algorithm named sillySort is O(n^2), then we know that ...

For each of the following problems, give the worst-case time complexity, assuming that a reasonable algorithm is used. (Note that the "^" symbol is used below to indicate an exponent.)

Question

Printing the entire contents of a binary search tree containing n nodes is ...

Question

In a complete binary search tree, every non-leaf node has exactly two children, and every leaf node is at the same depth.
Printing the entire contents of a complete binary search tree containing n nodes is ...

Question

Inserting a new value into a binary search tree containing n nodes ...

Question

Inserting a new value into a complete binary search tree containing n nodes is ...

Question

Finding the successor of an element in a singly-linked list of n elements, given the key value of the element and a reference to the beginning of the list is ...

Question

Finding the successor of an element in a singly-linked list of n elements, given a reference to the element is ...

Question

Finding the predecessor of an element in a singly-linked list of n elements, given the key value of the element and a reference to the beginning of the list is ...

Question

Finding the predecessor of an element in a singly-linked list of n elements, given a reference to the element is ...

Question

Sorting an array of n elements using mergesort is ... HERE!!

Recursion

Consider the following recursive method:

     public void printOut (Node s) {
        if (s != null) {
              printOut (s.next);
              System.out.println (s.data);
     }

   front -> 3 -> 12 -> 77 -> 13 -> 5

Question

What will be the output generated from this call?

Question

How many times in total will printOut be called, including the original call to printOut(front)?
State your answer as a number (e.g. 27).

Writing Specifications and Proving Correctness

Question

If you have written a proof of correctness for your code, then ...

Question

For which of the following purposes is it appropriate to prove correctness of a program?

Consider the following program fragment:

     int i = 1;
     int j = num;
     while (i < j) {
         int t = A[i];
         A[i] = A[j];
         A[j] = t;
         i++;
         j--;
     }

Question

What does this program fragment do?

Question

Let A+ represent the value of array A after the code has executed. Which of the following statements is the best postcondition for this code?

Question

Is the statement

     num <= A.length 

Exercise
Give a loop invariant for this while loop that relates i and j. Make it as strong a statement as possible.

Question

Which one of the following statements is NOT a loop invariant for this while loop?

Proof Methods

Question

Induction is suitable for proving loop invariants because ...