University of Waterloo
CS 234
CS234 Data Types and Structures
Spring 2015
Question 1: Multiple Choice Questions [marks 10]
1. (b) Python dictionary
2. (c) Tree
3. (c) Quick sort
4. (b) Recursive
5. (d) push
6. (b) False
7. (d) DCBA
8. (a) ABCD
9. (d) Dequeue
10. (d) Both change.
Question 2: Python Answers [9 marks]
(a) 3.5 [1 mark]
...[Show More]
CS234 Data Types and Structures
Spring 2015
Question 1: Multiple Choice Questions [marks 10]
1. (b) Python dictionary
2. (c) Tree
3. (c) Quick sort
4. (b) Recursive
5. (d) push
6. (b) False
7. (d) DCBA
8. (a) ABCD
9. (d) Dequeue
10. (d) Both change.
Question 2: Python Answers [9 marks]
(a) 3.5 [1 mark]
(b) Hello [2 marks]
Question 3: Short Answers [10.5 marks]
(a) What is a precondition and postcondition? [4 marks]
• Postconditions
(b) State two main differences between array and python list (array-based list)? [2 marks]
(c) What data structure implements LIFO behaviour? [1 mark]
(d) What requirement must an array meet before we can use binary search on it? List two
algorithms we might use to get an array into this required format. [2 marks]
(e) Consider the linked list implementation discussed in class. [1.5 mark]
Question 4: Complexity [19 marks]
(a) Define O(f(n)). [3 marks]
See definition in the slides. Alternative explanation: There is some input size such that if
the algorithm is provided with an input larger than that input size, say m, it performs at
most cf(m) steps.
Answer can be in the form: Formal definition, English, Draw and comment a picture
(b) Describe the worst case running time of the following functions [6 marks]
(c) For each of the functions f(n) given below [5 marks]
(d) What is the complexity of the following operations? [5 marks]
Answer can be in the form: description, drawing and commenting a picture
(i) Pushing a value onto a stack containing n values, implemented as a link list.
(ii) Pre-order traversal of a Perfect Binary Tree containing n elements
(iii) Finding (but not removing) the top value in a stack containing n elements.
(iv) Searching a target in linked list with n elements.
(v) Pushing a value onto stack implemented using python list.
Consider implementation of a linked list discussed in class. Implement find(self, target).
The function returns the position of the target in a linked list or None if it is not
present. Do not modify the methods that are shown as already implemented (i.e., you
cannot modify attributes in any of the classes). [9 marks]
[Show Less]
-preview.jpeg)
-preview.jpeg)
