Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 1 of 10


This exam paper must not be removed from the venue

Venue ____________________
Seat Number __________
Student Number |__|__|__|__|__|__|__|__|
Family Name ____________________
First Name ____________________


School of Information Technology and Electrical Engineering
EXAMINATION
Semester Two Final Examinations, 2021
COMP3506 Algorithms and Data Structures
This paper is for St Lucia Campus students.

Examination Duration: 120 minutes

Reading Time: 10 minutes

Exam Conditions:

This is a Closed Book examination - no written materials permitted
Any calculator permitted – unrestricted

During reading time (= planning time) - students are encouraged to
review and plan responses to the exam questions

This examination paper will be released to the Library

Materials Permitted In The Exam Venue:
(No electronic aids are permitted e.g. laptops, phones)

None.

Materials To Be Supplied To Students:

None.

Instructions To Students:

Additional exam materials (e.g. rough paper) will be provided upon
request.

Answer all questions.
For Examiner Use Only

Question

Mark





























































Total _________


Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 2 of 10
Multiple Choice Questions (10 marks. Marks distributed equally for each question.)
1. An algorithm is O(n2). It takes 20 sec for a given dataset. If twice as much data is
used, then:
◯ A. It will take 40 sec.
◯ B. It will take 80 sec.
◯ C. It will take 400 sec.
◯ D. The time it will take depends on whether the new dataset is the same
case as the initial dataset; average, best or worst case.
◯ E. None of the above.
2. Which of the following sorting algorithms has a possible worst-case running time of
O(n2) where n is the number of elements to be sorted?
◯ A. Merge-sort.
◯ B. Quick-sort.
◯ C. Selection Sort.
◯ D. A and C.
◯ E. B and C.
3. An important property of a doubly linked list compared to a singly linked list is the
ease of determining an item's predecessor. Which of the following operations can use
this property of a doubly linked list to the greatest advantage when compared with a
singly linked list? (Assume that the lists have head references but not tail
references.)
◯ A. Accessing an item.
◯ B. Adding an item at the front of the list.
◯ C. Deleting an item.
◯ D. Concatenating two lists.
◯ E. Copying a list.
4. Which of the following don’t affect the time complexity of bucket sort?
◯ A. The algorithm implemented for sorting individual buckets.
◯ B. The number of buckets used.
◯ C. The values to be sorted.
◯ D. None of the above.
◯ E. All of the above.
5. Which of the following data structures may be used to implement the Queue ADT such
that it provides amortised constant running time for all operations?
◯ A. An array.
◯ B. A singly-linked list.
◯ C. A doubly-linked list.
◯ D. A circularly linked-list.
◯ E. All of the above.
Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 3 of 10
6. Which of the following is the number of heaps with different key/node arrangements
that al l include the four keys 1, 2, 3 and 4?
◯ A. 2
◯ B. 3
◯ C. 4
◯ D. 5
◯ E. None of the above.

7. After inserting the keys 12, 25, 2, 32, 65 into a red-black tree, the resulting red-black
tree will have __ black nodes (Note: Null leaf nodes are not included.)
◯ A. 1
◯ B. 2
◯ C. 3
◯ D. 4
◯ E. None of the above.

8. Which of the following statements is correct, for a graph with n vertices and m edges?
◯ A. Topological sort can be applied to Directed Acyclic Graphs and can be
implemented using BFS.
◯ B. Topological sort can be applied to Directed Acyclic Graphs and can be
implemented using DFS.
◯ C. BFS can find the minimum number of edges between two vertices.
◯ D. A and C.
◯ E. All of the above.

9. To find the shortest paths to all other locations in a network from a given point,
which of the following algorithms are least applicable?
◯ A. Dijkstra’s.
◯ B. Floyd’s.
◯ C. Prim’s
◯ D. Kruskal’s
◯ E. B and C.


10. Which of the following is false about the string searching problem, where the pattern
has m characters, and the test has n characters?
◯ A. In many situations, the brute force string searching algorithm is sufficient.
◯ B. It is easy to code an implementation of brute force searching.
◯ C. The worst-case time complexity of brute force searching is O(m*n).
◯ D. None of the above.
◯ E. All of the above.





Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 4 of 10
Short Answer Questions (40 marks. Marks as indicated.)
Note: Answer each question in the box provided.
11. State the big-O complexity of the following recursive function with a short explanation.
(3 marks)



12. Is it possible for the amortised time complexity of an operation to be better than its worst-
case time complexity? In your answer describe what is meant by “amortised time
complexity”. Illustrate your answer with an example. (4 marks)

Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 5 of 10
13. Discuss the impact of choosing a pivot deterministically or randomly in quick sort. Hint:
For “Deterministic”, discuss how “always picking the last element as pivot” will affect the
worst-case time complexity. (4 marks)


14. We would like to sort 7 items, where each item is a 4-digit decimal number.
a) Briefly explain the maximum number of comparisons needed to sort these items
with a radix sort. (2 marks)
b) What would be the Big-Omega complexity to sort these items using an insertion
sort? (2 Marks)


Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 6 of 10
15. Given a pointer to the last node (rightmost node in bottom layer) of a complete binary tree,
describe how you would find its next adjacent node. That is, the next position where you
could insert and maintain a complete binary tree. Explain how the computational
complexity would differ between a linked list and an array-based representation.
(6 marks)





Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 7 of 10
16. Draw the splay tree at each stage after the elements 1, 2, 3, and 4 are added to an
initially empty splay tree.
(3 marks)


Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 8 of 10
17. There is a cycle in a linked list if there exists a node in the list that can be reached again
by continuously following the next pointer. An example of a cycle in a linked list is shown
below.
Design an efficient algorithm in pseudo code to detect if there is a cycle in a list of n
nodes, using a Hash Table. Provide the space and time complexity of your algorithm.
(5 marks)





Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 9 of 10
18. Would it be possible to employ Breadth First Search to find topological sorting of vertices
in a graph? If yes, write the algorithm in pseudo code, and explain it’s time complexity. If
not, provide the reason. (5 marks)


Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
Page 10 of 10
19. Using Huffman’s algorithm, construct a Huffman tree that defines an optimal prefix code
for the string “woolloomooloo”. Show the intermediate states of the priority queue.
(6 marks)




END OF EXAMINATION