QUEEN’S UNIVERSITY SCHOOL OF COMPUTING
CISC101, WINTER TERM, 2018 ELEMENTS OF COMPUTING SCIENCE FINAL EXAMINATION
April 17, 2018
Instructor: Alan McLeod
This exam refers exclusively to the use of the Python language version 3. Comments are not required in the code you write. For full marks, code must be efficient as well as correct.
Please write your answers in the boxes provided. The back of any page can be used for rough work. This exam is 3 hours in length. Please put your student number at the top of each page. Extra space is provided on the second-to-last page of the exam.
An aid sheet has been appended to the exam. You may detach this page from the exam and do not have to return it when you hand in your exam, but the proctors can recycle the page for you.
This is a closed book exam. No computers or calculators are allowed or needed.
PLEASE NOTE: “Proctors are unable to respond to queries about the interpretation of exam questions. Do your best to answer exam questions as written.”
Student Number:
1. / 30
2. / 10
3. / 15
4. / 20
5. / 25 6. / 10 7. / 10
TOTAL:
This material is copyrighted and is for the sole use of students registered in CISC101 and writing this exam. This material shall not be distributed or disseminated. Failure to abide by these conditions is a breach of copyright and may also constitute a breach of academic integrity under the University Senate’s Academic Integrity Policy Statement.
HAND IN
Answers Are Recorded on Exam Paper
/ 120
Student Number: _____________________ Page 2 of 20
Problem 1) [30 marks]
Indicate if the following statements are true or false by placing a “T” or an “F” on the line before the statement:
____ In order to reduce heat generation, modern CPU chips contain just a single processing core.
____ Modern CPU clock speeds are in the range of 2 to 10 MHz (“Megahertz”).
____ A connection pin to a CPU is either “on” or “off” – it either has a voltage or it does not.
____ RAM memory is volatile, meaning that it is erased when the power is turned off.
____ Ultimately, program instructions and data are stored in binary, or base 2 numeric format, on a computer.
____ Most modern computers have at least six BIOS chips.
____ The von Neumann Cycle is no longer part of modern computer architecture.
____ Transistors generate much less heat than vacuum tubes.
____ Integrated circuits are fabricated on thin wafers of polycrystalline silicon.
____ Photo-resist layers become electrically conductive when exposed to UV light, allowing fabricators to create electronic circuits on silicon wafers.
____ A transistor requires three electrical connections to operate.
____ A potential applied to a transistor’s Collector allows a current to flow between the Base and Emitter connections.
____ An “OR” gate is constructed using two transistors in series.
____ A “NOT” gate is constructed from two transistors and a resistor.
____ True XOR True is False.
Student Number: _____________________
Page 3 of 20
Problem 1, Cont.)
____ False AND True is True.
____ A Half Bit Adder has three inputs and two outputs.
____ A Full Bit Adder can be constructed from three Half Bit Adders.
____ A byte contains 8 bits.
____ A Unicode character code requires 2 bytes of memory to store.
____ A single hexadecimal digit requires a minimum of a byte of memory to store.
____ The floating pointer number, 0.125, cannot be stored exactly in binary on a computer.
____ 0xF is 16 in base 10.
____ A Stack is referred to as a “LIFO” or “Last-In-First-Out” type of data structure.
____ Carrying out a floating-point division like 1 / 3 in Python can result in a stack overflow.
____ A Python program is compiled to an executable file of machine language before it is run.
____ “Dynamic Typing” in Python means that there is no limit to the size of a stored int value.
____ An int type value cannot be converted to a str value in Python.
____ The float() BIF can be used to convert any string to a floating point number.
____ Python variable names can start with numbers or letters and they can be a mix of upper and lower case.
Student Number: _____________________ Page 4 of 20
Problem 1, Cont.)
____ The floor division operator, //, rounds calculation results so that it can eliminate the decimal portion of the result.
____ The multiplication operator, *, can work with an int on the left-hand side and a string on the right-hand side.
____ The “power of” operator, **, has precedence over all other binary arithmetic operators.
____ The “and” and “or” operators will be evaluated before any Boolean comparison operators like < and > in the same expression.
____ If the left-hand side of an “or” operation is True, then the right-hand side is not evaluated.
____ If you use the slice operator with a colon, :, then the operator must also contain two integers, one on each side of the colon.
____ A try/except structure can only catch one exception type.
____ The best and easiest way to determine if a string would make a valid float number is to try converting it with float() and catch an exception if it would not.
____ A python module can contain imperative code as well as function and class definitions.
____ The purpose of the function decomposition design process is to increase the size of parameter lists in programs.
____ You can only use keyword arguments for parameters that already have default arguments when you invoke a function.
____ All positional arguments must come before keyword arguments when invoking a function.
____ A python string is mutable.
____ A single character literal is just a string of length one.
____ A python dictionary collection is mutable.
Student Number: _____________________ Page 5 of 20
Problem 1, Cont.)
____ Each key name in a dictionary must be unique (ie. no duplicates).
____ It is not possible to update more than one dictionary key:value pair with a single method
call.
____ It is faster to sort a list of numbers first in order to locate a maximum value, instead of having to fully iterate through the list.
____ A for loop iterates through a list faster than a while loop using a counter variable.
____ Insertion and Selection sort are both characterized by a nested loop structure.
____ Selection sort works faster when the data being sorted is already almost in order.
____ Binary search requires that the data being searched is in order.
____ Bubble sort has the swap and comparison inside the inner loop.
____ When supplied to the grid() method in tkinter, the row and column values determine the position of the widget.
____ The widget pad() method adds internal and external space around a widget.
____ A widget object can be used as if it was a dictionary to obtain or set properties.
____ The command property for a button widget must be assigned to a function that does not take any arguments.
____ tkinter does not allow you to use the keyboard to emulate a button click.
____ A group of radio button widgets must all use the same IntVar object.
____ Changing the extension of a python tkinter program to *.pyc prevents the console window from showing when the program is run.
Student Number: _____________________ Page 6 of 20
Problem 2) [10 marks]
a) What is the value of the base 16 number 3F in base 2?
b) What is the value of the base 2 number 10101 in base 10?
c) Why is it convenient to define functions with default arguments?
d) List four python collection types and provide one distinguishing feature for each:
Student Number: _____________________ Page 7 of 20
Problem 3) [15 marks]
The following complete program runs without error. In the boxes below write the output of the program as generated by each print() BIF call. Remember to include the proper brackets if a collection is being printed.
def main() :
print( 9 // 10 )
print( 10 % 9 )
print( 9 – 10 / 4 + 5 )
print( (9 – 10) / 2 + 5 )
print( 1 == 2 or 5 + 6 <= 10 or 6 != 6 )
aList = list(range(2, 10, 2))
print( len(aList) )
bList = aList + [3, 5, 7]
print ( bList )
aList = [1, 2, 3, 4]
bList = [10, 20]
aList.append(bList)
print( aList )
bList = aList[1 : -1]
print( bList )
print( aList[0] )
aStr = "Eric Idle"
print( aStr.index("Id") )
print( aStr.find("Monty") )
aDict = {'A':100, 'B':200}
aDict['X'] = 500
print( aDict )
print( list(aDict.keys()) )
print( aDict.pop('A') )
main()
Student Number: _____________________ Page 8 of 20
Problem 4) [20 marks, (5 marks each for a) and b), 10 marks for part c))]
Each part of this problem presents a complete program, each of which runs without error. In the box below each program, write the output of the program when run as generated by the calls to the print() BIF.
The syntax of the print() BIF is
print(arg0, arg1, arg2, ..., sep= ' ', end= '\n ')
In other words, the BIF will accept any number of positional arguments of any type separated by commas. The string specified by the parameter “sep” will be placed between the arguments when displayed in the console. Collection types will be displayed with the appropriate brackets and with a comma and space combination separating the elements of the collection. Strings will be displayed without their quotation characters. The default string for sep is a single space. After all arguments are printed, the string specified by the parameter “end” is added to the end of what has been printed. By default, this is a linefeed, which moves the cursor down to the beginning of the next empty line in the console.
a)
def main() :
aList = [4, -2, 7, 6, 10, 21, -7, 3, 2]
aList.sort()
for aVal in aList :
if aVal % 2 == 0 and aVal > 0 :
print(aVal, end=”, “)
main()
Student Number: _____________________
Page 9 of 20
Problem 4, Cont.) b)
def aFunction(aVal, aStr, aList1, aList2, aList3) :
aVal = aVal * 10
aStr = aStr.upper()
for num in aList1 :
num = num * 10
aList2.sort()
del aList3[1 : 3]
def main() :
val = 20
string = “Monty Python”
list1 = [2, 3, 4]
list2 = [7, 3, 1, 5]
list3 = [3, 5, 7, 9, 11]
aFunction(val, string, list1, list2, list3)
print(val)
print(string)
print(list1)
print(list2)
print(list3)
main()
Student Number: _____________________
Page 10 of 20
Problem 4, Cont.) c)
def aFunction(param1, param2=”Hello”, param3=[1, 2, 3]) :
if isinstance(param1, int) or isinstance(param1, float) :
print(param2 + str(param1))
else :
print(param2, end=str(len(param1)) + “\n”)
print(list(reversed(param3)))
def main() :
aVal = 22
aStr = “Goodbye”
aList = [8, 7, 6]
aFunction(aVal, aStr, aList)
aFunction(aVal)
aFunction(aStr, param3=aList)
aFunction(aStr, param3=aList, param2=aStr)
aFunction(aVal, param2=aStr)
main()
Student Number: _____________________ Page 11 of 20
Problem 5) [25 marks, (5 marks each for a), b) and c), 10 marks for part d))]
a) In the box provided below write a non-recursive function called “factorial” that calculates and returns the factorial of an integer value supplied as an argument. The factorial of a number, n, is shown in mathematical format as “n!”. It is calculated using the cumulative product as:
𝑛! = 𝑛 ∗ (𝑛 − 1) ∗ (𝑛 − 2) ∗ … ∗ 2 ∗ 1
If the factorial function is supplied with an argument that is less than or equal to 1, return 1. You can assume that the function will only be invoked with an integer argument.
For example, if the factorial function was invoked with an argument of 5, then it would return 120. Use the dotted lines to help line up your indentation for all parts of this problem.
Student Number: _____________________ Page 12 of 20
Problem 5, Cont.)
b) In the box provided below write a function, to be included in the same *.py file as the function written for part a), called “combinations” which returns numCombinations as calculated below, as an int, given two integer arguments. The two integer arguments represent the size of a set of “things”, call it “all”, as well as the size of a sub-set of “things” which could be called “some”. The number of possible combinations of “some” when taken from “all” can be calculated using the formula:
𝑛𝑢𝑚𝐶𝑜𝑚𝑏𝑖𝑛𝑎𝑡𝑖𝑜𝑛𝑠 = 𝑎𝑙𝑙!
𝑠𝑜𝑚𝑒! (𝑎𝑙𝑙 − 𝑠𝑜𝑚𝑒)!
For example, there are six different combinations of two “things” when taken from a set of four “things”. If the “things” are letters, you would have the set {A, B, C, D} for example. The possible combinations of two letters would be: {A, B}, {A, C}, {A, D}, {B, C}, {B, D} and {C, D}. So, all is 4, some is 2 and numCombinations, as returned by the function, would be 6.
This formula involves the calculation of factorials, so your function must use the function you wrote for part a). If either argument to combinations is less than 1 or if “some” is greater than or equal to “all”, return 1. You may assume that only integer arguments will be supplied to this function.
Student Number: _____________________ Page 13 of 20
Problem 5, Cont.)
c) Write a function called “allCombinations” that accepts a single argument, that you can assume will be of type int. The function will be included in the same *.py file as the functions written for parts a) and b), above. The argument will be the “all” value used for a series of invocations of the combinations function written for part b). The allCombinations function will return a dictionary constructed from all possible combinations calculations for every possible number of choices given the value “all”. For example, if “all” is 4, you could choose 1, 2, 3 or 4 “things” from “all”. The keys in the dictionary will take the form of the following string, where the appropriate integers are substituted for “all” and “some”:
“(all,some)”
For example, if allCombinations was invoked with the value 4, it would return the dictionary:
{‘(4,1)’: 4, ‘(4,2)’: 6, ‘(4,3)’: 4, ‘(4,4)’: 1}
The values are the result of calls to the combinations function from part b). If the argument supplied to allCombinations is less than 1, return an empty dictionary.
Student Number: _____________________ Page 14 of 20
Problem 5, Cont.)
d) Last one! Write a function called “maxCombinations” that accepts a single argument, that you can assume will be of type int. The function will be included in the same *.py file as the functions written for parts a) to c), above. If the argument is less than one, return the string “Illegal argument!”. This function must obtain the dictionary returned from the allCombinations function from part c), which it must use to locate the dictionary key:value pair that has the highest number of combinations. The result of this search will be returned as a string. For example, if maxCombinations was invoked with the value 4, it would return the string:
Max is 6 for 2 chosen from 4
Student Number: _____________________ Page 15 of 20
Problem 6) [10 marks]
Here is a mixed-up jumble of lines of code from three functions, readNums, insertionSort and main:
Line# Code
1 file.close()
2 numsList[j] = temp
3 nums = line.strip().split(‘,’)
4 for line in file :
5j=j-1
6 for i in range(1, len(numsList)) : 7 numsList.append(int(num))
8 def readNums(filename) :
9 def main() :
10 def insertionSort(numsList): 11 temp = numsList[i]
12 for num in nums :
13 numsList[j] = numsList[j – 1] 14 return numsList
15 while j > 0 and temp < numsList[j - 1]: 16 file = open(filename)
17 insertionSort(nums)
18 j = i
19 numsList = []
20 nums = readNums("numbers.txt")
In the table to the right, list the lines of code in the proper order, starting with readNums, then insertionSort, and then main. The main function has two lines of code, first invoking readNums, then insertionSort. Next, indicate the proper indentation of the lines by providing a number between 0 and 3 inclusive. A def line would be an indentation of 0 and the line immediately under a def line would have an indentation of 1, for example.
All lines of code should be included and no line occurs more than once. The first row of the table is given, as a starting point.
readNums reads integer values from a comma-delimited text file and returns them as a list. insertionSort sorts the supplied list of numbers, in situ, using the Insertion Sort algorithm.
Line #
Indent
8
0
Student Number: _____________________ Page 16 of 20
Problem 7) [10 marks]
On this page and the next is a complete tkinter program that displays a GUI window when run:
import tkinter
FONT = "Arial 16 bold"
# top is the window containing the other widgets
top = tkinter.Tk()
# aNum is a control variable holding an int value
aNum = tkinter.IntVar()
# Canvas dimensions are in pixels. The top-left corner is (0, 0)
# "bg" means "background"
drawing = tkinter.Canvas(top, height=250, width=500, bg="white")
def main() :
top.title("Problem 7")
top.configure(bg="white")
# Add some padding to the rows and columns # Don't worry about drawing this! top.columnconfigure(0, pad=20) top.columnconfigure(1, pad=20) top.columnconfigure(2, pad=20) top.rowconfigure(0, pad=20) top.rowconfigure(1, pad=20)
# Creating widgets
sizeLabel = tkinter.Label(top, bg="white", font=FONT, textvariable=aNum)
unitLabel = tkinter.Label(top, bg="white", font=FONT, text="pixels")
button = tkinter.Button(top, bg="white", font=FONT, text="Draw Square", \
command=change)
# Putting widgets in the window
button.grid(row=0, column=0)
sizeLabel.grid(row=0, column=1)
unitLabel.grid(row=0, column=2)
drawing.grid(row=1, column=0, columnspan=3)
# Assign the control variable
aNum.set(50)
# This allows the window to respond to button clicks
tkinter.mainloop()
Student Number: _____________________ Page 17 of 20
Problem 7, Cont.)
def change() :
size = aNum.get()
# This canvas method, create_rectangle(x0, y0, x1, y1), draws a black
# rectangle outline from the point (x0, y0) to the point (x1, y1), where
# dimensions are in pixels. The point (x0, y0) is the top-left corner,
# and (x1, y1) is the bottom-right corner of the rectangle.
drawing.create_rectangle(size, size, size*2, size*2)
aNum.set(size * 2)
main()
You will need to sketch the window twice. Draw the button using a rectangular border and write the labels without a border in their proper relative positions in the window. Don’t worry about exact pixel positions or the appearance of the font – concentrate on getting the relative positions of the widgets correct. You don’t need to use a ruler to draw straight lines – freehand lines are fine. Assume that all backgrounds will be white.
First, draw the appearance of the window after the button, “Draw Square”, has been clicked on once:
Student Number: _____________________ Page 18 of 20
Problem 7, Cont.)
Now, draw the window again after the “Draw Square” has been clicked on for a second time:
Student Number: _____________________
Page 19 of 20
(blank page)
Some Built-In Functions:
abs(number) len(obj)
str(obj)
int(number or string) float(number or string) list(obj)
set(obj)
# #
# # # # #
the absolute value of number
the length of the iterable or string
convert obj to a string convert to an int convert to a float convert to a list
convert to a set where each element is unique
# creates an iterable used with a for loop
returns a string from the console
range([start,] stop [, step])
input(stringPrompt) #
print(obj,..., sep=’ ‘, end=’\n’) # displays output to
chr(unicode) ord(character)
reversed(obj) sorted(obj) isinstance(obj, type)
max(obj) min(obj)
sum(obj) open(filename, mode)
the console
# the character for the
unicode value
# the Unicode value for the
character
# a reversed iterable
# a sorted version of obj # True if obj is of the
supplied type
# the highest value in the
supplied iterable
# the lowest value
# the sum of the numeric
values in obj
# open filename – mode is
‘r’, ‘w’ or ‘a’
Some String Methods:
# the number of occurrences of str string.count(str, beg=0, end=len(string))
# True if the string ends with str string.endswith(str, beg=0, end=len(string)) # replace tabs with spaces string.expandtabs(tabsize=8)
# index location of str, -1 if not found string.find(str, beg=0, end=len(string)) string.format(args) # args are placed and
formatted into the string according to codes used in placeholders
# index location of str, ValueError raised if not found
string.index(str, beg=0, end=len(string))
List Methods:
list.append(obj) list.count(obj) list.index(obj) list.index(obj, i, j) list.insert(index, obj) list.pop()
list.remove(obj) list.reverse()
list.sort()
# appends obj to list
# counts occurrences of obj # first occurrence of obj
# search between i and j
# insert obj at index
# remove and return
element at index = -1
# search for, and remove
obj
# reverses in place # sorts in place
around str
# replaces all occurrences of str1 with str2
string.replace(str1, str2, num=string.count(str1))
# like find but searches from end
string.rfind(str, beg=0, end=len(string))
# like index but searches from end string.rindex(str, beg=0, end=len(string)) string.rpartition(str) # like partition but searches for
str from end of string string.rstrip() # strips whitespace from end
# splits string into a list of pieces using str as delimiter
string.split(str=“ “, num=string.count(str))
# splits string into a list using linefeed as delimiter string.splitlines(num=string.count(‘\n’))
# True if string starts with str
string.startswith(str, beg=0, end=len(string))
string.isalnum()
string.isalpha() string.isdigit() string.islower() string.isspace()
string.istitle() string.isupper() string.join(seq)
string.ljust(width) string.lower() string.lstrip() string.partition(str)
# True if letter or numeric character
# True if letter
# True if numeric character # True if lower case
# True if whitespace (space,
tab or linefeed)
# True if titlecase
# True if uppercase
# concatenate all strings in
sequence
# pad with spaces to width # change all to lower case
# strip whitespace from start # returns tuple of size 3 split
File Object Methods:
fileobj.read() fileobj.readline() fileobj.readlines() fileobj.write(str) fileobj.close()
# reads entire file # a single line
# a list of lines
# writes str to file # close file object
string.strip()
string.swapcase() string.title() string.upper()
# strip whitespace from beginning and end
# swaps letter case
# titlecased version of string # changes all to upper case