CS51 preparation check #
This selfadministered quiz is intended to determine your readiness for CS 51. You should be able to get these problems right easily in a relatively short period of time. Some of the examples use code examples written in C or Python, but no knowledge of the details of those languages should be necessary to understand and complete the problems.
While there is no minimum score required for enrollment, if you ﬁnd yourself confused by any of the concepts, get more than one or two questions wrong for reasons of preparation, or ﬁnd the programming exercises quite difﬁcult, you should carefully consider whether you are prepared for the course and talk to course staff for placement advice.
Problem 1 #
Consider the following block of C code:
int i, j;
for (i = 0; i < 5; i++)
for (j = i; j < 5; j++)
printf("*");
How many asterisks does this print in total?
 5
 10
 15
 25
 None of the above
Show solution
Problem 2 #
Now, we generalize the code by using a loop limit of n
instead of 5
:
int i, j;
for (i = 0; i < n; i++)
for (j = i; j < n; j++)
printf(" * ");
If we run this program with different values of n
, will there ever
be cases in which the number of asterisks printed exceeds $100 \cdot
n \cdot \log n$
 No, there will not.
 Yes, there will.
 There isn’t enough information to determine.
Show solution
Problem 3 #
In binary, what is $10111111 + 00000001$?
 10000000
 10111111
 11111101
 11000000
 None of the above
