CS代考 DECEMBER 2017 EXAMINATIONS

UNIVERSITY OF TORONTO Faculty of Arts and Science
DECEMBER 2017 EXAMINATIONS
CSC 108 H1F Instructor(s): Campbell, Fairgrieve, and —3 hours No Aids Allowed
You must earn at least 28 out of 70 marks (40%) on this final examination in order to pass the course. Otherwise, your final course grade will be no higher than 47%.

Student Number: UTORid: Family Name(s): First Name(s):
Do not turn this page until you have received the signal to start. In the meantime, please read the instructions below carefully.
This Final Examination paper consists of 12 questions on 21 pages (including this one), printed on both sides of the paper. When you receive the signal to start, please make sure that your copy of the paper is complete and fill in your Student Number, UTORid and Name above.
• Comments and docstrings are not required except where indi- cated, although they may help us mark your answers.
• You do not need to put import statements in your answers.
• No error checking is required: assume all function arguments
have the correct type and meet any preconditions.
• If you use any space for rough work, indicate clearly what you want marked.
• Do not remove pages or take the exam apart.
Marking Guide
#1: / 6 #2: / 4 #3: / 6 #4: / 4 #5: / 4 #6: / 6 #7: / 6 #8: / 3 #9: / 5
# 10: / 6 # 11: /12 # 12: /8
TOTAL: /70
Page 1 of 21 Good Luck!
PLEASE HAND IN
PLEASE HAND IN

CSC 108 H1F Final Examination December 2017 Question 1. [6 marks]
Each of the following sets of Python statements will result in an error when the code is run. In the table below, briefly explain why each error occurs.
Python statements Briefly explain why each error occurs
stations = (‘Pape’, ‘King’, ‘Kipling’)
stations[0] = ‘St. George’
st_to_line = {‘Chester’: 2,
‘Davisville’: 1,
‘Union’: 1}
if st_to_line[‘Dundas’] == 1:
print(‘Yonge-University’)
lines = [1, 2, 3, 4]
while lines[i] != 5 and i < len(lines): print(lines[i]) i=i+1 stops = ['Christie', 'Bay', 'Spadina'] sorted_stops = stops.sort() reversed_stops = sorted_stops.reverse() station = ' ' station[-4] = 'E' station[-3] = 'a' # Assume the next line runs without error. f = open('stations.txt') f.readline()[0] Page 2 of 21 cont’d. . . CSC 108 H1F Final Examination December 2017 Question 2. [4 marks] Fill in the boxes with the while loop condition and the while loop body required for the function to work as described in its docstring. See the bottom of this page for examples. def get_and_verify_password(password: str) -> bool:
“””Repeatedly prompt the user to enter their password until they get it
correct or until they guess wrong three times. Return True if and only if
the password was entered correctly.
msg = ‘Enter your password: ‘
guess = input(msg)
num_guesses = 1
return guess == password
———————————————————————————– Here are examples from using a correct implementation of get_and_verify_password:
>>> get_and_verify_password(‘csc108!’)
Enter your password: csc108!
>>> get_and_verify_password(‘^S33kReT’)
Enter your password: chairman
Enter your password: ^S33kReT
>>> get_and_verify_password(‘csc108!’)
Enter your password: CSC
Enter your password: 108
Enter your password: IDoNotKnow
Page3of21 Student #: over. . .

CSC 108 H1F Final Examination December 2017 Question 3. [6 marks]
In this question, you are to write code that uses a Python dictionary where each key represents the name of a meal (e.g., ‘stew’, ‘eggs’) and the associated value represents a list of table numbers (e.g., 1, 2, 3), with one list item for each meal order. If there are, for example, three orders for ‘stew’ at table 2, then 2 will appear three times in the list of table numbers associated with ‘stew’.
Part (a) [3 marks] Complete the following function according to its docstring.
def get_num_orders(meal_to_tables: Dict[str, List[int]], meal: str) -> int:
“””Return the number of orders for meal in meal_to_tables.
>>> m_to_t = {‘stew’: [4, 1], ‘eggs’: [6]}
>>> get_num_orders(m_to_t, ‘stew’)
>>> get_num_orders(m_to_t, ‘eggs’)
>>> get_num_orders(m_to_t, ‘brussel sprouts’)
Part (b) [3 marks] Complete the following function according to its docstring.
def order_meal(meal_to_tables: Dict[str, List[int]], meal: str, table: int) -> None:
“””Modify meal_to_tables to include a new order for meal at table. Place
table at the end of the list of table number(s) associated with meal.
>>> m_to_t = {}
>>> order_meal(m_to_t, ‘stew’, 4)
>>> m_to_t == {‘stew’: [4]}
>>> order_meal(m_to_t, ‘stew’, 1)
>>> m_to_t == {‘stew’: [4, 1]}
>>> order_meal(m_to_t, ‘eggs’, 6)
>>> m_to_t == {‘stew’: [4, 1], ‘eggs’: [6]}
Page 4 of 21
cont’d. . .

