THE HONG KONG POLYTECHNIC UNIVERSITY DEPARTMENT OF COMPUTING EXAMINATION
Course: 61431
Subject:COMP1011 Programming Fundamentals
Group: 2011
Session: 2019/2020, Semester 2
Date: 25 May 2020 Time: 12:30 – 14:30
Time Allowed: Two hours Subject Lecturer: Dr. Jesper JANSSON
The question paper has 7 pages, including this cover page.
Instructions to Candidates:
This is an online examination. To submit your answers to the six questions, put them in six separate files named:
• “E-1-99999999Z.txt” or “E-1-99999999Z.pdf”, • “E-2-99999999Z.c”,
• “E-3-99999999Z.txt” or “E-3-99999999Z.pdf”, • “E-4-99999999Z.txt” or “E-4-99999999Z.pdf”, • “E-5-99999999Z.c”,
• “E-6-99999999Z.c”,
(replacing “99999999Z” above by your student ID number) and upload them to Black- board before the submission deadline. Late submissions will not be accepted. You are not allowed to discuss the examination questions or your solutions with other people until after the deadline. The maximum possible score is 100 marks.
1
1. (a)
Let S1 and S2 be the following two statements written in the C programming language:
S1: x -= y;
S2: x =- y;
where x and y are variables of type int. Under what circumstances will statement S1 assign the same value to x as statement S2? (5 marks)
(b) Suppose that a is an array of 20 elements and that the ten elements a[3], a[4], . . . , a[12] need to be copied to a[5], a[6], . . . , a[14]. The C program code shown below does not give the desired result:
Explain what the issue is and how to fix it. (5 marks)
(c) Give an example of when it can be useful for a programmer to include two pointers to variables of type int in a C function’s parameter list. (5 marks)
size_t index_source = 3; size_t index_destination = 5; size_t i;
for (i = 0; i < 10; i++)
a[index_destination + i] = a[index_source + i];
2
2. Write a C program that:
(a) First seeds the random number generator with the current time using srand(time(NULL)). Then, asks for an integer between 1 and 9 until the user inputs an integer x in this range. (5 marks)
(b) Next, generates and prints an x-digit number y according to the rule that for every integer i with 1 ≤ i ≤ x, the ith digit (from left to right) of y is a random integer between 1 and i. The program should use a variable of type long to represent y, and call the rand()-function x times to obtain the individual digits of y. (5 marks)
(c) Finally, if y has any triplicate digit (i.e., a digit that occurs at least three times), prints the largest such digit. Otherwise, let it print a message saying that the generated number has no triplicate digits. (10 marks)
Sample program output 1:
Please input an integer between 1 Please input an integer between 1 Please input an integer between 1 Please input an integer between 1 Please input an integer between 1 The generated number is: 11334613 Its largest triplicate digit is: 3
Sample program output 2:
Please input an integer between 1 The generated number is: 12142
It has no triplicate digits.
and 9: 1011 and 9: 2020 and 9: -88 and 9: 0 and 9: 8
and 9: 5
3
3. Recall the Tower of Hanoi problem from Lecture 5 (Exercise 5.36 in the textbook):
There are three pegs and n disks of different sizes. Initially, all disks are on the leftmost peg and arranged in order of decreasing size, with the smallest disk on top. The task is to move all the disks to the rightmost peg, under the constraints that:
• Only one disk can be moved in each step; and
• A larger disk may never be placed on top of a smaller disk.
The C program below outputs a sequence of moves that solves the Tower of Hanoi problem:
#include
void tower_of_Hanoi(int n, char pegFrom , char pegExtra , char pegTo);
int main(void) {
int n;
printf(“Please input number of disks: “); scanf(“%d”,&n);
tower_of_Hanoi(n, ’A’, ’B’, ’C’);
}
// Recursively move n disks from pegFrom to pegTo, using pegExtra. void tower_of_Hanoi(int n, char pegFrom , char pegExtra , char pegTo) {
if (n > 0) {
tower_of_Hanoi(n-1, pegFrom, pegTo, pegExtra); printf(“Move disk #%d: %c –> %c\n”, n, pegFrom, pegTo); tower_of_Hanoi(n-1, pegExtra , pegFrom , pegTo);
} }
(a) In the function tower_of_Hanoi, what happens in the base case of the recursion? (5 marks) (b) Is it possible for some other C program to output shorter valid sequences of moves for the
Tower of Hanoi problem than the program shown here? Justify your answer. (10 marks)
4
4. Consider the C function display32BitPattern, based on displayBits from Chapter 10.9 in the textbook:
void display32BitPattern(unsigned long value, char fillCharacter) {
unsigned long displayMask = 1; displayMask <<= 31;
unsigned int c;
for (c = 1; c <= 32; ++c) {
putchar(value & displayMask ? fillCharacter : ’ ’);
value <<= 1; // shift value left by 1 }
putchar(’\n’); }
Suppose that display32BitPattern is called five times and that the five numbers given to it are 1010582140, 1650878054, 1617320572, 1650878048, and 1010591328:
Then the following pattern will be displayed:
Question: How should the initialization of the graphix-array be changed to make the given program code segment display the mirror image (along the vertical axis) of the above pattern? To answer this question, list five unsigned longs that, when supplied to display32BitPattern, will produce the pattern:
Hint: Write a program to help you calculate these five numbers from the given ones. (10 marks)
unsigned long graphix [] = {1010582140 , 1650878054 , 1617320572 , 1650878048 , 1010591328};
size_t nr_of_rows = sizeof(graphix) / sizeof(graphix[0]);
size_t i;
for (i = 0; i < nr_of_rows; i++) {
display32BitPattern(graphix[i], ’X’); }
XXXX XXXX XX X XX XX XX XXXX XX X XX XX XXXX XXXX
XX XX XX XXXX XX XX XX XX
XXXXX XX XX XXXXX XX
XX
XXXXX XX XX XXXXX XX XX
XX XX XX XXXX XX XX XX XX
XXXX XXXX XX XX X XX XXXX XX XX XX X XX XXXX XXXX
5
5. Write a C program that analyzes a given text file named “data.txt” and stores the results in three files named “vowels.txt”, “consonants.txt”, and “summary.txt” according to the following specifications:
• “vowels.txt”:
A text file consisting of all characters from “data.txt” that are vowels (’A’, ’E’, ’I’, ’O’, ’U’, and their lowercase versions) in the order that they appear in “data.txt”.
• “consonants.txt”:
A text file consisting of all characters from “data.txt” that are consonants (’B’, ’C’, ’D’, ’F’, . . . , ’X’, ’Y’, ’Z’, and their lowercase versions) in the order that they appear in “data.txt”.
• “summary.txt”:
A text file consisting of a single sentence that says how many vowels and how many consonants the file “data.txt” contains.
If “data.txt” can be opened then the program should overwrite or create each of the three files “vowels.txt”, “consonants.txt”, and “summary.txt” depending on whether or not it already exists. On the other hand, if “data.txt” cannot be opened, the program should not overwrite or create any files.
As an example, if the file “data.txt” can be opened and looks like this:
then after running the program, “vowels.txt”, “consonants.txt”, and “summary.txt” should be:
Remark: To keep the problem simple, the letter Y is always considered to be a consonant here. (20 marks)
COMP1011: Programming Fundamentals 25 May 2020
(THE HONG KONG POLYTECHNIC UNIVERSITY)
OoaiuaeaaEOOOEIUIEI
CMPPrgrmmngFndmntlsMyTHHNGKNGPLYTCHNCNVRSTY
The number of vowels is 19 and the number of consonants is 43.
6
6. Define a self-referential structure for representing binary trees as follows:
struct treeNode {
struct treeNode *leftPtr; // pointer to left subtree int data; // node value
struct treeNode *rightPtr; // pointer to right subtree
};
typedef struct treeNode TreeNode; typedef TreeNode *TreeNodePtr;
For any path P in a binary tree that starts at some node and follows zero or more leftPtr- and rightPtr-pointers, the sum of the data-values of all nodes belonging to P is referred to as P’s path value. For example, in the tree depicted below, the path from the root node to the leaf node with data-value 0 has path value 12 + (−1) + 8 + 4 + 0 = 23.
12
-1 14
-4 8 13 4 11
0 5 10
Write a C function that returns the maximum path value taken over all paths in a binary tree that start at the root node and end at a leaf node. The function prototype should be:
int maxPathValue(TreeNodePtr treePtr);
where treePtr points to the root of a binary tree. In case treePtr is NULL, let the function return
the value INT_MIN from
To continue the example, if rootPtr is a TreeNodePtr pointing to the root node of the tree shown above then maxPathValue(rootPtr) should return 40. The reason is that the path from the root node to the leaf node with data-value 10 has path value 12+(−1)+8+11+10 = 40, and this is the largest possible. (20 marks)
** END ** 7