PRACTICAL EXAM - CSD201 - FALL 2025
Duration: 85 minutes
Note: Submit 1 java file only! Can use own lab exercises, course notes, but NOT Internet access.
Write a Java program to manage information of products. Each product includes two fields: code: int
- a unique product code, price: int.
I. [6.25 pts] Binary Search Tree (BST):
Implement a Product class and a Node class (1.0 pts). Then, for a binary search tree T, where
nodes are ordered by code, implement the following functions:
1. [2.0 pts] Build T from a given product array P.
2. [1.0 pts] Print all products in T in descending order of their codes.
3. [0.5 pts] Add field level to each node and compute it for all nodes, where:
• The root has a level of 0,
•
Each child node has a level equal to its parent's level plus 1.
4. [0.5 pts] Add field bal factor (balance factor) to each node and compute it for all nodes,
defined as the height of the left subtree minus that of the right subtree.
5. [0.5 pts] Count the total number of nodes of T using an iterative traversal with a stack.
6. [0.75 pts] Check whether the tree T is height-balanced.
II. [2.0 pts] Sorting:
1. [1.5 pts] Write a function to sort a given product array in descending order of price,
using an algorithm with the lowest possible average-case time complexity.
2. [0.5 pts] Briefly explain why this algorithm was chosen.
III. [1.75 pts] Main Function:
1. Build the BST T from array P = {(5, 500), (3, 300), (2, 200), (4, 400), (7, 700), (6, 600), (8,
800), (1, 100), (9,900)}.
2. Invoke and test all functions implemented in Part I and II.
3. Display the output results for each step.
Zoom
- FUO
+ 100%
Close
