讲解 CSC108H1S : Introduction to Computer Programming APRIL 2024 EXAMINATIONS辅导留学生Python语言

CSC108H1S : Introduction to Computer Programming

Winter 2024

APRIL 2024 EXAMINATIONS

Short Python function/method descriptions:

int(x: object) -> int Convert x to an integer, if possible. A floating point argument will be truncated towards zero. len(x: object) -> int Return the length of list, tuple, dict, or string x. max(iterable: object) -> object max(a, b, c, ...) -> object With a single iterable argument, return its largest item. With two or more arguments, return the largest argument. Dictionary order used for str. min(iterable: object) -> object min(a, b, c, ...) -> object With a single iterable argument, return its smallest item. With two or more arguments, return the smallest argument. Dictionary order used for str. open(name: str[, mode: str]) -> TextIO Open a file. Legal modes are "r" (read) (default), "w" (write), and "a" (append). print(values: object) -> None Prints the values. range([start: int], stop: int, [step: int]) -> list-like-object of int Return the integers from start (inclusive) to stop (exclusive) with step specifying the amount to increment (or decrement). If start is not specified, the sequence starts at 0. If step is not specified, the values are incremented by 1. type(x: object) -> the object's type Return the type of the object x. file open for reading (TextIO): F.close() -> None Close the file. F.read() -> str Read until EOF (End Of File) is reached, and return as a string. F.readline() -> str Read and return the next line from the file, as a string. Retain any newline. Return an empty string at EOF (End Of File). F.readlines() -> list[str] Return a list of the lines from the file. Each string retains any newline. file open for writing (TextIO): F.close() -> None Close the file. F.write(x: str) -> int Write the string x to F and return the number of characters written. list: list(x: object) -> list Return an object converted to its list representation, if possible. lst[ind: int] -> object Produce the item at index ind in lst or an Index out of range error. lst[start: int, stop: int, [step: int]] -> list Produce a list containing every step items from lst, starting at index start, going up to but not including index stop. (Default: step == 1) x in L --> bool Produce True if x is in L and False otherwise. L.append(x: object) -> None Append x to the end of the list L. L.extend(iterable: object) -> None Extend list L by appending elements from the iterable. Strings and lists are iterables whose elements are characters and list items respectively. L.index(value: object) -> int Return the lowest index of value in L, but raises an exception if value does not occur in S. L.insert(index: int, x: object) -> None Insert x at position index. L.pop(index: int) -> object Remove and return item at index (default last). L.remove(value: object) -> None Remove the first occurrence of value from L. L.reverse() -> None Reverse the list *IN PLACE*. L.sort() -> None Sort the list into non-decreasing order *IN PLACE*. dict: D[k] --> object Produce the value associated with the key k in D or a Key error. del D[k] Remove D[k] from D. k in D --> bool Produce True if k is a key in D and False otherwise. D.get(k: object) -> object Return D[k] if k in D, otherwise return None. D.items() -> list-like-object of Tuple[object, object] Return the (key, value) pairs of D, as 2-tuples. D.keys() -> list-like-object of object Return the keys of D. D.pop(k) -> object Remove specified key from D and return the corresponding value. D.values() -> list-like-object of object Return the values associated with the keys of D. str: str(x: object) -> str Return an object converted to its string representation, if possible. s[ind: int] -> str Produce the character at index ind in s or an Index out of range error. s[start: int, stop: int, [step: int]] -> str Produce a str containing every step characters from s, starting at index start, going up to but not including index stop. (Default: step == 1) x in s -> bool Produce True if and only if string x is in string s. S.isalpha() -> bool Return True if and only if all characters in S are alphabetic and there is at least one character in S. S.isalnum() -> bool Return True if and only if all characters in S are alphanumeric and there is at least one character is S. S.isdigit() -> bool Return True if and only if all characters in S are digits and there is at least one character in S. S.islower() -> bool Return True if and only if all cased characters in S are lowercase and there is at least one cased character in S. S.isupper() -> bool Return True if and only if all cased characters in S are uppercase and there is at least one cased character in S. S.lower() -> str Return a copy of the string S converted to lowercase. S.replace(old: str, new: str) -> str Return a copy of string S with all occurrences of the string old replaced with the string new. S.split([sep: str]) -> list[str] Return a list of the words in S, using string sep as the separator and any whitespace string if sep is not specified. S.strip(chars: str) -> str Return a copy of S with leading and trailing whitespace removed. If chars is given and not None, remove characters in chars instead. S.upper() -> str Return a copy of the string S converted to uppercase.

