日拱一卒，伯克利的Python期中考试，你能通过吗？
大家好，日拱一卒，我是梁唐。
我们继续伯克利的CS61A公开课之旅，这一次是这门课的期中测试。算是对前半课程的内容进行回顾，前一半内容主要都是围绕Python。包括Python的基础语法，以及Python的函数式编程，和面向对象基础，以及一些算法和数据结构基础。
虽然每一个部分都不算非常深入，但基本上重要的内容都涵盖了，作为一门大一的入门课程来说，无论是深度还是广度都绰绰有余了。
这也是很大大佬力推这门课作为新人入门CS的第一门课的原因，因为学完这一门课就可以对编程的各个方面有一个基本的了解。
下面就让我们看看伯克利的期中测试难度如何吧。
还是和之前一样，我们要先去往实验的官网，下载lab08压缩包。
这一次我们要编辑的是lab08.py和lab08_extra.py，其他的都是测试文件，不需要改动。
Required Questions
Linked Lists
Q1: Deep Linked List Length
如果一个链表中的一个或多个元素是另外一个链表，那么我们把这样的链表称为深度链表（deep linked list）。
编写函数deep_len，它接收一个链表，返回它的deep长度。deep长度是链表中所有元素的个数，查看下方测试样例获取更多信息。
提示：使用isinstance来检查对象是否是某个类的实例
def deep_len(lnk):
""" Returns the deep length of a possibly deep linked list.
>>> deep_len(Link(1, Link(2, Link(3))))
3
>>> deep_len(Link(Link(1, Link(2)), Link(3, Link(4))))
4
>>> levels = Link(Link(Link(1, Link(2)), \
Link(3)), Link(Link(4), Link(5)))
>>> print(levels)
<<<1 2> 3> <4> 5>
>>> deep_len(levels)
5
"""
"*** YOUR CODE HERE ***"
使用ok命令来进行测试：python3 ok -q deep_len
答案
链表可能有嵌套，并且题目也没有明确说嵌套只有一层。在不知道链表嵌套层数的情况下，显然没办法使用迭代的方法来解，那就只有递归了。
属于递归的基本应用，对能坚持完成课程的同学来说应该没有难度。
def deep_len(lnk):
ret = 0
while lnk is not Link.empty:
if isinstance(lnk.first, Link):
ret += deep_len(lnk.first)
else:
ret += 1
lnk = lnk.rest
return ret
Orders of Growth
Q2: Finding Orders of Growth
选择题，读代码选择代码的时间复杂度
使用ok命令进行答题：python3 ok -q growth -u
一共只有三题，比较简单：
# is_prime 的时间复杂度是什么？
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
# bar函数的时间复杂度是什么？
def bar(n):
i, sum = 1, 0
while i <= n:
sum += biz(n)
i += 1
return sum
def biz(n):
i, sum = 1, 0
while i <= n:
sum += i**3
i += 1
return sum
# foo函数的时间复杂度是什么？n表示list长度
# 假设list切片操作和len操作复杂度都是O(1)
def foo(lst, i):
mid = len(lst) // 2
if mid == 0:
return lst
elif i > 0:
return foo(lst[mid:], -1)
else:
return foo(lst[:mid], 1)
Optional Questions
Objects
Q3: WWPP: Methods
填空题，阅读Python代码填写Python打印的结果
使用ok进行答题：python3 ok -q foobar -u
提示：如果结果是函数，输入Function，如果报错，输入Error
关于面向对象和继承的基础问题，有个别题目稍微有点刁钻，想不明白可以拷贝代码进入Python解释器中实际运行一下。
>>> class Foo:
... def print_one(self):
... print('foo')
... def print_two():
... print('foofoo')
>>> f = Foo()
>>> f.print_one()
______
>>> f.print_two()
______
>>> Foo.print_two()
______
>>> class Bar(Foo):
... def print_one(self):
... print('bar')
>>> b = Bar()
>>> b.print_one()
______
>>> Bar.print_two()
______
>>> Bar.print_one = lambda x: print('new bar')
>>> b.print_one()
______
Q4: WWPP: Attributes
填空题，阅读Python代码填写输出结果
使用ok命令进行答题：python3 ok -q attributes -u
提示：如果结果是函数，输入Function，如果报错，输入Error
有两题有点像是脑筋急转弯……
>>> class Foo:
... a = 10
... def __init__(self, a):
... self.a = a
>>> class Bar(Foo):
... b = 1
>>> a = Foo(5)
>>> b = Bar(2)
>>> a.a
______
>>> b.a
______
>>> Foo.a
______
>>> Bar.b
______
>>> Bar.a
______
>>> b.b
______
>>> Foo.c = 15
>>> Foo.c
______
>>> a.c
______
>>> b.c
______
>>> Bar.c
______
>>> b.b = 3
>>> b.b
______
>>> Bar.b
______
Q5: Keyboard
我们将要创建一个Keyboard类，它接收若干Buttons并且将这些Buttons存入字典。
字典的key是Button出现的下标，value是对应的Button。根据描述将我们Keyboard类中的方法补充完整，使用doctest作为Keyboard的行为参考
class Keyboard:
"""A Keyboard takes in an arbitrary amount of buttons, and has a
dictionary of positions as keys, and values as Buttons.
>>> b1 = Button(0, "H")
>>> b2 = Button(1, "I")
>>> k = Keyboard(b1, b2)
>>> k.buttons[0].key
'H'
>>> k.press(1)
'I'
>>> k.typing([0, 1])
'HI'
>>> k.typing([1, 0])
'IH'
>>> b1.pressed
2
>>> b2.pressed
3
"""
def __init__(self, *args):
"*** YOUR CODE HERE ***"
def press(self, info):
"""Takes in a position of the button pressed, and
returns that button's output"""
"*** YOUR CODE HERE ***"
def typing(self, typing_input):
"""Takes in a list of positions of buttons pressed, and
returns the total output"""
"*** YOUR CODE HERE ***"
class Button:
def __init__(self, pos, key):
self.pos = pos
self.key = key
self.pressed = 0
使用ok命令进行测试：python3 ok -q Keyboard
答案
这题是面向对象的基本应用，非常基础，难度不大，但需要我们仔细阅读注释里的题意。
class Keyboard:
def __init__(self, *args):
self.buttons = dict()
for but in args:
self.buttons[but.pos] = but
def press(self, info):
self.buttons[info].pressed += 1
return self.buttons[info].key
def typing(self, typing_input):
ret = ''
for t in typing_input:
ret += self.buttons[t].key
self.buttons[t].pressed += 1
return ret
Nonlocal
Q6: Advanced Counter
完成make_advanced_maker函数定义，它创建一个会创建计数器的函数。
这些计数器只会更新它们自己的count以及全局共享的count，它们也能reset任意一个count。
def make_advanced_counter_maker():
"""Makes a function that makes counters that understands the
messages "count", "global-count", "reset", and "global-reset".
See the examples below:
>>> make_counter = make_advanced_counter_maker()
>>> tom_counter = make_counter()
>>> tom_counter('count')
1
>>> tom_counter('count')
2
>>> tom_counter('global-count')
1
>>> jon_counter = make_counter()
>>> jon_counter('global-count')
2
>>> jon_counter('count')
1
>>> jon_counter('reset')
>>> jon_counter('count')
1
>>> tom_counter('count')
3
>>> jon_counter('global-count')
3
>>> jon_counter('global-reset')
>>> tom_counter('global-count')
1
"""
"*** YOUR CODE HERE ***"
使用ok命令进行测试：python3 ok -q make_advanced_counter_maker
答案
仔细阅读题目之后，会发现这是一个多层嵌套的高阶函数。
对于每一个count来说，它们需要有自己的value。函数内部不能存储变量，所以需要一重闭包。加上还需要维护全局的count，又需要再加一层。所以最终的结果是三层函数嵌套的高阶函数。
理清楚题意之后，代码同样不算难写，需要仔细阅读doctest理解逻辑。
def make_advanced_counter_maker():
outer_cnt = 0
def func():
cnt = 0
def f(operation):
nonlocal cnt, outer_cnt
if operation == 'count':
cnt += 1
return cnt
if operation == 'reset':
cnt = 0
if operation == 'global-count':
outer_cnt += 1
return outer_cnt
if operation == 'global-reset':
outer_cnt = 0
return f
return func
Mutable Lists
Q7: Environment Diagram
画出下面程序的运行环境图
记住几点：
- 当你修改一个list时，你是对它原始的list进行修改
- 当你拼接两个list时，你是在创建一个新的list
- 当你把一个名称赋值给一个已经存在的对象，你是在创建同样对象的引用，而非拷贝一个对象
def got(lst, el, f):
welcome = []
for e in lst:
if e == el:
el = f(lst[1:], 2, welcome)
return lst[3:] + welcome
def avocadis(lst, i, lst0):
lst0.append(lst.pop(i))
return len(lst0)
bananis = [1, 6, 1, 6]
n = bananis[3]
we = got(bananis, n, avocadis)
答案如下：
Q8: Trade
在整数市场，每一个参与者都用一个整数list用来交易。当两个参与者相遇时，它们交易他们list中最小的非空前缀。一个前缀是一个从下标0开始的切片。
编写一个函数trade，它可以交互list first前m和list second前n个元素。保证这些元素的和相等，并且这个和越小越好。如果没有对应的前缀存在，返回No deal!，否则的话，交换元素，并且返回Deal!。逻辑的一部分已经实现了。
你可以通过切片赋值来修改一个切片，在等号左侧指定[i:j]，在等号右边是你要修改成的list。这个操作会将区间[i: j]内的所有元素替换成等号右边的list，并且长度可以不等。
>>> a = [1, 2, 3, 4, 5, 6]
>>> b = a
>>> a[2:5] = [10, 11, 12, 13]
>>> a
[1, 2, 10, 11, 12, 13, 6]
>>> b
[1, 2, 10, 11, 12, 13, 6]
def trade(first, second):
"""Exchange the smallest prefixes of first and second that have equal sum.
>>> a = [1, 1, 3, 2, 1, 1, 4]
>>> b = [4, 3, 2, 7]
>>> trade(a, b) # Trades 1+1+3+2=7 for 4+3=7
'Deal!'
>>> a
[4, 3, 1, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c = [3, 3, 2, 4, 1]
>>> trade(b, c)
'No deal!'
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[3, 3, 2, 4, 1]
>>> trade(a, c)
'Deal!'
>>> a
[3, 3, 2, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[4, 3, 1, 4, 1]
"""
m, n = 1, 1
"*** YOUR CODE HERE ***"
if False: # change this line!
first[:m], second[:n] = second[:n], first[:m]
return 'Deal!'
else:
return 'No deal!'
使用ok命令进行测试：python3 ok -q trade
答案
我们只需要实现找到让两个list和相等的部分，逻辑很简单，就是使用while循环，将总和比较小的那边的下标增加。如果有一边的下标超出了总长还没能构成相等，说明已经不可能相等了，break。
def trade(first, second):
m, n = 1, 1
"*** YOUR CODE HERE ***"
deal = False
while True:
if sum(first[:m]) == sum(second[:n]):
deal = True
break
if m > len(first) or n > len(second):
break
if sum(first[:m]) < sum(second[:n]):
m += 1
if sum(first[:m]) > sum(second[:n]):
n += 1
if deal: # change this line!
first[:m], second[:n] = second[:n], first[:m]
return 'Deal!'
else:
return 'No deal!'
Recursive objects
Q9: Linked Lists as Strings
Kevin和Jerry 喜欢在Python中用不同的方式来展示链表。Kevin喜欢盒和指针的图，Jerry更喜欢新潮的方法。编写一个函数make_to_string，它会返回一个函数，这个函数接收一个链表，根据他们喜欢的方式将读入的链表转化成string后返回。
提示：你可以通过str函数将数字转化成字符串，并且你可以直接通过+将字符串相连
>>> str(4)
'4'
>>> 'cs ' + str(61) + 'a'
'cs 61a'
def make_to_string(front, mid, back, empty_repr):
""" Returns a function that turns linked lists to strings.
>>> kevins_to_string = make_to_string("[", "|-]-->", "", "[]")
>>> jerrys_to_string = make_to_string("(", " . ", ")", "()")
>>> lst = Link(1, Link(2, Link(3, Link(4))))
>>> kevins_to_string(lst)
'[1|-]-->[2|-]-->[3|-]-->[4|-]-->[]'
>>> kevins_to_string(Link.empty)
'[]'
>>> jerrys_to_string(lst)
'(1 . (2 . (3 . (4 . ()))))'
>>> jerrys_to_string(Link.empty)
'()'
"""
"*** YOUR CODE HERE ***"
使用ok命令来进行测试：python3 ok -q make_to_string
答案
这题题意当中说得比较笼统，就说两人喜欢的风格不同，但没有说清楚两人喜欢的到底是什么风格。
所以必须要仔细阅读一下测试样例，才能理解它的运行方式。理解了题意之后，并不困难。
def make_to_string(front, mid, back, empty_repr):
def f(lnk):
if lnk is Link.empty:
return empty_repr
return front + str(lnk.first) + mid + f(lnk.rest) + back
return f
Q10: Tree Map
实现一个函数tree_map，它接收一个tree以及一个单参数函数fn，返回一个新的tree，它是将fn应用在tree上所有节点的结果。
def tree_map(fn, t):
"""Maps the function fn over the entries of t and returns the
result in a new tree.
>>> numbers = Tree(1,
... [Tree(2,
... [Tree(3),
... Tree(4)]),
... Tree(5,
... [Tree(6,
... [Tree(7)]),
... Tree(8)])])
>>> print(tree_map(lambda x: 2**x, numbers))
2
4
8
16
32
64
128
256
"""
"*** YOUR CODE HERE ***"
使用ok命令进行测试：python3 ok -q tree_map
答案
我们之前做过类似的题目，本质上是在树上做递归的典型例子。
def tree_map(fn, t):
if t.is_leaf():
return Tree(fn(t.label))
return Tree(fn(t.label), [tree_map(fn, b) for b in t.branches])
Q11: Long Paths
实现long_paths函数，它返回一个树上长度大于等于n的所有路径的list。一个树上的路径是一个从根节点直到叶子节点的链表。链表上每一个后续元素，都是之前元素的子节点。路径的长度就是路径中节点的数量。路径按照从左到右排序，查看doctest获取例子
def long_paths(tree, n):
"""Return a list of all paths in tree with length at least n.
>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12, [Tree(13, [Tree(14)])])])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> for path in long_paths(whole, 2):
... print(path)
...
<0 1 2>
<0 1 3 4>
<0 1 3 4>
<0 1 3 5>
<0 6 7 8>
<0 6 9>
<0 11 12 13 14>
>>> for path in long_paths(whole, 3):
... print(path)
...
<0 1 3 4>
<0 1 3 4>
<0 1 3 5>
<0 6 7 8>
<0 11 12 13 14>
>>> long_paths(whole, 4)
[Link(0, Link(11, Link(12, Link(13, Link(14)))))]
"""
"*** YOUR CODE HERE ***"
使用ok进行测试：python3 ok -q long_paths
答案
这道题有一些难度，遍历树上的路径，拿到每条路径的长度这并不难。但麻烦的点在于我们最后要返回的是路径的list，而Python当中传参传的都是对象的引用。所以我们要开辟新的路径时，不能直接在原先的链表上修改，而需要把之前的链表复制一份。
比如一个链表为1 -> 3，当我们在末尾加上一个数字，比如2时，原先的链表也会变成1 -> 3 -> 2。我们不会得到1 -> 3, 1 -> 3 -> 2两条链表，而是得到相同的两条1 -> 3 -> 2。
所以这里我们单独实现了copy_link方法用来拷贝链表。
def long_paths(tree, n):
def copy_link(lnk):
head = Link(lnk.first)
tail = head
lnk = lnk.rest
while lnk is not Link.empty:
nxt = Link(lnk.first)
tail.rest = nxt
tail = nxt
lnk = lnk.rest
return head, tail
ret = []
def f(t, head, length):
if t.is_leaf():
if length >= n:
ret.append(head)
return
for b in t.branches:
hd, tail = copy_link(head)
tail.rest = Link(b.label)
f(b, hd, length + 1)
f(tree, Link(tree.label), 0)
return ret
More Orders of Growth
Q12: Zap (Orders of Growth)
下列zap函数的时间复杂度是什么？使用Θ\ThetaΘ来表达。
def zap(n):
i, count = 1, 0
while i <= n:
while i <= 5 * n:
count += i
print(i / 6)
i *= 3
return count
使用ok来回答：python3 ok -q zap -u
答案
虽然看着有两重循环，但我们分析一下会发现当内层循环i <= 5*n退出时外层的i <= n也一样会退出，所以本质上只有一层循环。我们再看下里面的逻辑，i每次操作都会翻三倍，所以这是一个指数级的增长。那么对应到复杂度就是log级
Q13: Boom (Orders of Growth)
下列函数的时间复杂度是什么？使用Θ\ThetaΘ来表示
def boom(n):
sum = 0
a, b = 1, 1
while a <= n*n:
while b <= n*n:
sum += (a*b)
b += 1
b = 0
a += 1
return sum
使用ok命令来测试python3 ok -q boom -u
答案
我们读一下代码会发现，两层循环的终止条件都是要大于n * n，而每次迭代变量只会增加1，所以每一重循环的复杂度都是n2n^2n2，两重循环相乘就是n4n^4n4