printable version
Test 1
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
Problem X1.1.
[12 pts]
The hailstone sequence is defined by the following
loop.
while n ≠ 1:
if n is odd:
n ←
3 n + 1
else:
n ←
n / 2
Starting with 7, this loop iterates n through a sequence of
17 numbers:
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
If we started with 5, the sequence
would contain just six numbers — 5, 16, 8, 4, 2, 1.
Complete the following function so that it returns how many
numbers are in the hailstone sequence starting from its parameter;
thus, hailstone(7) should return 17 while
hailstone(5) returns 6.
int hailstone(int start) {
int hailstone(int start) {
int n;
int count;
n = start;
count = 1;
while (n != 1) {
if (n % 2 == 1) {
n = 3 * n + 1;
} else {
n = n / 2;
}
count++;
}
return count;
}
OR
int hailstone(int start) {
if (start == 1) {
return 1;
} else if (start % 2 == 1) {
return 1 + hailstone(3 * start + 1);
} else {
return 1 + hailstone(start / 2);
}
}
Problem X1.2.
[8 pts]
What does the below C program display?
#include <stdio.h>
int main() {
int i; int j;
int *p; int *q; int *r;
i = 7;
j = 6;
p = &i;
q = &j;
r = q;
q = p;
*p = 5;
*q = 4;
*r = 3;
printf("%d %d\n", i, j);
printf("%d %d\n", *p, *q);
printf("%d\n", *r);
}
4 3
4 4
3
Problem X1.3.
[10 pts]
Complete the following function so that it displays its
parameter string in reverse. For example, printr("straw")
should print warts
onto the screen.
(Recall that you can use printf("%c", s[0]) to display
the first character of a string s. You can feel free to
use standard C functions like strcpy.)
void printr(char *letters) {
void printr(char *letters) {
int i;
for (i = strlen(letters) - 1; i >= 0; i--) {
printf("%c", letters[i]);
}
}
Problem X1.4.
[8 pts]
Suppose that nums is an int* pointing to the first
integer of an array containing the following numbers:
3, 0, −1, 2, −2, −4
Thus, *nums is 3. What is displayed by the following
sequence of statements?
while (*nums != 0) {
printf("%d\n", *nums);
nums = nums + *nums;
}
3
2
-4
Problem X1.5.
[12 pts]
Consider the following function, which uses the standard C
functions isupper for testing whether the parameter character
is a capital letter
and toupper that returns an upper-case equivalent of the
parameter character.
(For example, isupper('A') returns 1 while
isupper('b') returns 0; and toupper('c') returns
the capital letter C.)
1 void print_capitalized(char *s) {
2 char *t;
3
4 if (isupper(s[0])) {
5 /* s is already capitalized, so just print s. */
6 printf("%s", s);
7 } else {
8 /* create a copy of s with first letter capitalized. */
9 t = (char*) malloc(strlen(s) * sizeof(char));
10 strcpy(t, s);
11 t[0] = toupper(s[0]);
12 printf("%s", t);
13 }
14 free(t);
15 }
This function has two bugs, identified by valgrind
as below. For each bug, explain the
circumstances that lead to the problem as the computer
executes the code on the line identified by valgrind,
and explain how to repair the code to avoid
the problem (while retaining the basic structure of the function as
much as possible).
a. When the parameter s does not start with
a capital letter, we enter the else clause and allocate
in line 9 an array holding space for each of the characters of
s — but we do not include enough room for the
terminating NUL character. Then, in line 10, when s is
copied into this array, strcpy will attempt to place a
NUL character after the final character it copies into t;
but this is beyond the length of the allocated array.
The solution is to change line 9 to include space for this
extra character:
t = (char*) malloc((strlen(s) + 1) * sizeof(char));
b. When the parameter s starts with a
capital letter, we enter the if clause, which does not
alter t from its value, and so t remains uninitialized.
Then we continue to line 14, which asks free to deallocate
based on the value of this uninitialized variable t.
The message indicates that free uses the value of this
uninitialized variable.
The solution is to move line 14 so that it only occurs after
t has been given a value — i.e., in the else clause.
Thus, we should move line 14 to be just after line 12.
Problem X1.6.
[12 pts]
Suppose we have declared a C struct as below
for representing a linked list's node.
struct node {
int value;
struct node *next;
};
Complete the following function so that it displays every
other number in the linked list. If the list contains 1,
2, 3, 4, 5, 6, 7, the function should display 1, 3, 5, 7 (on
separate lines without commas).
void list_print_alternates(struct node *head) {
void list_print_alternates(struct node *head) {
struct node *cur;
cur = head;
while (cur != NULL) {
printf("%d\n", cur->value);
cur = cur->next;
if (cur != NULL) {
cur = cur->next;
}
}
}
Problem X1.7.
[6 pts]
Approximate 242 in the form
x × 10y,
with x and y both being base-10 integers.
(Your answer need not be normalized.)
4 × 1012
Problem X1.8.
[12 pts]
Perform each of the following conversions.
| a. | 10110(2) |
to decimal |
| b. | 38(10) |
to binary |
| c. | 123(8) |
to decimal |
| d. | 5CAFF01D(16) |
to binary |
| a. | 10110(2) |
= | 22(10) |
| b. | 38(10) |
= | 100110(2) |
| c. | 123(8) |
= | 83(10) |
| d. | 5CAFF01D(16) |
= | 101 1100 1010 1111 1111 0000 0001 1101(2) |
Home
Syllabus
Readings
Assignments
Tests