1. [10 marks] Short answer

Each of the following interactions in the Python shell ends with an expression and blank space. For each one, write the value that would be displayed in the blank space, or the word NOTHING if nothing would be displayed. If evaluating the code would cause an error, (1) circle the part of the code that causes the error, (2) write the word ERROR beside the circle and (3) briefly explain why the error occurs. Then continue with the statements that follow.

>>> 1 + 2 >>> '1' + '2' >>> 4 // 2 >>> 4 / 2 >>> x = 0 >>> if x < 1: ... x = x + 10 ... elif x < 50: ... x = x + 200 ... else: ... x = x + 3000 ... >>> x >>> def f(x: int) -> int: ... """Docstring omitted.""" ... x = x + 2 ... return x ... >>> x = 0 >>> f(x) >>> x >>> lst = [9, 6, 7] >>> lst.sort().reverse() >>> lst >>> british_spelling = 'organise' >>> american_spelling = british_spelling >>> american_spelling[-2] = 'z' >>> american_spelling >>> british_word_list = ['organise', 'realise'] >>> american_word_list = british_word_list >>> american_word_list[-2] = 'z' >>> british_word_list >>> american_word_list >>> def g(x: list[int], y: list[int]) -> None: ... """Docstring omitted.""" ... x[0] = x[0] + y[0] ... y[0] = x[0] - y[0] ... >>> a = [3, 4] >>> b = [5] >>> g(a, b) >>> a >>> b >>> d = {} >>> d['fish'] = ['swim'] >>> 'swim' in d >>> d['penny'] = d['fish'] >>> len(d) >>> d['tom'].append('skate') >>> len(d) >>> d['tom'] = ['run'] >>> len(d)

2. [9 marks] Function writing

Write a complete function named has_alpha_order that takes a list of str as a parameter.

The function has_alpha_order should return True if and only if the items in the given list are in alphabetical order. The case of letters in strings should be ignored when they are compared. That is, the string 'apple' should be considered to come before the string 'BANANA', despite the fact that the value of the Python expression 'apple' < 'BANANA' is False.

The function should assume that the str in the given list only contain alphabetic characters.

Your complete function must include:

• a complete header with appropriate type annotations,

• a complete docstring that includes a proper description, preconditions and at least two suitable examples,

• and a correct function body.

3. [10 marks] Lists and Dicts

(a) [6 marks] The function in this question works with a nested list of data about students. Each item in the inner list contains the following information about an individual student in the order:

• the student’s name (a str)

• the student’s college (a str)

Complete the following function according to its docstring.

def group_valid(group: list[list[str]], max_group_size: int) -> bool:

"""Return True if and only if group meets all of the following conditions

for being a valid group of students:

- group contains at most max_group_size students

- all students in the group are in the same college

- no two students in the group have the same name

Each sublist in group contains the following information about a student,

in order: name (a str), college (a str)

Preconditions:

- len(group) > 0

- len(group[i]) == 2 for each value of i in range(len(group))

>>> g1 = [['mohi', 'sgs'], ['laura', 'sgs'], ['fernando', 'sgs']]

>>> group_valid(g1, 5)

True

>>> group_valid(g1, 2) # group too big

False

>>> g2 = [['jen', 'oise'], ['paul', 'trn'], ['sadia', 'oise']]

>>> group_valid(g2, 3) # not all in same college

False

>>> g3 = [['david', 'vic'], ['tom', 'vic'], ['david', 'vic']]

>>> group_valid(g3, 8) # two 'david's

False

"""

(b) [4 marks] Complete the following function according to its docstring. Be sure to make use of the constants that are defined before the function definition.

EVEN = 'even'

ODD = 'odd'

def get–properties(nums: list[int]) -> dict[int, str]:

"""Return a dictionary in which each key is an item from nums and its value is one of the constants EVEN or ODD, depending on whether the item is

even or odd, respectively . If nums is the empty list, return an empty

dictionary .

>>> nums = [1, 2, 9, 8, 8, 6, 1]

>>> result = get–properties(nums)

>>> result == {1: ODD, 2: EVEN, 9: ODD, 8: EVEN, 6: EVEN}

True

>>> get–properties([])

{}

"""

