## 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 ﬁnal exam has 6 quesons, 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.

Queson 1

/ 10

Queson 2

/ 10

Queson 3

/ 10

Queson 4

/ 10

Queson 5

/ 10

Queson 6

/ 20

Total

/ 70

1

Queson 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 enre 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 Inseron sort run in O( ______ ) whether the data is sorted or not.

However,

Bubble sort can be modiﬁed to provide the advantage of verifying whether the data is sorted.

The

modiﬁed version of Bubble sort will run in O( ____ ).

Queson 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 eﬃcient than using a

Binary Search.

2)

In hash table implementaons, 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ﬅen aﬀected by whether the data is somewhat sorted or not.

2

Queson 3:

(10 marks)

Tracing and code review.

Describe three diﬀerent issues with the following code, and suggest an improvement regarding each of

the idenﬁed 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

Queson 4:

(10 marks)

Stack implementaon: evaluate a posix expression using a Stack (ADT on page 8 of exam).

Implement the funcon

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

Queson 5:

(10 marks)

Write a funcon to delete a parent node in a Binary Search Tree.

The parent node you will delete has

only a right child.

You may use funcons from the TreeNode class provided on page 9 of this exam.

5

Queson 6:

(20 marks)

Compare the design and implementaon of a min Binary Heap vs. a max Binary Heap.

Describe in detail

the implementaon of the min Binary Heap vs. that of the max Binary Heap given the funcons of the

Binary Heap ADT we have studied in class.

You may use the Binary Heap operaons – provided on page

10 of this exam – as a guideline for your comparison of the design and implementaon 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 implementaon 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