Final Exam Review

A great source of practice questions for the final is to look at previous practice exams and the exams themselves. In particular, take any question about arrays (there were lots!) and rephrase them to be about linked lists. Or doubly linked lists. Or even circular linked lists.

Also, consider these questions:

  1. Suppose we have

    typedef struct tree_node {
  int data;

  struct tree_node* left;
  struct tree_node* right;
} tree_node;

    Write a function int min_tree(tree_node* root) that finds the minimum element in a non-empty binary tree rooted at root. Do not assume that the tree is a binary search tree.

  2. Suppose we have

    typedef struct dlist_node {
  int data;

  struct dlist_node* prev;
  struct dlist_node* next;
} dlist_node;

    Write a function dlist_node* remove_evens(dlist_node* head) that, given a correctly-linked doubly linked list of dlist_nodes, removes every alternating node. For example, it should remove the 2nd node, 4th node, 6th node, and so on from the list, making sure that the resulting list is also correctly structure. The function returns the new head of the list.

  3. Problems from the book, chapter 17: 3, 4, 5, 7, 8, 9, 12, 13, 14, 15, 16.