4. [10 marks] Files

The course coordinator is interested in learning more about how students used the radical generosity late policy this term with Assignment 3. Comma Separated Value (CSV) files were used to keep track of extension requests. These files have the following format:

• The first line of the file contains information about the course, the term and the section.

• The second line of the file contains descriptions of each column of data on the remaining line(s).

• The remaining line(s) of the file contain information about each extension request. Each of these lines has the format:

— student number followed by a comma (',')

— student name followed by a comma (',')

— number of days of extension followed by the newline character ('\n')

As an example, the file named csc108-1 .csv given below follows the specifications described above:

"CSC108 Winter 2024 Section 1",,

student number,student name,extension days

81235,Mary Simon,1

91112,Julie Payette,28

72341,David Johnston,64

18181,Michaelle Jean,1

35810,Adrienne Clarkson,10

Note:

• in this example, students could receive an extension of more than 7 days.

• the newline characters are not displayed. They cause data about each student to begin on a new line.

In the questions that follow, you may assume that extension data files are correctly formatted and follow the specifications described above. Also assume that at least one student requested an extension of at least 1 day. Also assume that each student’s number and name appears at most once in an extension data file.

(a) [6 marks] Complete the following function according to its docstring:

from typing import TextIO

def maximum–extension(data–file: TextIO) -> int:

"""Return the maximum number of days of extension recorded in the radical generosity extension file data–file .

The parameter data–file refers to a file that has been opened for reading .

>>> my–file = open('csc108-1.csv')

>>> maximum–extension(my–file)

>>> my–file.close()

"""

(b) [4 marks] Since there are 7 separate lecture sections of CSC108, the course coordinator has orga- nized students by lecture section, and has kept 7 separate extension request files. The file names are csc108-1 .csv, csc108-2 .csv, csc108-3 .csv, . . . , csc108-7 .csv. Assume that these files have the correct format and that at least one student requested an extension in each section. The following function is to be used to determine the maximum extension across all sections of CSC108.

Complete the following function according to its docstring. In your solution, you must call the function maximum extension as a helper function. You may assume that the function maximum extension has been correctly implemented.

def maximum– course–extension(course–name: str, num – sections: int) -> int:

"""Return the maximum number of days of extension recorded across all of

the radical generosity extension files for course course–name that has

num – sections sections .

Assume that the extension file names have the format:

course–name followed by ' - ' followed by the section number followed by ' .csv' Assume that the section numbers are 1 through num – sections, inclusive .

>>> maximum–course–extension('csc108', 1)

>>> maximum– course–extension('csc108', 7) # assume the given result is correct 144

"""

5. [10 marks] Testing

In this question, you are to consider the problem of testing the function frequencies. This function has the following header and docstring:

def frequencies(s: str) -> dict[str, int]:

"""Return a dictionary in which each key is a single character from s

and its value is the number of times that character occurs in s . If s

is the empty string, return an empty dictionary . Each different character

in s appears as a key in the returned dict .

>>> frequencies('loop') == {'l': 1, 'o': 2, 'p': 1}

True

>>> frequencies('') == {}

True

"""

(a) [3 marks] In the table below, we have outlined one test case for frequencies. Add three more test cases that could be part of a complete set of cases for thoroughly testing the function. Do not include duplicate test cases.

Test Case Description	s	Expected Return Value
empty string	''	{}

(b) [3 marks] Complete the following module by writing appropriate pytest functions for the test cases proposed in Part (a). Complete the function headers, add docstring descriptions (with no examples) and add function bodies.

"""Unit tests for the function frequencies . """

import pytest

def test–empty– string() -> None:

"""Test that an empty dictionary is returned when the argument

is the empty string .

"""

assert frequencies('') == {}

def

if ––name–– == ' ––main–– ':

# Perform the unit tests using pytest

pytest.main(['test–frequencies.py'])

(c) [1 mark] Would it be appropriate to add a pytest function that tests whether the function frequencies mutates its argument? Answer yes or no and briefly justify your response.

(d) [1 mark] Here is a buggy implementation of the frequencies function.

def frequencies(s: str) -> dict[str, int]:

