UNIVERSITY OF TORONTO Faculty of Arts & Science
December 2019 Examinations
CSC 108 H1F
Duration: 3 hours
Copyright By PowCoder代写 加微信 powcoder
Aids Allowed: None
First (Given) Name(s):
Last (Family) Name(s):
10-Digit Student Number:
Do not turn this page until
you have received the signal to start.
In the meantime, write your name, student number, and UTORid below (please do this now!) and carefully read all the information on the rest of this page.
UTORid (e.g., pitfra12):
• This final examination consists of 10 questions on 22 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 examination is complete.
• Answer each question directly on the examination paper, in the space provided, and use a “blank” page for rough work. If you need more space for one of your solutions, use one of the “blank” pages and indicate clearly the part of your work that should be marked.
• Comments and docstrings are not required except where indicated, 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.
• Remember that, in order to pass the course, you must achieve a grade of at least 40% on this final examination.
• As a student, you help create a fair and inclusive writing environment. If you possess an unauthorized aid during an exam, you may be charged with an academic offence.
Marking Guide
No 10: /20 TOTAL: /75
students must hand in all examination materials at the end
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question1. [4marks]
Part (a) [1 mark] Complete the function is_eligible_for_award according to its docstring below.
def is_eligible_for_award(gpa: float, major: str, req_gpa: float, req_major: str) -> bool: “””Return True if and only if gpa is greater than or equal to req_gpa and
major is equal to req_major.
>>> is_eligible_for_award(4.0, ‘CS’, 3.5, ‘CS’)
>>> is_eligible_for_award(4.0, ‘Econ’, 3.5, ‘CS’)
>>> is_eligible_for_award(3.3, ‘CS’, 3.5, ‘CS’)
Part (b) [3 marks] Complete the function get_award_winners according to its docstring below. Your code must
call the function is_eligible_for_award from Part (A).
def get_award_winners(applicants: List[Tuple[float, str, str]], req_gpa: float,
req_major: str) -> List[Tuple[float, str]]:
“””Return a new list of students from applicants who are eligible for an
award, based on req_gpa and req_major. Each student in applicants is of
the form (gpa, name, major).
In the new list, award winning students should be of the form (gpa, name)
and should appear in the same order as they appear in the original list.
>>> get_award_winners([(3.6, ‘JC’, ‘CS’), (4.0, ‘MB’, ‘CS’), (3.7, ‘JW’, ‘Econ’)], 3.2, ‘CS’) [(3.6, ‘JC’), (4.0, ‘MB’)]
>>> get_award_winners([(3.6, ‘JC’, ‘Bio’), (4.0, ‘MB’, ‘Bio’),
[(4.0, ‘MB’)]
(3.7, ‘JW’, ‘Econ’)], 3.7, ‘Bio’)
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question2. [4marks]
Function mask_string has been correctly implemented. Fill in the missing parts of the docstring description and
examples so that they match the function’s header and body.
def mask_string(s: str, mask: List[bool], ch: str) -> str:
“””Return a new string that is the same as
but with each character that corresponds to a True element in replaced with .
Precondition : len(ch) == 1 and
>>> mask_string(‘mask’,[True, True, True, True],‘?’)
>>> mask_string(‘ComSc’, [
‘C–S-’ “””
masked_string = ‘’
for i in range(len(s)):
, , , , ], )
if mask[i]:
masked_string = masked_string + ch
masked_string = masked_string + s[i]
return masked_string
Question3. [6marks]
In Assignment 1, we split a message into substrings (called tweets), where each tweet had a length equal to MAX_LENGTH characters, except the last tweet which had a length of at least 1 up to MAX_LENGTH (inclusive). For example, for a MAX_LENGTHof10andthemessage‘This is such an amazing note!’,inA1wesplitthemessageinto3tweets:
‘This is su’,‘ch an amaz’,and‘ing note!’.
You must implement an improved version in which the message is split so that no word is divided across multiple tweets. In this improved version, the message above is split into the 4 tweets with lengths as close to MAX_LENGTH as possible (but not longer than MAX_LENGTH) and spaces omitted from the beginning and end of tweets:
‘This is’,‘such an’,‘amazing’,‘note!’.
Complete the function split_message according to the description above and docstring below. Do not add any code outside of the boxes. Your code must use the provided constant. You may assume that there is exactly one space between words in the message and that there is no whitespace at the beginning or end of the message.
MAX_LENGTH = 10
def split_message(msg: str) -> List[str]:
“””Return a new list containing msg split into tweets so that no words are
divided across multiple tweets. A word is a sequence of non-whitespace
characters. In the tweets, each pair of words must have a space between them.
There should not be any spaces at the beginning or end of tweets.
Precondition: no word in msg is longer than MAX_LENGTH
>>> split_message(‘One hundred and one’)
[‘One’, ‘hundred’, ‘and one’]
# split message into words
while i < :
# combine tweet i and tweet i+1 into a potential tweet
potl_tweet =
# update tweet i to be potential tweet; remove tweet i + 1
# couldn’t combine tweets, so increment i (tweet i is finalized) i=i+1
return tweets
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question4. [6marks]
This problem involves using a point system to score words. Each letter has a point value and is represented in a "letter to points" dictionary, where each key is a lowercase letter and each value is the points corresponding to that letter. An example of a "letter to points" dictionary is:
{‘a’: 1, ‘b’: 2, ‘c’: 3, ‘d’: 2, ‘e’: 1, ‘f’: 4, ..., ‘z’: 10}
Words are scored by adding up the points associated with each of their letters. According to the dictionary above, the word ‘Bee’ is worth 4 points (2 + 1 + 1) and the word ‘bEAd’ is worth 6 points (2 + 1 + 1 + 2). Only lowercase letters appear in "letter to points", so uppercase letters are scored based on the corresponding lowercase letter’s points.
Consider this example file with one word per line: a
BE bee Bee bEAd
Each line in the file contains a unique word composed only of letters. Each word has at least one letter. There are no blank lines in the file. Words are case-sensitive (e.g., ‘bee’ and ‘Bee’ are considered to be different words.)
Given the example file above opened for reading and the "letter to points" dictionary above, function build_word_to_score should return this "word to score" dictionary:
{‘a’: 1, ‘BE’: 3, ‘bee’: 4, ‘Bee’: 4, ‘bEAd’: 6}
Complete the function build_word_to_score according to the example above and the docstring below. You may
assume the given file has the correct format and the "letter to points" dictionary contains all 26 lowercase letters.
def build_word_to_score(word_file: TextIO, letter_to_points: Dict[str, int]) -> Dict[str, int]:
“””Return a “word to score” dictionary, where each key is a word from word_file and
each value is the score for that word based on the points in letter_to_points.
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question5. [7marks]
In this question, you will implement two different algorithms for solving the same problem. Given a list of integers in
which each item occurs either once or twice, count the number of items that occur twice. Part(a) [4marks]
Complete this function according to its docstring by implementing the algorithm below:
1. Use an integer accumulator to keep track of the number of matches.
2. For each item in lst, compare it to all other items in lst and if the item matches an item other than itself, add to
the number of matches.
3. Return the number of duplicates.
Note: you must not use any list methods, but you may use the built-in function len().
To earn marks for this question, you must follow the algorithm described above.
def count_duplicates_v1(lst: List[int]) -> int:
“””Return the number of duplicates in lst.
Precondition: each item in lst occurs either once or twice.
>>> count_duplicates_v1([1, 2, 3, 4])
>>> count_duplicates_v1([2, 4, 3, 3, 1, 4])
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Part(b) [3marks]
Complete this function according to its docstring by implementing the algorithm below:
1. Use a dictionary accumulator to track items and the number of times they occur in lst.
2. For each item in lst, if it is not already a key in the dictionary, add it along with a value of 1. If it is already a key
in the dictionary, increase the value associated with it by 1.
3. Return the difference between the number of items in lst and the number of items in the dictionary.
Note: you must not use any list methods, but you may use the built-in function len().
To earn marks for this question, you must follow the algorithm described above.
def count_duplicates_v2(lst: List[int]) -> int:
“””Return the number of duplicates in lst.
Precondition: each item in lst occurs either once or twice.
>>> count_duplicates_v2([1, 2, 3, 4])
>>> count_duplicates_v2([2, 4, 3, 3, 1, 4])
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question6. [4marks]
Part (a) [3 marks] Consider using a List[List[int]] to represent a square grid of integers (as we did in A2 to
represent an elevation map). Complete the function swap_rows_and_columns according to its docstring below.
def swap_rows_and_columns(grid: List[List[int]]) -> None:
“””Modify grid so that each row in grid is swapped with the corresponding column.
For example, row 0 is swapped with column 0, row 1 is swapped with column 1, and so on.
Precondition: each list in grid has the same length as grid and len(grid) >= 2
>>> G2 = [[1, 2],
… [3, 4]]
>>> swap_rows_and_columns(G2)
>>> G2 == [[1, 3],
… [2, 4]]
>>> G3 = [[1, 2, 3],
… [4, 5, 6],
… [7, 8, 9]]
>>> swap_rows_and_columns(G3)
>>> G3 == [[1, 4, 7],
[2, 5, 8],
[3, 6, 9]]
[1 mark] Circle the term below that best describes the running time of the swap_rows_and_columns
constant linear quadratic something else
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question7. [6marks]
Forthisquestion,a”persontofriends”dictionary(Dict[str, List[str]])hasaperson’snameasakeyandalist
of that person’s friends as the corresponding value. You can assume that each person has at least one friend.
Complete the function complete_person_to_friends according to its docstring below. Do not modify the provided code and only write your code after the provided code.
def complete_person_to_friends(p2f: Dict[str, List[str]]) -> None:
“””Modify the “person to friends” dictionary p2f so that all friendships are
bidirectional. That is, if person B is in person A’s list of friends, then
person A must be in person B’s list of friends. The friend lists must be
sorted in alphabetical order.
>>> friend_map = {‘JC’: [‘MB’]}
>>> complete_person_to_friends(friend_map)
>>> friend_map == {‘JC’: [‘MB’], ‘MB’: [‘JC’]}
>>> friend_map = {‘B’: [‘A’, ‘D’], ‘A’: [‘B’, ‘C’, ‘D’]}
>>> complete_person_to_friends(friend_map)
>>> friend_map == {‘B’: [‘A’, ‘D’], ‘A’: [‘B’, ‘C’, ‘D’], \
‘D’: [‘A’, ‘B’], ‘C’: [‘A’]}
>>> friend_map = {‘JC’: [‘MB’], ‘MB’: [‘JW’]}
>>> friend_map == {‘JC:’: [‘MB’], ‘MB’: [‘JC’, ‘JW’], ‘JW’: [‘MB’]}
>>> complete_person_to_friends(friend_map)
keys = list(p2f.keys())
for person in keys:
Question8. [7marks] Consider the function below:
def get_first_even(items: List[int]) -> int:
“””Return the first even number from items. Return -1 if items contains
no even numbers. The number 0 is considered to be even.
Part (a) [5 marks] Add five more distinct test cases to the table below. Do not test if the input, items, is mutated. No marks will be given for duplicated test cases. The six test cases below are not intended to be a complete test suite.
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Test Case Description
Expected Return Value
The empty list
Part (b) [2 marks] A buggy implementation of the get_first_even function is shown below. In the table below, complete the two test cases by filling in the three elements of items. The first test case should not indicate a bug in the function (the test case would pass), while the second test case should indicate a bug (the test case would fail). Both test cases should pass on a correct implementation of the function. If appropriate, you may use test(s) from Part (a).
def get_first_even(items: List[int]) -> int:
even_number = -1
for item in items:
if item % 2 == 0:
even_number = item
return even_number
Does not indicate bug (pass) [
Expected Return Value
Actual Return Value
Indicates bug (fail) [
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question9. [11marks]
In this question, you will write method bodies in classes to represent hotel and hotel room data. Here is the header and
docstring for class Room. class Room:
“””A hotel room.”””
Part (a) [1 mark] Complete the body of this class Room method according to its docstring.
def __init__(self, num: int, max_occupancy: int) -> None:
“””Initialize a room with room number num and a maximum occupancy of
max_occupancy that is not currently booked.
>>> r = Room(404, 2)
>>> r.room_number
>>> r.max_occupancy
>>> r.is_booked
[2 marks] Complete the body of this class Room method according to its docstring.
def book_room(self) -> bool:
“””If this room is not currently booked, update this room’s booking
status to booked and return True. Otherwise, return False and do not
change the booking status.
>>> r = Room(401, 4)
>>> r.book_room()
>>> r.is_booked
>>> r.book_room()
>>> r.is_booked
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Part (c) [2 marks] Complete the body of this class Room method according to its docstring. def __str__(self) -> str:
“””Return the string representation of this room.
>>> r = Room(48, 3)
>>> str(r)
‘Room 48 has a maximum occupancy of 3 and is not booked.’
>>> r.book_room()
>>> str(r)
‘Room 48 has a maximum occupancy of 3 and is booked.’
Now consider the class Hotel. Here is the header and docstring for class Hotel. You may assume classes Room and Hotel are in the same file (they do not need to be imported).
class Hotel:
“””A hotel that contains rooms.”””
Part (d) [1 mark] Complete the body of this class Hotel method according to its docstring. def __init__(self, hotel_name: str) -> None:
“””Initialize a hotel with a hotel_name and an empty rooms list.
>>> h = Hotel(“Sleep EZ”)
>>> h.hotel_name
‘Sleep EZ’
>>> h.rooms
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Part (e) [1 mark] Complete the body of this class Hotel method according to its docstring.
def add_room(self, room: ‘Room’) -> None:
“””Add this room to the end of this hotel’s rooms list.
You may assume that this room is not already in this hotel’s rooms list.
>>> h = Hotel(“Sleep EZ”)
>>> h.rooms
>>> r = Room(99, 4)
>>> h.add_room(r)
>>> h.rooms[0] == r
[2 marks] Complete the body of this class Hotel method according to its docstring. def get_max_occupancy(self) -> int:
“””Return the total occupancy of this hotel.
>>> h = Hotel(“Nighty Night”)
>>> h.add_room(Room(100, 3))
>>> h.add_room(Room(101, 4))
>>> h.get_max_occupancy()
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Part (g) [2 marks] Complete the body of this class Hotel method according to its docstring. For full marks on this question, your code should use existing methods (either directly or indirectly) where possible.
def __str__(self) -> str:
“””Return the string representation of this hotel.
>>> h = Hotel(“Nighty Night”)
>>> print(h)
Hotel: Nighty Night
>>> r1 = Room(100, 3)
>>> r2 = Room(101, 4)
>>> r2.book_room()
>>> h.add_room(r1)
>>> h.add_room(r2)
>>> print(h)
Hotel: Nighty Night
Room 100 has a maximum occupancy of 3 and is not booked.
Room 101 has a maximum occupancy of 4 and is booked.
rslt = ‘Hotel: {0}\n : {1}\n’.format( , )
rslt = rslt + ‘Rooms:’
for room in :
rslt = rslt +
return rslt
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
Question10. [20marks]
DO NOT put your answers here. You must fill in your answers on the last page of this booklet.
For Questions 1-4, consider the following assignment statement.
placements = {
‘NB’: [1, 5, 6],
‘Nike’: [2, 4],
‘Adidas’: [3, 7, 8],
‘Puma’: [9, 10]
1. What does the expression len(placements) == 10 evaluate to? (A) True
(C) Nothing, because an error will occur
2. What will this code print?
for x in placements:
for y in x:
print(y, end=‘,’)
(A) 1,5,6,2,4,3,7,8,9,10,
(B) 0,1,2,3,4,5,6,7,8,9,
(C) N,B,N,i,k,e,A,d,i,d,a,s,P,u,m,a,
(D) NB,Nike,Adidas,Puma,
(E) Nothing, because an error will occur
3. What will this code print?
for x in placements:
print(type(placements[x][0]))
(A)
(B)
(C)
(D)
(E) Nothing, because an error will occur
4. What will this code print?
del placements[‘NB’]
del placements[‘Adidas’]
print({‘Puma’: [9, 10], ‘Nike’: [2, 4]} == placements or ‘NB’ in placements)
(C) Nothing, because an error will occur
December 2019 Examinations CSC 108 H1F
Duration: 3 hours
DO NOT put your answers here. You must fill in your answers on the last page of this booklet.
For Questions 5-7, consider the plain text file my_file.txt (below left) and Python code (below right). Assume that the Python code is executed and runs without any errors.
Roses are red, Violets are blue. I love CSC108! How about you?
5. What does the variable jennifer refer to? (A) The empty string: ‘’
(B) The string: ‘Roses are red,\n’ (C) The string: ‘Roses are red,’
(D) The string: ‘Violets are blue.’
6. What does the variable joseph refer to? (A) The string: ‘Roses are red,\n’
mario = open(‘my_file.txt’, ‘r’)
jennifer = mario.readline().strip()
joseph = mario.readlines()[0]
jonathan = mario.read()
(B) The string: ‘Violets are blue.\n’
(C) The string: ‘How about you?\n’
(D) The list: [‘Violets are blue.\n’, ‘I love CSC108!\n’, ‘How about you?\n’] (E) The list: [‘Roses are red,\n’, ‘Violets are blue.\n’,
‘I love CSC108!\n’, ‘How about you?\n’]
7. What does the variable jonathan refer to? (A) An empt
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com