Practice Midterm Exam CS 261 1. Given the following code: int main() { int i = 10000; int *p = &i; printf(“p = %p\n”, p); printf(“p+2 = %p\n”,p+2); return 0; } And given that the first half of the output is the following: p = 0x7ffee38eba64 What is the second half of the output? SOLUTION: The address would be the previous address plus 8, for the size of 2 ints. Given the last two digits, we have 64 + 8 = 6c because it goes 5,6,7,8,9,a,b,c for it to be 8 positions forward so that the hex code would be: p+2 = 0x7ffee38eba6c 2. What is the output of the following code: int* p; int length = 5; p = (int*)malloc(length * sizeof(int)); for(int i=0; i *(i+p) = i; } printf(“p[3] = %d\n”,p[3]); SOLUTION: The output would be as if the value was stored as p[i] because of pointer arithmetic and because i+p = p+i = p[i] as far as the compiler is concerned: p[3] = 3 3. What is the runtime of following code: int main() { int n = 10; for(int i = n; i > 0; i /= 2) { printf(“index = %d\n”,i); } return 0; } SOLUTION: The runtime is O(log2(n)) 4. What is the runtime of following code: int main() { int n = 10; for(int i = 1; i < n; i *= 2) { printf("index = %d\n",i); } return 0; } SOLUTION: The runtime is O(log2(n)) 5. What is the runtime of following code: int main() { int n = 10; for(int i = 0; i < n; i *= 2) { printf("index = %d\n",i); } return 0; } SOLUTION: This is an infinite loop because it is initialized at 0, and 0 *= 2 is still 0 6. What is best data structure to use to implement a double-ended queue (deque)? Why? SOLUTION: doubly linked list. I might add that a singly linked list would cost O(n) for “dequeue from back” operation, because accessing the second-to-last node would cost O(n) list traversal. 7. What is the worst data structure to use to implement a queue? Why? SOLUTION: I would guess a dynamic array because it would cost O(n) to enqueue (or dequeue depend on how it was implemented). Other implementations like linked list would take O(1) for these operations. 8. What is the average case time complexity of appending to a linked list? O(1) 9. What is the time complexity of reversing a linked list? O(n)
