Beijing-Dublin International College
__________________________________________
SEMESTER I FINAL EXAMINATION – 2018/2019 ___________________________________________
School of Computer Science COMP2002J Data Structures and Algorithms 1
HEAD OF SCHOOL: Pádraig Cunningham MODULE COORDINATOR: Lina Xu*
Time Allowed: 120 minutes
Instructions for Candidates
All questions carry equal marks. The distribution of marks in the right margin shown as a percentage gives an approximate indication of the relative importance of each part of the question.
BJUT Student ID: ________________ UCD Student ID: ________________
I have read and clearly understand the Examination Rules of both Beijing University of Technology and University College Dublin. I am aware of the Punishment for Violating the Rules of Beijing University of Technology and/or University College Dublin. I hereby promise to abide by the relevant rules and regulations by not giving or receiving any help during the exam. If caught violating the rules, I accept the punishment thereof.
Honesty Pledge:_____________________________________________ (Signature)
Instructions for Invigilators
Non-programmable calculators are permitted.
No rough-work paper is to be provided for candidates.
BDIC Semester One Academic Year (2017 – 2018)
Obtained score
10
Question 1: Stack
1. ArraybasedimplementedStack(size=10),whatthearrayshouldbelikeafter executing the following operations? (5 Marks) push(12); push(17); push(4); push(8); pop(); pop(); top(); push(1); push(7);
2. ForLinkbasedimplementedStack,whichofthefollowingoperationswill
successfully push Node N into the stack.
a. Nßtop;topßN;
b. N.nextßtop;topßN;
c. N.nextßtop;Nßtop;
d. topßN;N.nextßtop;
e. top ß N. next; top ßN;
The Node is implemented as follow: public class Node {
int data;
Node next;
public Node(int i){data = i;}
}
Question 2: List
(5 Marks)
Obtained score
20
a. Amongsinglelinkedlist,doublelinkedlistandarraybasedlist,whichimplementation is the most time efficient one when performing insertAfter()? Which implementation is the most time efficient one when performing insertBefore()? (4 Marks)
b. ArraybasedListisalistofArrPosobjects.WhatvaluesarestoredinArrPosandwhy
do we need them?
(2 Marks)
Page 2 of 5
BDIC Semester One Academic Year (2017 – 2018)
c. I have a set of Tasks that need to be finished. I have received those Tasks in a random order. I want to store all the related information about each task into a list. In the list, I wish to sort the Tasks in an increasing order according to their deadlines (days remaining). What you suggest me to do in order to achieve that? Present your answer
in Java Code. Supposedly you have class Task implemented already as below. public class Task {
int taskID;
int deadline; //days remaining to finish the task …
}
Question 3: Queue
(14 Marks)
Obtained score
20
a. Stack,QueueandListareallADT,whatarethefundamentaldifferencesbetween them in term of data access? (4 Marks)
b. In a circular array based queue (array size = 5), what the array will be like after performing the following instructions? What the outputs of those instructions? (6 Marks)
enqueue(5); enqueue(1); enqueue(7); enqueue(9); dequeue(); enqueue(3); enqueue(11); dequeue();
c. Link based Double ended queue is implemented based on Node class, which maintains
two references: next and pre. Implement addLast(int o) function in Java.
public class Node implements Position { private Object element;
Node next;
Node previous;
(10 Marks)
Page 3 of 5
BDIC Semester One Academic Year (2017 – 2018)
public Node(int e) { this.element = e; } public Object element() {return element; } }
Question 4: Map
a. How can you put an element v with a key value k to a double linked list based Map? What is the complexity? (5 Marks)
b. We can use an array of single linked list to implement Map. Describe how you can find an entry with a key value k. What is the complexity? (5 Marks)
c. There are two main types of collision handling strategies in Map. What are they and how do they work? (5 Marks)
Question 5: Sorting and Complexity
1. Sort the following complexity in big O notation from the fastest to the slowest. O(n!), O(1), O(n3), O(logn), O(n2), O(nlogn), O(n) (5 Marks)
2. Explain the reason why advanced sorting can be quicker than traditional sorting in your own word. (5 Marks)
3. If Radix sort is implemented based on Bucket Sort, how to determine how many times Bucket Sort will be executed? (5 Marks)
4. The best case of complexity for Quick Sort is O(nlogn) and the worst case is O(n2). Page 4 of 5
Obtained score
15
Obtained score
35
BDIC Semester One Academic Year (2017 – 2018)
Demonstrate the reason through examples. (5 Marks) 5. Suppose you have MergeSort implemented already. How you can implement
BucketSort based on MergeSort.
(15 Marks)
Page 5 of 5