University of Waterloo

• CS 136

• 1 (8 points) Multiple Choice: circle the most correct answer. (a) (2 points) What strategy can we use to amortize our run-time when dynamically allocating memory? (a) Wrapper Strategy (b) Functional Strategy (c) Augmentation Strategy (d) Doubling Strategy Doubling Strategy (b) (2 points) What is the difference between a C string and an array of chars in C? (a) C Strings are always stored in read-only memory, whereas an array of chars do not have this restriction (b) An array of chars cannot be initialized using the double quote syntax (i.e. char a[] = "Hello, World"). (c) An array of chars stores its length. (d) C strings are null terminated. (e) There is no difference C strings are null terminated (c) (2 points) Which approach permits us to write an O(1) add to back function for a singly linked list? (a) Use the augmentation strategy (b) Use recursion in our add to back function (c) Use iteration in our add to back function (d) Use the wrapper strategy Use the wrapper strategy (d) (2 points) What approach would be able to determine the height of the BST in O(1) time? (a) Augment the BST node to store the height of the subtree and increase it during each insertions. (b) Recurse through the longest subtree (c) Count the number of items store in the tree, returning log2(n) + 1 where n is the number of items stored (d) It is not possible to implement a O(1) height function for a BST. Augment the BST node to store the height of the subtree and increase it during each insertions