这是一个加拿大的Java强化辅导相关Quiz的Java代写作业案例

Question 1

Heaps are often represented as complete binary trees. What is the height of a complete
binary tree with 375 elements?

a) 0
b) 5
c) 6
d) 7
e) 8
f) 9

Question 2

Recall the buildHeap algorithm from the lecture, which uses a sequence of upHeaps. Use the
buildHeap algorithm to make a heap out of the following strings, assuming lexicographic
ordering.

(fish, duck, snail, pig, ant, elephant, bird, rabbit)

What is the state of the heap built after adding all the strings in the order given?

a) (ant, duck, bird, pig, fish, elephant, snail, rabbit )
b) (ant, duck, bird, pig, fish, snail, elephant, rabbit )
c) (ant, bird, duck, elephant, fish, pig, rabbit, snail )
d) (ant, bird, duck, pig, rabbit, elephant, fish, snail )

Question 3

The elements 32, 14, 20, 30, 12, 24, 16 are inserted in the given order into a Max Heap
(parent has larger priority value than child). The resultant Max Heap is:

Question 4

Given two min heaps of size n each, what is the big O time complexity of sorting the 2n
elements?

Assume that the sorting algorithm does the following: repeatedly compare the minimum
elements of the two heaps, remove the smaller one, and put it in an array. You may assume
that the array length is large enough to hold all 2n elements.

O(n2 log n)
O(n (log n)2)
O(n)
O(n log n)

Question 5

Suppose we were to define a hash code on strings s by:

where

n is the length of the string s,
x=216 ,
s[ i ] denotes the 16-bit unicode value of the character at position i in the string, so s[
i ] is a number in the range to 0 to 216 − 1.

How many bits are in the binary representation of the hash code as a function of n?

Question 6

Consider the following hash function:

– keys: 10 digit phone numbers

– hashcode: partition the key into five pairs of consecutive digits and sum up

e.g. for 654-351-3214 , the hashcode is 65+43+51+32+14.

– compression function: hashcode mod b, where b = 200.

What is the hash value for the phone number that has the maximum hashcode ?