1. What condition indicates that a linked list is empty?

2. The table below represents a portion of a computers main memory containing a linked list. Each entry consists of two cells, the first being data, the second being a pointer to the next entry. If the nil pointer is represented by 00 and the lists head pointer contains 52, modify the memory cells so the data at address 50 is inserted as the second entry in the list.

Address Contents

50 AA

51 00

52 BB

53 58

54 CC

55 00

56 DD

57 00

58 EE

59 54

3. Why is a queue normally implemented as a circular queue?

4. Suppose a binary tree is implemented as a linked structure in which each node contains both a left child pointer and a right child pointer. Which of the following statements is false?

A. The number of nodes in the tree is always at least the number of nodes on the longest path in the tree.

B. The number of NIL pointers in the tree is always greater than the number of nodes in the tree.

C. Each terminal node in the tree is always at the end of a path that is at least as long as any other path in the tree.

D. Both the left child and right child pointers of every terminal node are NIL.