Show solution
Problem 4 #
Below are four different Python programs that each print the string
“hello world” a different number of times. Rank them from 1 to 4 by
the number of times each prints “hello world”, where 1 prints “hello
world” the fewest times and 4 the most. (For reference, the Python
operator //
used in hello_two
is the integer division operator, so
for instance, 5 // 2
is 2.)
def hello_one(n):
if n <= 0:
return
else:
print("hello world")
hello_one(n  1)
hello_one(50)
def hello_two(n):
if n <= 0:
return
else:
print("hello world")
hello_two(n // 1)
hello_two(50)
def hello_three(n):
if n <= 0:
return
else:
print("hello world")
hello_three(n  1)
hello_three(n  1)
hello_three(50)
def hello_four(n):
if n <= 0:
return
else:
print("hello world")
print("hello world")
print("hello world")
hello_four(n  1)
hello_four(50)
Show solution
The next two problems ask you to write short programs. Try to write a correct solution without the aid of a compiler or interpreter and then run your code to check your work. See if you can get the correct output on your ﬁrst try. You may use any programming language of your choice.
Problem 5 #
Write a program that prints the numbers from 1 to 100, one per line, but for multiples of three print “Fizz” instead of the number and for multiples of ﬁve print “Buzz”. For numbers which are multiples of both three and ﬁve print “FizzBuzz”: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16…
Show solution
There are many ways to solve this problem. Here is a Python solution:
def fizzbuzz(n):
for i in range(1, n + 1):
if i % 3 == 0:
if i % 5 == 0:
print("FizzBuzz")
else:
print("Fizz")
elif i % 5 == 0:
print("Buzz")
else:
print(i)
fizzbuzz(100)
Write the following functions that deal with lists of ﬂoatingpoint numbers.
Problem 6 #
Write a function that returns the arithmetic mean of a list of numbers (that is, their sum divided by the number of elements).
Show solution
A direct implementation performing the sum and length calculations simultaneously is
def mean(lst):
sum = 0
length = 0
for i in lst:
sum += i
length += 1
return sum / length
Making use of some builtin Python functions sum
and len
:
def mean(lst):
return sum(lst) / len(lst)
The sum
and len
functions can themselves be implemented recursively as
def sum(lst):
if lst == []:
return 0
else:
return lst[0] + sum(lst[1:])
def len(lst):
if lst == []:
return 0
else:
return 1 + len(lst[1:])
or iteratively as
def sum(lst):
accum = 0
for i in lst:
accum += i
return accum
def len(lst):
accum = 0
for i in lst:
accum += 1
return accum
Problem 7 #
The median element in a list is the element in the “middle”, with the same number of larger and smaller elements in the list. For instance, the median element of the list 5, 1, 8, 3, 2, 4, 8 is 4, since there are three elements smaller (1, 2, 3) and three larger (5, 8, 8). (For even length lists (like 1, 2, 3, 4), you can use either of the two middle elements (2 or 3) as the median.) Write a function that returns the median of a list of numbers.
Show solution
Here is a simple Python implementation. For even length lists, it uses the larger of the two middle elements.
def median(lst):
sorted_list = sorted(lst)
midpoint = len(lst) // 2
return sorted_list[midpoint]
Problem 8 #
Alice has fallen down the rabbit hole into Wonderland, where she meets the Queen of Hearts and her King. While the Queen challenges Alice to Croquet, the King challenges Alice to a series of puzzles. The King tells Alice that the Queen is always either happy (☺) or sad (☹). There are four different spells the King can put on the Queen to try to change her mood: $\heartsuit, \diamondsuit, \clubsuit, \spadesuit$. If the Queen is happy about someone being beheaded, but sad about losing croquet, the King can put the $\diamondsuit$ spell on her to make her completely happy again. In our symbolic notation, this would mean that: $\diamondsuit$(☺, ☹) = ☺.
The other spells can inﬂuence the Queen’s moods as follows:
$$ \begin{aligned} \spadesuit(☺) &= ☹ \cr \spadesuit(☹) &= ☺ \cr \heartsuit(☺, ☺) &= ☺ \cr \heartsuit(☺, ☹) &= ☹ \cr \heartsuit(☹, ☹) &= ☹ \cr \diamondsuit(☺, ☺) &= ☺ \cr \diamondsuit(☺, ☹) &= ☺ \cr \diamondsuit(☹, ☹) &= ☹ \cr \clubsuit(☺, ☺) &= ☹ \cr \clubsuit(☹, ☺) &= ☺ \cr \clubsuit(☹, ☹) &= ☹ \end{aligned} $$
Note that the order of moods within the spells does not matter, so $\clubsuit(☺, ☹) = \clubsuit(☹, ☺)$. In all of the following situations, Alice must tell the King which spell he should use in place of the $\square$ symbol to make the Queen happy! Choose the corresponding answers below.

$\square(☹)$
 $\spadesuit$
 $\heartsuit$
 $\diamondsuit$
 $\clubsuit$
 None of the above

$\spadesuit(\square(☺, ☹))$
 $\spadesuit$
 $\heartsuit$
 $\diamondsuit$
 $\clubsuit$
 None of the above

$\diamondsuit(☹, \spadesuit(\square(☺, ☺)))$
 $\spadesuit$
 $\heartsuit$
 $\diamondsuit$
 $\clubsuit$
 None of the above
Show solution
 $\square(☹)$: a. $\spadesuit$
 $\spadesuit(\square(☺, ☹))$: b. $\heartsuit$
 $\diamondsuit(☹, \spadesuit(\square(☺, ☺)))$: d. $\clubsuit$
Problem 9 #
Consider the following pseudocode program:
for each student
if student average > 60
award student a D
else if student average > 70
award student a C
else if student average > 80
award student a B
else if student average > 90
award student an A
else
award student an E
If a student gets 100 in the class, what grade is that student awarded?
 A
 B
 C
 D
 E
 None of the above
Show solution
In the next two problems, you’ll work with Python logical values and
operators). In Python, the values True
and False
are used for the
logical values indicating truth and falsity, the logical negation
operator is not
, the logical conjunction operator is and
, the logical
disjunction operator is or
, the equality operator is ==
, and the
inequality operator is !=
.
Problem 10 #
Which of the following conditions are sufficient for not (A or B)
to
evaluate to True
? Select all options that apply:
A
isTrue
andB
isTrue
A
isTrue
andB
isFalse
A
isFalse
andB
isTrue
A
isFalse
andB
isFalse
(not a) and (not b)
isTrue
Show solution
d. A
is False
and B
is False
e. (not a) and (not b)
is True
Problem 11 #
Which of the following conditions are sufficient for (A != B) and (A or B)
to evaluate to True
? Select all options that apply:
A
isTrue
andB
isTrue
A
isTrue
andB
isFalse
A
isFalse
andB
isTrue
A
isFalse
andB
isFalse
Show solution
b. A
is True
and B
is False
c. A
is False
and B
is True
Problem 12 #
Imagine that the school registrar has asked you to build a program to verify student enrollments. You have one text file containing the names of all students in good standing with the University, and another set of files containing the names of all students who have enrolled in courses. You need to ﬁnd out which students enrolled in courses are not in good standing, and plan to read one of the text files into a data structure.
Which of the following data structures is best suited for this task?
 array
 binary search tree
 hash table
 linked list
 none of the above