Lecture 37 - Test

If you do not currently have a directory for tests, create one in your cs170 directory, and also create a directory for the final. 

$ mkdir ~/cs170/tests
$ mkdir ~/cs170/tests/final
$ cd ~/cs170/test/final

This portion of the test is worth 35 total points. You may reference any files within your directory. You may only access the Python documentation website and the tkinter documentation website. NO OTHER WEBSITES ARE PERMITTED. As usual, you are not allowed to directly copy any code from the Internet or another individual without citation. You should also follow all coding standards discussed thus far.

Final

Question 10

Download the file queue.py, and save it into your test directory. Write a function called reverse_queue(a_queue) in a file called question_10.py. This function should take a queue as a parameter, and modify the queue so that all of the elements are now in reverse order. You may use any additional data structures necessary. 

>>> my_queue = queue.Queue()
>>> for i in range(10):
...     my_queue.enqueue(i)
>>> print(my_queue)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> reverse_queue(my_queue)
>>> print(my_queue)
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

(10 points)

Question 11

Download the file tree.py, and save it into your test directory. Write a function called is_complete_binary_tree(a_binary_tree) in a file called question_11.py. This function should take a binary tree as a parameter, and recursively determine whether the tree is a complete binary tree order.

YOU WILL NEED A HELPER FUNCTION FOR THIS

Remember, a tree is a complete binary tree if every node has 0 children, just a left child, or has both children. 

>>> my_tree = tree.BinaryTree()
>>> my_tree.insert(5)
>>> my_tree.insert(3)
>>> my_tree.insert(2)
>>> my_tree.insert(4)
>>> my_tree.insert(7)
>>> my_tree.insert(6)
>>> print(is_complete_binary_tree(my_tree))
True
>>> my_tree.root.right.left = None
>>> my_tree.root.right.right = my_tree._Node(6)
>>> print(is_complete_binary_tree(my_tree))
False

(10 points)

Question 12

Download the graph.py file into your test directory. In a file called question_12.py, write a function called is_connected(a_graph), which returns True if the specified undirected graph is connected.

Recall that a undirected graph is connected if every vertex appears in a depth first traversal of the graph, irrelevant of the starting position. Write a function called depth_first(a_graph, curr_vertex, visited_list), which adds all of the verticies that can be reached from curr_vertex to the visited list.

exam_sample.in 
>>> my_graph = graph.Graph("exam_sample.in")
>>> print(is_connected(my_graph))
True
>>> my_graph.adjacency_matrix[2][4] = 0
>>> print(is_connected(my_graph))
False

(15 points)

Submission

When you have finished, create a tar file of your final directory. To create a tar file, execute the following commands:

cd ~/cs170/tests
tar czvf final.tgz final/

To submit your activity, go to cseval.roanoke.edu. You should see an available assignment called Test 2. Make sure you include a header listing the authors of the file.

Last modified: Fri Mar 21 12:35:54 EDT 2014