SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion | Answered Latest 2026.

SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 1 of 16 Select the best answer: At the start of a lab, students download the lab handout and source code files from cuLearn. Which of the following collections should the cuLearn server software use to ensure that download requests are processed in the same order in which they are received? ! A stack. ! A queue. ! A list. Which of the following collections would be the best choice when designing the software that implements the "undo" operation in a text editor. ! A stack. ! A queue. ! A list. In two labs, you implemented a list collection that used a dynamically allocated array as the underlying data structure. Could this collection be redesigned to use a circular, singly-linked list as its underlying data structure? (Recall that, in another lab, you used this type of linked list to implement a queue.) ! Yes ! No A stack's pop operation: ! Inserts an item at the bottom of the stack. ! Inserts an item at the top of the stack. ! Inserts an item at the specified position in the stack ! Returns the item at the top of the stack, but doesn't modify the stack. ! Returns the item at the bottom of the stack, but doesn't modify the stack. ! Returns the item at the specified position in the stack, but doesn't modify the stack. ! Removes and returns the item at the top of the stack. ! Removes and returns the item at the bottom of the stack. ! Removes and returns the item at the specified position in the stack.SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 2 of 16 Suppose s points to a stack that stores integers. Functions that provide push, peek and pop operations have been defined. The following statements are executed, starting with an empty stack: push(s, 10); push(s, 20); push(s, 30); int i = peek(s); int j = pop(s); push(s, 40); int k = pop(s); int m = pop(s); What is the value of m after these statements are executed? ! 10 ! 20 ! 30 ! 40 ! None of the above. Suppose q points to a queue that stores integers. Functions that provide enqueue, dequeue and front operations have been defined. The following statements are executed, starting with an empty queue: enqueue(q, 10); enqueue(q, 20); enqueue(q, 30); int w = dequeue(q); int x = front(q); enqueue(q, 40); int y = dequeue(q); int z = dequeue(q); What is the value of z after these statements are executed? ! 10 ! 20 ! 30 ! 40 ! None of the above.SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 3 of 16 Suppose all of the heap is available to a C program. The program allocates an array on the heap. Every time the array is filled to its capacity, the program allocates a new array that is twice the size of the original, copies all the elements from the original array to the new array, then deallocates the original array. What is the maximum size of the program's array (approximately)? ! 25% of the heap. ! 33% of the heap. ! 50% of the heap. ! 66% of the heap. ! 75% of the heap. ! 100% of the heap. What does this code fragment do? int *arr = malloc(sizeof(int) * 4); // Initialize array to {1, 2, 3, 4} arr[0] = 1; arr[1] = 2; arr[2] = 3; arr[3] = 4; int *ptr = &arr[0]; arr = arr + 1; free(ptr); ! It frees the first element of the array, and adjusts arr so that it point to the element that contains 2. (The array now contains 2, 3 and 4). ! It adds 1 to the first element of the array (so the array now contains 2, 2, 3 and 4), then frees variable ptr. ! It frees the entire array. ! It may damage the heap, because the pointer passed to free isn't a pointer that was returned by malloc.SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 4 of 16 What does this program print? void mystery(int *var1, int *var2) { int *temp = malloc(sizeof(int)); assert(temp != NULL); *temp = *var1; *var1 = *var2; *var2 = *temp; } int main(void) { int *x = malloc(sizeof(int)); assert(x != NULL); *x = 50; int *y = malloc(sizeof(int)); assert(y != NULL); *y = 100; mystery(x, y); printf("%d %dn", *x, *y); return 0; } ! 50 50 ! 50 100 ! 100 50 ! 100 100 ! Nothing. The program has syntax errors, so it won't compile. ! We can't determine what is printed, because the program has a bug. Consider this code fragment: int *arr = malloc(sizeof(int) * 100); arr[10] = 7; Which of these statements does the same thing as arr[10] = 7; ? ! *(arr + 10) = 7; ! *arr + 10 = 7; ! *(arr + 10 * sizeof(int)) = 7; ! arr + 10 = 7;SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 5 of 16 This loop iterates over an array named arr containing n integers. What are the missing statements in the for loop? int sum = 0; int *p; for(p = arr; ________ _______) { // complete this line sum += *p; } ! p != NULL; p += 1 ! p != NULL; p = p-next ! p-next != NULL; p = p-next ! p n; p += 1 ! p != arr + n; p += 1 Function no27 is passed an array containing n integers (n = 2). It should return true if there are no instances of 2 immediately followed by a 7; otherwise it should return false. For example, when nums is [2, 5, 7] the function should return true, but when nums is [1, 2, 7, 4, 5] it should return false. _Bool no27(int nums[], int n) { for (int i = 0; i n-1; i += 1) { if (nums[i] == 2 && nums[i+1] == 7) { return false; // line 1 } else { // line 2 return true; // line 3 } } return true; // line 4 } What changes, if any, should be made to this function? ! The function is correct, so don't change any code. ! Switch line 1 and line 3; that is, change line 1 to return true; and line 3 to return false; ! Delete line 2 and line 3. ! Delete line 4. ! Change line 4 to return false;SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 6 of 16 Function silly is passed an array containing n integers (n = 2). What does it do? _Bool silly(int nums[], int n) { int current = 1; _Bool flag = true; while (current n && flag) { if (nums[current] nums[current-1]) { flag = false; } current = current + 1; } return flag; } ! Sorts the integers in array nums into ascending (increasing) order. ! Sorts the integers in array nums into descending (decreasing) order. ! Returns true if the integers in array nums are sorted in descending (decreasing) order. ! Returns true if the integers in array nums are sorted in ascending (increasing) order. ! Returns false if the integers in array nums are sorted in descending (decreasing) order. ! Returns false if the integers in array nums are sorted in ascending (increasing) order. ! None of the above (the function has a bug). The nodes in this linked list are instances of a struct that has two members, value (which stores an integer) and next (which stores a pointer to the next node). The statement curr-next-next-value = 5; ! replaces the 10 with 5. ! replaces the 20 with 5. ! replaces the 30 with 5. ! replaces the 40 with 5. ! inserts a new node containing 5 into the linked list. ! changes the capacity of the linked list to 5. ! has undefined behaviour, because it dereferences a NULL pointer. struct declarations used below: currSYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 7 of 16 typedef struct intnode { int value; struct intnode *next; } intnode_t; typedef struct { intnode_t *top; } stack_t; Consider this implementation of a stack's pop operation: int pop(stack_t *stack) { int popped; intnode_t *node_to_delete; assert(stack != NULL); assert(stack-top != NULL); node_to_delete = stack-top; stack-top = stack-top-next; popped = stack-top-value; free(node_to_delete); return popped; } ! A. The function correctly implements the pop operation. ! B. The function will not compile. ! C. The function returns the wrong value. ! D. The function frees the wrong node. ! E. When the function returns, stack-top contains NULL. ! Both C and D. ! Both C and E. ! Both D and E. ! All of C, D and E.SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 8 of 16 Consider this implementation of a stack's pop operation: int pop(stack_t *stack) { int popped; intnode_t *node_to_delete; assert(stack != NULL); assert(stack-top != NULL); popped = stack-top-value; stack-top = stack-top-next; node_to_delete = stack-top; free(node_to_delete); return popped; } ! A. The function correctly implements the pop operation. ! B. The function will not compile. ! C. The function returns the wrong value. ! D. The function frees the wrong node. ! E. When the function returns, stack-top contains NULL. ! Both C and D. ! Both C and E. ! Both D and E. ! All of C, D and E.SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 9 of 16 In two labs, you developed a C module that implements a list collection. It used a struct and a dynamically allocated array as the underlying data structure. Here is the declaration of the list's "type": typedef struct { int *elems; // Points to the list's backing array. int capacity; // Maximum number of elements in the list. int size; // Current number of elements in the list. } intlist_t; A function named intlist_take takes two arguments, a pointer to a list and an integer: int *intlist_take(intlist_t *list, int n); This function returns a pointer to a new array (not a list) that has room for exactly n integers. The function removes the first n elements from the list, and stores them in the new array. For example, suppose parameter list points to a list containing [3, 2, 5, 7, 8, 2] and parameter n equals 4. The function will return a new array containing [3, 2, 5, 7]. The list now contains [8, 2]. The function must terminate (via assert) if it is passed a NULL pointer or if n is nonpositive or if the list contains fewer than n elements. Your intlist_take function can call functions from the C standard library (see the crib sheet at the end of this question paper); however, it cannot call any functions from the list module you developed in the labs; e.g., intlist_construct, intlist_append, etc. Complete the definition of intlist_take: int *intlist_take(intlist_t *list, int n) { ... }SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 10 of 16 Linked List Here is the declaration of a struct for the nodes in a singly-linked list: typedef struct intnode { int value; struct intnode *next; } intnode_t; Variables head and tail are declared this way: intnode_t *head; intnode_t *tail; Here is a picture of a singly-linked list that contains the integers 10, 20, 30, 40, and 50, in that order: Variables head and tail point to the first and last nodes in the list. When we "rotate" the nodes one position to the left, the node containing 20 becomes the node at the head of the linked list, and the node containing 10 becomes the node at the tail of the linked list, as shown here: The diagrams on the following pages depict the step-by-step execution of the four C statements that rotate this linked list. Each step corresponds to the execution of one statement; however, the statements have been replaced by ruled lines. For each step, write the missing C statement on the ruled line. (In other words, write the C statement that transforms the linked list shown above the ruled line into the linked list shown below the ruled line.) 50 head tail head tailSYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 11 of 16 _____________________________________________________________ // Step 1 _____________________________________________________________ // Step 2 ______________________________________________________________ // Step 3 50 head tail Original List 50 head tail 50 head tail 50 head tailSYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 12 of 16 ______________________________________________________________ // Step 4 50 head tail 50 head tail Rotated list (This is the same as the diagram at the bottom of the previous page.)SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 13 of 16 Linked Lists Here is the declaration of a struct for the nodes in a singly-linked list: typedef struct intnode { int value; struct intnode *next; } intnode_t; A function named remove_odds takes one argument, a pointer to a linked list in which 0 or more nodes contain odd integers: intnode_t *remove_odds(intnode_t *head); The function removes all the nodes containing odd integers from the linked list. The remaining nodes (the ones containing even integers) must remain in the same order that they appear in original linked list. The function returns a pointer to the first node in the modified linked list. For example, suppose variable my_list points to this linked list: and remove_odds is called this way: my_list = remove_odds(my_list); After remove_odds returns, the modified list looks like this: remove_odds should return an empty linked list if it passed an empty linked list or if all the nodes contain odd integers. Your remove_odds function can call functions from the C standard library (see the crib sheet at the end of this question paper); however, it cannot call any of the linked list functions that were developed in lectures and labs. No marks will be awarded for a solution that allocates new nodes or copies values from one node to another. Marks will be deducted for code that performs more traversals of the linked list than are necessary. Complete the code for remove_odds. intnode_t *remove_odds(intnode_t *head) { ... } my_list 3 8 4 5 3 6 7 2 1 my_list 8 4 6 2SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 14 of 16 Memory Diagrams Trace the execution of this program: void mystery(int a[], int n) { int *copy = a; copy[1] = a[n - 1] - a[2]; // Line A printf("About to leave mysteryn"); } int main(void) { int arr[] = {3, 5, 8, 4, 18, 6, 12}; mystery(arr, 7); return 0; } Draw a memory diagram similar to one that would be produced by the C Tutor immediately after the assignment statement at Line A has been executed, but before printf is called. Clearly identify the stack and the heap. Trace the execution of this program: typedef struct { int minutes; int seconds; } timer_t; timer_t *create_timer(int minutes, int seconds) { timer_t *timer; timer = malloc(sizeof(timer_t)); assert(timer != NULL); timer-minutes = minutes; timer-seconds = seconds; return timer; } void count_up(timer_t *timer) { timer-seconds = timer-seconds + 1; if (timer-seconds == 60) { timer-seconds = 0; timer-minutes = timer-minutes + 1; } // if statement was executed, // about to call printf printf("The time is %d:%dn", timer-minutes, timer-seconds); } int main(void) { timer_t *timer1 = create_timer(1, 0); for (int i = 1; i = 90; i++) { count_up(timer1); } return 0; } The for loop in main calls function count_up multiple times. This question deals with the program's state during the last iteration of the loop, after the final call to count_up. Draw a memory diagram similar to one that would be produced by the C Tutor after the if statement has been executed and immediately before printf is called, when count_up is executing for the final time. Don't show the output displayed by printf. Clearly identify the stack and the heap.SYSC 2006 Sample Exam Questions: Pointers, Arrays, Stacks, Queues, and Linked Lists, plus Memory Diagrams and Recursion Page 15 of 16 Recursion In the last panel of this Foxtrot cartoon, Marcus is referring to the Perrin sequence, which is defined by the recurrence relation: !(0) = 3 !(1) = 0 !(2) = 2 !(") = !(" # 2) + !(" # 3); " % 3 An interesting fact: if n is a prime number, then P(n) is divisible by n; for example, P(19) = 209 and 209/19 = 11. Write a recursive function named Perrin that calculates and returns P(n). An iterative function will receive no marks. The function should assume that n is a nonnegative integer; in other words, it shouldn't check if n is negative. int Perrin(int n) { ... }