Problem 1
In class we wrote some, but not all, methods of adding and deleting
objects in a linked list: we did insertFront
and removeFront. For this problem, write
insertBack
to insert an item at the back of the linked list. You can use pseudocode.
Your pseudocode should be about as close to Java as what we wrote in
class.
You can find what we wrote in class here.
Problem 2
Brookshear, Chapter Seven Review Problem 16 (pg 298).
Use only the operations for a stack: push
to add an
item to the top of the stack and pop to delete an item from
the top of the stack. Do not try to change the contents of a stack
by any other means. You may define a second stack to use in your algorithm.
Express the algorithm in pseudocode.
Problem 3:
Brookshear, Chapter Seven Review Problem 22 (pg 298).
Problem 4:
Give the values of the nodes examined, in the order examined,
in the binary search tree shown below if the value 131 is being sought.
100
/ \
/ \
/ \
25 130
/ \ / \
/ \ / \
18 60 111 135
/ \ \ / \
3 20 87 131 200
Problem 5:
Extra Credit Problem:
Write
removeBack
to remove an item from the back of a singly-linked list. A singly-linked
list is the linked list we worked with in class: items are linked in a chain
from the first item, at the front of the list, to the last item, at the back
of the list. Each item has a single link out of it; hence the
name "singly-linked". You can't get from an item to the item before it
directly from the link structure. This makes removing an item from
the back of the list more difficult than the other three basic modifications:
inserting at the back of the list, inserting at the front of the list,
and removing from the front of the list. You should write
removeBack at the same level of pseudocode that you used
for Problem 1.