Final (AY22/23)
Problems
Question paper without answers:
Question paper with answers:
5. Recursion
In this question, every time we need to make two recursive calls. So, we need to think both cases to decide how we can modify to make the recursion finite!
6. Memory Leak
Whenever you call a malloc(), always be careful not to point the pointer to else where. This will cause memory leak!
7. Multi-dimensional Array Decay
See Array Name Decay (Multidimensional Array) for more detail information. But this statement is pretty useful:
Since an array in C consists only of a contiguous region of memory that stores the elements of the array, the address of an array is the same as the address of the first of the array.
With this information, image + 1, first, use the knowledge of Pointer Arithmetic, the pointer image points to an array of long *, so +1 will move it to the second row. So, it has the type as the second row (an array) and its value is the address of the first long in the row.
However, &image[1][0], &image[0][1], &image[1][1] all have the type as a long, which is not an array. For image[0] + 1, it has the , and its value is the second long in the first row! Wrong also.
For the correct answer &image[1], firstly, image[1] is of type long, but add & operator will change it to type "array". So, now it is of type array (second array) and has value of the address of the first element in the second row.
8. Illegal Memory Access
This is a trickly question in the final paper. Illegal Memory Access needs to satisfy two requirements:
the memory address is Illegal (NULL and the examples in 9. Illegal Memory Access which appears in Final (AY20/21))
you try to the memory address
In this the code below:
list[0] = calloc(ncols * nrows, sizeof(long));
for (size_t i = 1; i < nrows; i += 1)
{
list[i] = list[i - 1] + ncols;
}If list[0] is NULL, as long as we don't access its memory address (read/write), we are not doing anything illegal. (See this question)
15. Recursion
The official solution for this problem is awesome!
bool can_sum_to (long a[], size_t i , size_t n, long q)
{
if (q == a[i])
{
return true;
}
if (i >= n - 1)
{
return false;
}
return can_sum_to(a, i + 1, n, q) || can_sum_to(a, i + 1, n , q - a[i])
}
For the recursion part, it utilises the idea that we can narrow our list range by either using the a[i] to try forming our sum or not using the a[i] to form our sum.
For the base case, every time we check whether our "updated" q is equal to the first element or not, if it is, means we can find one such combination that sums to q in the list. Otherwise, if the range of the list is 0 or negative, means that we cannot find such a combination.
The recurrence relation is . And use the basic knowledge of geometric sequence, we can get .
16. Call Stack Diagram
The quesition is to draw the stack diagram for the following code:
void qux(long **ptrptr, long *numptr2)
{
long *numptr1 = numptr2;
*ptrptr = numptr2;
*numptr1 = 57;
// Line X
}
void baz(long **ptrptr, long *numptr)
{
qux(ptrptr, numptr);
}
int main()
{
long *ptr;
long num = 1;
baz(&ptr, &num);
}
The answer should be:
The most important thing to note is inside baz() to call qux(), we are actually passing the address of the num and ptr in the main()! So the pointer should point to these two variables in the main(), instead of pointing to the temp variable in the baz()!
Tips
Include the five Array Name Decay (Multidimensional Array) examples in the cheatsheet and include the small observation behind the examples into the cheatsheet also.
Last updated