University of Waterloo

• CS 136

• Student Signature: UW Student ID Number: Number of Exam Pages 23 pages (including this cover sheet) Exam Type Closed Book Additional Material Allowed NO ADDITIONAL MATERIALS ALLOWED Marking Scheme (for graders’ use only) Question Max Score Grader 1 8 2 6 3 6 4 35 5 6 Maximum Total Score: 131 Question Max Score Grader 6 10 7 10 8 10 9 15 10 25 Total Score: Instructions: Exam instructions. CS 136 Sample Final Examination Winter 2015 Page 2 of 23 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 (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) (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