UNIVERSITY OF TORONTO Faculty of Arts and Science
DECEMBER 2018 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%.
Copyright By PowCoder代写 加微信 powcoder
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 10 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.
• As a student, you help create a fair and inclusive writing envi- ronment. If you possess an unauthorized aid during an exam, you may be charged with an academic offence.
Marking Guide
#1: / 6 #2: / 6 #3: / 5 #4: / 6 #5: / 6 #6: / 6 #7: /12 #8: /6 #9: /7
# 10: /10 TOTAL: /70
Page 1 of 21 Good Luck!
PLEASE HAND IN
PLEASE HAND IN
CSC 108 H1F Final Examination December 2018 Question 1. [6 marks]
Part 1: Select the option on the right that best describes what happens when the code on the left is run.
L = [1, 1, 2, 2, 3, 4] (A) [1, 1, 2, 2, 3, 4] is printed
for item in L:
if item % 2 == 1:
item = item + 1
(B) [2, 2, 2, 2, 4, 4] is printed
(C) A different list is printed
(D) An error occurs when the code is run
Part 2: Select the option on the right that best describes what happens when the code on the left is run.
L = [‘cat’, 5, ‘dog’, 4] (A) [‘cat\n’, ‘5\n’, ‘dog\n’, ‘4\n’] is printed
f = open(‘output.txt’, ‘w’)
for item in L:
f.write(str(item))
f = open(‘output.txt’, ‘r’)
print(f.readlines())
(B) [‘cat, ‘5’, ‘dog’, ‘4’] is printed (C) [‘cat5dog4’] is printed
(D) A different list is printed
(E) An error occurs when the code is run
Part 3: Select the option on the right that best describes what happens when the code on the left is run.
s = ‘big orange cats are best’
result = False
for each in s.split():
if each == ‘cats’:
result = True
result = False
if result:
print(‘cats found’)
print(‘no cats found’)
(A) cats found is printed
(B) no cats found is printed
(C) Something else is printed
(D) An error occurs when the code is run
Part 4: Select the option below that best describes what happens when this code is run.
shoes = [‘Saucony’, ‘Asics’, ‘Asics’, ‘NB’, ‘Saucony’, ‘Nike’, ‘Asics’, ‘Adidas’, ‘Saucony’, ‘Asics’]
shoes_to_places = {}
for i in range(len(shoes)):
shoes_to_places[shoes[i]].append(i + 1)
print(shoes_to_places)
(A) {‘Saucony’: [1, 5, 9], ‘Asics’: [2, 3, 7, 10], ‘NB’: [4], ‘Nike’: [6], ‘Adidas’: [8]} is printed (B) {‘Saucony’: [0, 4, 8], ‘Asics’: [1, 2, 6, 9], ‘NB’: [3], ‘Nike’: [5], ‘Adidas’: [7]} is printed (C) {‘Saucony’: [9], ‘Asics’: [10], ‘NB’: [4], ‘Nike’: [6], ‘Adidas’: [8]} is printed
(D) {‘Saucony’: [1], ‘Asics’: [2], ‘NB’: [4], ‘Nike’: [6], ‘Adidas’: [8]} is printed
(E) Something else is printed
(F) An error occurs when the code is run
Consider the following code.
D = {‘cat’: 5}
x = VALUE1
D[x] = VALUE2
Circle ALL of the options below that could Circle ALL of the options below that could used be in place of VALUE1 so the code would used be in place of VALUE2 so the code would
Page 2 of 21
cont’d. . .
run without error. (A) ‘dog’
run without error. (A) ‘dog’
(D) [‘a’, ‘b’]
(E) (‘a’, ‘b’)
(F) {‘a’: ‘b’}
(G) D[‘cat’]
(H) None of the above
(G) D[‘cat’]
(H) None of the above
CSC 108 H1F Final Examination December 2018 Question 2. [6 marks]
A board is a list of lists of length 1 strings, where each inner list has the same length. Precondition for all three functions below: the first parameter represents a board with at least one row and column.
Part (a) [1 mark] Complete the following function according to its docstring. def get_row(board: List[List[str]], row_num: int) -> List[str]:
“””Return row row_num of board.
>>> b = [[‘a’, ‘b’, ‘c’], [‘d’, ‘e’, ‘f’], [‘g’, ‘h’, ‘i’]]
>>> get_row(b, 0)
[‘a’, ‘b’, ‘c’]
>>> get_row(b, 2)
[‘g’, ‘h’, ‘i’]
Part (b) [2 marks] Complete the following function according to its docstring. def get_column(board: List[List[str]], column_num: int) -> List[str]:
“””Return column column_num of board.
>>> b = [[‘a’, ‘b’, ‘c’], [‘d’, ‘e’, ‘f’], [‘g’, ‘h’, ‘i’]]
>>> get_column(b, 0)
[‘a’, ‘d’, ‘g’]
>>> get_column(b, 2)
[‘c’, ‘f’, ‘i’]
Part (c) [3 marks] Complete the following function according to its docstring. Call at least one of the functions from Part (a) or Part (b) as a helper function.
def get_rotated_board(original: List[List[str]]) -> List[List[str]]:
“””Return a new board that is the same as board original but with its rows and columns swapped.
(Row 0 is swapped with column 0, row 1 is swapped with column 1, and so on.)
>>> b = [[‘a’, ‘a’, ‘a’, ‘a’], [‘b’, ‘b’, ‘b’, ‘b’], [‘c’, ‘c’, ‘c’, ‘c’]]
>>> get_rotated_board(b)
[[‘a’, ‘b’, ‘c’], [‘a’, ‘b’, ‘c’], [‘a’, ‘b’, ‘c’], [‘a’, ‘b’, ‘c’]]
Page 3 of 21
CSC 108 H1F Final Examination December 2018 Question 3. [5 marks]
A palindrome is a string that is read the same from front-to-back and back-to-front. For example, noon and racecar are both palindromes.
There are several ways to check whether a string is a palindrome. One algorithm compares the first letter to the last letter, the second letter to the second last letter, and so on, stopping when the middle of the string is reached or when a mismatch is found.
Part (a) [3 marks] Complete the function below using the algorithm described above. Do not modify code that is given outside of a box and do not add code outside of a box.
def is_palindrome(s: str) -> bool:
“””Return True if and only if s is a palindrome.
>>> is_palindrome(‘noon’)
>>> is_palindrome(‘racecar’)
>>> is_palindrome(‘dented’)
# In the box below, declare any additional variable(s), if needed
# In the box below, write the while loop condition
# In the box below, write the while loop body
return i == len(s) // 2
Part (b) [1 mark] For a string s of length n, where n is divisible by 2, how many times will the while
loop in is_palindrome iterate in the worst case?
Part (c) [1 mark] Circle the term below that best describes the worst case running time of the is_palindrome function.
something else
Page 4 of 21
cont’d. . .
constant linear quadratic
CSC 108 H1F Final Examination December 2018 Question 4. [6 marks]
Complete the function below to according to its docstring.
def update_messages(msgs: List[str], lens: List[int]) -> None:
“””Update the list of the strings in msgs so their lengths are adjusted to
match the value at the corresponding position in lens. Strings that are too
long should be shortened by leaving off characters at the end and strings
that are too short should be lengthened by adding underscores to the end.
Precondition: len(msgs) == len(lens) and all values in lens are >= 0
>>> messages = [‘aardvark’, ‘bear’, ‘cat’, ‘dog’]
>>> update_messages(messages, [6, 5, 5, 3])
>>> messages
[‘aardva’, ‘bear_’, ‘cat__’, ‘dog’]
>>> messages = [”, ‘cat’]
>>> update_messages(messages, [3, 0])
>>> messages
[‘___’, ”]
Page 5 of 21
CSC 108 H1F Final Examination December 2018 Question 5. [6 marks]
Each of the functions below has a correct docstring, but one or more bugs in the code. In the table below each function, write two test cases. 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 or an error would occur). If the code would stop due to an error on the second test case, write ‘Error’ in the Actual Return Value column for that test. Both test cases should pass on a correct implementation of the function.
def find_a_digit(s: str) -> int:
“””Return the index of the first digit in s, or the length of s if there are no digits. “””
while not s[i].isdigit():
i=i+1 return i
Does not indicate bug (pass)
Indicates bug (fail/error)
Argument for s
Actual Return Value
Expected Return Value
def has_a_fluffy(s: str) -> bool:
“””Return True if and only if s contains at least one character that is in ‘fluffy’.
for ch in s:
if ch in ‘fluffy’:
return True
return False
Does not indicate bug (pass)
Indicates bug (fail/error)
Argument for s
Actual Return Value
Expected Return Value
def get_year_of_study(num_credits: float) -> int:
“””Return the year of study at UofT given the number of credits num_credits, using these rules:
14.0 credits or more
9.0 to 13.5 credits
4.0 to 8.5 credits
< 4.0 credits
if num_credits >= 4.0:
elif num_credits >= 9.0:
elif num_credits < 4.0:
Does not indicate bug (pass)
Indicates bug (fail/error)
Argument for num_credits
Actual Return Value
Expected Return Value
Page 6 of 21
cont’d. . .
CSC 108 H1F
Final Examination
December 2018
Question 6. [6 marks] Consider this function:
def mystery(s: str) -> str:
“””
result = ”
while i < len(s) and not s[i] == '.':
result = result + s[i]
i=i+1 return result
Part (a) [1 mark]
Give an example of an argument of length 4 that would produce the best case behaviour of this function.
Part (b) [1 mark]
How many assignment statements would be executed on one call to this function with an argument of
length 4 that produces the best case?
Part (c) [1 mark]
Circle the term below that best describes the best case running time of this function on a length n string.
constant linear quadratic something else
Part (d) [1 mark]
Give an example of an argument of length 4 that would produce the worst case behaviour of this function.
Part (e) [1 mark]
How many assignment statements would be executed on one call to this function with an argument of
length 4 that produces the worst case?
Part (f) [1 mark]
Circle the term below that best describes the worst case running time of this function on a length n string.
constant linear quadratic something else
Page 7 of 21
CSC 108 H1F Final Examination December 2018 Question 7. [12 marks]
Emotion analysis categorizes text as positive, negative, or neutral. For example, an emotion analysis program might categorize the text "happy birthday" as positive, and the text "it was disastrous" as negative.
Part (a) [4 marks]
Words are scored from -5 (most negative) to 5 (most positive). Word scoring data is stored in a comma
separated values (CSV) file with a word, followed by its score, on each line. Here is an example word scoring CSV file:
amazing,4 happy,3 anxious,-2 disastrous,-3 awesome,4 outstanding,5 woohoo,3
Each line in the file contains one word that contains only lowercase letters (no punctuation), followed by one comma, and then a valid score. There are no blank lines in the file. Each word has at least one character.
Neutral words, which would have a score of 0, are not included in the CSV file.
Given the example CSV file opened for reading, function read_word_scores should return:
{'amazing': 4, 'happy': 3, 'anxious': -2, 'disastrous': -3, 'awesome': 4,
'outstanding': 5, 'woohoo': 3}
Complete the function read_word_scores according to the example above and the docstring below. You may assume the argument file has the correct format.
def read_word_scores(f: TextIO) -> Dict[str, int]:
“””Return a dictionary that has words from f as keys and their
corresponding scores as values.
Precondition: words in f are unique
Page 8 of 21
cont’d. . .
CSC 108 H1F Final Examination December 2018 Part (b) [4 marks] Complete the function below according to its docstring:
def score_document(text: str, word_to_score: Dict[str, int]) -> float:
“””Return the emotion analysis score for text. The score is the average of the score for
each word in text using word_to_score. If a word from text does not appear in word_to_score,
its score is 0.
Precondition: text contains only words made up of only lowercase alphabetic characters
(no punctuation), and each word is separated by a space. text contains at least one word.
>>> word_to_score = {‘amazing’: 4, ‘happy’: 3, ‘anxious’: -2, \
‘disastrous’: -3, ‘awesome’: 4, ‘outstanding’: 5, ‘woohoo’: 3}
>>> score_document(‘everything is awesome’, word_to_score)
1.3333333333333333
>>> score_document(‘outstanding and amazing’, word_to_score)
>>> score_document(‘it is’, word_to_score)
>>> score_document(‘i am happy but anxious’, word_to_score)
Part (c) [4 marks] Complete the function below according to its docstring:
def find_similar_words(word: str, word_to_score: Dict[str, int]) -> List[str]:
“””Return a list of words from word_to_score that are similar to word. Two words
are considered similar if they start with the same letter, have the same length,
and have the same score in word_to_scores. A word cannot be similar to itself.
Precondition: word is lowercase and word is in word_to_score
>>> word_to_score = {‘amazing’: 4, ‘happy’: 3, ‘anxious’: -2, \
‘disastrous’: -3, ‘awesome’: 4, ‘outstanding’: 5, ‘woohoo’: 3}
>>> find_similar_words(‘amazing’, word_to_score)
[‘awesome’]
>>> find_similar_words(‘happy’, word_to_score)
Page 9 of 21
CSC 108 H1F Final Examination December 2018 Question 8. [6 marks]
Complete the function below to according to its docstring.
To receive full marks on this function, your solution must not remove any keys from the parameter card_to_total, even temporarily, such as by using the method dict.clear().
def update_amounts(card_to_total: Dict[str, int], amts: List[Tuple[str, int]]) -> None:
“””Update card_to_total with the amounts for each card from amts.
>>> D = {}
>>> update_amounts(D, [(‘visa’, 1000), (‘amex’, 50), (‘visa’, 500)])
{‘visa’: 1500, ‘amex’: 50}
>>> update_amounts(D, [(‘amex’, 50), (‘visa’, 1000), (‘mc’, 100)])
{‘visa’: 2500, ‘amex’: 100, ‘mc’: 100}
>>> update_amounts(D, [(‘paypal’, 25), (‘amex’, -100)])
{‘visa’: 2500, ‘amex’: 0, ‘mc’: 100, ‘paypal’: 25}
Page 10 of 21
cont’d. . .
CSC 108 H1F Final Examination December 2018 Question 9. [7 marks]
Recall the algorithms insertion sort, selection sort, and bubble sort. Throughout this question, lists are to be sorted into ascending (increasing) order.
Part (a) [1 mark] Consider the following lists:
L1 = [1, 3, 4, 5, 2, 6, 7, 8, 9]
L2 = [9, 8, 7, 6, 5, 4, 3, 2, 1]
Which list would cause Selection Sort to do more comparisons? Circle one of the following. L1 L2 they would require an equal number
Part (b) [1 mark] Consider the following lists:
L1 = [1, 3, 4, 5, 2, 6, 7, 8, 9]
L2 = [9, 8, 7, 6, 5, 4, 3, 2, 1]
Which list would cause Insertion Sort to do more comparisons? Circle one of the following. L1 L2 they would require an equal number
Part (c) [5 marks] Consider the following lists. For each list, and each algorithm, consider whether at least two passes of the algorithm could have been completed on the list. If at least two passes could have been completed, check the box corresponding to that list and algorithm.
Insertion? Selection? Bubble?
[1, 2, 4, 6, 5, 7, 3]
[1, 3, 4, 6, 5, 7, 2]
[1, 3, 4, 5, 2, 6, 7]
[5, 4, 3, 2, 1, 6, 7]
[1, 2, 4, 5, 6, 7, 8]
Page 11 of 21
CSC 108 H1F Final Examination December 2018 Question 10. [10 marks]
In this question, you will complete some docstrings and write method bodies in classes to represent bridge and highway data.
Here is the header and docstring for class Bridge. class Bridge:
“””A bridge and its data”””
Part (a) [1 mark] Complete the body of this class Bridge method according to its docstring.
def __init__(self, name: str, span_list: List[float]) -> None:
“””Initialize a bridge with name and the spans from span_list.
>>> b = Bridge(‘CNR Subway’, [13.1, 10.5, 11.2])
>>> b.name
‘CNR Subway’
>>> b.spans
[13.1, 10.5, 11.2]
Part (b) [2 marks] Complete the body of this class Bridge method according to its docstring.
def extend_bridge(self, new_span: float, at_start: bool) -> None:
“””Update this bridge to include a new span new_span at either the start or
end of the list of spans, according to at_start.
>>> b = Bridge(‘CNR Subway’, [13.1, 10.5, 11.2])
>>> b.extend_bridge(5.5, True)
>>> b.spans
[5.5, 13.1, 10.5, 11.2]
>>> b.extend_bridge(8.8, False)
>>> b.spans
[5.5, 13.1, 10.5, 11.2, 8.8]
Page 12 of 21
cont’d. . .
CSC 108 H1F Final Examination December 2018
Part (c) [1 mark] Complete the body of the class Bridge __eq__ method according to its docstring. Use the provided class Bridge helper method get_length in your solution. You can assume get_length has been implemented according to its docstring.
def get_length(self) -> float:
“””Return the total length of the spans in this bridge.
>>> b = Bridge(‘CNR Subway’, [1.5, 1.5, 1.0])
>>> b.get_length()
# assume this method has been correctly implemented
def __eq__(self, other: ‘Bridge’) -> bool:
“””Return True if and only if this bridge has the same name and length as other.
>>> b1 = Bridge(‘CNR Subway’, [1.5, 1.5, 1.0])
>>> b2 = Bridge(‘CNR Subway’, [1.0, 1.0, 2.0])
>>> b1 == b2
>>> b3 = Bridge(‘CNR Subway’, [1.0, 1.0, 2.5])
>>> b1 == b3
Now consider the class Highway. Here is the header and docstring for class Highway. class Highway:
“””A highway that contains bridges and runs through regions.”””
Part (d) [2 marks] Complete the body of this class Highway method according to its docstring.
def __init__(self, hw_number: int, region: str) -> None:
“””Initialize a highway with highway number hw_number that begins in region. This new
highway should have a length of 0 and no bridges.
>>> h = Highway(400, ‘Toronto’)
>>> h.number
>>> h.regions
[‘Toronto’]
>>> h.length
>>> h.bridges
Page 13 of 21
CSC 108 H1F Final Examination December 2018
Part (e) [2 marks] Complete the docstring of the class Highway method add_bridge according to its function body. You can assume that the method extend_highway has been implemented according to its docstring.
def extend_highway(self, extension_len: float, new_regions: List[str]) -> None:
“””Update this highway by increasing its length by extension_len, and appending any
regions from new_regions that are not already in its regions list in the same order
as they appear in new_regions.
>>> h = Highway(400, ‘Toronto’)
>>> h.extend_highway(50.5, [‘Toronto’, ‘York’])
>>> h.length
>>> h.regions
[‘Toronto’, ‘York’]
>>> h.extend_highway(20.1, [‘Simcoe’, ‘York’])
>>> h.length
>>> h.regio
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com