DOC

exam(ch26, 27, 28)

By Alma Clark,2014-10-16 17:33
9 views 0
exam(ch26, 27, 28)

Name:_______________________ CSCI 2410 Data Structures and Algorithms

    Covers Armstrong Atlantic State University

    50 min Instructor: Y. Daniel Liang

    (Open book test, you can only bring the textbook)

    Part I: Multiple Choice Questions: (1 pts each) 1. (2 pts) Show the BST after inserting 45, 43, 100, 34, 23, and 3 into an empty BST.

    2. (2 pts) Show the BST after deleting 15 from the following BST.

     60 root

    15 100

    57 67 107

    49 64

    3. (2 pts) Show the BST after deleting 60 from the following BST.

     1

     60 root

    15 100

    57 67 107

    49 64

4. (3 pts) Show the inorder, preorder, and postorder of the

    following BST.

     60 root

    15 100

    57 67 107

    49 64

    5. (2 pts) Draw a DFS tree from the following graph starting from vertex E.

     D A

    B E

    C

    6. (2 pts) Draw a BFS tree from the following graph starting from vertex E.

     2

     D A

    B E

    C

    7. (2 pts) Find a MST in the following graph.

     1 D A

    6 5 2 10 11

    4 B E G

    12 9 7 8 3 F C

8. (2 pts) Find all shortest paths starting from vertex A

    in the following graph.

     1 D A

    6 5 2 10 11

    4 B E G

    12 9 7 8 3 F C

     3

    Part II: Multiple Choice Questions: (1 pts each) (Take the multiple-choice questions online from LiveLive before midnight today. Log in and click Take Instructor Assigned Quiz Quiz2. You have to take it before it is due. You have to submit it within 20 minutes.)

1. The ________ is to visit the left subtree of the current node first, then the current node itself, and finally the right

    subtree of the current node.

a. postorder traversal

    b. preorder traversal

    c. inorder traversal

    d. breadth-first traversal

    Key:c

#

    2. The time complexity for finding an element in a binary search tree is _________.

    a. O(logn)

    b. O(nlogn)

    c. O(n)

    d. O(1)

    Key:c

#

    3. To add a new node, you need to start a process by first placing it as _______ and move it up to maintain the heap

    property.

a. the last node in the heap

    b. the new root

    c. the right child of the root

    d. the left child of the root

    Key:a

#

    4. The time complexity of the DFS algorithm is O(|E|). a. true

    b. false

    Key:a

#

    5. A ____ is an edge that links a vertex to itself. a. loop

    b. parallel edge

    c. weighted edge

    d. directed edge

    Key:a

#

    6. If two vertices are connected by two or more edges, these edges are called ______.

    a. loop

    b. parallel edge

    c. weighted edge

    d. directed edge

    Key:b

#

    7. A _________ is the one in which every two pairs of vertices are connected.

    a. complete graph

     4

b. weighted graph

    c. directed graph

    Key:a

#

    8. A graph may have several minimum spanning tree. a. true

    b. false

    Key:a

#

    9. A ___________ of a graph is a subgraph that is a tree and connects all vertices in the graph.

    a. spanning tree

    b. shorted path

    Key:a

     5

Report this document

For any questions or suggestions please email
cust-service@docsford.com