CS 136 Elementary Algorithm Design and Data Abstraction - University of Waterloo Sample Final Examination.

Document Content and Description Below

University of Waterloo Sample Final Examination 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 dynamicall... y 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. 3 of 23 (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. 4 of 23 2. (6 points) Multiple Choice: Select the appropriate ADT. (a) (2 points) A movie theatre has created a points card, which allows frequent customers to gain movie points every time they buy a ticket. They need to keep track of how many points each customer has. Which ADT would be best suited for the task? a. Queue b. Stack c. Dictionary d. Set (b) (2 points) A web browser keeps track of the order in which you visit websites, and allows you to go back to previous pages in the reverse order you visited them. Which ADT should be used to store the pages? a. Queue b. Stack c. Dictionary d. Set (c) (2 points) You have been hired by a popular online store which sells merchandise to write software to keep track of their orders. They would like to complete their orders on a first-come-first-served basis; that is, orders are processed in the order in which they are received. Which ADT should you use for this? a. Queue b. Stack c. Dictionary d. Set 5 of 23 3. (6 points) Multiple Choice: circle the answer with the lowest correct upperbound. Consider the runtime in the worst case. (a) (2 points) What is the runtime of the following function in terms of n, where n is the length of lon? (define (list-max lon) (cond [(empty? lon) -inf.0] [(> (first lon) (list-max (rest lon))) (first lon)] [else (list-max (rest lon))])) a. O(n) b. O(n2) c. O(2n) d. O(n log n) (b) (2 points) What is the runtime of the following function in terms of n, where n is the string length of str? char lastletter(char *str) { char retval = '\0'; for (int i = 0; i < strlen(str); i++) { if (((str[i] >= 'a') && (str[i] <= 'z')) || ((str[i] >= 'A') && (str[i] <= 'Z'))) { retval = str[i]; } } return retval; } a. O(1) b. O(log n) c. O(n) d. O(n2) 6 of 23 (c) (2 points) What is the runtime of the following function in terms of n, where n is the length of lon? (define (part-sum lon) (cond [(empty? lon) 0] [(empty? (rest lon)) (first lon)] [(empty? (rest (rest lon))) (+ (first lon) (second lon))] [else (+ (first lon) (second lon) (third lon))]) a. O(1) b. O(log n) c. O(n) d. O(n2) [Show More]

Last updated: 2 years ago

Preview 1 out of 23 pages