Home
Syllabus
Assignments
Tests
printable version
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17]
[6 pts]
If x's value is 18, what is the value of each of the
following Python expressions?
a. 3 + x * 2
b. x % 7
a. 3 + x * 2 is 39
b. x % 7 is 4
[10 pts]
Tabulate all values taken on by the variables i, j,
and j as the program fragment below executes.
j = 3
k = 4
for i in range(1, 4):
j = k - j
k = k + i
i: |
1, | 2, | 3 | |
j: |
3, | 1, | 4, | 3 |
k: |
4, | 5, | 7, | 10 |
[12 pts] Without using built-in functions (most importantly, without using any logarithm function) — though using loops is OK —, complete the following program so that when the user types an integer, it displays how many times the number can be halved before reaching 1. For example, if the user types 20, it would display 5: The first halving reaches 10, then 5, then 2.5, then 1.25, but the fifth halving goes down to 0.625.
query = input('Starting number? ')
count = 0
current = query
while current >= 1:
current = current / 2
count += 1
print count
[6 pts]
If name refers to the string Arkansas, what is
name[3:6]?
[8 pts]
Both functions and methods allow names to be associated with
complex computations. For example, with strings, you can use the
len function and the count method. What
distinguishes them?
A function is initiated using just its name, and any
information it needs is supplied in the parameters, but a method
must be invoked by preceding the method name with the value
it's operating on
. Thus, if we have a string variable
called name, you'd invoke the count method by
writing
, but you'd invoke the
name.count('e')len function by writing
.len(name)
[8 pts] Perform each of the following conversions. Show your intermediate work.
a. the two's-complement bit pattern 00011010 as a base-10 number.
b. 49(10) in an eight-bit two's-complement representation.
c. −64(10) in an eight-bit two's-complement representation.
a. 26(10)
b. 00110001
c. 11000000
[8 pts] What does the below program display?
def go(x):
y = step(x)
z = step(y)
print x, y, z
def step(a):
a = a + 1
return a + 1
go(5)
[12 pts]
Write a function longest that takes a list of strings as a
parameter and returns the longest string in the list. For example,
longest(['z', 'yyy', 'xx']) should return the string yyy.
def longest(words):
best = ''
for word in words:
if len(word) > len(best):
best = word
return best
[8 pts] Write a context-free grammar describing the language containing all strings of a's and b's with at least two letters of which the first and last letters are the same. Examples include aa, baaab, and ababaa, but not b or aaabb.
| S | → | a T a | b T b |
| T | → | a T | b T | λ |
[8 pts] What does a name server do in the Internet's Domain Name System (DNS)?
A name server receives requests including the name of a computer (such as ozark.hendrix.edu) and responds with the computer's IP address (such as 209.65.57.4).
[8 pts]
Draw a recursion tree representing the recursive calls made when
computing the value of f(1) using the following
function.
def f(a):
if a >= 5:
return a
else:
b = f(a + 1)
c = f(a + 2)
return b + c
[10 pts]
Without using loops (i.e., by using recursion), and also
without using other functions or methods except len,
create a function is_all_ms that takes a string parameter
returns True if all characters in the string are the
lower-case letter m and False otherwise. (When
given the empty string, the result isn't important, as long as
the function works for other strings.)
def is_all_ms(word):
if len(word) <= 1:
return word == 'm'
elif word[0] == 'm':
return is_all_ms(word[1:])
else:
return False
[8 pts] Create a regular expression for strings containing two integers separated by either a hyphen or a slash. Examples include 450-1377 and 12/25.
[0-9]+[-/][0-9]+
[10 pts]
Complete the Scorecard class below so that the get_sum method returns the total of all the scores given into
the tally method. Thus, a program might use the Scorecard class as follows.
game = ScoreCard()
print game.get_sum() # displays 0
game.tally(4)
game.tally(6)
print game.get_sum() # displays 10
game.tally(5)
print game.get_sum() # displays 15
class Scorecard():
def __init__(self):
def tally(self, score):
def get_sum(self):
class Scorecard():
def __init__(self):
self.total = 0
def tally(self, score):
self.total += score
def get_sum(self):
return self.total
[8 pts] In your own words, describe how merge sort works.
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] Suppose a game player has constructed a game tree as given at right. In this tree, high numbers represent good boards for X, and it is currently X's move. Fill in all empty circles with the values assigned them according to the minimax evaluation algorithm.
[10 pts]
Suppose we have a variable first that refers to the
first Node in a linked list of strings, using the Node class for
linked lists that we studied, listed below. Write a program
fragment that displays the final string in the list.
class Node():
def __init__(self, value, next):
self.data = value
self.next = next
cur_loc = first
while cur_loc.next != None:
cur_loc = cur_loc.next
print cur_loc.data