Application: You need to maintain a large dictionary of term definitions in a foreign language. You need efficient searc

[answerhappygod]

Application You Need To Maintain A Large Dictionary Of Term Definitions In A Foreign Language You Need Efficient Searc 1 (99.78 KiB) Viewed 24 times

Application: You need to maintain a large dictionary of term definitions in a foreign language. You need efficient search, but the dictionary is growing so efficient insertion is needed too. Also you need to be able to output the dictionary in sorted order on demand. Assume n entries. Make exactly two selections: the computational model you choose, and the time complexity for the main operations specified: ООООО A. Model: Array implementation of Heap for partial order B. Model: Dynamic Set ADT using Hashtable with chaining C. Model: Dynamic Set ADT with Binary Search Tree D. Model: Dynamic Set ADT with Red-Black Tree or Skip List E. Model: Flow network using Edmunds-Karp F. Model: Sorted List maintained with Randomized Quicksort G. Model: Union-Find ADT using forest with rank and path heuristics H. Model: Weighted Graph; Dijkstra's algorithm for shortest paths 1. Time: 0(1 + n/m) where m is an additional parameter you choose J. Time: O(E lg V) since it's connected K. Time: O(VE?) L. Time: O(a(V)), which is for practical purposes O(1) M. Time: Odlg n) for most operations; O(n) for listing contents N. Time: O(n Ig n) expected 0. Time: O(n) ОООООООО P. Time: O(n) to build it, O(lg n) to extract items