1. Consider a singly linked list of integers that are sorted into ascending order. The head pointer points to the first node, which contains the smallest integer. See Figure 1 (a). Write a pseudo-code algorithm to revises the list so that its data are sorted into descending order. The head pointer points to the first node, which contains the largest integer. See Figure 1 (b).
head (a)
(b)
137
137
Figure 1
9 1
9 1
head
2. Consider the binary search tree in Figure 2.
a. What tree results after you insert the nodes 80, 65, 75, 45, 35, and 25, in
that order?
b. After inserting the nodes in part a, what tree results when you delete the
nodes 50 and 20?
3. Draw a (single) binary tree T, such that
- Each internal node of T stores a single character
- A preorder traversal of T yields ALGORITHMS
- An inorder traversal of T yields GOLATIHRMS
Programming Part [ 30 points] :
1. Write a java program to count the number of elements in a singly linked list.– Iteratively
– Recursively
2. Write a java program to evaluate a binary tree containing an expression which would use a stack -illustrated in Figure 3.
1
Figure 2
+ LR
2B-32 51
|
1 |
|||
|
5 |
|||
|
– |
4 |
4 |
|
|
2 |
2 |
2 |
|
|
X |
X |
X |
8 |
|
+ |
+ |
+ |
+ |
Figure 3
Stack to evaluate an expression tree
2
For on-line submission the various files should be included in a single directory which is tar-balled and compressed (.tgz) or zipped or rared. It should include a README file detailing the Course, Section, team ID, name, student IDs and ENCS accounts of each member of the team and list of files submitted in your on-line submission. Submission must be before the deadline by the group leader to the Course manager. (Only one file is to be uploaded for each group. You may replace a file by a new file by first deleting the old version BEFORE uploading a new one. Multiple files for each assignment cannot be submitted!)
