# 数据结构代写 | CS 234 Spring 2020 — Assignment 5

这个作业是完成哈希表相关的数据结构

CS 234 Spring 2020 — Assignment 5

W1. (5 marks) You are given a positive integer n of the form n = 2h − 1, for some integer h ≥ 1. Give an example

of an array of length n where the following method of building a heap

step 1. Place the new key at the first free leaf

step 2. The heap-order property might be violated: perform a bubble-up,

uses Ω(n log(n)) element comparisons. Justify your answer.

W2. (5 marks) Suppose we have an array A of numbers such that A[i] = ai + b with a > 0 and b as real numbers.

Show that interpolation search for a target k which is in the array, achives a runtime O(1).

W3. (a) (5 marks) Let the array A contain the following keys: [3, 1, 4, 1, 17, 26, 6, 5, 9, 5, 98, 2, 6, 10]. Show the

array after each Bubble-Down call during the Heapify operation (there will be 7 such arrays). Specifically,

use the algorithm that processes the array from right to left (applying Bubble-Down procedure for each

index in the array that corresponds to an internal node of the heap), until the entire array forms a

(min-)heap, using the procedure showed in lectures.

(b) (5 marks) If we modify the Heapify operation to fix up the heap from left to right (rather than right to

left), while still applying the Bubble-Down procedure at each step (i.e. for each internal node of the heap),

would the resulting array produce a heap? If not, give an example of an array A (or a corresponding

binary tree) that would not generate a heap after applying this version of Heapify. Justify your answer.

W4. (5 marks) Consider a self-organizing heuristic which alternates between Move-To-Front and Transpose. Precisely, to organize the list after the i’th access, the accessed item is moved to front if i is odd and is swapped

with its previous item if i is even. For example, for a sequence initially ordered as [A,B,C,D], if D is searched

first and C is search second, the algorithm proceeds by moving D to the front and then swapping C with B,

resulting in [D,A,C,B].

Consider a sequence of n keys, k1, k2, . . . , kn, where n is an odd integer. Describe the sequence of n searches

that results in the maximum cost and compute the cost of performing these n searches.

W5. (5 marks) Assume that we have a hash table of size N = 5, we use the hash function f(x) = x mod 5, and

we use separate chaining for collision resolution. Demonstrate the insertion of the keys 0, 1, 2, . . . , 12 into the

(initially empty) hash table (in that order). You just need to draw the state of the hash table after all insertions

are done. Justify your answer briefly.

W6. (12 marks) Consider a hash table dictionary possible keys U = {0, 1, 2, . . . , 25} and size M = 5. If items with

keys k = 17, 10, 20, 13 are inserted in that order, draw the resulting hash table if we resolve collisions using:

(a) Chaining with h(k) = (k + 2) mod 5.

(b) Linear probing with h(k) = (k + 2) mod 5

(c) Double hashing with h1(k) = (k + 2) mod 5 and h2(k) = 1 + (k mod 4).

(d) Identify a serious problem with the choice of hash functions h2(k) = bk/5c.

W7. (3 marks) Assume that we have a hash table of size 6 and that our keys are selected uniformly at random from

the set A = {1, 2, 3, . . . , 600}. Consider the following two hash functions:

h1(k) = k mod 6,

h2(k) = 2k mod 6.

Which hash function is better? Justify your answer.