1. Consider a singly linked list of integers that are sorted into ascendingorder. 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)
head (b)
Figure 1
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 whichwould use a stack -illustrated in Figure 3.
Figure 2
1
5
-
4
4
2
2
2
X
X
X
8
+
+
+
+
Stack to evaluate an expression tree
Figure 3
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!)
DO NOT FORGET TO DO A PEER EVALUATION
IT CAN BE DONE ANYTIME UP TO T THE DUE DATE FOR THE MARKED
ENTITY
NO EXTENSIONS
YOU GET A 0 IF YOU DO NOT EVALUATE THE MEMBERS OF YOUR TEAM! \
READ/REREAD THE REQUIREMENTS ABOUT FILE TO BE UPLOADED AND ITS NAME}
- Read the README FIRST in the Course Outline section of the course home page in in CrsMgr
