1. The following refer to symbol table implementations. a. What is the benefit o
ID: 3693454 • Letter: 1
Question
1. The following refer to symbol table implementations.
a. What is the benefit of using a key-indexed array implementation?
b. Give a circumstance under which a key-indexed array implementation is inappropriate.
2. Short programming assignment. Implement the array-based symbol table from program 12.5, adding a remove operation.
3. In the following sorted file we are searching for J. Show the values that would be checked at each step for both a binary search and an interpolation search. Show all calculations.
A A B E F H J M N N N N O P P P P P R R R R T T T Z Z Z Z Z Z Z
4. The following refer to binary search trees.
a. Draw the binary search tree that results when the keys I N S E R T M D (in that order) are inserted into an initially empty tree.
b. Explain why searching and insertion may still require N operations in the worst case for binary search trees.
5. The following refer to indexed implementations of symbols tables.
a. What is the advantage of an indexed implementation when table items are large?
b. When is an indexed implementation inappropriate?
6. Using the algorithm represented in Programs 12.13 and 12.12, show the BST that results from inserting D into the following:
7. The following refer to methods of providing guaranteed performance for search trees.
a. Explain how the algorithm in Program 13.1 results in a balanced tree.
b. Explain the difference between randomized, amortized, and optimized approaches to gauranteed performance.
c. Why does a randomized BST require that each node store the count of nodes in the subtree?
8. The following refer to splay BSTs.
a. What is the difference between a splay BST and an ordinary BST?
b. Draw the splay BST that results when you insert the items I N S E R T M D into an initially empty tree.
9. Convert the following 2-3-4 tree into a red-black tree:
10. The following refer to skip lists.
a. Explain the trade-offs resulting from increasing and decreasing the parameter t.
b. Draw the skip list that results from inserting the keys I N S E R T M into an initially empty list, assuming that randX returns the sequence 1 1 2 1 3 2 3.
Explanation / Answer
1. a) key-indexed array is a collection values associated with a key. its advantages are given below,
b) key-indexed array does not give an ordered list of data. it has randomized access. since it doesn't work well for sorting.
4.a) bst is given below.( i am not able to upload image. i tried a lot. the below image is getting when doing in word). I is the root of bst. E is the left subtree of I. N is the right subtree of I. D is the left subtree of E. M is the left subtree of N.
I
E N
D M R
S
T
b) in worst case search:- a binary search tree must search from root to last leaf node. in such cases it takes N time.
In worst case insertion:- before inserting a value 'k' to a BST, it should perform search in the existing BST for the value 'k'. if the search is unsuccessful, the value 'k' can be inserted at the point where search is stopped.since if the search is worst case, it should require N time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.