Home
Syllabus
Readings
Projects
Tests
printable version
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15]
[6 pts]
If nums is [11, 2, 7, 5, 3],
what is the value of each of the following expressions?
a. nums[1] + nums[-1]
b. sum(nums[1:4])
c. nums[min(nums)]
a. 5
b. 14
c. 7
[12 pts] The below program reads 50 integers from the user. Modify the program so that after reading the fiftieth integer, it displays the sum of all those integers that are less than 100. For example, if the user enters 200, 59, 99, 105, and 10, then enters 150 forty-five times, the output should be 168 (from 59 + 99 + 10).
for index in range(50):
num = int(input())
total = 0
for index in range(50):
num = int(input())
if num < 100:
total += num
print(total)
[6 pts] Write a regular expression for all sequences of a's and b's that all a's precede all b's, including at least one of each. Examples include ab, aaab, and aaabb, but not aabbabb or aaaaa.
a+b+
[8 pts]
What single value for template would result in the following
strings being produced? (Don't include the quotes.)
template.format(212, 100) | → | “100.0 C = 212.0 F” |
template.format(98.6, 37) | → | “ 37.0 C = 98.6 F” |
“{1:5.1f} C = {0:5.1f} F” (without the
quotes)
[8 pts]
What does the below program display?
def go(x):
y = step(x)
z = step(y)
print('{0} {1} {2}'.format(x, y, z))
def step(a):
a = a + 2
return a + 3
go(5)
5 10 15
[14 pts]
Write a function input_between, which should take two
parameters, both numbers, and return a number typed by the user
that is above the first parameter and below the second. It will
continue to request a number from the user until the required
number is given. (A number exactly matching the first number or
the second will be accepted. You may assume that first number is
below the second and that the user only types valid
numbers.)
For example, suppose we have the following program using your function.
n = input_between(0, 40)
m = 1
for i in range(2, n + 1):
m *= i
print('Factorial is ' + str(m))
The below shows one possible run of the program, with boldface indicating what the user types.
Number? -5 Too low Number? 50 Too high Number? 42 Too high Number? 4 Factorial is 24
def input_between(lo, hi):
while True:
print('Number?')
n = int(input())
if n < lo:
print('Too low')
elif n > hi:
print('Too high')
else:
return n
[8 pts]
Draw a recursion tree representing the recursive calls made when computing the value of f(60) using the following function.
def f(n):
if n < 10:
return n
else:
a = f(n // 2)
b = f(n // 3)
return a - b
[14 pts]
Suppose the file pops.txt is a tab-separated values
file, where each line contains three values: a city name, a
state name, the city's current population. Here are five example
lines from the file.
Chicago Illinois 9899902
Los Angeles California 18238998
New York New York 23362099
San Francisco California 8370967
Washington DC 9331587
Write a program that displays the name of each state represented in the file followed by the number of cities in that state with a current population exceeding 1,000,000. For example, if the file contained only the five lines listed above, the output of the program would be as illustrated below. (You don't need to worry about the order of the lines.)
Illinois 1
California 2
New York 1
DC 1infile = open('pops.txt')
for line in infile:
data = line.rstrip().split('\t')
states = {}
infile = open('pops.txt')
for line in infile:
data = line.rstrip().split('\t')
if int(data[2]) > 1000000:
states[data[1]] = states.get(data[1], 0) + 1
for state in states:
print('{0} {1}'.format(state, states[state]))
[8 pts] In your own words, describe how merge sort works. What is the base case?
The base case is when the array has one element; in this case, nothing happens.
When there is more than one element, merge sort consists of three major steps. First, we split the array into two halves. Then we sort each half through recursively applying the merge sort algorithm to each. And finally, we merge the two halves together by successively “removing” the lesser of the two halves' first elements and placing the removed item into the array holding our result.
[8 pts] Define the function of a router in the Internet.
A router is a computing device that is attached to two or more separate networks. Any time it receives a message, it forwards the message to the appropriate computer on the other network as necessary.
[14 pts]
Write a class TruncatedLog providing the following
constructor and method.
TruncatedLog(max_lines)max_lines of output.show(line)line on the screen if this is among the first
lines displayed (before the log is truncated).The following fragment illustrates how a program might use the
TruncatedLog class.
my_log = TruncatedLog(2)
my_log.show('haste') # Displays "haste"
my_log.show('makes') # Displays "makes"
my_log.show('waste') # (no display since two lines already shown)
class TruncatedLog:
def __init__(self, max_lines):
self.max_lines = max_lines
self.lines_done = 0
def show(self, line):
if self.lines_done < self.max_lines:
self.lines_done += 1
print(line)
[10 pts] Suppose a game player has constructed the following game tree.
In this tree, high numbers represent good boards for X, and it is currently X's move. (As you can see, X has three possible moves from which to choose, labeled A, B, and C.)
a. Fill in all empty circles with the values assigned them according to the minimax evaluation algorithm.
b. Which move will X choose?
| a. |  |
| b. | C |
[12 pts] Recall the two classes we defined for dealing with linked lists.
class Node:
def __init__(self, value, next):
self.data = value
self.next = nextclass LinkedList:
def __init__(self):
self.head = None
The below function attempts to delete every node in a linked list that contains a negative number. There are several things wrong with it. Identify two distinct problems, and explain how to repair the function to address each issue.
def delete_negatives(list_obj):
cur = list_obj.head
while cur.next is not None:
if cur.next < 0:
cur.next = cur.next.next
cur = cur.next
In “if cur.next < 0”, cur.next is a
reference to a Node object, not a number that can
be compared to 0. To get the number within the node, we would
need “if cur.next.data < 0”.
If the list is empty (head is None), then
this function would end up setting cur to None
in the first line and then the next line would try to retrieve
the next attribute of None, which would lead to
an exception. The solution would to add an if statement
before the while loop to test for this:
“if cur is None: return”.
If the list happens to start with a negative number, that
will never be observed by the function, and the node would not
be removed. To repair this, we could
add a while loop at the beginning of the function (we
need a while loop because there could be
multiple negative numbers to be removed at the list's
beginning):
while list_obj.head is not None and list_obj.head.data < 0:
list_obj.head = list_obj.head.next
If the list has multiple negative numbers in a row (after the
first node), then only every other negative number will be
deleted: When cur is the node before the first of the
sequence, the loop removes the first negative node and then steps
cur forward to the next node (the second negative node), then the
next iteration would delete the third negative node and step
cur forward to the next node (the fourth negative node),
and so on. The solution is to change cur only if we're
not deleting the node after cur:
while cur.next is not None:
if cur.next.data < 0:
cur.next = cur.next.next
else:
cur = cur.next
list_obj.head = list_obj.head.next
[14 pts]
Using the Node and LinkedList classes defined previously,
write a function count_long that takes a parameter referencing
a LinkedList object whose values are strings
and returns the number of string with more than five
letters.
def count_long(word_list):
def count_long(word_list):
count = 0
cur = word_list.head
while cur is not None:
if len(cur.data) > 5:
count += 1
cur = cur.next
return count
[8 pts]
Modify the below program so that, should the filename typed
by the user correspond to something that cannot be opened,
the program displays “file not opened” and exits
(without attempting to read the file).
Recall that open raises an IOError exception
if the named file is not accessible.
filename = input('Filename:')
infile = open(filename)
text = infile.read()
print('# characters: ' + str(len(text)))
filename = input('Filename:')
try:
infile = open(filename)
text = infile.read()
print('# characters: ' + str(len(text)))
except IOError:
print('file not opened')