Instructions Please print
Answer all questions on this paper in
the spaces provided.
No aids, including calculators, are
permitted.
All
... [Show More] solutions must be placed in this
booklet.
If you need more space to complete
an answer, you may be writing too
much. However, if you need extra
space, use the extra blank pages at the
end of the exam clearly labeling the
question and indicate that you have
done so in the original question.
First Name: _______________________
Last Name: _______________________
Student ID: _______________________
Section: __________________________
Questions: 1 2 3 4 5 6 7 8 9 10
Mark:
Question: 11 12 13 14 15 16 17 18 19 20
Mark:
Total (out of 30):
PART 1 – Multiple Choice – 6 marks
1. [1 mark] Which of the following statements is NOT correct about the Abstract Data Types
(ADTs)?
a) In designing an ADT, we focus on what the ADT can do, not how it does it.
b) ADTs are implementation independent; that is, implementation details are hidden.
c) ADT operations can be grouped into four categories constructors, accessors, mutators and
iterators.
d) One reason for using ADTs is that we can focus on implementation instead of functionality.
2. [1 mark] What is the output of the following arithmetic calculation in Python:
20 * 2 + 8 // 4
a) 50.0
b) 42.0
c) 12.0
d) 60.0
3. [1 mark] What is the result of executing the following two statements:
print(str(10 + 10))
print(str(10) + str(10))
a) 20, 20
b) 20, 1010
c) 1010, 1010
d) 1010, 20
4. [1 mark] Assuming that n is the input parameter, which of the followings correctly lists the
expressions from lowest to highest asymptotic growth rate?
a) n * log(log n), n * log n, n3/2, 22015
b) 22015, n * log(log n), n3/2, n * log n
c) 22015, n * log n, n * log(log n), n3/2
d) 22015, n * log(log n), n * log n, n3/2
5. [1 mark] Which statement is NOT correct?
a) Stack is a LIFO data structure.
b) We can implement the pop() operation of the Stack using singly linked list such that its
running time will be O(1) time.
c) When implementing the Stack ADT using linked list, at least one of the pop()or
push(item) operations will be always O(n) time, where n is the size of the Stack.
d) The Stack ADT is a better choice than the Queue ADT to solve the balanced delimiters
problem (opening and closing curly braces or parentheses in expressions or codes).
6. [1 mark] Which of the following data structures is the most suitable to keep track of the patients
visiting a dentist office, where the patients will visit the dentist in a first-come, first-served fashion.
a) Stack b) Queue
c) Linked list d) Python list
7. [1 mark] Suppose that we have a singly-linked list myList, and an external variable curNode
that is referring a node in the middle of myList. Moreover, let preNode be the node immediately
before curNode in myList. Which of the following code fragments correctly removes curNode
from the list and returns it?
a) curNode.next = preNode.next
curNode.next = None
return curNode
b) preNode.next = curNode.next
curNode.next = None
return curNode
c) curNode.next = None
preNode.next = curNode.next
return curNode
d) preNode.next = None
curNode.next = preNode.next
return curNode
8. [1 mark] The best-case and worst-case running times of function append(item) of a Python list
with size n are _______________ and _______________ time, respectively.
a) O(1), O(1) b) O(1), O(n)
c) O(n), O(n) d) O(n), O(1)
9. [1 mark] You are given an unsorted array of n integer values. Using the Binary Search Algorithm,
what is the worst-case time complexity of finding the largest value?
a) O(log n)
b) O(n)
c) O(n log n)
d) It is not possible.
10. [1 mark] Which of the following algorithms does NOT use [Show Less]