xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

python代写-LEVEL 4

时间：2020-12-30

The University of Nottingham

SCHOOL OF COMPUTER SCIENCE

A LEVEL 4 MODULE, AUTUMN SEMESTER 2019-2020

Programming

G54PRG/COMP4008

Time allowed 2 Hours

Candidates may complete the front cover of their answer book and sign their

desk card but must NOT write anything else until the start of the examination

period is announced

Answer ALL FOUR questions

No calculators are permitted in this examination.

Note that all the questions are about Python 3.x.

Dictionaries are not allowed with one exception. Those whose first language is

not English may use a dictionary to translate between that language and English

provided that neither language is the subject of this examination. No electronic

devices capable of storing and retrieving text may be used.

DO NOT turn examination paper over until instructed to do so

COMP4008.G54PRG-E1 1 Turn Over

2 COMP4008.G54PRG-E1

Question 1:

a. We initialise two variables m and lst as follows:

m = [’A’,[]]

lst = [m[0], 3, m]

If we execute the following lines of code in order, what is the output

of each line?

lst[1:]

lst[0][0][-1]

lst[:1]+lst[-1:]

[lst[1]]+[lst[0]]

m[1]=[1,2,3]

lst

Some lines may have no output or trigger an error. In the latter

case, specify what the reason of the error is. Note that some

instructions may depend on the result of previous lines (e.g. a

previous assignment).

(10 marks)

b. Define a function shiftRight which receives a list as input, and

returns a list with all the elements shifted to the right, so that, the

last element will become the first. You may assume that the list has

at least one element. E.g. the function should behave as follows:

myList = list("Thor")

shiftRight(myList)

[’r’, ’T’, ’h’, ’o’]

Will your solution work with strings? Briefly explain your answer.

(5 marks)

COMP4008.G54PRG-E1 2

3 COMP4008.G54PRG-E1

c. Define a function shiftRightX which gets a list as input, which will

be modified, shifting its elements to the right, so that, the last element

will become the first. The function should not return anything. You

may assume that the list has at least one element. E.g. the function

should behave as follows:

>> myList=list("Thor")

>> shiftRightX(myList)

>> myList

[’r’, ’T’, ’h’, ’o’]

Will your solution work with strings? Briefly explain your answer.

(5 marks)

d. What would be the output of the following program?

var = 1

def test(var) :

var = var+1

print(var)

test(var+1)

print(var)

(5 marks)

COMP4008.G54PRG-E1 3 Turn Over

4 COMP4008.G54PRG-E1

Question 2:

a. What are the outputs of the following programs?

(i) b = True

c = not b

d = b and c

if b and c or d:

print("a")

elif b or c and d:

print("b")

else :

print("c")

(ii) x = 3

try :

x = int("x")

print("a")

except ValueError:

print("b")

(iii) b=True

while b :

print("a",end="")

b = not b

if not b :

break

print("b",end="")

print("c",end="")

(iv) x=-2

try :

x = int(x)

print("7",end="")

except ValueError :

print("8")

(v) for i in range(0,2):

for j in [’1’,2,’3’]:

print(j, end=",")

(10 marks)

b. Write a function isPrime that returns True if the input parameter

is a prime number, and False if it is not. Remember that a prime

number is a number (greater than 1) that is only divisible by itself and

COMP4008.G54PRG-E1 4

5 COMP4008.G54PRG-E1

1 with remainder 0. The function assumes that the input is always

higher than 0. For example:

>> isPrime(2)

True

>> isPrime(4)

False

(5 marks)

c. Using the previous function isPrime, you are asked to write another

function primes that prints the first n prime numbers. The function

receives the total number of prime numbers to print as input. For

example:

>> primes(10)

2 3 5 7 11 13 17 19 23 29

(5 marks)

d. Write a function transpose that gets a square matrix (same number

of rows and columns) as a 2-dimensional list. The function should

return the transpose of the matrix, so that, the rows and columns are

swapped.

For example given,

matr = [[1,2,3],

[4,5,6],

[7,8,9]]

the call

transpose(matr)

should return:

[[1, 4, 7],

[2, 5, 8],

[3, 6, 9]]

The program should not modify the input but return a new matrix

which is the transpose of the input. (5 marks)

COMP4008.G54PRG-E1 5 Turn Over

6 COMP4008.G54PRG-E1

Question 3:

a. Given the following recursive functions:

def f0(x) :

if x==-1 :

return 0

else :

return 1-f0(x-1)

(i) What is the output of f0(3)?

def f1(x) :

if x==1 :

return 0

else:

return 1+f1(x+2)

(ii) What is the output of f1(4)?

def f2(x) :

if x==5 :

return x

else :

y,z = f2(x+1),f2(x+1)

return y+z

(iii) What is the output of f2(3)?

def f3(x) :

if x==0 :

return -1

else :

return f3(x-1)+f3(x-1)

(iv) What is the output of f3(3)?

def f4(x):

if x>0:

f4(x-1)

print("*",end="")

f4(x-1)

(v) What is the output of f4(2)?

(10 marks)

b. Write a recursive function inits that computes all the initial seg-

