SYSC 2006 Sample Final Exam
This sample exam contains questions from the Fall 2016, Winter 2017 and Fall 2017 final exams. The
format of the Fall 2018 exam is similar.
Page 1 of 22
SYSC 2006 Sample Final Exam
Question 1 [16 marks]
Put a checkmark, ✔, or an ✗, in the box, ⬜, beside the correct answer. For each part, 1 mark will be
awarded for selecting the correct answer and 0 marks will be awarded for selecting an incorrect answer.
0 marks will be awarded if you select more than one answer, even if one of your selections is correct.
(a) [1 mark] 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.
(b) [1 mark] 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.
(c) [1 mark] 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
(d) [1 mark] 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.
Page 2 of 22
SYSC 2006 Sample Final Exam
(e) [1 mark] 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 .
(f) [1 mark] 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.
Page 3 of 22
SYSC 2006 Sample Final Exam
(g) [1 mark] 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.
(h) [1 mark] 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 .
Page 4 of 22
SYSC 2006 Sample Final Exam
(i) [1 mark] 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 %d\n", *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.
(j) [1 mark] 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;
Page 5 of 22
SYSC 2006 Sample Final Exam
(k) [1 mark] 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
(l) [1 mark] Function no27 is passed an array containing n integers ( n >= 2 ). It should return t rue if
there are no instances of 2 immediately followed by a 7 ; otherwise it should return f alse . For example,
when nums is [2, 5, 7] the function should return t rue , but when nums is
[1, 2, 7, 4, 5] it should return f alse .
_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;
Page 6 of 22
SYSC 2006 Sample Final Exam
(m) [1 mark] 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).
(n) [1 mark] 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.
Page 7 of 22
SYSC 2006 Sample Final Exam
Parts (o) and (p) use these struct declarations:
typedef struct intnode {
int value;
struct intnode *next;
} intnode_t;
typedef struct {
intnode_t *top;
} stack_t;
(o) [1 mark] 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.
Page 8 of 22
SYSC 2006 Sample Final Exam
(p) [1 mark] 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.
Page 9 of 22
SYSC 2006 Sample Final Exam
Question 2 [14 marks]
(a) 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 mystery\n");
}
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. (7 marks)
Stack Heap
Page 10 of 22
SYSC 2006 Sample Final Exam
(b) 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:%d\n",
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 .
On the following page , 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 . (7 marks)
Page 11 of 22
SYSC 2006 Sample Final Exam
Stack Heap
Page 12 of 22
SYSC 2006 Sample Final Exam
Question 3 [9 marks]
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)
{
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
Continue your solution on the next page.
Page 13 of 22
SYSC 2006 Sample Final Exam
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
}
Page 14 of 22
SYSC 2006 Sample Final Exam
Question 4 [4 marks] 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 page depict the 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.)
Page 15 of 22
SYSC 2006 Sample Final Exam
_____________________________________________________________ // Step 1
_____________________________________________________________ // Step 2
______________________________________________________________ // Step 3
______________________________________________________________ // Step 4
Page 16 of 22
SYSC 2006 Sample Final Exam
Question 5 [12 marks]
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.
On the following page , complete the definition of remove_odds .
Page 17 of 22
SYSC 2006 Sample Final Exam
intnode_t *remove_odds(intnode_t *head)
{
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
If necessary, continue your solution on the next page.
Page 18 of 22
SYSC 2006 Sample Final Exam
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
}
Page 19 of 22
SYSC 2006 Sample Final Exam
Question 6 [5 marks]
In the last panel of this Foxtrot cartoon, Marcus is referring to the Perrin sequence, which is defined by
the recurrence relation:
(0)P = 3
(1)P = 0
(2)P = 2
(n) (n ) (n ); n P = P − 2 + P − 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.
On the following page , write a recursive function named Perrin that calculates and returns P ( n ). An
iterative function will receive 0 marks . The function should assume that n is a nonnegative integer; in
other words, it shouldn't check if n is negative.
Page 20 of 22
SYSC 2006 Sample Final Exam
int Perrin(int n)
{
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
_______________________________________________________________________________
}
Page 21 of 22
SYSC 2006 Sample Final Exam
Selected Functions from the C Standard Library
assert.h
assert( expression );
If expression evaluates to true , assert does nothing. If expression evaluates to false ,
assert causes the program to display information and terminate. The information displayed
includes the text of the expression, the name of the source file, the source line, and the name of
the enclosing function.
stdlib.h
void *malloc(int size);
Allocates a block of memory with the specified size from the heap and returns a pointer to the
block. Returns the NULL pointer if the block cannot be allocated.
void free(void *ptr);
Causes the memory pointed to by ptr to be deallocated (made available for subsequent
allocation by malloc ). The function does nothing if ptr is NULL . The behaviour of this function
is undefined if ptr is not a pointer that was previously returned by malloc . The behaviour of
this function is undefined if the memory pointed to by ptr was previously deallocated by a call
to free .
Page 22 of 22