CMPSC-132: Programming and Computation II
Lab #8
编程和计算代写 Watch the video lectures before starting the assignment. For any credit, final answer must be uploaded using the answer…
Watch the video lectures before starting the assignment. For any credit, final answer must be uploaded using the answer sheet provided.
Instructions: 编程和计算代写
– The work in this lab must be completed alone and must be your own.
– This is a non-coding assignment
– Make sure your answers are legible, you must submit 1 question per page. You can use the Word document provided on Canvas. File should be only 7 pages long (no more, no less).
– To receive any credit, circle your final answer, that will help us to locate your answers faster. If you are unable to complete a question, leave the page blank
– In order to ease the grading process, please use the provided Word template (if you are creating your own file, please exact 7 pages, 1 page per question) so graders get direct access to the page instead of traversing the entire file looking for your answers. Check the Sample Solutions File for do’s and don’ts
– Submit your answers as a PDF file to the Lab8 GradeScope assignment before the due date
Question 1 [2.5 pts]: 编程和计算代写
Draw the binary search tree obtained when inserting the values 47, 5, 3, 70, 23, 53, 15, 66, 81, 64, 85, 31, 83, 33, 9, 7 in that order into an empty BST. In which order are the elements of the obtained binary search tree accessed during a BFS, Preorder DFS, Inorder DFS and Postorder DFS traversal? What is the height of the tree? List the child node(s) of the node with value of 23
Question 2 [1 pt]: Draw the heap that results from inserting 10, 12, 1, 14, 3, 17, 7, 2, 5, 8, 6 and 70 (in that order) into an initially empty binary max heap. What is the array representation of the obtained heap? Show the result of performing 3 deleteMax operation in the resulting heap
Question 3 [1.5 pt]: Based on the following undirected graph (where there are no weights assigned to the edges), draw the BFS tree (vertices and tree edges) that results when performing a BFS traversal starting at node D, also draw the DFS tree that results when performing a DFS traversal starting at node H. Include with each tree the traversal path. Follow the alphabetical convention discussed in the video lectures
Question 4 [1 pts]. Performing DFS starting at node A, what is the topological sorting of the following graph? Draw the final topological sort. Remember that the topological sort is the decreasing ending times of the DFS traversal. When doing the traversal, follow the nodes in
alphabetical order
Question 5
[1 pt]. Run Dijkstra’s algorithm in the directed graph given below and complete the status of the table when the algorithm is done calculating the shortest path from node s to every other node in the graph. Based on that table, what is the shortest path and its cost from node s to
node t?
Question 6 [1 pt]: Find the minimum spanning tree for the graph given below using both Prim’s and Kruskal’s algorithms.
Question 7 [2 pt]: Assume you have a hash table of size 11. What is the final status of the hash table after inserting the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5 (in that order) assuming collisions are handled by open addressing using:
a) linear probing (+1 probe) and the hash function H(i) = (3*i+5) %11
b) quadratic probing and the hash function H(i) = (i) %11
c) double hashing and using the hash functions H1(i) = (i) %11 and H2(i) = 7- (i %7).
