DOC PREVIEW
UMD CMSC 132 - Midterm #2 Practice Questions

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC132, Midterm #2, Practice QuestionsProblem 1 Treesa. Binary search trees (BST)a. What is the key property of a binary search tree?b. On average, what is the complexity of doing an insertion in a binary search tree?c. On average, what is the complexity of doing a find in a binary search tree?d. What is the worst-case complexity of doing a find in a binary search tree?e. What can cause worst-case behavior in a binary search tree?b. Binary search trees examplesa. Draw the binary search tree created when the following values are inserted in order: 6, 5, 2, 8, 10, 3b. Given the previous BST, draw the tree created when the node 5 is removed c. Traversalsa. What is a tree traversal?b. What is the difference between a depth-first and breadth-first traversal?c. Pre-order, in-order, and post-order are all depth-first traversals T or Fd. Pre-order traversals are faster than post-order traversals T or Fe. For the following binary tree, provide an example of ai. Preorder traversalii. Postorder traversaliii. Breadth-first traversal1510452 25 30d. Given the following Java class definition for a binary treeClass Node { int myValue; Node left; Node right;}Class Tree { Node root; // root node in tree Node find(int k) { … } int treeHeight( ) { … } void preorder( ) { … }}Write the following code:a. find( k ) – Use a recursive algorithm to find a node with myValue = k in treeb. treeHeight( ) – Use a recursive algorithm to find the height of a treec. preorderPrint( ) – Use a recursive algorithm to print myValue for each node using a preorder traversal of the tree, starting from the rootProblem 2 Java Programminge. True or Falsea. Using “==” and .equals() always return the same resultb. Variables of type Integer and int are both referencesc. Autoboxing creates an Integer object from an intd. Exceptions are used to capture run-time errorsf. Write Java code for a Card classa. Use an enumerated type for the suits in a card deck (Spades, Hearts, Diamonds, Clubs)b. Implement the comparable interface for Card objects so that the suits are ranked in the order listed (Spades > Hearts > Diamonds > Clubs) g. Write Java code for a Deck classa. Uses an ArrayList to store multiple Card objectsb. Use an anonymous inner class to generate an Iterator over Card objects in the Deck2Problem 3 Heapsh. Properties & characteristicsa. What are two key properties of a heap?b. What operation(s) supported by binary search trees are not supported by heaps?c. On average, what is the complexity of doing an insertion in a heap?d. On average, what is the complexity of doing a find in a heap?e. What is the worst-case complexity of doing a find in a heap?f. How can heaps be stored in a compact array representation?g. Why are heaps used to implement priority queues?i. Examplesa. Draw the heap created when the following values are inserted in order: 6, 5, 2, 8, 10, 3b. Given the previous heap, draw the heap produced when the smallest value is removedc. Show the tree representation of the following heap (in array representation)A, B, C, D, E, Fd. Show the array representation of the following heap (in tree representation)Problem 4 Compression & Huffman Codes362228 45 25j. Compressiona. What are two sources of compressibility?b. What are two types of compression?c. What is a prefix code?d. What are Huffman codes?e. How do Huffman codes achieve compression?f. Given the following Huffman tree, decode the sequence “00110010”g. Using the same Huffman tree, encode the string “arts” as a sequence of 0’s and 1’sh. Given the following symbol frequencies, create a Huffman tree for the symbolsA = 5, B = 8, C = 4, D = 6, E =


View Full Document

UMD CMSC 132 - Midterm #2 Practice Questions

Documents in this Course
Notes

Notes

8 pages

Recursion

Recursion

12 pages

Sorting

Sorting

31 pages

HTML

HTML

7 pages

Trees

Trees

19 pages

HTML

HTML

18 pages

Trees

Trees

19 pages

Honors

Honors

19 pages

Lecture 1

Lecture 1

11 pages

Quiz #3

Quiz #3

2 pages

Hashing

Hashing

21 pages

Load more
Download Midterm #2 Practice Questions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm #2 Practice Questions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm #2 Practice Questions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?