SHARE
TWEET

Untitled

a guest Aug 12th, 2017 42 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ### CSC 148H past final exams ###
  2. ### August 2010 ###
  3.  
  4. ### Question 1 ###
  5.  
  6. """
  7.  
  8. Part a)
  9.  
  10. No, because not all levels are filled from the left to the right. (node '12'
  11. has a right child, but no left child)
  12.  
  13. This violates the first property of a min heap: every 'level' is filled from
  14. the left.
  15.  
  16. Part b)
  17.  
  18. Yes, it respects both properties of a min heap.
  19.  
  20. Part c)
  21.  
  22. No, because node '8' has a child smaller than him. (node '3')
  23.  
  24. This violates the second property of a min heap: no parent has a child with
  25. a smaller value.
  26.  
  27. """
  28.  
  29. ### Question 2 ###
  30.  
  31. """
  32.  
  33. Part a)
  34.  
  35. The list representing the new heap would be:
  36. L = [1, 6, 2, 8, 9, 4, 5, 12]
  37.  
  38. Part b)
  39.  
  40. The list representing the new heap would be:
  41. L = [5, 7, 9, 10, 12]
  42.  
  43. """
  44.  
  45. ### Question 3 ###
  46.  
  47. """
  48.  
  49. Part a)
  50.  
  51. """
  52.  
  53. def _parent(index):
  54.     ''' Return the index of the parent of the specified index in a heap. '''
  55.    
  56.     return (index - 1) / 2
  57.  
  58. def _left_child(index):
  59.     ''' Return the index of the left child of the specified index. '''
  60.    
  61.     return index * 2 + 1
  62.  
  63. def _right_child(index):
  64.     ''' Return the index of the right child of the specified index. '''
  65.    
  66.     return index * 2 + 2
  67.  
  68. def is_min_heap(L):
  69.     ''' Takes a list L and returns True if the list is a representation of a min
  70.     heap and False otherwise. '''
  71.    
  72.     i = 0
  73.     while _left_child(i) < len(L):
  74.         if L[i] > L[_left_child(i)] or L[i] > L[_right_child(i)]:
  75.             return False
  76.         i += 1
  77.    
  78.     return True
  79.  
  80. """
  81.  
  82. Part b)
  83.  
  84. Answer: Yes.
  85.  
  86. """
  87.  
  88. ### Question 4 ###
  89.  
  90. """
  91.  
  92. Part a)
  93.  
  94. The output is: [100, 0, 0, 0]
  95.  
  96. Part b)
  97.  
  98. The output is: [0, 0, 0, 0]
  99.  
  100. """
  101.  
  102. ### Question 5 ###
  103.  
  104. class Node(object):
  105.     ''' A linked list node containing data and a reference to the next node. '''
  106.     def __init__(self, data):
  107.         ''' A new node to hold data and no next node. '''
  108.         self.data = data
  109.         self.next = None
  110.        
  111. class LinkedList(object):
  112.     ''' A linked list implementation of a list. '''
  113.     def __init__(self):
  114.         ''' A new empty list. '''
  115.         self.head = None
  116.        
  117. def sum_every_other(L):
  118.     ''' Takes a list L and returns the sum of every other element of L. '''
  119.    
  120.     if L == []:
  121.         return 0
  122.     else:
  123.         return L[0] + sum_every_other(L[2:])
  124.    
  125. def duplicate(L):
  126.     ''' Takes a list L and duplicates every node. It modifies L so that it
  127.     contains every element from the original list twice in a row. '''
  128.    
  129.     for i in range(len(L)):
  130.         L.insert(i + i, L[i + i])
  131.        
  132. ### Question 6 ###
  133.  
  134. """
  135.  
  136. The output is: 'AHH'
  137.  
  138. """
  139.  
  140. ### Question 7 ###
  141.  
  142. def reverse_stack(stack):
  143.     ''' Takes as input a stack and returns a new stack that contains all the same
  144.     items, but in reverse order. '''
  145.    
  146.     new_stack = Stack()
  147.     return reverse_stack_helper(stack, new_stack)
  148.  
  149. def reverse_stack_helper(stack, new_stack):
  150.     ''' A helper function for reverse_stack. '''
  151.    
  152.     while not stack.is_empty():
  153.         new_stack.push(stack.pop())
  154.        
  155.     return new_stack
  156.  
  157. ### Question 8 ###
  158.  
  159. class Node(object):
  160.     ''' A node of a binary tree. '''
  161.  
  162.     def __init__(self, key):
  163.         ''' A new node to hold data and with no children. '''
  164.        
  165.         self.key = key
  166.         self.right = None
  167.         self.left = None
  168.        
  169. class BinaryTree(object):
  170.     ''' A binary tree. '''
  171.    
  172.     def __init__(self):
  173.         ''' Creates an empty binary tree. '''
  174.        
  175.         self.root = None
  176.        
  177. def print_even(bst):
  178.     ''' Prints the even values of a binary search tree in ascendin order. '''
  179.    
  180.     print_even_helper(bst.root)
  181.    
  182. def print_even_helper(node):
  183.     ''' Prints the even values of a binary search tree rooted at the given
  184.     node (in ascending order). '''
  185.    
  186.     if not node:
  187.         return
  188.     else:            
  189.         print_even_helper(node.left)
  190.         print node.key
  191.         print_even_helper(node.right)
  192.  
  193. ### Question 9 ###
  194.  
  195. """
  196.  
  197. Not necessary. :-)
  198.  
  199. """
  200.  
  201. ### Testing out the code. ###
  202.  
  203. ##if __name__ == "__main__":
  204.    
  205.     ##a = Node(8)
  206.     ##a.left = Node(3)
  207.     ##a.left.left = Node(1)
  208.     ##a.left.right = Node(6)
  209.     ##a.left.right.left = Node(4)
  210.     ##a.left.right.right = Node(7)
  211.     ##a.right = Node(10)
  212.     ##a.right.right = Node(14)
  213.     ##a.right.right.left = Node(13)
  214.     ##tree = BinaryTree()
  215.     ##tree.root = a
  216.    
  217.     ##print_even(tree)
  218.    
  219.     ##L = [1,4,2,5,8,6,3]
  220.     ##print is_min_heap(L)
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top