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
