Practice Questions

Introduction to Algorithms &

Programming II
Part of an old midterm

University of Windsor
School of Computer Science
Ryan Bluteau

READ ALL INSTRUCTIONS CAREFULLY.

1. This is a closed book test. No laptops, no books, no phones, no calculators, no
additional paper. Only a pen/pencil, eraser, and your ID should be with you.
2. Your full name and student ID number should be printed clearly on this page where
indicated below.
3. Do not remove any pages from this exam. Missing pages will void your exam and will
result in a grade of 0 for this exam.
4. You are not permitted to communicate with other students/people aside from the
instructor or GA/TAs for the course. You cannot receive any unauthorized help with
this exam. You cannot ask the GA/TAs for answers to an exam question. Otherwise,
as per the senate bylaws, you will be reported and the exam will be voided.
5. If multiple answers are provided to a question, the worst grade between all answers
is the final grade for that question. Multiple choice and fill-in-the-blanks style
questions receive 0 when provided multiple answers.
6. Unclear answers will receive partial or complete mark deductions depending on
severity.
7. The exam is 2 hours.
8. Good luck! Make sure to attempt all questions.

STATEMENT ON ACADEMIC INTEGRITY

I attest that all work in this exam is my own and completed independently without
unauthorized help.
First name:
Last name:
Student ID:

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 1 of 14
Question 1: Multiple Choice.

1A: For the following code fragment, what section of memory is variable “a” placed in?
Line 1: const int c = 42;
Line 2: int adder(int a, int b){
Line 3: return a + b;
Line 4: }
Line 5: int main(){
Line 6: int d = adder(4, 2);
Line 7: }
(a) Heap
(b) Stack
(c) Code line 2
(d) Global Data
(e) None of the above

1B: For the code referenced in question 1A, what section of memory is variable “c” placed
in.
(a) Heap
(b) Stack
(c) Code line 1
(d) Global Data
(e) None of the above

1C: For the code referenced in question 1A, when we compute the sum a+b on line 3 and
return, where is that sum stored in memory after returning?
(a) Heap
(b) Stack
(c) Code line 3
(d) Global Data
(e) None of the above

1D: For the code referenced in question 1A, which of the following best describes the stack
frame of ‘adder’ when called on line 6?
(a) R/A: adder Line 2, a:4, b:2, return a+b
(b) adder, a:4, b:2, return a+b
(c) adder, a:4, b:2, R/A: main:6
(d) adder, c:42, a:4, b:2, R/A: main:6
(e) adder, c:42, a:4, b:2, d:???, R/A: main:6

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 2 of 14
1E: Which of the following columns best describes the memory sections of a program?

Column A Column B Column C Column D Column E

Heap Stack Read-Only Data Global Data Code
Stack Code Global Data Heap Read-Only Data
Code Heap Stack Read-Only Data Global Data
Global Data Read-Only Data Code Stack Heap
Read-Only Data Global Data Heap Code Stack

(a) Column A
(b) Column B
(c) Column C
(d) Column D
(e) Column E

1F: Consider the code fragment below. For the options provided, which line produces an
error if placed on line 5, if any?
Line 1: int i = 42;
Line 2: int *P = &i;
Line 3: int * const * P2 = &P;
Line 4: int j = 5;
Line 5: ______________

(a) int ** const P3 = &P;

(b) j = **P2;
(c) **P2 = *P;
(d) *P2 = &i;
(e) None of the above

1G: Consider the code fragment below. For the options provided, which line produces an
error if placed on line 5, if any?
Line 1: int arr[5] = {1, 2, 3, 4, 5};
Line 2: int *p = arr;
Line 3: int **pp = &p;
Line 4: int value;
Line 5: ______________
(a) value = *p;
(b) value = *(p + 2);
(c) value = **pp;
(d) value = *((*pp)+2)
(e) None of the above

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 3 of 14
1H: Consider the code fragment below. How does Line 3 alect the array?
Line 1: int A = 20, B=15;
Line 2: int array[A][B];
Line 3: **array = 0;
(a) Initializes all array elements to 0
(b) Turns array into a NULL pointer
(c) Sets the first element of the array to 0
(d) Changes the array pointer from NULL to 0
(e) This generates an error

1I: For the code fragment below, what will be the output?
Line 1: int array[10];
Line 2: int main(){
Line 3: int array2[5] = {1};
Line 3: printf("%d - %d\n", array[0], array2[1]);
Line 4: }

(a) [Garbage Value] - 1

(b) [Garbage Value] - [Garbage Value]
(c) 0-0
(d) 0-1
(e) An error.

1J: Which of the following is an invalid array initializations:

(a) char array[3];
(b) char array[3] = {'c', 'a', 't'};
(c) int array[2] = {0, 0, 0};
(d) int array[3] = {0, 0};

1K: Which of the following is correct when accessing an integer array defined as an
uninitialized global array named ‘array’ with length 5?
(a) array[5];
(b) array[array[0]];
(c) array[0][0];
(d) array[‘a’];
(e) array[0.0];

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 4 of 14
Question 2: Short answers.

2A: Write a single line of code to create an integer array named “array” with length 3 and set
all its values to 1.

2B: Write a function prototype called “my_func” that returns a pointer to an integer and
accepts a one dimensional array of integers and its size. Use parameter names ‘array’ and
‘size’.

