EXAM CODES: TITLE OF PAPER: EXAM DURATION:
Rules
FIT1008
Introduction to computer science 3 hours 10 mins
Semester Two 2019 Examination Period
Faculty of Information Technology
During an exam, you must not have in your possession any item/material that has not been authorised for your exam. This includes books, notes, paper, electronic device/s, mobile phone, smart watch/device, calculator, pencil case, or writing on any part of your body. Any authorised items are listed below. Items/materials on your desk, chair, in your clothing or otherwise on your person will be deemed to be in your possession.
You must not retain, copy, memorise or note down any exam content for personal use or to share with any other person by any means following your exam.
You must comply with any instructions given to you by an exam supervisor.
As a student, and under Monash University¡¯s Student Academic Integrity procedure, you must undertake your in-semester tasks, and end-of-semester tasks, including exams, with honesty and integrity. In exams, you must not allow anyone else to do work for you and you must not do any work for others. You must not contact, or attempt to contact, another person in an attempt to gain unfair advantage during your exam session. Assessors may take reasonable steps to check that your work displays the expected standards of academic integrity.
Failure to comply with the above instructions, or attempting to cheat or cheating in an exam may constitute a breach of instructions under regulation 23 of the Monash University (Academic Board) Regulations or may constitute an act of academic misconduct under Part 7 of the Monash University (Council) Regulations.
Authorised Materials
OPEN BOOK YES NO CALCULATORS YES NO SPECIFICALLY PERMITTED ITEMS YES NO if yes, items permitted are:
Instructions
Page 1 of 25
Please answer all questions.
This exam is worth 60% of your overall mark.
To answer a question that requires a code response use 2 spaces to represent each indentation level. Do not use the Tab key to indent, as this will not indent and instead move you to the next field.
Page 2 of 25
Instructions
Information
Please answer all questions.
This exam is worth 60% of your overall mark.
To answer a question that requires a code response use 2 spaces to represent each indentation level. Do not use the Tab key to indent, as this will not indent and instead move you to the next field.
Page 3 of 25
Multiple Choice
Question 1
This question is about hash tables with open addressing.
A hash table of size 10 uses hash functionhash(key) = key % 10and linear probing to handle collisions. After inserting 6 keys into an empty hash table, the corresponding hash table is as follows: [None, None, 32, 13, 54, 22, 46, 53, None, None]
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?
Select one:
a. 46, 32, 54, 22, 13, 53
b. 54, 32, 13, 22, 53, 46 c. 46, 54, 32, 13, 22, 53 d. 32, 46, 53, 13, 54, 22 e. 53, 46, 22, 54, 13, 32 f. None of the above
Question 2
Consider the array representation of Heap class as seen in the lectures. Which one of the following arrays does not represent a max heap.
Select one:
a. [None,9,5,6,3,4,1]
b. [None,11,9,3,5,6,1] c. [None,8,6,5,3,2,2]
d. [None,15,6,10,2,7,8] e. [None,11,7,9,5,6,8] f. None of the above.
3
Marks
3
Marks
Page 4 of 25
MIPS
Information
To answer a question that requires a code response use 2 spaces to represent each indentation level. Do not use the Tab key to indent, as this will not indent and instead move you to the next field.
Question 3
This question is about MIPS. (The MIPS reference sheet is included below.)
3
Marks
Page 5 of 25
Page 6 of 25
Assume you want to translate to MIPS the Python condition
where both x and y are global variables. Which of the following pieces of MIPS code correctly translates the Python condition? Indicate what each line of the selected code does, or (if “None of the above”) provide the correct code.
a)
if x <= y:
Page 7 of 25
b)
c)
d)
e)
f)
g)
h)
i)
None of the above.
Question 4
This question is about MIPS. (The MIPS reference sheet is included below.)
3
Marks
lw $t0, x
lw $t1, y
slt $t2, $t0, $t1
bneq $t2, $0, endif
lw $t0, x
lw $t1, y
slt $t2, $t1, $t0
bne $t2, $0, endif
lw $t0, x
lw $t1, y
slt $t2, $t1, $t0
beq $t2, $0, endif
slt $t2, x, y
beq $t2, $0, endif
slt $t2, x, y
bne $t2, $0, endif
slt $t2, y, x
beq $t2, $0, endif
slt $t2, y, x
bne $t2, $0, endif
lw $t0, x
lw $t1, y
slt $t2, $t0, $t1
beq $t2, $0, endif
Page 8 of 25
Page 9 of 25
The following piece of MIPS code translates the Python array access
where x, the_list and i are all global variables. The code is correct ifi>0. This might seem strange, as the MIPS code does not include an instruction to subtract 1 from index i. Explain why this is not needed when i>0 (no explanation no marks).
x = the_list[i-1]
Page 10 of 25
lw $t0, i
lw $t1, the_list
addi $t2, $0, 4
mult $t0, $t2
mflo $t0
add $t0, $t0, $t1
lw $t0, ($t0)
sw $t0, x
Page 11 of 25
Sorting
Information
To answer a question that requires a code response use 2 spaces to represent each indentation level. Do not use the Tab key to indent, as this will not indent and instead move you to the next field.
Question 5
This question is about sorting. Consider the following piece of code:
8
Marks
def some_sort(the_array): n = len(the_array)
for p in range(n):
tmp = the_array[p]
q=0
while the_array[q] < tmp:
q += 1
while q <= p:
r = the_array[q]
the_array[q] = tmp
tmp = r
q += 1
Is this a correct sorting algorithm? If so, explain the invariant that ensures correctness; if not, give an example where it fails.
Question 6
Given the following implementation of Quick Sort, implement the partition function, choosing thelast element of the list as pivot.
7
Marks
def quick_sort(array): start = 0
end = len(array) - 1 quick_sort_aux(array, start, end)
def quick_sort_aux(array, start, end): if start < end:
boundary = partition(array, start, end) quick_sort_aux(array, start, boundary - 1) quick_sort_aux(array, boundary + 1, end)
Page 12 of 25
Data Structures
Question 7
This question is about Data Structures.
Consider a List class implemented using arrays, whose partial implementation is as follows:
4
Marks
def __init__(self, size): if size <= 0:
raise ValueError("Size should be positive") self.array = [None] * size
self.count = 0
def size(self):
return self.count
def is_empty(self):
return self.size() == 0
def is_full(self):
return self.size() >= len(self.array)
Add to the class an implementation of the method
which returns True if item appears in the list. Note that __contains__ should have O(N) worst case complexity (where n is the number of items in the list).
Question 8
Consider a List class implemented using arrays, whose partial implementation is as follows:
7
Marks
__contains__(self, item)
def __init__(self, size): if size <= 0:
raise ValueError("Size should be positive") self.array = [None] * size
self.count = 0
def size(self):
return self.count
def is_empty(self):
return self.size() == 0
def is_full(self):
return self.size() >= len(self.array)
Add also to the List class an implementation of the method
which removes and returns the element at index 0, ensuring all other elements are correctly swapped to the left. You should appropriately account for any errors.
remove_first(self)
Page 13 of 25
Question 9
Consider the following partial implementation of aQueue class, which is implemented using only two Stacks (with the usual operations).
Explain how you would implement the append(self, item) and serve(self) methods with this representation. Try to make it as efficient as possible (you do not need to give code).
6
Marks
class Queue:
def __init__(self):
self.left = Stack()
self.right = Stack()
Page 14 of 25
Linked Lists
Question 10
This question is about understanding code that uses linked lists. Consider a List class implemented using linked nodes, and defined as follows:
8
Marks
class Node:
def __init__(self, item, link = None):
self.item = item self.link = link
class List:
def __init__(self):
self.head = None
def add(self, item):
self.head = Node(item,self.head)
def mystery(self):
while (self.head is not None and self.head.item < 0):
self.head = self.head.link if self.head is not None:
previous = self.head current = self.head.link
while current is not None: if current.item < 0:
previous.link = current.link else:
previous = current current = current.link
Which list of those shown below is the result of calling themystery method for linked list? Option A:
Option B:
Option C:
Option D:
Option E:
Page 15 of 25
Option F:
Option G:
None of the above
Explain why (no explanation, no marks). If the answer is "None of the above" provide the elements of the correct resulting list.
Page 16 of 25
Recursion
Question 11
This question is about Recursion.
You are visiting a friend, who has previously completed FIT1008/FIT2085, for the weekend. But when you arrive, your friend is nowhere to be found; and instead of their door code, they have just left you a pair of numbers, and the following clue:
2
Marks
def clue(x, y):
if y == 0:
return 1
elif y % 2 == 1:
y = clue(x, y-1)
return x * y
else:
y = clue(x, y//2)
return y * y
You may assume all inputs are positive integers.
Write the result of the function clue for the input values:
x = 100, y = 1
Question 12
This question is about Recursion.
You are visiting a friend, who has previously completed FIT1008/FIT2085, for the weekend. But when you arrive, your friend is nowhere to be found; and instead of their door code, they have just left you a pair of numbers, and the following clue:
2
Marks
def clue(x, y):
if y == 0:
return 1
elif y % 2 == 1:
y = clue(x, y-1)
return x * y
else:
y = clue(x, y//2)
return y * y
You may assume all inputs are positive integers.
Write the result of the function clue for the input values: x = 4, y = 2
Page 17 of 25
Question 13
This question is about Recursion.
You are visiting a friend, who has previously completed FIT1008/FIT2085, for the weekend. But when you arrive, your friend is nowhere to be found; and instead of their door code, they have just left you a pair of numbers, and the following clue:
2
Marks
def clue(x, y):
if y == 0:
return 1
elif y % 2 == 1:
y = clue(x, y-1)
return x * y
else:
y = clue(x, y//2)
return y * y
You may assume all inputs are positive integers.
Write the result of the function clue for the input values:
x = 2, y = 3
Question 14
This question is about Recursion.
You are visiting a friend, who has previously completed FIT1008/FIT2085, for the weekend. But when you arrive, your friend is nowhere to be found; and instead of their door code, they have just left you a pair of numbers, and the following clue:
2
Marks
def clue(x, y):
if y == 0:
return 1
elif y % 2 == 1:
y = clue(x, y-1)
return x * y
else:
y = clue(x, y//2)
return y * y
You may assume all inputs are positive integers.
Write the result of the function clue for the input values: x = 2, y = 5
Page 18 of 25
Question 15
You are visiting a friend, who has previously completed FIT1008/FIT2085, for the weekend. But when you arrive, your friend is nowhere to be found; and instead of their door code, they have just left you a pair of numbers, and the following clue:
3
Marks
def clue(x, y):
if y == 0:
return 1
elif y % 2 == 1:
y = clue(x, y-1)
return x * y
else:
y = clue(x, y//2)
return y * y
You may assume all inputs are positive integers.
What is the worst-case time complexity of clue (using big-O time complexity)? Explain your answer (no explanation, no marks).
Page 19 of 25
Binary Search Trees
Question 16
This question is about Binary Search Trees.
Complete the missing expressions (#1 to #5) of sum_leq, which recursively computes the sum of all
elements in a BST tree which are less than or equal to item.
9
Marks
def sum_leq(self, item):
return self.sum_leq_aux(self.root, item)
def sum_leq_aux(self, current, item): if tree is None:
return #1
else:
low_sum = #2
if tree.item == item:
return #3
elif #4
return low_sum
else:
return #5
Question 17
The following method either returns the sum of the items in the tree that areancestors of the node whose item is value in the tree, or returns None if value is not present.
2
Marks
def sum_parents(node, value): if node is None:
return None
elif node.item == value:
return 0
elif value < node.item:
below = sum_parents(node.left, value) else:
below = sum_parents(node.right, value) if below is None:
return None
else:
return below + node.item
What is the worst-case complexity of sum_parents? (Remember to define any variables you use). For what kind of trees does this occur?
Page 20 of 25
Question 18
Complete the tail-recursive function sum_parents_tail, which is computes the same value as sum_parents
5
Marks
def sum_parents_tail(node, value):
return sum_parents_tail_aux(node, value, 0)
def sum_parents_tail_aux(node, value, acc): if node is None:
return #1
elif node.item == value:
return #2
else:
#3
Page 21 of 25
Heaps
Question 19
This question is about heaps.
Consider an implementation of a MaxHeap, which provides the following methods:
__init__(self), which creates a MaxHeap object
add(self, item), which adds an item to the heap
get_max(self), which removes (and returns) the highest value item from the Heap.
Write a function find_kth_smallest(alist, k) which finds the kth smallest item in array alist (with 1 being the smallest). You must start your implementation with the following code:
You cannot use any additional MaxHeaps or other data structures.
8
Marks
def find_kth_smallest(alist, k): mx = MaxHeap()
n = len(alist)
# TODO
Page 22 of 25
Assertions / Exceptions
Question 20
This question is about Assertions and Exceptions. Consider the following (somewhat strange) code:
4
Marks
class MyError(Exception): pass
def mystery1(a, b):
assert a >= b, “a should be greater or equal to b” if a != b:
raise MyError(“a is not equal to b”) return 15
def mystery2(a, b):
try:
return mystery1(a, b)
except MyError:
return 8
if __name__ == ‘__main__’: try:
result = mystery2(3, 4)
print(“Result:” + str(result)) except AssertionError as e:
print(e)
except MyError as e:
print(e)
Select the correct output, and explain your selection (no explanation, no marks).
It will terminate normally and output “a is not equal to b”.
It will terminate normally and output “a should be greater or equal to b”. It will terminate normally and output “Result: 15”.
It will terminate normally and output “Result: 8”.
It will terminate normally, but produces no output.
It will crash with an Assertion Error.
It will crash with a Type Error.
It will crash with MyError “a is less than b”.
Page 23 of 25
Page 24 of 25
Page 25 of 25