• 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]

(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]