Fall 2000 PIC 10b Practice
Final
The final is Sunday, Dec 10 3-6pm in Moore 100.
The real final will have seven problems of equal value and should be about
the same difficulty. One problem from the practice final is guaranteed
to be on the actual final.
1. Define the following terms:
(a) FILO
(b) tail recursion
(c) memoization
(d) external node
(e) adaptive sorting
2. Write a function with prototype:
template<class Item>
Node<Item>* reverse(Node<Item>* list);
to reverse a linked-list where the Node's
class is:
template <class Item>
class Node
{
public:
Node(Item i, Node* n){item=i; next=n;}
void setItem(Item i){item =i;}
void setNext(Node* n){next=n;}
Item getItem(){return item;}
Node* getNext(){return next;}
private:
Item item;
Node* next;
};
3. Briefly explain why the first version of insertion sort we described
in class was non-adaptive and why it runs in time O(N2)
if N items are to be sorted.
4. Consider the following tree:
a
/ \
h p1
/ \
p2 y
Write out the nodes in the order they would be visited if one did a
(a) a preorder traversal, (b) an inorder traversal, (c) postorder traversal,
and (d) a level order traversal.
5. Let the node's for a binary tree be given by the struct:
struct node { int item; node *l, *r;};
typedef node *link;
Write a recursive function with prototype:
int exNodeCount(link h);
to compute the number of external nodes in the tree pointed to by h.
6. A palindrome is a string that is spelled the same forwards and backwards.
For example, "bob" and "abba" are palindromes but toy in not since "toy"
spelled backwards is "yot". Describe an algorithm in English or C++ that
uses a stack to check if a word is a palindrome. You can assume you are
told in advance the length of the word.
7. Write a divide and conquer program with prototype
int min(int a[], int l, int r)
to return the minimum value stored in a[] for indices between and
including l and r.
8. Explain how a Queue ADT works and give an example of where one would
use a Queue.
9. Explain using words and diagrams the intermediate steps that a mergesort
algorithm would go through in sorting:
2 7 4 8 1 5
10. Suppose the following keys 7,2,4,3,5 are inserted into a hash table
of size 5 with hash function x%5 where collisions are resolved using
linear probing. Write out the resulting hash table.
|