## Exam Information

Login / Sign Up to View Document

## Sample Document Text

Selected Answers to the Final Exam: CMSC 420, Fall 2002
Problem A. In order to implement an up-tree, recall that in addition to the tree itself, we also
need a data structure that gives us, for each key K, a pointer to where K is in the tree. Below
are three possibilities for what this data structure might be. For each possibility, describe the
conditions under which it would work better than the other two possibilities.
1. [5 points] An array.
Answer. Let k be the size of the key space, i.e., the range of values from the smallest to
largest possible values of (int)(K). If we have enough room to allocate an array of size k without
running into memory problems, then we would prefer to use an array rather than a hash table or
an AVL tree, because an array is the easiest to implement and will give the fastest running time.
2. [5 points] A hash table.
Answer. Suppose the key space is too large for an array to be feasible, but suppose we know that
the total number of keys in the tree will never exceed ...

## Related Documents

Either...or Exam

Easy Exercise Notes

Either...or Notes

Database Administration Exam

Either...or Exam

Either...or Notes

Either...or Notes

Internal Sort Notes

Report Generator Notes

© Copyright 2020 , Koofers, Inc. All rights reserved.

The information provided on this site is protected by U.S. and International copyright law, and other applicable intellectual property laws, including laws covering data access and data compilations. This information is provided exclusively for the personal and academic use of students, instructors and other university personnel. Use of this information for any commercial purpose, or by any commercial entity, is expressly prohibited. This information may not, under any circumstances, be copied, modified, reused, or incorporated into any derivative works or compilations, without the prior written approval of Koofers, Inc.