首页 > > 详细

讲解SPSS|辅导Python编程|辅导Python程序|辅导留学生 Statistics统计、回归、迭代

Identifying information will be
printed here.
University of Waterloo
Final Examination
CS 234
Term: Spring Year: 2020
Due Date: August 15, 2020, 5:00 pm
Sections: 001–002
Student Signature:
UW Student ID Number:
Number of Exam Pages 15 pages
Exam Type Online
Instructions:
• We intend for you to print the exam and complete the answers on the exam book. However, the exam can
be completed by hand on blank paper or as a pdf.
• You are responsible for submitting your exam to Crowdmark by the due date. Ensure your solutions match
the questions on Crowdmark.
• Where you are asked to provide pseudocode, you may instead choose to write Python code to describe
an algorithm. You do not need to write a design recipe for your algorithms or express their running time,
unless otherwise indicated.
• When asked to complete pseudocode, you cannot modify any of the provided pseudocode.
• Unless otherwise indicated, your solutions should only use the data structures and ADTs described on the
reference sheet. Your solutions should not use built-in Python data structures such as lists and dictionaries.
• If you believe there is an error in the exam, contact the course staff on Piazza.
• It is your responsibility to properly interpret a question.
• The amount of space allocated to a question does not necessarily reflect the length of the response required.
• If you require more space to answer a question, there are blank pages at the end you may use instead, but
you must clearly indicate in the provided answer space that you have done so. Marks for that question
will be recorded on the initial page for that question and not the additional space.
Marking Scheme
Total Mark:
CS 234 Final Examination Spring 2020 Page 2 of 15
Marks on this page: 5
1. Hashing
(a) (2 marks) List two properties of a good function for hashing.
Why is each of the following not a good hash function for h(k) = f(k) mod N where N is the
number of slots in the hash table?
(b) (1 mark) f(k) = 2 ∗ k, where k is an integer
(c) (1 mark) f(k) = sum of the digits of k, where k is an integer
(d) (1 mark) f(k) = length of k where k is a string that is one English word
CS 234 Final Examination Spring 2020 Page 3 of 15
Marks on this page: 4
Suppose we have a hash-table that is implemented well. That is, the expected runtime of each
operations is θ(1). For each of the following ADTs, would you implement the ADT with a
hash-table? If you would, briefly describe the operations for inserting and deleting? If you would not,
what is one operation it would make more complicated to implement than an implementation from
class? Why is this operation complicated?
(e) (2 marks) Set
(f) (2 marks) Stack
CS 234 Final Examination Spring 2020 Page 4 of 15
Marks on this page: 4
2. (2,3)-Tree
(a) (4 marks) Write the function find node(T, key) that consumes a (2,3)-Tree T and an
integer key and produces the leaf node in T that key can be inserted into (before a possible
split). If T is empty, return False. You may assume key is not present in T.
CS 234 Final Examination Spring 2020 Page 5 of 15
Marks on this page: 5
(b) (2 marks) Suppose we have a (2,3)-Tree that contains the keys 1 to 7. What is the minimum and
maximum height the tree can be? Draw an example of a minimum and maximum height
(2,3)-Tree.
(c) (3 marks) Given the following (2,3)-Tree, insert 70.
20 40
4 12 26 34 63 81
CS 234 Final Examination Spring 2020 Page 6 of 15
Marks on this page: 4
3. Algorithm Analysis
(a) (4 marks) The following is a graph algorithm for finding the shortest path from start (which is a
vertex) to all other vertices.
Determine the runtime of the algorithm in Big-O notation in terms of the functions and
operations used for all ADTs used (Set, Dictionary, and Graph). Assume that the graph is
connected and has n vertices and m edges. You may assume each node has at most d neighbours.
Use R(f unction) to denote the runtime for a function. For example, R(Vertices) represents the
runtime of Vertices.
short_paths(Graph, start):
V <- Vertices(Graph) // returns a Set
Distance <- Dictionary()
Prev <- Dictionary()
for i from 0 to Len(V) - 1:
v <- Access(V, i)
Add(Distance, v, Infinity)
Add(Prev, v, None)
Add(Distance, start, 0)
while not Is_Empty(Distance):
min <- Minimum(Distance)
Delete(V, Key(min))
for v in Neighbours(Graph, Key(min)):
dist <- Value(min) + Edge_Value(Graph, Key(min), v)
if dist < Lookup(Distance, v):
Add(Distance, v, dist)
Add(Prev, v, Key(min))
return Pair(Distance, Prev)
CS 234 Final Examination Spring 2020 Page 7 of 15
Marks on this page: 7
(b) (2 marks) Simplify the runtime for the previous operation given that the operations for
Dictionary and Set have the following runtimes:
Set: Access - O(1), Delete - O(1)
Dictionary: Dictionary - O(1), Add - O(logn), Delete - O(logn), Is Empty - O(1), Minimum -
O(logn)
Simplify the runtime from part b) given each implementation of the Graph ADT and the runtime of
the operations.
(c) (1 mark) Edge List: Vertices - O(m), Neighbours - Neighbours - O(m), Edge Value - O(m)
(d) (1 mark) Adjacency List: Vertices - O(n), Neighbours - O(d), Edge Value - O(d), where d is
the degree of the vertex.
(e) (1 mark) Adjacency Matrix: Vertices - O(n), Neighbours - O(n), Edge Value - O(1)
(f) (2 marks) Which implementation has the best runtime for vertices having at most 3 neighbours?
Justify your choice.
CS 234 Final Examination Spring 2020 Page 8 of 15
Marks on this page: 4
4. Heap
In class, we looked only a min heap. However, by reversing the heap order property, i.e. the values in
the children of a node must be smaller than in the node, we will have a max heap.
(a) (1 mark) A min heap is implemented to find and remove the minimum value quickly. What
were the runtimes for the following operations?
insert(Heap, Value)
find min(Heap)
remove min(Heap)
(b) (3 marks) Your friend comes to you and proposes a new ADT, a Min-Max-Heap. They suggest
that the ADT will be able to find and remove the minimum and maximum items in logarithmic
time.
They plan to implement that ADT using a Min Heap and a Max Heap. They will insert each new
added item into both heap as follows.
insert(MMHeap, item):
MMHeap.min_heap.insert(item)
MMHeap.max_heap.insert(item)
Explain why the delete min and delete max functions for this implementation will not be
in logarithmic time.
CS 234 Final Examination Spring 2020 Page 9 of 15
Marks on this page: 3
(c) (3 marks) Consider the following MinMaxNode class.
class MinMaxNode:
def __init__(self, value):
self.value = value
self.min_parent = None
self.min_left = None
self.min_right = None
self.max_parent = None
self.max_left = None
self.max_right = None
Using this class to store a value in both a Min Heap and a Max Heap would allow us to remove
the node from both heaps in logarithmic time.
We want to write the delete min function for a MinMaxHeap. Finish the function below.
delete_min(MMHeap):
# returns the MinMaxNode removed from the min_heap
node = MMHeap.min_heap.delete_min()
min_value = node.value
# write the code that removes the node from the max heap
CS 234 Final Examination Spring 2020 Page 10 of 15
Marks on this page: 6
5. AVL
(a) (3 marks) Consider the following AVL tree. Write the balances
height(right subtree)−height(left subtree)
of all nodes (in the figure itself).
(b) (3 marks) Draw the AVL tree obtained by deleting 27 from the one above. Give the balances of
all nodes.
CS 234 Final Examination Spring 2020 Page 11 of 15
Marks on this page: 7
6. Interpolation Search
(a) (3 marks) What is the running time of interpolation search on A = [1,2,...,n−1,n
1000] if we
are searching for n−1? Justify your answer.
(b) (4 marks) Suppose A is an array of size 16 and A[i] = t