2C: Given the code fragment below, write a loop to initialize the array’s elements to ones
using the space provided. Use the square bracket notation when accessing arrays.
Line 1: int array[5][5];

Line 2: _______________________________________

Line 3: _______________________________________

Line 4: _______________________________________

2D: Give the code fragment referenced in question 2C, solve the same problem using pointer
notation to initialize the array to ones using the space provided.
Line 1: int array[5][5];

Line 2: _______________________________________

Line 3: _______________________________________

Line 4: _______________________________________

2E: Assume a randomly populated array that was defined as follows `int array[A][B];` where
A and B are integer values defining the size of the array dimensions. Assume you have a
function available to you, `void bubble_sort(int [], int size)`, which sorts a provided 1D array.
Write a for loop which sorts each of the rows of the array using the provided function.

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 5 of 14
Question 3: Medium-length answers.

3A: Make a function that implements binary search using recursion. No main function
required. Return -1 if not found, otherwise return the position of the found element.

3B: Make a recursive function that computes and returns `n!`. Recall the definition of
factorial as `n! = 1x2x…x(n-1)xn`. Consider the problem where we want to compute integers
larger than 4 bytes.

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 6 of 14
Question 4: Long Answer.

Given the program below, draw the memory stack when the Fibonacci function is called on
line 12. The stack frames should be clearly marked including all components within them.
Clearly mark the stack frames that get popped. Draw all stack frames until the final base
case is reached (before it returns).

1: #include <stdio.h>
2:
3: int fib(int n) {
4: if (n <= 1) {
5: return n;
6: }
7: return fib(n - 1) + fib(n - 2);
8: }
9:
10: int main() {
11: int n = 4;
12: printf("Fibonacci of %d is %d\n", n, fib(n));
13: return 0;
14: }

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 7 of 14
[More space for Question 4]

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 8 of 14
Question 5: Long Answer.
**** This question requires some knowledge about strings from Chapter 6 which is not
part of the upcoming Midterm ****
You are tasked to create a chessboard and some functionality. A diagram of how the
chessboard is set up is presented below, where:
- R = Rook
- N = Knight
- B = Bishop
- Q = Queen
- K = King
- P = Pawn
- Uppercase represents the opponent’s pieces
- Lowercase represents your pieces

R N B Q K B N R
P P P P P P P P
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
p p p p p p p p
r n b q k b n r

Complete a program with the following requirements:

(1) Create a main function that sets up a chessboard.
a. Create the chessboard using a character array.
b. No global variables are allowed.
c. Call the `rook_move` function (defined below) to move the piece from
position (3, 4) to (3, 7) (it is your turn). Assume this is mid-game and the
board could be in any state.
d. Confirm whether the piece moved (is a valid move) based on return.
(2) Implement a function `rook_move` that takes the chessboard, the current position
(r, c) of a rook, the new position (new_r, new_c), and a boolean user to determine the
turn (false = opponent, true = you). The function should:
a. Validate the piece is a rook ('R' or 'r') based on the user.
b. Validate the move according to the following rules:
§ The provided new position is dilerent from current position
§ The rook moves in a straight line [Hint: only row or column changes].
§ There are no pieces in the path.
§ If the destination has an enemy piece, capture it (delete) and move
the rook. [Hint: Determine if piece is capital or not (based on user).]
§ Note: If the destination has a friendly piece, the move is invalid.
c. Return a pointer to the current piece (rook) on success, or NULL on
error/invalid move.

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 9 of 14
[Space for question 5]

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 10 of 14
[Space for Question 5]

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 11 of 14
[Space for Question 5]

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 12 of 14
Question 6: Bonus Question. [OPTIONAL for bonus marks]

Queen Move Function:

This question is in reference to Question 5.

Assume you have a `bishop_move` function which operates on the ‘B’ or ‘b’ piece. It works
similarly to the rook with all the same requirements, however it only moves diagonally along
the board (anywhere diagonal from its current position compared to the rook that moves
anywhere horizontally/vertically from its current position). Now you have a way to move
rooks and bishops on the board.

Create the `queen_move` function. The queen can move like a rook and a bishop. So it can
take either the action of a rook or the action of a bishop. While there are many approaches
to code this move, we don’t want to duplicate the rook/bishop requirements and
functionality for the queen.

To do this, you need to reuse the prior functions `rook_move` and `bishop_move` for the
queen. The process is as follows (and must be followed):
(1) Convert the queen piece (if it is the queen) into a rook piece on the board. (Change
Q/q to R/r).
(2) Call the rook move function for the new R/r piece you created. The function should
return NULL on error/invalid move or the rook pointer on success.
a. If successful, use the returned pointer to change the R/r piece back to the
queen piece Q/q and return the pointer (queen piece).
(3) On failure, convert the rook R/r piece to a bishop B/b piece on the chessboard.
Then call the bishop move function.
a. If successful, use the returned piece and change the B/b piece to the
queen piece Q/q and return the pointer.
(4) On failure return NULL. Ensure you change the queen piece back to its original
state before returning (revert any changes).

This is an approach to move the queen without ever needing to code the requirements. Since
we completed all the work for the rook and bishop, the queen can simply reuse the functions
to make its move.

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 13 of 14
[Space for Question 6 – Bonus]

© 2024 Ryan Bluteau. Document cannot be distributed or duplicated. All rights reserved.

Page 14 of 14