CSC 108 H1F Final Examination Question 4. [4 marks]
Complete the following function according to its docstring.
def char_count(s: str, words: List[str]) -> List[int]:
“””Return a new list in which each item is the number of times
that the character at the corresponding position of s appears in
the string at the corresponding position of words.
Lowercase and uppercase characters are considered different.
Precondition: len(s) == len(words)
# In the example below, ‘a’ is in ‘apple’ 1 time,
# ‘n’ is in ‘banana’ 2 times, and
# ‘b’ is in ‘orange’ 0 times.
>>> char_count(‘anb’, [‘apple’, ‘banana’, ‘orange’])
>>> char_count(‘xdaao’, [‘cat’, ‘dog’, ‘cat’, ‘banana’, ‘cool’])
[0, 1, 1, 3, 2]
>>> char_count(‘fW’, [‘sandwiches’, ‘waffles’])
December 2017
Page 5 of 21 Student #:

CSC 108 H1F Final Examination December 2017 Question 5. [4 marks]
The docstring below is correct. However, the code in the function body contains one or more bugs. As a result the function does not work as specified in the docstring.
def increment_sublist(L: List[int], start: int, end: int) -> None:
“””Modify L so that each element whose index is in the range from start (inclusive)
to end (exclusive) is incremented by 1.
Precondition: 0 <= start < end <= len(L) >>> a_list = [10, 20, 30, 40, 50, 60]
>>> increment_sublist(a_list, 0, 3)
>>> a_list
[11, 21, 31, 40, 50, 60]
for value in L[start:end]:
value = value + 1
Part (a) [1 mark]
Complete the example below to show what happens when the buggy function body given above is used.
>>> a_list = [10, 20, 30, 40, 50, 60]
>>> increment_sublist(a_list, 0, 3)
>>> a_list
Part (b) [3 marks]
Write a new function body that correctly implements the function as described in its docstring above.
def increment_sublist(L: List[int], start: int, end: int) -> None:
“””
Page 6 of 21 cont’d. . .

CSC 108 H1F Final Examination December 2017
Question 6. [6 marks]
In each of the following, circle the best answer that follows directly below the question.
Part (a) [1 mark] If you were searching a sorted list of one million unique items for a particular value, and the value being searched for was the second item in the sorted list, which algorithm would take the least time?
[1 mark] If you were searching a sorted list of one million unique items for a particular value, and the value being searched for was not in the sorted list, which algorithm would take the least time to discover that it was not in the list?
binary a tie between linear an error
search search and binary search would occur
If you had an unsorted list of one million unique items, and knew that you would only search it once for a value, which of the following algorithms would be the fastest?
use linear
search on the
unsorted list
use insertion sort
to sort the list
and then binary
search on the
sorted list
use insertion sort an error
to sort the list would occur
and then linear
search on the
sorted list
binary a tie between linear an error
search search and binary search would occur
Part (d) [1 mark] Our sorting code completes all passes of the algorithm, even if the list becomes sorted before the last pass. After how many passes of the bubble sort algorithm on the list [ 3, 1, 6, 4, 9, 8 ] could we stop because the list has become sorted?
Part (e) [1 mark] Our sorting code completes all passes of the algorithm, even if the list becomes sorted be- fore the last pass. After how many passes of the insertion sort algorithm on the list [ 9, 8, 3, 1, 6, 4 ] could we stop because the list has become sorted?
Part (f) [1 mark] Our sorting code completes all passes of the algorithm, even if the list becomes sorted be- fore the last pass. After how many passes of the selection sort algorithm on the list [ 9, 8, 6, 4, 3, 1 ] could we stop because the list has become sorted?
Page 7 of 21 Student #: over. . .

