CIS 2168 data structures quiz 2

Suppose that an intermixed sequence of (stack) push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence(s) could not occur?

(a) 4 3 2 1 0 9 8 7 6 5

(b) 4 6 8 7 5 3 2 9 0 1

(c) 2 5 6 7 4 8 9 3 1 0

(d) 4 3 2 1 0 5 6 7 8 9

(e) 1 2 3 4 5 6 9 8 7 0

(f) 0 4 6 5 3 8 1 7 2 9

(g) 1 4 7 9 8 6 5 3 0 2

(h) 2 1 4 3 6 5 8 7 9 0

(b) 4 6 8 7 5 3 2 9 0 1

0 1 cannot occur

(f) 0 4 6 5 3 8 1 7 2 9

1 7 cannot occur.

(g) 1 4 7 9 8 6 5 3 0 2

0 2 cannot occur.

Suppose that a client performs an intermixed sequence of (queue) enqueue anddequeue operations. The enqueue operations put the integers 0 through 9 in order onto the queue;the dequeue operations print out the return value. Which of the following sequence(s) could notoccur?

(a) 0 1 2 3 4 5 6 7 8 9

(b) 4 6 8 7 5 3 2 9 0 1

(c) 2 5 6 7 4 8 9 3 1 0

(d) 4 3 2 1 0 5 6 7 8 9

(b) 4 6 8 7 5 3 2 9 0 1

(c) 2 5 6 7 4 8 9 3 1 0

(d) 4 3 2 1 0 5 6 7 8 9

queues always preserve order

Suppose that initially a max-heap contains just a single node whose key is equalto 0. Then, for all i from 1 to n, you insert i into the max-heap. You do this by attaching a newkey to some leaf of the current tree. What is the height of the tree after you've attached the lastnode with key n?

(a) Θ(n2)

(b) Θ(n)

(d) Θ(n log n)

(d) Θ(n log n)

Follow the heapify procedure to turn the array

.a = [5, 3, 17, 10, 84, 19, 6, 22, 9]

into a max-heap.

84, 5, 19, 22, 3, 17, 6, 10, 9

Insertion into and removal from a heap is a operation.

(a) O(n)

(b) O(n2)

(c) O(log2 n)

(d) O(nlog2 n)

(e) O(log10 n)

(c) O(log2 n)

(True/False) In Java's PriorityQueue, the poll method first saves the item at the top of the heap. (Check your answer by consulting the javadoc).

True

(True/False) Removal from a heap is always from the bottom.

False

The ________ is used to implement a priority queue.

Heap

Add each of these elements into a min-heap. Show both the array and (draw) the tree.

(a) 23, 17, 19, 21, 11, 7, 13, 10, 0, 7

(b) 1, 2, 3, 4, 5, 6, 7, 8, 9, 0

a) [0, 7, 11, 10, 7, 19, 13, 23, 17, 21]

0

7 11

10 7 19 13

23 17 21

b)[0, 1, 3, 4, 2, 6, 7, 8, 9, 5]

0

1 3

4 2 6 7

8 9 5

Which array corresponds to the following heap? Check the heap in ex 5.21

(a) [- X W V S P U Q R J D C H... ]

(b) [- X S V P W Q U R C D J H... ]

(c) [- X W J V U D H S P Q R C...]

(c) [- X W J V U D H S P Q R C...]

If you insert the letter M into the heap above (Exercise 1.11), which array entries change?

(a) 3, 6, 7, 12, 13

(b) 3, 6, 13

(c) 1, 2, 4, 5, 8, 9, 10, 11, 13

(d) 6, 13

(e) 3, 6, 12, 13

(b) 3, 6, 13

If you delete the max from the original heap in Exercise 1.11, which entries change?

(a) 1, 3, 6, 12

(b) 1, 3, 7, 12

(c) 1, 2, 4, 8, 12

(d) 1, 3, 12

(e) 1, 3, 6, 7, 12

(c) 1, 2, 4, 8, 12

Suppose that the sequence

P R I O R I T Y Q U E U E

(where a letter means insert and an asterisk means remove-the-maximum) is applied to an initially empty priority queue. Give the sequence of values returned by remove-the-maximum operations.

R, R, P, O, T, Y, I, I, U, Q, E, U,

Which of the following is an example of a map?

(a) (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (B, Bill)

(b) (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (B2, Bill)

(c) (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (J, Jane)

(d) (S, Sam), (B, Bill), (S, Sam), (B1, Bob), (B2, Bill)

(b) (J, Jane), (B, Bill), (S, Sam), (B1, Bob), (B2, Bill)

(True/False) Using a hash table enables us to retrieve an item in O(n log n) time.

False

Hash table retrival is O(1)

(True/False) Using Huffman codes to encode text files should give you files with more bits than you would get using other codes.

False

Huffman codes uses fewer bits for the most common characters and more bits for the uncommon characters

The following algorithm is a(n)___________ .

if the tree is empty

Return null (target is not found).

else if the target matches the root node's data

Return the data stored at the root node.

else if the target is less than the root node's data

Return the result of searching the left subtree of the root.

else

Return the result of searching the right subtree of the root..

(a) algorithm for removal from a heap

(b) algorithm for insertion into a heap

(c) algoithm for insertion into a a binary tree

(d) recursive algorithm for searching a binary tree

(d) recursive algorithm for searching a binary tree

Expanding and contracting arrays are operations.

(a) O(n)

(b) O(log2 n)

(c) O(√n)

(d) O(n2)

(a) O(n)

Complete the following algorithm which recursively inserts an item into a binary search tree.

if the root is null

Replace empty tree with a new tree with the item at the root and return true.

else if the item is equal to root. data__________

else if the item is less than root.data

Recursively insert the item in the left subtree.

else

Recursively insert the item in the right subtree.

(a) The item is not in the tree; return false.

(b) The item is already in the tree; return false.

(c) The item is not in the tree; return true.

(d) The item is already in the tree; return true.

(b) The item is already in the tree; return false.

Searching a binary search tree is a process.

(a) O(n)

(b) O(1)

(c) O(logn)

(d) O(n2)

(c) O(logn)

The ___________ of a node is a measure of its distance from the root.

Level

The _____________ is the number of nodes in the longest path from the root node to a leaf node.

Height

(True/False) If node n is not the root of tree T, its level is 1 + the level of its parent.

True

(True/False) Collections implementing the Set interface must contain unique elements.

True

Consider a document that has the following symbols and frequencies:(Check table in the the quiz)

(a) Draw a Huffman Tree for these symbols. Break ties alphabetically.

(b) Encode the string "Poets" into binary using this encoding.

Not sure

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?

C)

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for x ranging from 0 to 2020?

(a) x^2 mod 10

(b) x^3 mod 10

(c) (12·x^2) mod 1

(b) x^3 mod 10