• API
• FAQ
• Tools
• Archive
daily pastebin goal
9%
SHARE
TWEET

# Untitled

a guest Aug 12th, 2017 43 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.
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.
112.     ''' A linked list implementation of a list. '''
113.     def __init__(self):
114.         ''' A new empty list. '''
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top