A27544 No calculator allowed in this examination
School of Computer Science
Fourth Year Undergraduate/Postgraduate
21921
Fundamentals: Data Structures
Main Summer Examinations 2019
Time allowed: 1:30
[Answer all questions]
– 1 – Turn Over
No calculator
Note
Answer ALL questions. Each question will be marked out of 20. The paper will be marked
out of 60, which will be rescaled to a mark out of 100.
Question 1 Lists and Trees
(a) (i) Explain what lists, stacks, and queues are and what is the main difference
between them [4 marks]
(ii) Which of the following tree is an AVL tree and why ? Justify the answer for
each of the trees. [4 marks]
(b) Consider a dynamic list implemented as an array. The initial array size is 10000
elements. New elements are inserted in the array until it is full. Every time the array
is full, a new array is created with 5000 additional elements than the previous one.
Answer the following questions.
(i) What is the complexity of the insertion operation in the worst case? [2 marks]
(ii) Calculate the amortized complexity of the insertion operation. [4 marks]
(c) In this exercise we ask you to threat the memory as a large array Mem[-] , and write
code in OS++ in order to directly access Mem[-] .
Following from b), now assume that an array containing 10000 elements already ex-
ists in memory. The first location is stored in the variable old arr . current size
indicates the current size of the array, which currently is 10000 (the array is com-
pletely full). Implement OS++ code for a function:
int insertWhenFull(int old arr, int new elem) .
The goal of the above function is to allocate a new array of the appropriate size us-
ing void allocate memory(int n) (allocates n consecutive blocks in Mem[-] ),
copy all the elements of the old array into the new one, put the new element in-
side the new array, modify current size , and free the memory of the old array
using void free memory(int address) (frees all the allocated blocks starting
from address ). Assume old arr contains the address in Mem[-] of the old
array, and that new elem is the new element to be inserted. The function should
return the address of the new array. [6 marks]
– 2 – Turn OverA27544
No calculator
Question 2 Heaps and Sorting
(a) (i) Explain how selection sort works for an integer array. [4 marks]
(ii) Execute selection sort on the following array of integers 27, 6, 21, 24, 9, 15, 3.
For each iteration, show the content of the array, how the two parts of the
array are divided, and the element being selected at that iteration. [4 marks]
(b) (i) Explain the difference between a max-priority queue and a queue. [3 marks]
(ii) If you have a list of integers and you want to create a max-heap tree, will you
bubble the values up or down? Provide an informal explanation, stating the
complexity for the two options. [3 marks]
(c) Dr. Xavier has opened a new branch campus of his world renown academy, that
has very strict admission requirements in terms of GPA. To attract the first cohort
of students, he decided to award a scholarship to the best k students in terms of
GPA. Mr. Stark, who is providing the funds for the new campus, has been very
clear: he has only money for k scholarships, independent of the number of students
n Dr. Xavier will eventually receive. Dr. Xavier eventually received applications in a
random order, therefore the list of n students is not ordered by GPA.
Your task is to describe (in words and without necessarily providing the pseudo-code)
the type of algorithm you would need to implement partial sorting, which takes the
n students and finds the best k students in terms of GPA and ordered by GPA
(the remaining n − k students can remain unordered). Additionally, state the time
complexity of partial sorting algorithm, and justify your answer. [6 marks]
– 3 – Turn OverA27544
No calculator
Question 3 Hashtables and Graphs
(a) (i) Provide the definition of the following concepts: hash table, hash collision,
direct chaining, load factor. [4 marks]
(ii) Discuss what are the advantages and disadvantages of storing data in a hash
table. [4 marks]
(b) (i) A hash table is built as an array of size 10, using direct chaining. It stores
4-digit numbers, with the primary hash code given by the largest of the 1st and
the 3rd digit (from left to right). For example, the hash code for 1234 is given
by max(1, 3) = 3. The hash table is initially empty and the following numbers
are then inserted: 6392, 1233, 7483, 2345, 1293. Show the state of the hash
table after each insertion. [3 marks]
(ii) Is this a good or poor choice for a hash function? Discuss why [3 marks]
(c) Suppose you are given a graph and a starting node. Which algorithm would you
use and how would you modify it in order to find the k nodes that are most easily
reachable from the starting node? [6 marks]
– 4 – End of PaperA27544
This page intentionally left blank.
– 5 –A27544
Do not complete the attendance slip, fill in the
front of the answer book or turn over the
question paper until you are told to do so
Important Reminders
• Coats/outwear should be placed in the designated area.
• Unauthorised materials (e.g. notes or Tippex) must be placed in the
designated area.
• Check that you do not have any unauthorised materials with you
(e.g. in your pockets, pencil case).
• Mobile phones and smart watches must be switched off and
placed in the designated area or under your desk. They must not
be left on your person or in your pockets.
• You are not permitted to use a mobile phone as a clock. If you have
difficulty seeing a clock, please alert an Invigilator.
• You are not permitted to have writing on your hand, arm or other
body part.
• Check that you do not have writing on your hand, arm or other body
part – if you do, you must inform an Invigilator immediately
• Alert an Invigilator immediately if you find any unauthorised item
upon you during the examination.
Any students found with non-permitted items upon their person
during the examination, or who fail to comply with Examination
rules may be subject to Student Conduct procedures.
A27544 Fundamentals: Data Structures