Test is cumulative – this set of sample questions is only on material since second midterm

A(n) ________ of a tree is a node that has no children.

If you need to add an element at the end of a data structure, which is the most efficient data structure to add to?

1. linked list
2. array
3. vector
4. they are all the same

PUT ON SAMPLE

For which of the following data structures is adding to the end a supported operation:

Array

Vector

List

Stack

Queue

Tree

For each, tell whether valid or invalid. If invalid, tell why!

For the set of elements shown below, tell if it is a valid tree. If not, tell why!

PUT ON SAMPLE – probably longer than could go on test though

If the following linked list of Accounts has been created using the AccountList and AccountLink classes used in class (sorry, couldn’t fit balances in the picture, or prevLink pointers – they’re there), what does the list look link after the following fragment of code (in some relevant class member function):

<continued on next page>

// there is code up here to do some setting up – like setting workPtr and lookPtr

AccountLink * beforeWork = workPtr® prevLink;

AccountLink * afterWork = workPtr® nextLink;

AccountLink * beforeLook = lookPtr® prevLink;

AccountLink * afterLook = lookPtr® nextLink;

lookPtr® nextLink = afterWork;

lookPtr® prevLink = beforeWork;

workPtr® nextLink = afterLook;

workPtr® prevLink = beforeLook;

beforeWork® nextLink = lookPtr;

afterWork® prevLink = lookPtr;

beforeLook® nextLink = workPtr;

afterLook® prevLink = workPtr;

// there is code after here to do some cleaning up

PUT ON SAMPLE

If the following tree is an AVL tree of integers, what does the tree look like after the addition of an element 1 (one) (and any necessary adjustments have been made)

PUT ON SAMPLE

(10 points)

Write a function Largest for the account list internal class AccountList that will, given no parameters will report back the largest balance of any account in the list.

OR report the account itself