Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ### CSC 148H past final exams ###
- ### August 2010 ###
- ### Question 1 ###
- """
- Part a)
- No, because not all levels are filled from the left to the right. (node '12'
- has a right child, but no left child)
- This violates the first property of a min heap: every 'level' is filled from
- the left.
- Part b)
- Yes, it respects both properties of a min heap.
- Part c)
- No, because node '8' has a child smaller than him. (node '3')
- This violates the second property of a min heap: no parent has a child with
- a smaller value.
- """
- ### Question 2 ###
- """
- Part a)
- The list representing the new heap would be:
- L = [1, 6, 2, 8, 9, 4, 5, 12]
- Part b)
- The list representing the new heap would be:
- L = [5, 7, 9, 10, 12]
- """
- ### Question 3 ###
- """
- Part a)
- """
- def _parent(index):
- ''' Return the index of the parent of the specified index in a heap. '''
- return (index - 1) / 2
- def _left_child(index):
- ''' Return the index of the left child of the specified index. '''
- return index * 2 + 1
- def _right_child(index):
- ''' Return the index of the right child of the specified index. '''
- return index * 2 + 2
- def is_min_heap(L):
- ''' Takes a list L and returns True if the list is a representation of a min
- heap and False otherwise. '''
- i = 0
- while _left_child(i) < len(L):
- if L[i] > L[_left_child(i)] or L[i] > L[_right_child(i)]:
- return False
- i += 1
- return True
- """
- Part b)
- Answer: Yes.
- """
- ### Question 4 ###
- """
- Part a)
- The output is: [100, 0, 0, 0]
- Part b)
- The output is: [0, 0, 0, 0]
- """
- ### Question 5 ###
- class Node(object):
- ''' A linked list node containing data and a reference to the next node. '''
- def __init__(self, data):
- ''' A new node to hold data and no next node. '''
- self.data = data
- self.next = None
- class LinkedList(object):
- ''' A linked list implementation of a list. '''
- def __init__(self):
- ''' A new empty list. '''
- self.head = None
- def sum_every_other(L):
- ''' Takes a list L and returns the sum of every other element of L. '''
- if L == []:
- return 0
- else:
- return L[0] + sum_every_other(L[2:])
- def duplicate(L):
- ''' Takes a list L and duplicates every node. It modifies L so that it
- contains every element from the original list twice in a row. '''
- for i in range(len(L)):
- L.insert(i + i, L[i + i])
- ### Question 6 ###
- """
- The output is: 'AHH'
- """
- ### Question 7 ###
- def reverse_stack(stack):
- ''' Takes as input a stack and returns a new stack that contains all the same
- items, but in reverse order. '''
- new_stack = Stack()
- return reverse_stack_helper(stack, new_stack)
- def reverse_stack_helper(stack, new_stack):
- ''' A helper function for reverse_stack. '''
- while not stack.is_empty():
- new_stack.push(stack.pop())
- return new_stack
- ### Question 8 ###
- class Node(object):
- ''' A node of a binary tree. '''
- def __init__(self, key):
- ''' A new node to hold data and with no children. '''
- self.key = key
- self.right = None
- self.left = None
- class BinaryTree(object):
- ''' A binary tree. '''
- def __init__(self):
- ''' Creates an empty binary tree. '''
- self.root = None
- def print_even(bst):
- ''' Prints the even values of a binary search tree in ascendin order. '''
- print_even_helper(bst.root)
- def print_even_helper(node):
- ''' Prints the even values of a binary search tree rooted at the given
- node (in ascending order). '''
- if not node:
- return
- else:
- print_even_helper(node.left)
- print node.key
- print_even_helper(node.right)
- ### Question 9 ###
- """
- Not necessary. :-)
- """
- ### Testing out the code. ###
- ##if __name__ == "__main__":
- ##a = Node(8)
- ##a.left = Node(3)
- ##a.left.left = Node(1)
- ##a.left.right = Node(6)
- ##a.left.right.left = Node(4)
- ##a.left.right.right = Node(7)
- ##a.right = Node(10)
- ##a.right.right = Node(14)
- ##a.right.right.left = Node(13)
- ##tree = BinaryTree()
- ##tree.root = a
- ##print_even(tree)
- ##L = [1,4,2,5,8,6,3]
- ##print is_min_heap(L)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement