edumeister_logo

CMPUT 175 B2: Final examName: showing page 1-10 out of 10

CMPUT 175 B2: Final exam
Name:
Instructor:
ID:
Percentage: 35%
Grade:
__
/ 70
Date: April 23, 2014
This final exam has 6 quesons, and a total of 10 pages.
Page 7 of this exam is a blank page for your use and answers.
This is a closed book exam (except for one cheat sheet).
No calculators or any other electronic devices allowed.
Queson 1
/ 10
Queson 2
/ 10
Queson 3
/ 10
Queson 4
/ 10
Queson 5
/ 10
Queson 6
/ 20
Total
/ 70
1
Queson 1:
(10 marks)
Time-complexity
: Fill in the blanks.
In the average case, Quicksort runs in O( ______ ) while in the worst case, it runs in O( _____ ).
Appending a data item to a Python list costs O( ______ ) while appending to a linked list costs O( ____ ).
Retrieving the smallest value in a min Binary Heap costs O( _____ ).
Traversing an enre Binary Search Tree costs O( ________ ).
In the best case scenario, searching for a value in a hash table costs O( _____ ) while in the worst case
scenario, a hash table that uses open addressing and linear probing can cost O( _____ ).
Both Bubble sort and Inseron sort run in O( ______ ) whether the data is sorted or not.
However,
Bubble sort can be modified to provide the advantage of verifying whether the data is sorted.
The
modified version of Bubble sort will run in O( ____ ).
Queson 2:
(10 marks)
Indicate whether each of the below statements is True or False.
Correct False ones
.
1)
Searching linearly for the largest value through a sorted dataset is more efficient than using a
Binary Search.
2)
In hash table implementaons, reducing collisions relies mainly on whether the hash table uses
chaining or linear probing.
3)
Searching through an imbalanced Binary Search Tree may cost the same amount of me as
searching through a linked list.
4)
Max Binary Heaps have a structure similar to Binary Search Trees (BST).
But unlike BST, max
Binary Heaps maintain the largest value at the root node and smaller values in the leaf nodes.
5)
The performance of Mergesort is oſten affected by whether the data is somewhat sorted or not.
2
Queson 3:
(10 marks)
Tracing and code review.
Describe three different issues with the following code, and suggest an improvement regarding each of
the idenfied issues:
max = 8
values =
[1, 3, 5, 8, 7, 5, 5, 4, 6, 1,9,11,9,12]
counts = [0] * max
for i in values:
counts[i] = counts[i] + 1
j = 0
for n in range(len(counts)):
for k in range(counts[n]):
values[j] = n
j = j + 1
print(values)
3
Queson 4:
(10 marks)
Stack implementaon: evaluate a posix expression using a Stack (ADT on page 8 of exam).
Implement the funcon
evaluatePostfix (expression)
to make the following program work
properly.
Note: an
expression
is a string.
An example of
expression
: 7 8 + 3 2 + /
def evaluatePostfix(expression):
def doMath(op, op1, op2):
if op == "*":
return op1 * op2
elif op == "/":
return op1 / op2
elif op == "+":
return op1 + op2
else:
return op1 - op2
4
Queson 5:
(10 marks)
Write a funcon to delete a parent node in a Binary Search Tree.
The parent node you will delete has
only a right child.
You may use funcons from the TreeNode class provided on page 9 of this exam.
5
Queson 6:
(20 marks)
Compare the design and implementaon of a min Binary Heap vs. a max Binary Heap.
Describe in detail
the implementaon of the min Binary Heap vs. that of the max Binary Heap given the funcons of the
Binary Heap ADT we have studied in class.
You may use the Binary Heap operaons – provided on page
10 of this exam – as a guideline for your comparison of the design and implementaon of the min Binary
Heap vs. the max Binary Heap.
You
don’t
need to implement the Binary Heaps but only compare their
design and implementaon in detail.
6
7
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
8
class TreeNode:
def __init__(self,key,val,left=None,right=None,parent=None):
self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent
def hasLeftChild(self):
return self.leftChild
def hasRightChild(self):
return self.rightChild
def isLeftChild(self):
return self.parent and self.parent.leftChild == self
def isRightChild(self):
return self.parent and self.parent.rightChild == self
def isRoot(self):
return not self.parent
def isLeaf(self):
return not (self.rightChild or self.leftChild)
def hasAnyChildren(self):
return self.rightChild or self.leftChild
def hasBothChildren(self):
return self.rightChild and self.leftChild
def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.payload = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self
9
Binary Heap Operations
The basic operations for a binary heap are as follows:
BinaryHeap()
creates a new, empty, binary heap.
insert(k)
adds a new item to the heap.
findMin()
returns the item with the minimum key value; or
findMax()
returns the item
with the maximum key value while leaving item in the heap.
delMin()
returns the item with the minimum key value; or
delMax()
returns the item
with the maximum key value removing the item from the heap.
isEmpty()
returns true if the heap is empty, false otherwise.
size()
returns the number of items in the heap.
buildHeap(list)
builds a new heap from a list of keys.
10

Upload your course documents to receive views for accessing documents on Edumeister.

Upload documents to earn views.