Exercises: Unit 9 — Data Structures

The following commands are carried out on an empty stack.

PUSH(4)
PUSH(7)
PUSH(1)
X = POP()
PUSH(6)
PUSH(3)
Y = POP()
PUSH(8)
Z = POP()
W = POP()

What is the value of W?

The following commands are carried out on an empty queue.

PUSH(C)
PUSH(A)
PUSH(T)
X = POP()
PUSH(D)
PUSH(O)
Y = POP()
PUSH(G)
Z = POP()
W = POP()

What is the value of W?

The following commands are carried out on an empty queue.

PUSH(5)
PUSH(8)
X = POP()
Y = POP()
PUSH(2)
Z = POP()
W = POP()

What is the value of W?

Build a binary search tree by inserting the letters of LIBRARY, in order. What is its internal path length?

Build a binary search tree by inserting the letters of PUMPKIN, in order. How many leaves does it have?

Build a binary search tree by inserting the letters of BANANAS, in order. What is the depth of the third A that was inserted?

The first line of input is STACK or QUEUE, telling you which structure to use. The second line is a whole number n, the number of commands. Each of the next n lines is one command on that structure, which starts out empty:

• PUSH v, where v is a number or a word, puts v in;
• POP takes an item out, by the rules of the structure.

For every POP, print the value taken out, on its own line. If the structure is empty, print NIL instead.

Constraints

• 1 ≤ n ≤ 100, and at least one command is a POP.
• Each v is a whole number or a word of capital letters, with no spaces.

Sample Input

STACK
7
PUSH 12
PUSH 5
POP
PUSH 9
POP
POP
POP

Sample Output

5
9
12
NIL

The fourth POP finds the stack empty. With QUEUE on the first line, the same commands print 12, 5, 9 and NIL.

The input is one line holding a word of capital letters. Insert its letters, in order, into an empty binary search tree (a letter equal to one already in the tree goes to the left).

Print two lines:

1. the depth of each letter, in the order the letters were inserted, separated by single spaces;
2. the internal path length of the tree.

Constraints

• The word has between 1 and 30 letters.

Sample Input

PROGRAM

Sample Output

0 1 1 2 2 3 3
12

This is ACSL's sample tree: P is the root, and the second R goes to the left of the first.

The following commands are carried out on an empty stack.

PUSH(5)
PUSH(3)
PUSH(9)
X = POP()
Y = POP()
PUSH(X - Y)
PUSH(X * Y)
Z = POP()
W = POP()
PUSH(Z + W)
V = POP()

What is the value of V?

The following commands are carried out on an empty queue.

PUSH(4)
PUSH(10)
PUSH(7)
X = POP()
PUSH(X * 2)
Y = POP()
PUSH(Y - X)
Z = POP()
W = POP()
PUSH(W - Z)
V = POP()

What is the value of V?

Build a binary search tree by inserting the letters of ALGORITHM, in order. Write its preorder traversal.

Build a binary search tree by inserting the letters of BIRTHDAY, in order. Write its postorder traversal.

Build a binary search tree by inserting the letters of TENNESSEE, in order. What is its external path length?

The letters of SCHOOLBUS are inserted, in order, into an empty min-heap. Write the bottom row of the heap, from left to right.

The numbers 15, 40, 22, 8, 31, 50, 27, 12 and 45 are inserted, in that order, into an empty max-heap. Number the positions row by row, from left to right, with the root at position 1. At what position is 15?

The input is one line holding a word of capital letters. Insert its letters, in order, into an empty binary search tree (a letter equal to one already in the tree goes to the left).

Print three lines: the inorder, the preorder and the postorder traversal of the tree, each with its letters run together.

Constraints

• The word has between 1 and 30 letters.

Sample Input

AMERICAN

Sample Output

AACEIMNR
AAMECIRN
ACIENRMA

This is the tree of Lesson 2, Example 6.

The first line of input is MIN or MAX. The second line holds whole numbers separated by single spaces. Insert the numbers, in order, into an empty min-heap (for MIN) or max-heap (for MAX), by ACSL's rule: each new number goes in the next free place, then swaps with its parent while it is out of order.

Print the heap one row per line, from the root down, with the numbers of each row from left to right, separated by single spaces.

Constraints

• There are between 1 and 50 numbers, each from -1000 to 1000.
• Numbers may repeat. A number that equals its parent does not swap.

Sample Input

MIN
40 25 31 12 18 7

Sample Output

7
18 12
40 25 31

The last row has only three numbers, because the heap holds six.

Build a binary search tree by inserting the letters of TRIANGLES, in order. Then delete R by ACSL's rule. What is the internal path length of the new tree?

The letters of HEAPSORT are inserted, in order, into an empty min-heap. Then the root is removed by ACSL's rule. Write the bottom row of the new heap, from left to right.

Build a binary search tree by inserting the letters of ALGORITHM, in order. Then delete L by ACSL's rule. Write the preorder traversal of the new tree.

The first line of input is a word of capital letters. The second line is one capital letter that appears in the word exactly once.

Insert the letters of the word, in order, into an empty binary search tree (a letter equal to one already in the tree goes to the left). Then delete the given letter by ACSL's rule:

• a node with no children is removed;
• a node with one child is replaced by that child;
• a node with two children is replaced by its left child, and its right subtree becomes the right child of the right-most node of the left child's tree.

Print the preorder traversal of the new tree, with its letters run together.

Constraints

• The word has between 2 and 30 letters.
• The letter to delete may be the root.

Sample Input

KEYBOARD
K

Sample Output

EBADYOR

K is the root, with left child E and right child Y. E becomes the root, and since E has no right child, the Y subtree becomes the right child of E.