ments of a list. That is for example:

COMP4008.G54PRG-E1 6

7 COMP4008.G54PRG-E1

inits([1,2,3])

returns:

[[1, 2, 3], [1, 2], [1], []]

The program should not modify its input. (10 marks)

c. Write a program that computes a knight’s tour of the chess board

using backtracking. A knight is a chess piece that can move as follows:

A knight’s tour is a sequence of moves where the knight starts on

the top-left corner (coordinates y=0,x=0) and visits all chess fields

exactly once.

To make it easier here is some initialisation code:

size = 8

board = []

for y in range(size) :

board = board + [[-1]*size]

moves= [[1,2],[1,-2],[-1,2],[-1,-2],

[2,1],[2,-1],[-2,1],[-2,-1]]

board contains the board representing the fields the knight has visited

(with the number of the move filled in). -1 means the knight hasn’t

yet visited this field. moves contains all the 8 possible moves of the

knights in the form of the difference in the y and the x direction.

Your task is to provide a function:

COMP4008.G54PRG-E1 7 Turn Over

8 COMP4008.G54PRG-E1

def knight(n,y,x)

which prints a solution (or several solutions) of the problem, where n

is the number of the move (starting with 0), and y, x is the current

position of the knight. E.g.

knight(0,0,0)

should print the first knights tour, starting in the position (0, 0) and

then print the remaining solutions once the user has pressed the return

key.

knight(0,0,0)

[[ 0, 3, 56, 19, 46, 5, 48, 21],

[33, 18, 1, 4, 57, 20, 45, 6],

[ 2, 55, 34, 59, 36, 47, 22, 49],

[17, 32, 37, 54, 51, 58, 7, 44],

[38, 13, 52, 35, 60, 43, 50, 23],

[31, 16, 39, 42, 53, 26, 61, 8],

[12, 41, 14, 29, 10, 63, 24, 27],

[15, 30, 11, 40, 25, 28, 9, 62]]

That is the number in each field now represent the number of the

step when the knight has visited the field. (5 marks)

COMP4008.G54PRG-E1 8

9 COMP4008.G54PRG-E1

Question 4:

a. Given the following class definitions:

class Tree :

def setx(self) :

self.x=10

class Node (Tree) :

def __init__(self,left,right) :

self.left,self.right = left,right

def __str__(self) :

return "({},{})".format(self.left,self.right)

class Leaf (Tree) :

def __str__(self) :

return "[]"

We create a variable mytree as follows:

mytree = Node(Leaf(),Node(Leaf(),Leaf()))

What are the outputs of the following blocks of code?

(i) print(mytree)

(ii) print(mytree.right.left)

(iii) mytree.left = mytree.right

print(mytree)

(iv) mytree.left.setx()

print(mytree.right.x)

(v) mytree.right = mytree

print(mytree)

(10 marks)

b. Design a class hierarchy to represent a simple knowledge base which

can for example be used to implement a simple customer advice sys-

tem.

Knowledge A superclass, all subclasses of Knowledge implement a

run() method which implements a simple dialogue.

Question Representing a yes/no question. Objects are created using

Question(s,y,n) where s is the question string and y,n are

Knowledge objects representing the yes/no cases.

COMP4008.G54PRG-E1 9 Turn Over

10 COMP4008.G54PRG-E1

Answer Representing an answer. Objects are created using Answer(a)

where a is the string representing the answer.

For example: we create the following knowledge base:

kb = Question("Do you want to carry it around?",

Question("Do you need to make calls?",

Answer("Buy a mobile phone."),

Answer("Buy a tablet.")),

Answer("Buy a computer"))

(i) Define the classes with the appropriate __init__ methods such

that we can create the knowledge base. (6 marks)

(ii) Implement run methods which conduct a dialogue with the user

and finish with a recommendation. E.g. we can have the follow-

ing runs:

>>> kb.run()

Do you want to carry it around?yes

Do you need to make calls?no

Buy a tablet.

or

>>> kb.run()

Do you want to carry it around?no

Buy a computer

(4 marks)

c. We can use classes to implement lists as follows:

class List:

pass

class Nil (List) :

def __str__(self) :

return "Nil()"

def append(self,lst) :

pass

class Cons (List) :

def __init__(self,hd,tl) :

self.hd = hd

self.tl = tl

COMP4008.G54PRG-E1 10

11 COMP4008.G54PRG-E1

def __str__(self) :

return "Cons("+str(self.hd)+","+str(self.tl)+")"

def append(self,lst) :

pass

For example we can create 2 lists and print the first:

lst1 = Cons(1,Cons(2,Cons(3,Nil())))

lst2 = Cons(4,Cons(5,Nil()))

print(lst1)

Which results in the following output.

Cons(1,Cons(2,Cons(3,Nil())))

Complete the definition of append method, so that it appends two

lists (without modifying the existing lists). e.g.

print(lst1.append(lst2))

has the following output:

Cons(1,Cons(2,Cons(3,Cons(4,Cons(5,Nil())))))

(5 marks)

COMP4008.G54PRG-E1 11 END