COMP10001 Foundations of Computing Final Examination, Semester 1, 2019

Part 1: Code Interpretation

Question 1

Evaluate the following expressions, and provide the output in each case.

(a) 'smart array'[::-1]

(b) 7 / 2 * 2

(c) 'cat'[1:] in 'hat' and 'fox'[1:] in 'sox'

(d) sorted({'hobbits': ['bilbo', 'frodo'], 'dwarves': ['gimli', 'thorin']}.values())[-1][1]

(e) [x * 2 for x in str(90210)]

Question 2

What are the fifinal values of each of the variables indicated below, on completion of execution of the following code:

VALUES = '2A'
SUITS = 'SHDC'
PLAYERS = 2
ROUNDS = 4

deck = []
for value in VALUES:
    for suit in SUITS:
        deck.append(value + suit)

hands = []
for i in range(PLAYERS):
    hands.append([])

for i in range(ROUNDS):
    for player in range(PLAYERS):
        hands[player].append(deck.pop())

(a) i

(b) deck

(c) hands

Question 3

The following code is intended to calculate a list of valid “old school” vs. “new school” superhero running races. The rules are:

1. “old school” characters are defifined as those who were created prior to a given year, and “new school” characters are those created in the given year or later。
2. each old school superhero races against each new school superhero whose costume is a different colour to their own
3. superheroes with the same colour costumes don’t race against one another—that would just be confusing! Such pairings are deemed invalid

The code takes the form of the defifinition of a function called race_list, which takes two arguments:

• afile: a CSV fifile containing superhero data, including their name, the year they were created and their costume colour
• year: the year used to distinguish “old school” from “new school” superheroes

and returns a 2-tuple containing: (1) a sorted list of valid races (as strings); and (2) a count of invalid pairings of superheroes (on the basis of their costumes being the same colour).

An example input for afile is the fifile superheroes.csv:

name,year,colour
Hedgehog Man,1965,brown
Captain Penguin,1962,purple
The Mystifier,1973,purple
Telephone Girl,1978,green
Little Llama,1991,beige.

An example function call, based on the provided superheroes.csv fifile, is:

>>> race_list('superheroes.csv', 1970)
(['Captain Penguin vs. Little Llama', 'Captain Penguin vs. Telephone Girl', 'Hedgehog Man vs. Little Llama', 'Hedgehog Man vs. Telephone Girl', 'Hedgehog Man vs. The Mystifier'], 1)

(ie, there is one invalid pairing in this example: Captain Penguin and The Mystififier do not race against one another because their costumes are both purple.)

You can assume that the following two library imports have been made earlier in the code, prior to the function defifinition:

import csv
import itertools

As presented, the lines of the function are out of order. Put the line numbers in the correct order and introduce appropriate indentation (indent the line numbers to show how the corresponding lines would be indented in your code), by placing line numbers in the table below the code (one line number per row in the table). Note that the provided code makes use of a semi-colon (“;”) at two different locations, to combine two statements (to initialise variables) into a single line of code.

1 if old[pair[0]] != new[pair[1]]:
2 old = {}; new = {}
3 with open(afile) as f:
4 new[row['name']] = row['colour']
5 else: 6 old[row['name']] = row['colour']
7 for pair in itertools.product(old, new):
8 invalid += 1
9 if int(row['year']) < year:
10 races.append(f'{pair[0]} vs. {pair[1]}')
11 for row in csv.DictReader(f):
12 else:
13 return (sorted(races), invalid)
14 def race_list(afile, year):
15 races = []; invalid = 0

Question 4

The following function is intended to work out the value of the optimal combination of items to place in a bag in terms of maximising the value of the items, subject to a weight limit on the bag.

下面的函数旨在计算最优组合物品的价值，以最大化物品的价值，同时受到放入背包的重量限制的限制。

It takes two arguments:

它需要两个参数:

• capacity: the total weight that can be held by the bag

  容量:袋子所能承受的总重量

• items: a list of items, each of which is represented as a dictionary storing the weight and value of that item

  项目(Items):项目的列表，每个项目都表示为一个字典，存储了该项目的权重和值

and returns the maximum value of combined items that can be achieved subject to the weight constraint.

并返回在权重约束下所能得到的最大物品组合值。

For example, when run over the following example of items:

例如，当运行以下项目的例子:

items = [{'weight': 13, 'value': 6}, {'weight': 15, 'value': 11},
         {'weight': 16, 'value': 13}, {'weight': 22, 'value': 17},
         {'weight': 10, 'value': 5}]

the function should produce the following outputs (based on the combination of items provided in the comment, in each case):

这个函数应该产生如下输出(在每种情况下，基于注释中提供的项的组合):

>>> rec_knapsack(35, items)
24 # based on items[1] and items[2]
>>> rec_knapsack(40, items)
30 # based on items[2] and items[3]

As presented, there are bugs in the code. Identify exactly three (3) errors in the code (using the provided line numbers), identify for each whether it is a “syntax”, “run-time” or “logic” error, and provide a replacement line which corrects the error.

如前所述，代码中有bug。准确识别代码中的三(3)个错误(使用提供的行号)，识别每个错误是“语法”、“运行时”还是“逻辑”错误，并提供一个更正错误的替换行。

1 def rec_knapsack(capacity, items):
2 if capacity == 0 or len(items) == 0:
3 return 0 45 cur_item = items(0)
6
7 if cur_item['weight'] >= capacity
8 return rec_knapsack(capacity, items)
9
10 take_value = (cur_item['value']
11 + rec_knapsack(capacity - cur_item['value'], items[1:]))
12 leave_value = rec_knapsack(capacity, items[1:])
13 return max(take_value, leave_value)

公众号：AI悦创【二维码】