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