COSC202 Final Exam, 12/10/2025 - Answers and Grading Information

The answers given are with respect to the exam posted on the class web site, which is exam.pdf. Several questions used banks, and in those cases, I will give explanations with respect to the posted exam, but I will also give answers for all banks.

The exam was two hours, pencil/paper only.

Question 1 -- 20 points

I give these explanations with respect to the example exam above. However, at the end of each part, I identify where to find the question on each exam. There will be a table with three entries: The procedure name in part A of the exam. The procedure name that corresponds to the relevant question on that exam. And the "Part" label for the question.

So, to find this question on your exam, look at the procedure name of "Part A" in theh first column of the table. Then go to the "Part" specified, and you'll find it.

Grading

Two points per part. I gave some partial credit.

Question 2 -- 14 points

This question required you to read and understand a simple recursive method. Each time the method is called, it does the following: I'll go over answers using the example exam above, and for each part, I'll show where to find that in your exam.

Grading

2 points per part. I gave liberal partial credit.

Question 3 -- 12 points

Each bank had a similar set of six questions. I'm going to go over the answers from easiest to hardest. You'll note that each exam has a 5-character hash before the table. Therefore, after each explanation, I'll put the hash, the part, the action, and the answer(s):

Grading

2 points per part.

Question 4 -- 12 points

Each bank here had the same trees, but in different orders. The answers here are straightforward:

Case 1: If A is an ancestor of B, then A comes before B in the preorder traversal, and after B in the postorder traversal.

Case 2: If A is in the left subtree of the root and B is in the right subtree, then A comes before B in both traversals. Here are the answers going left-to-right, then top to bottom: 

            1 2 3 4 5 6 7 8 9 10 11 12
            - - - - - - - - - -- -- --
Hash 02684: Y N Y Y Y N Y Y Y  N  Y  Y
Hash 106c7: Y Y Y N Y N Y Y Y  Y  Y  N
Hash 5e7fa: Y Y Y N Y Y Y N Y  Y  Y  N 
Hash df8e8: Y Y Y Y Y N Y Y Y  N  Y  N 
Hash f2595: Y N Y Y Y N Y N Y  Y  Y  Y

Grading

1 point per answer.

Question 5 -- 12 points

All of these are straight from the heap lecture. Here are answers. 
Hash    A   B   C   D   E   F   G   H   I   J   K   L  
-----   --  --  --  --  --  --  --  --  --  --  --  -- 
606ef   83  67  60  18  21  38  96  3   4   10  8   14 
89dde   21  60  22  9   19  23  97  3   4   8   5   14 
a0667   26  67  39  18  26  29  48  4   7   13  12  22 
e33aa   17  51  81  12  19  44  87  3   4   15  14  21 
ee247   45  81  77  9   34  61  69  1   6   10  7   26

Grading

1 point per answer, with some partial credit.

Question 6 -- 10 points

Straight from the lecture notes on trees ( https://web.eecs.utk.edu/~jplank/plank/classes/cs202/Notes/Trees/index.html).

Case 1: The node has no children (it's a leaf node). You can simply delete it.

Case 2: The node has just one child. To delete the node, replace it with that child.

Case 3: The node has two children. In this case, you find the node in the tree whose value is the greatest value less than (or equal to) the node's value. That will be the rightmost node in the subtree rooted by the left child. That node will not have a right child. First, delete it. Then use it to replace the node that you are deleting. Alternatively, you can replace it with the leftmost node in the tree rooted by the node's right child. Both will work.

Grading

You needed to talk about the three cases to get full credit.

Question 7 -- 10 points

This is a simple postorder traversal: 

int height(Node *t)
{
  int l, r;

  if (t == NULL) return 0;
  l = height(t->left);
  r = height(t->right);
  if (r > l) l = r;
  return l+1;
}

You needed to use recursion here. Otherwise, your code was convoluted and inevitably incorrect. You lost a point if you did not check to see whether t was NULL.

Question 8 -- 10 points

First, you need to catch two errors:
  1. If root is NULL, then you can't rotate, so throw an error.
  2. If root->left is NULL, then there's no child about which to rotate, so throw an error.
Otherwise, the tree looks as follows: 
           root
          /    \
         /      \
        lc       c
       /  \
      /    \
     a      b
Set variables for lc and b. Note that b
  • lc->right should be set to root.
  • lc->left should be set to b. Then return lc: 

    Node *left_rotate(Node *root)
{
  Node *lc, *b;

  if (root == NULL) throw ((string) "Error");
  if (root->left == NULL) throw ((string) "Error");
  
  lc = root->left;
  b = lc->right;

  root->left = b;
  lc->right = root;
  return lc;
}

    Grading

    You lost two points if you didn't check for whether root was NULL. The reason is that your code segfaults instantly otherwise.

    You also needed to check to make sure root->left was not NULL.

    A bunch of you put sentinels and parent pointers into your code, which just shows that you're not reading the question carefully.