Intermediate Programming BST二叉树数据结构讲解、讲解讲解BST树数据结构

CMPSC-122: Intermediate Programming

Summer 2018

Lab #11

Due Date: 07/06/2018, 11:59PM EST

Instructions:

- The work in this lab must be completed alone.

- This is a non-coding assignment

Question 1 [2 pts]

In which order are the elements of this binary tree accessed during a BFS, Preorder DFS, Inorder

DFS and Postorder DFS traversal?

13

Question 2 [2 pts]

 What is the adjacency matrix and adjacency list representation of the following undirected

graph?

 In which order are the elements of this graph accessed during a BFS and DFS traversal starting

at node A? Include also the BFS and DFS tree (vertices and tree edges). When doing the

traversal, follow the nodes in alphabetical order

Question 3 [2 pts]

Performing DFS starting at node B, 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

I

Question 4 [2 pts]

Using Dijkstra's algorithm, what is the shortest path and its cost from node A to node F?

Complete the status of the table when the algorithm is done calculating the shortest path to show

the shortest path from A to every other node

Question 5 [2 pts]

Assume you have a hash table of size 11. What is the final status of the hash table after inserting

10, 22, 31, 4, 15, 28, 17, 88, 59 (in that order) using linear probing with probe +1 and quadratic

probing? Do the operations by hand first!

Deliverables:

 Submit your answers in a PDF file name LAB11.pdf to the Lab11 CANVAS assignment

before the due date