CS 88 Computational Structures in Data Science
app | 作业Python – 本题是一个 Data Science代做, 对 Data Science进行训练解析, 涵盖了 Data Science/Python等程序代做方面
Fall 2021 Midterm
INSTRUCTIONS
- You have 120 minutes to complete the exam.Do NOT open the exam until you are instructed to do so!
- Youmust notcollaborate with anyone inside or outside of CS88.
- Youmust notuse any internet resources to answer the questions.
- If you are taking an online exam, at this point you should have started your Zoom / screen recording. If something happens during the exam, focus on the exam! Do not spend more than a few minutes dealing with proctoring.
- When a question specifies that you must rewrite the completed function, you shouldnotrecopy the doctests.
- The exam is closed book, closed computer, closed calculator, except your hand-written 8.5" x 11" cheat sheets of your own creation and the official CS88 Reference Sheet
Full Name
Student ID Number
Official Berkeley Email (@berkeley.edu)
What room are you in?
Name of the person to your left
Name of the person to your right
By my signature, I certify that all the
work on this exam is my own, and I will
not discuss it with anyone until exam
session is over.(please sign)
POLICIES & CLARIFICATIONS
- If you need to use the restroom, bring your phone and exam to the front of the room.
- Youmay notuse example functions defined on your study guide unless a problem clearly states you can.
- For fill-in-the-blank coding problems, we will only grade work written in the provided blanks. You may only write one Python statement per blank line, and it must be indented to the level that the blank is indented.
- Unless otherwise specified, you are allowed to reference functions defined in previous parts of the same question.
- Online Exams: You may start you exam as soon as you are given the password.
- You may have a digitial version of the CS88 Reference Sheet, or the PDF, but no other files.
- Open Reference Sheet
- (5.0 points) WWPD
For each of the expressions in the table below, write the output displayed by the interactive Python interpreter
when the expression is evaluated. The output may have multiple lines. If an error occurs, write Error. If a
function is outputted, write function. Your answers must fit within the boxes provided. Work outside the
boxes will not be graded.
(a) (1.0 pt)
>>> False or 1 and 8 or True
(b) (2.0 pt)
>>> lucky = (lambda x: lambda y: (y - x) % 8 == 0)(8)
>>> def mystery(x, y):
... if lucky(x):
... print('ready')
... while x > y:
... x = x // 10
... print(x)
... return'go'
>>> mystery(40, 2)
(c) (2.0 pt)Note the variableluckyand themysteryfunction are redefined here for your convenience.
>>> lucky = (lambda x: lambda y: (y - x) % 8 == 0)(8)
>>> def mystery(x, y):
... if lucky(x):
... print('ready')
... while x > y:
... x = x // 10
... print(x)
... return'go'
>>> print('a', mystery(7, 9))
- (7.0 points) Environment Diagram Analysis
Fill in the blanks to complete the environment diagram. All the code used is in the box to the right.Some
arrows have been removed from the diagram.You may wish to draw in the arrows, but it is not required.
Question 2 Environment Diagram
(a) (1.0 pt) (a)What is the parent frame of thejellyfunction on line 2?
(b)(1.0 pt) (b)What is the final value ofitemin thef2frame when the environment diagram is complete?
(c) (1.0 pt) (c)What is the return value of thef2frame?
(d)(2.0 pt) (d)For the variablebeanin thef1frame, what isbean[4]when the environment diagram is
complete?
(e) (1.0 pt) (e)What is the return value of framef1?
(f) (1.0 pt) Line 15What islen(bean)in the global frame?
- (5.0 points) Just Keep Summing
Implement the functionsum_until, which takes in an integertotal, and returns a one-argument function,
add_num. Theadd_numfunction keeps accepting integers until the sum of all the integers it has accepted reaches
or exceeds the total, in which case it returnsTrueorFalserespectively.
The expected behavior of the function is detailed in the doctests below.
def sum_until(total):
"""
>>> f = sum_until(0)
>>> f(0) # 0 = 0
True
>>> f(-7) # -7 < 0, so continue to accept more numbers
<function sum_until.<locals>.add_num at ....>
>>> f(-7)(5)(2) # -7 + 5 + 2 = 0
True
>>> f(-7)(5)(8) # -7 + 5 + 8 = 6 > 0
False
>>> g = sum_until(-5)
>>> g(-6)(3) # -6 + 3 = -3 > -
False
>>> g(-11)(-2)(-2)(4)(6) # -11 + -2 + -2 + 4 + 6 = -
True
"""
def add_num(x):
if x > total:
return _____________Part A________________
elif _____________Part B________________:
return _____________Part C________________
return sum_until(_____________Part D________________)
return add_num
(a) (1.0 pt)Fill in the code for Part A.
(b) (1.0 pt)Fill in the code for Part B.
(c) (1.0 pt)Fill in the code for Part C.
(d) (2.0 pt)Fill in the code for Part D.
- (7.0 points) Flip Flop
Implement theflip_flopfunction which takes in a non negative numbernand computes the value generated
when alternating between adding then subtracting each of the digits innfrom left to right.
You may use theget_lengthfunction that takes in an integernand returns the number of digits inn. This
functions implementation is hidden, but you can assume it works correctly.
def get_length(n):
"""
Helper function that computes the number of digits in an
integer.
>>> get_length(7)
1
>>> get_length(123)
3
>>> get_length(454545)
6
"""
# Implementation hidden
def flip_flop(n):
"""
>>> flip_flop(124) # 1 + 2 - 4
flip_flop(7315) # 7 + 3 – 1 + 5 14 flip_flop(61323) # 6 + 1 – 3 + 2 – 3 3 """ if ____________________________________: ____________________________________ else: last_digit = ____________________________________ if ____________________________________: return ____________________________________ else: return ____________________________________
(a) (7.0 pt)Write the fullycompletedflip_flopfunction below using the skeleton code provided. You may not add, change, or delete lines from the skeleton code. Dont forget to use the helper functionget_length(n).
def flip_flop(n):
if ___________________________________________________:
___________________________________________
else:
last_digit = ________________________________________________
if ___________________________________________________:
return __________________________________________________
else:
return __________________________________________________
- (8.0 points) Cra88y Crawl
You are working at an amusement park this summer and are in charge of the Cra88y Crawl ride! Complete the
following questions to collect information that can improve visitors experience on this ride!
The line of visitors is represented as a list of two element tuples.
- The first element in the tuple is the time when the visitor joined the line.
- The second element is the amount of time the visitor is expected to wait to begin their ride. Time is represented as the number of minutes elapsed since the amusement park opened for that day. For example, the tuple(80, 40)represents that a visitor joined at the 80th minute and is expected to wait in line for 40 minutes. (a) (3.0 pt)Complete the return statement for theexpected_start_timesfunction that, given a line, returns a list of the times (represented in minutes) at which every visitor is expected to start their ride! def expected_start_times(line): """
expected_start_times([(80, 40), (105, 20)]) [120, 125] expected_start_times([(5, 15), (8, 12), (14, 6), (222, 3)]) [20, 20, 20, 225] expected_start_times([(4, 6), (5, 5), (5, 5), (6, 15), (100, 20), (150, 0)]) [10, 10, 10, 21, 120, 150] """ return ______________________________________________
(b)(5.0 pt)Implement theremove_frustrated_visitorsfunction that removes the tuples corresponding to visitors who are expected to wait more thanmax_wait_timeminutes in line. def remove_frustrated_visitors(line, max_wait_time): """
line_a = [(80, 40), (105, 20)] # format per tuple: (join time, expected wait time) remove_frustrated_visitors(line_a, 15) line_a [] line_b = [(5, 15), (8, 12), (14, 6), (222, 3)] remove_frustrated_visitors(line_b, 10) line_b [(14, 6), (222, 3)] line_c = [(4, 6), (5, 5), (5, 5), (6, 15), (100, 20), (150, 0)] remove_frustrated_visitors(line_c, 5) line_c [(5, 5), (5, 5), (150, 0)] """ position = 0 while position < len(line): if ____________________________________:
else:
Fill in the solution in the spce provided. You should not need to add or remove lines.
def remove_frustrated_visitors(line, max_wait_time):
position = 0
while position < len(line):
if ___________________________________________________:
___________________________________________________
else:
___________________________________________________
- (7.0 points) Chefs Assistant
You are a chef managing orders for your restaurant! Every order consists of a food item and its quantity.
Implement the functionadd_new_orderswhich takes in a dictionaryall_ordersrepresenting the orders a
chef is currently assigned, and mutates it to include new orders from the listnew_orders. Each element in
new_ordersis a tuple, where the first element is the food item and the second element is that items quantity.
def add_new_orders(all_orders, new_orders):
"""
>>> order = {'fries': 3, 'burger': 4}
>>> add_new_orders(order, [('fries', 4), ('milk', 2)])
>>> order == {'fries': 7,'burger': 4,'milk': 2}
True
>>> add_new_orders(order, [('fries', 2), ('taco', 1)])
>>> order == {'fries': 9,'burger': 4,'milk': 2,'taco': 1}
True
"""
if _________________________________________:
return
food_item = new_orders[0][0]
quantity = new_orders[0][1]
if _________________________________________:
_________________________________________
else:
_________________________________________
add_new_orders(_________________________, _________________________)
(a) (7.0 pt)Complete the skeleton code. You may not add, change, or delete lines from the skeleton code.
def add_new_orders(all_orders, new_orders):
if ______________________________:
return
food_item = new_orders[0][0]
quantity = new_orders[0][1]
if ______________________________:
______________________________
else:
______________________________
add_new_orders(________________, ________________)
- (6.0 points) Smoooooooooth
Your friend is trying to implement a functionsmoothwhich takes in a list of integers,lst, and returns asmooth
version of the list, where smoothing a list means connecting each of the adjacent integers in the old list with
consecutive integers.
For example, the smoothed version of[1, 5, 3]is[1, 2, 3, 4, 5, 4, 3], and the smoothed version of[1,
3, 4, 6]is[1, 2, 3, 4, 5, 6]. There is guaranteed to be at least one number in the list and there will not
be identical numbers consecutively, so[1, 1, 1, 1]is an invalid input. Your friends code has 3 bugs which
you need to find!
- def smooth(lst):
- new_lst = []
- for i in range(len(lst) – 1):
- curr = lst[i]
- next = lst[i + 1]
- while curr != next:
- new_lst + [curr]
- if curr > next:
- curr += 1
- else:
- curr -= 1
- return new_lst In each box:Identifyoneof the 3 unique bugs and explain how to fix each bug. You must specify the line number you would change or delete, or between which lines you would add a new line of code. (a) (2.0 pt)
(b) (2.0 pt)
(c) (2.0 pt)
- (10.0 points) Overlap
You are working on representing users on a new messaging app called Overlap, which focuses on users interests
as a way to connect them! EveryUserhas a name, a list of interests, and a list of followers!
Implement the following functions of theUserclass based on the descriptions below. For a givenUser,a_user,
we should be able to execute:
- a_user.add_follower(other_user): Takes in another User objectother_userand adds it to this users followers list if they are not already in the list
- a_user.mutual_interests(other_user): Takes in another User objectother_userand returns a list containing all of this users interests that are shared withother_user
- a_user.find_new_interest(): Returns a string representing a new interest for this User. To determine this new interest, first identify this users follower that has the largest number of mutual interests with this user. Then return a randomly selected interest from this follower. But be careful, this randomly selected interest must not already exist in this users interests (otherwise it would not be new!). Assume that the users interests and followers are non-empty. import random
class User:
def __init__(self, name, interests=[]):
self.name = name
self.interests = interests
self.followers = []
def add_follower(self, other_user):
""" Part A """
def mutual_interests(self, other_user):
""" Part B """
def separate_interests(self, other_user):
""" Implementation not shown. Assume that this function takes in
another User object and returns a list containing all
of this users interests that are NOT shared with other_user"""
def find_new_interest(self):
""" Part C """
(a) i.(3.0 pt)Implement theadd_followermethod which takes in anotherUserobject,other_user, and adds that user to this users followers list if they are not already in the list. def add_follower(self, other_user): """
u1 = User(‘bob’, [‘cooking’, ‘archery’,’tv’]) u2 = User(‘alice’, [‘shopping’, ‘guitar’, ‘cooking’]) u3 = User(‘mike’, [‘poker’, ‘tv’,’cooking’]) u1.add_follower(u2) u1.add_follower(u3) u1.add_follower(u2) # no change [u.name for u in u1.followers] [‘alice’, ‘mike’] """ if _____________________________________________:
Write the fullyadd_followerfunction below using the skeleton code provided. You may not add, change, or delete lines from the skeleton.
def add_follower(self, other_user):
if _____________________________________________:
_____________________________________________
(b) i.(3.0 pt)Implement themutual_interestsmethod which takes in anotherUserobject,other_user, and returns a list containing all of this users interests that are shared withother_user. (Again, there isno needto copy the doctests.) def mutual_interests(self, other_user): """
u1 = User(‘bob’, [‘cooking’, ‘archery’,’tv’]) u2 = User(‘alice’, [‘shopping’, ‘guitar’, ‘cooking’]) u3 = User(‘mike’, [‘poker’, ‘tv’,’cooking’]) u1.mutual_interests(u2) [‘cooking’] u1.mutual_interests(u3) [‘cooking’,’tv’] """ return _____________________________________________ Complete thereturnstatement of themutual_interestsfunction below.
(c) i.(4.0 pt)Implement thefind_new_interestmethod that returns a string representing a new potential interest for thisUser. To determine this new interest, first identify this users most similar follower that has the largest number of mutual interests with this user. Then return a randomly selected interest from this follower. But be careful, this randomly selected interest must not already exist in this users interests (otherwise it would not be new!). For this problem, assume that the users interests and followers are non-empty. Note that the separate_interestsfunction (seeUserclass skeleton) may be helpful here. You may userandom.choice(lst) to return a radomly selected item from a list,lst. def find_new_interest(self): """
u1 = User(‘bob’, [‘cooking’, ‘archery’,’tv’]) u2 = User(‘alice’, [‘shopping’, ‘guitar’, ‘cooking’]) # has one in common with bob u3 = User(‘mike’, [‘poker’, ‘tv’,’cooking’]) # has two in common with bob u1.add_follower(u2) u1.add_follower(u3) u1.find_new_interest() ‘poker’ """ most_similar_follower = max( ____________________________________, key = _______________________________________ ) return random.choice(_____________________________________________) Write the fullycompletedfind_new_interestfunction below using the skeleton code provided. You may not add, change, or delete lines from the skeleton code.
def find_new_interest(self):
most_similar_follower = max(
____________________________________,
key = _______________________________________
)
return random.choice(_____________________________________________)
No more questions.