attached


CSCI 2421: Data Structures and Program Design Spring 2020 Final Exam, Time: 120 minutes Q1. (30 Points) Choose the correct answer: 1. A node in a General tree can have: a. Two children at most b. Only one child c. Any number of children d. Three children at most 2. The height of a tree is: a. Number of nodes on longest path from root to a leaf-1 node b. Number of nodes on any path from root to a leaf c. Number of nodes on longest path from root to a leaf d. None of the above 3. The following tree is an example of: a. Complete and Binary tree b. Full tree c. Binary but not a complete tree d. All of the above 4. The number of nodes of a full binary tree at height 7 is: a. 23 b. 46 c. 64 d. 128 5. Assuming a balances search tree, addition time complexity will be: a. O(n) b. O(n log n) c. O(log n) d. None of the above 6. Which of the following algorithm will perform better when the data is already sorted: a. Merge Sort b. Bubble sort c. Selection Sort d. All of the above 7. In the average case scenario of a sorting problem, which algorithm will perform better: a. Merge Sort b. Quick sort c. Heap sort d. All will perform the same 8. Which of the following collision resolving method can introduce a clustering problem: a. Linear Probing b. Quadratic probing c. Double hashing d. Only a and b 9. The efficiency of hashing is measured by: a. The number of elements to store b. A load factor c. The complexity of the hash function used d. None of the above 10. One of this is not a property of a red-black tree: a. The root is black b. Every black node has a red parent c. A red node cannot have red children d. The black height is the same for every path from the root to any leaf node. Q2. (10 Points) Draw the 11-entry hash table that results from using the hash function, h(i) = (3i+5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by quadratic probing. Q3. (10 Points) a. Create a max Heap using these keys in order from left to right: 23, 70, 30, 80, 50, 40, 55, 88, 33 b. Perform only one remove operation on your max heap (Extract MAX). Q4. (10 Points) Considering the following AVL tree, check if it is valid (Balanced). If not, re-balance the tree and Insert 80, then 88. Q5. (10 Points) Considering the following valid Red-Black tree, Insert 5, 53 and 44. Q6. (10 Points) Apply Breadth First Search traversal on the following graph. Show your steps and the updated queue. Q7. (10 Points) Apply Dijkstra algorithm on the following graph to find the shortest path. Q8. (10 Points) Another application of matching delimiters using stacks is in the validation of markup languages such as HTML or XML. HTML is the standard format for hyperlinked documents on the Internet and XML is an extensible markup language used for a variety of structured data sets. A sample HTML document is as follows:

The Little Boat

The Little Boat

The storm tossed the little The storm tossed the little boat boat like a cheap sneaker in an like a cheap sneaker in an old washing machine. old washing machine.

1. Will the salesman die?

2. What color is the boat?

1. 
   Will the salesman die?
   


2. 
   What color is the boat?
   

In an HTML document, portions of text are delimited by HTML tags. A simple opening HTML tag has the form “” and the corresponding closing tag has the form “”. Design an algorithm using pseudo code or write java code to check if the HTML tags in a giving HTML file passed as string are balanced. End Of Questions