数据结构代写 | Coursework 2 1 4CCS1DST: Data Structures, 2019-20

这个作业是回答数据结构相关的问题，包括ADT操作、哈希函数等
Coursework 2 1
4CCS1DST: Data Structures, 2019-20
Coursework 2
Last Name:
First Name:
Student Number:
By submitting this coursework, I declare that I understand the nature of plagiarism
as defined in the Department Handbook and that the content of this coursework
submission is entirely my own work.
4CCS1DST: Data Structures,
2019-2020
Coursework 2
Coursework posted on 14 March 2020 Submit
your answers on KEATS.
Submission deadline: 24 March 2020, 23:00.
Submission Instructions
Submit your answers on KEATS as a single pdf file (recommended) or MS Word file. Other formats
will not be accepted. The name of your file has to include your name and your KCL id number (the
number on your college ID card in the following format (beginning with the last name):
LastName FirstName KCLid CW2
with the extension indicating the type of file. The submission deadline is given above. Late submissions
will not be accepted (unless a formal deadline extension request has been accepted by the Chair of
the Exam Board). The maximum size of a submission file is 2MB. Your submission must be typeset
in such a way that it properly prints on A4 paper. In particular, lines in source codes should be
formatted so that they fit within the page width. Please do check before submitting your file that it
prints properly in black and white on A4 paper. Do not use colours – a black–and-white print-out of
your submission will be used for marking.
This Coursework 2 assignment contributes to your final mark for the 4CCS1DST module (7.5%), so
your submission must be your own individual work. The College Academic Regulations and procedures
apply, including the College’s statement and strategy on plagiarism and related forms of cheating.
You must include the following information and declaration in the beginning of your submission file:
Coursework 2 2
Questions
1. (15 marks) The ADTs Map, Dictionary and Priority Queue maintain collections of key-value
entries, but support different operations. For each of these three ADTs and for the sequence of
operations given in the tables below, show in the column ‘operation’ the name and arguments
(if any) of this operation. If a given operation is not supported by any single operation of the
ADT, then write “not supported”. If the operation is supported, then show also, in the last two
columns in the tables, the effect of applying this operation (the output, if any, and the collection
after this operation is performed), assuming that the initial collection is (7, F ), (8, Q), (3, H).
Each operation is to be applied to the collection which is the result of the previous operation.
Use the deftnition of these three ADTs as given in the lecture slides.
Operation description Map
operation output collection after the operation
(7, F ), (8, Q), (3, H)
insert the entry (6, R)
remove an entry with key 5
insert the entry (3, E)
return the number of entries
remove an entry with the smallest key
search for key 3
remove an entry with value B
make the collection empty
Operation description Dictionary
operation output collection after the operation
(7, F ), (8, Q), (3, H)
insert the entry (6, R)
remove an entry with key 5
insert the entry (3, E)
return the number of entries
remove an entry with the smallest key
search for key 3
remove an entry with value B
make the collection empty
Operation description Priority Queue
operation output collection after the operation
(7, F ), (8, Q), (3, H)
insert the entry (6, R)
remove an entry with key 5
insert the entry (3, E)
return the number of entries
remove an entry with the smallest key
search for key 3
remove an entry with value B
make the collection empty
Coursework 2 3
2. (a) (5 marks) Draw the binary tree representation of the following arithmetic expression:
(17 ∗ (((22 + 14)/7) − 8))
(b) (5 marks) Give the output from performing the post-order traversal algorithm on the binary
tree you have drawn for Question 2(a).
3. (15 marks) A heap is maintained in an array X of length 11. The current heap has size 9 and
its elements are stored in X as shown below (only the keys are shown).
0 1 2 3 4 5 6 7 8 9 10
X :
Insert key 4 to this heap. Then, from the updated heap, remove the minimum key. Show how
the array changes during the execution of these operations (show all intermediate arrays).
4. Three keys 20, 9 and 12 have been hashed into a 7-entry table:
0 1 2 3 4 5 6
20 9 12
Add to this hash table further three keys 10, 16, 250 (in this order), assuming that the hash
function is
h(k) = (3k + 5) mod 7,
and collisions are handled by:
(a) (4 marks) linear probing;
(b) (5 marks) double hashing using the following secondary hash function:
h
J
(k) = 5 − (k mod 5).
(c) (1 mark) Is this an efficient hash map?
In both cases show the final hash table.
2 7 12 14 13 20 22 25