Description
- 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
- Consider the binary search tree in Figure 2.
- What tree results after you insert the nodes 80, 65, 75, 45, 35, and 25, in that order?
- After inserting the nodes in part a, what tree results when you delete the nodes 50 and 20?
- 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] :
- Write a java program to count the number of elements in a singly linked list.
- Iteratively
- Recursively
- Write a java program to evaluate a binary tree containing an expression whichwould use a stack -illustrated in Figure 3.
Figure 2
|
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 CrsMgr