CSC 108 H1F Final Examination December 2017 Question 7. [6 marks]
Complete the following function according to its docstring.
Your code must not mutate the parameters!
def collect_sublists(L: List[List[int]], threshold: int) -> List[List[int]]:
“””Return a new list containing the sublists of L in which all the values
in the sublist are above threshold.
Precondition: all sublists of L have length >= 1
>>> collect_sublists([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 5)
[[7, 8, 9]]
>>> collect_sublists([[15, 20], [10, 11], [30, 40], [7, 17]], 10)
[[15, 20], [30, 40]]
Page 8 of 21
cont’d. . .

CSC 108 H1F Final Examination Question 8. [3 marks]
Fill in the boxes to complete the docstring examples for the function below.
def mystery(L: List[str], D: Dict[str, str]) -> None:
“””
>>> list1 = [‘I’, ‘love’, ‘midterms’]
>>> dict1 = {‘midterms’: ‘finals’}
>>> mystery(list1, dict1)
>>> dict2 =
>>> mystery(list1, dict2)
[‘We’, ‘love’, ‘programming’]
>>> list3 = [‘m’, ‘y’, ‘q’, ‘p’, ‘w’, ‘m’]
>>> dict3 = {‘m’: ‘r’, ‘q’: ‘r’}
>>> mystery(list3, dict3)
for key in D:
index = L.index(key)
L[index] = D[key]
December 2017
Page 9 of 21 Student #:

CSC 108 H1F Final Examination December 2017 Question 9. [5 marks]
Part (a) [4 marks] The docstring below is correct. However, the code in the function body contains one or more bugs. As a result the function does not work as specified in the docstring.
def is_valid_word(potential_word: str, word_list: List[str]) -> bool:
“””Return True if and only if potential_word is one of the items in word_list.
>>> is_valid_word(‘cat’, [‘cat’, ‘dog’, ‘fox’])
>>> is_valid_word(‘wombat’, [‘cat’, ‘dog’, ‘fox’])
for word in word_list:
if potential_word in word:
return True
return False
Complete the unittest code below so that: (1) the assertions both fail when the buggy function body given above is used, and (2) the assertions both pass when a function body that correctly implements the function as described in its docstring is used. Both arguments must have the correct type. Assume that the is_valid_word function has been correctly imported and may be called as written below.
class TestIsValidWord(unittest.TestCase):
def test_case1(self):
potential_word =
word_list =
actual = is_valid_word(potential_word, word_list)
expected = False
self.assertEqual(actual, expected)
def test_case2(self):
potential_word =
word_list =
actual = is_valid_word(potential_word, word_list)
expected = True
self.assertEqual(actual, expected)
Part (b) [1 mark] Circle the term below that best describes the number of times the loop iterates when the buggy version of the is_valid_word function given in Part (a) is called.
something else
Page 10 of 21
cont’d. . .
constant linear quadratic

CSC 108 H1F
Final Examination
December 2017
Question 10. [6 marks] Consider this code:
def mystery(n: int) -> None:
“””
for i in range(n):
for j in range(n):
if i == j:
print(i + j)
Part (a) [1 mark]
What is printed when mystery(3) is executed?
Part (b) [1 mark]
Write an English description of what function mystery prints in terms of n.
Part (c) [1 mark]
For function mystery the best and worst case running times are the same. Circle the term below that best
describes the running time of the mystery function as written above.
constant linear quadratic something else
Part (d) [2 marks]
The code above can be rewritten to complete the same task, but with a reduced running time. Write the
body of a new version of mystery in which the running time expressed in terms of n is improved.
def mystery_improved(n: int) -> None:
“””
Part (e) [1 mark]
Circle the term below that best describes the running time of the your mystery_improved function.
Page 11 of 21
constant linear quadratic something else Student #: over. . .

CSC 108 H1F Final Examination December 2017
Question 11. [12 marks] Part (a) [6 marks]
Station data is stored in a comma separated values (CSV) file with one station’s ID, name, latitude, and longitude per line in that order. Here is an example station data CSV file:
1,Allen,43.667158,-79.4028 12,Bayview,43.656518,-79.389 8,Chester,43.648093,-79.384749 17,Davisville,43.66009,-79.385653
Given the example station data CSV file opened for reading, function build_dictionaries returns:
({1: [43.667158, -79.4028], 12: [43.656518, -79.389],
8: [43.648093, -79.384749], 17: [43.66009, -79.385653]},
{1: ‘Allen’, 12: ‘Bayview’, 8: ‘Chester’, 17: ‘Davisville’})
Complete the function build_dictionaries according to the example above and its docstring below.
Assume the given file has the correct format.
def build_dictionaries(f: TextIO) -> Tuple[Dict[int, List[float]], Dict[int, str]]:
“””Return a tuple of two dictionaries with station data from f. The first dictionary
has station IDs as keys and station locations (two item lists with latitude and longitude)
as values. The second dictionary has station IDs as keys and station names as values.
Precondition: station IDs in f are unique
Page 12 of 21 cont’d. . .

CSC 108 H1F Final Examination December 2017 Part (b) [6 marks]
You may assume the function get_distance has been implemented:
def get_distance(lat1: float, long1: float, lat2: float, long2: float) -> float:
“””Return the distance between the location at lat1 and long1 and
the location at lat2 and long2.
Using get_distance as a helper function, complete function get_closest_station according to its docstring:
def get_closest_station(lat: float, long: float, id_to_location: Dict[int, List[float]],
id_to_name: Dict[int, str]) -> str:
“””Return the name of the station in id_to_name and id_to_location that is
closest to latitude lat and longitude long. You may assume that exactly one
station is closest.
Precondition: id_to_location and id_to_name have the same keys
and len(id_to_location) >= 1
>>> id_to_location = {3: [40.8, -73.97], 4: [43.6, -79.4], 11: [51.5, -0.1]}
>>> id_to_name = {3: ‘Grand Central’, 4: ‘Union’, 11: ‘Blackfriars’}
>>> get_closest_station(43.5, -79.6, id_to_location, id_to_name)
Page 13 of 21 Student #: over. . .

CSC 108 H1F Final Examination December 2017 Here is the header and docstring for class Restaurant.
class Restaurant:
“””Information about a Restaurant.”””
Part (a) [1 mark] Complete the body of this class Restaurant method according to its docstring.
def __init__(self, name: str) -> None:
“””Initialize a new restaurant that is named name with an empty list
of tables.
>>> rest1 = Restaurant(‘UofT Diner’)
>>> rest1.name
‘UofT Diner’
>>> rest1.tables
Part (b) [3 marks] Complete the body of this class Restaurant method according to its docstring. Use class Table when possible.
def add_table(self, num_seats: int) -> None:
“””Add a new table with num_seats seats to this restaurant. Table IDs should
be in the order that tables are added to this restaurant starting from 1.
No seats at the table are occupied.
Precondition: num_seats >= 1
>>> rest1 = Restaurant(‘UofT Diner’)
>>> rest1.tables
>>> rest1.add_table(4)
>>> str(rest1.tables[0])
‘Table 1: 0 of 4 seats occupied’
>>> rest1.add_table(6)
>>> str(rest1.tables[1])
‘Table 2: 0 of 6 seats occupied’
Page 15 of 21 Student #: over. . .

CSC 108 H1F Final Examination December 2017 Part (c) [4 marks]
Complete the body of this class Restaurant method according to its docstring.
def calculate_occupancy(self) -> float:
“””Return the percentage of seats that are occupied for all tables in
this restaurant.
Precondition: len(self.tables) >= 1
>>> rest1 = Restaurant(‘Snacks-R-Us’)
>>> rest1.add_table(2)
>>> rest1.add_table(6)
>>> rest1.tables[0].set_occupancy(2)
>>> rest1.tables[1].set_occupancy(3)
>>> rest1.calculate_occupancy()
Page 16 of 21
cont’d. . .

CSC 108 H1F Final Examination December 2017 DO NOT DETACH THIS PAGE
Use the space on this “blank” page for scratch work, or for any answer that did not fit elsewhere.
Clearly label each such answer with the appropriate question and part number, and refer to this answer on the original question page.
Page 17 of 21 Student #: over. . .

CSC 108 H1F Final Examination December 2017 DO NOT DETACH THIS PAGE
Short Python function/method descriptions:
__builtins__:
input([prompt: str]) -> str
Read a string from standard input. The trailing newline is stripped. The prompt string,
if given, is printed without a trailing newline before reading.
abs(x: float) -> float
Return the absolute value of x.
chr(i: str) -> Unicode character
Return a Unicode string of one character with ordinal i; 0 <= i <= 0x10ffff. 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts