Past Exam for CMSC 420 - Data Structures at Maryland (UMD)

Exam Information

Material Type:Final
Class:CMSC 420 - Data Structures
Subject:Computer Science
University:University of Maryland
Term:Fall 2002
  • Either...or
  • To
  • at (time)
  • Assumptions
  • Algorithm Work
  • Manipulation
  • Maximum Number
  • Initialization
  • Total Number
  • Possible Values
  • Data Structure
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5

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
155, "/var/app/current/tmp/"