i for 0 ≤ i ≤ 15 where t is some positive
number. If we are searching for t in A using interpolation search, in how many iterations does the
algorithm terminate? Compare the running time of this search with the average case (for evenly
spaced data) running time of interpolation search. Justify your answer and explain the difference.
CS 234 Final Examination Spring 2020 Page 12 of 15
Marks on this page: 5
7. Trie
(a) (2 marks) Draw the standard trie (with alphabet {0,1}) that is obtained after inserting the
following keys into an initially empty trie:
1011,001,1101,10010,10,11,10100,1,000,101,00
(b) (3 marks) Find the exact height, in terms of k, of the trie with keys that are binary
representations of numbers 0,1,2,3,4,...,2
k −1 without leading 0s, and inserted into the trie in
increasing order. That is, insert 0,1,10,11,100, etc.
CS 234 Final Examination Spring 2020 Page 13 of 15
Marks on this page: 3
8. Skip-List Consider the skip-list L shown below.
Show how Search(L,360) proceeds. More specifically show the order of all nodes of the skip list that
are visited (you do not need to include the positions that are looked up but not visited). You should
refer to the nodes using their keys and levels, e.g. (104,L1). The lowest/bottom level is L0.
CS 234 Final Examination Spring 2020 Page 14 of 15
Marks on this page: 4
9. Improving Implementations
When working with ADTs, we can often improve the running time of operations by augmenting the
data structure with additional information.
For example, the size of the subtree rooted at each node can be stored in the node. This enables a
logarithmic time search for the i
th largest element in the tree. However, this additional information
must be maintained by all operations.
Suppose we want to add this augmentation to the Binary Search Tree ADT. We will add the field
size in each node to store the size of the subtree rooted at the node. Add the modifications needed to
the pseudocode provided for add leaf to ensure that all nodes in the tree have the correct size after
a value is added. Recall that add leaf may replace a subtree that already exists with a single node.
You may assume that the field size is set to 1 when a Node is created and that the size field is
maintained for all Nodes prior to this operation being called.
There is a field in the Binary Search Tree ADT called root that stores the root of the tree.
add_leaf(T, Value, Parent, Side):
if Parent == None:
T.root = Node(value)
else if Side == "left":
Parent.left = Node(value)
else:
Parent.right = Node(value)
(a) (1 mark) What is the runtime of add leaf? You may assume that all other BinaryTree and
Node operations on the reference sheet have a constant runtime. No justification is required.
CS 234 Final Examination Spring 2020 Page 15 of 15

联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!