CSC263 Summer 2022 Worksheet 3
代做Data structure – 这是Data structure进行训练的代写, 对Data structure的流程进行训练解析, 是比较典型的Data structure等代写方向
June 8, 2022
Hash tables
Describe how to use hash tables to solve the following problems.
Ex. 1 Given a list of integers [x 1 ,… , xn] and an integers, determine if there is a pair of integersxi, xjsuch thatxi+xj=s.
Answer (Ex. 1) Initialize a hash tableTwithn(or more) buckets. Insert each of the integers into the hash tableT. Then, for eachxi, search for the keysxiin the table. If found, return True. (Notice that wedo notrequire thati 6 =j.) Otherwise, continue with the next integer in the list. If we iterate overx 1 ,… , xnwithout returning, then return False.
Ex. 2 Given an unsorted list ofnstudent names along with their ages, determine if two of them have the same name but are different ages.
Answer (Ex. 2) Initialize a hash tableTwithn(or more) buckets. The buckets of the table will be used to store (name, age) pairs. Use student names as keys. For each (name, age) pair, search for the keynameinT. If no student is found, then insert the pair (name, age) into the table and continue. Otherwise, check the age of the student with namenamein the table; if different fromage, then return True. If we iterate over all of the students without returning, then return False.
Ex. 3 Given an unsorted list ofnstudent names, output the list of names in sorted order. Does using a hash table make sense in this situation? Why/why not?
Answer (Ex. 3) A hash table does not work well for this problem. Hash tables do not provide an easy way to iterate over the keys present in the table.
Heaps
Ex. 4 Consider the heap implementation that was presented in lecture. Without using any other data structures and without augmenting the heap, how could we search for an item with a given key in the heap? What is the worst-case runtime of this approach?
Answer (Ex. 4) One option is to simply iterate over the nodes of the heap until we reach the desired key (or we reach the end of the heap). This approach has worst-case runtime (n).
Ex. 5 Describe a new Data structure that supports all of the heap operations along with a more efficient search operation.
Answer (Ex. 5) Simply combine a heap with a hash table. Every time we insert a new item with keyk, first insert it into the heap using the standard heap insertion algorithm.
1
Then insert the keykinto the hash table; in the bucket that containsk, also store a pointer to the node that was just inserted into the heap. FindMax is unchanged. ExtractMax also removes the returned key from the hash table. To search for an item with keyk, we first do the standard hash table search for the keyk. If an item is found, we follow the pointer stored in this bucket to the appropriate node in the heap and return the item stored there.