Semester Two Final Examinations, 2021 COMP3506/7505 Algorithms and Data Structures
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/7505 Algorithms and Data Structures
This paper is for External 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 _________
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.
6. Which of the following is the number of heaps with different key/node arrangements that all 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.
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)
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)
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)
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)
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)
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)
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)
20. If you needed to make any assumptions to complete the questions on this exam, please list them below. Ensure you indicate the questions each assumption applies for.
(0 marks)
END OF EXAMINATION
Page 11 of 11