"""Return a dictionary in which each key is a single character from s

and its value is the number of times that character occurs in s . If s

is the empty string, return an empty dictionary . Each different character

in s appears as a key in the returned dict .

>>> frequencies('loop') == {'l': 1, 'o': 2, 'p': 1}

True

>>> frequencies('') == {}

True

"""

d = {}

for character in s:

if character in d:

d[character] += 1

else:

d[character] = 0

return d

Fill in the two boxes below with values chosen to demonstrate that this implementation contains a bug.

>>> actual = frequencies( )

>>> expected = { }

>>> actual == expected

False

(e) [2 marks] What is the bug in the above function body and how could it be fixed?

6. [11 marks] Sorting, Searching and Runtime

(a) [1 mark] In the list below, 4 passes of the bubble sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index 0 is missing. Fill in the missing item with an appropriate value that will cause bubble sort to make the most number of interchanges on the next pass of the algorithm.

(b) [1 mark] In the list below, 4 passes of the insertion sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index i is missing. Fill in the missing item with a value that will cause insertion sort to move the most number of items on the next pass of the algorithm.

(c) [1 mark] In the list below, 4 passes of the insertion sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index i is missing. Fill in the missing item with a value that will cause insertion sort to move the fewest number of items on the next pass of the algorithm.

(d) [1 mark] In the list below, 4 passes of the selection sort algorithm have been completed, and the double bar separates the sorted part of the list from the unsorted part. The item at index i is missing. Fill in the missing item with a value that will cause selection sort to interchange this value with the value 9 on the next pass of the algorithm.

A friend has given you a Python list that has length n and has told you that it contains each of the integers between 0 and n except for one integer. They challenged you to figure out which integer was missing. (Note that there are n + 1 integers between 0 and n, inclusive. The list has length n.)

A recent graduate of CSC108 wrote the following Python function to solve the puzzle:

def my – search(lst: list[int]) -> int:

"""Return the integer between 0 and len(lst) that does not appear in lst .

Preconditions:

- len(lst) > 0

- 0 <= lst[i] <= len(lst) for each value of i in range(len(lst))

- the items in lst are all different

>>> my–search([5, 2, 0, 1, 4])

>>> my–search([1])

"""

for i in range(len(lst) + 1):

# Search lst for i . Return i when i is not found .

found– i = False

for j in range(len(lst)):

if i == lst[j]:

found– i = True

print(i, j, lst[j]) # print statement to produce data for table if not found– i:

return i

(e) [2 marks] Suppose the function call my search([3, 0, 2]) is executed. Complete the following table to show the values of i, j and lst[j] that would be printed when the code is evaluated. Write the values in the same order as they would be printed. We have completed the first row for you. You may not need all of the rows in the table.

i	j	lst[j]
0	0	3

(f) [1 mark]

Fill in the first box below with an argument list of size 4 for which the call to my search exhibits its best case (i.e., fastest) running time for a list of size 4. Fill in the second box with value returned by the function call.

>>> my–search( )

(g) [1 mark]

Fill in the first box below with an argument list of size 4 for which the call to my search exhibits its worst case (i.e., longest) running time for a list of size 4. Fill in the second box with value returned by the function call.

>>> my–search( )

(h) [1 mark] Circle the term below that best describes the worst case running time of the function

my search:

constant linear quadratic something else

Another approach!

A different graduate of CSC108 wrote the following Python function to solve the puzzle:

def puzzle– search(lst: list[int]) -> int:

"""Return the integer between 0 and len(lst) that does not appear in lst .

Preconditions:

- len(lst) > 0

- 0 <= lst[i] <= len(lst) for each value of i in range(len(lst))

- the items in lst are all different

>>> puzzle–search([5, 2, 0, 1, 4])

>>> puzzle–search([1])

"""

# make a list for keeping track of found numbers

found–list = []

for i in range(len(lst) + 1):

found–list.append(False)

# note which numbers appear in lst

for number in lst:

found–list[number] = True

# return the number that was not found

for i in range(len(lst) + 1):

if not found–list[i]:

return i

(i) [1 mark] If len(lst) == n, and the missing number is n, what is the total number of loop iterations performed by the function puzzle search()? Include the iteration in which the value is returned. (Your answer should be a formula that involves n.)

(j) [1 mark] Circle the term below that best describes the worst case running time of the function puzzle search:

constant linear quadratic something else

联系我们