#18 Graphs and Trees

1. Starting at 'T' on the graph shown below, which of these sequences is given by a depth-first search?

• A. TXYZUVW
• TVUZXYW
• TUVWXYZ
• TVUXWZY

2. Which of these statements is true?

• A. A directed graph has a root node and ends at leaf nodes
• B. An undirected graph cannot be traversed using a depth-first search
• C. Both a directed and an undirected graph can be traversed using either breadth-first or depth-first traversal techniques
• D. An undirected graph has a root node and ends at leaf nodes

3. What data structure is commonly used to manage breadth-first traversal of graph data structures?

• A. Hash table
• B. Linked list
• C. Stack
• D. Queue

4. Which of these real-world scenarios does not lend itself to representation by a graph data structure?

• A. Railway stations and tracks between them
• International flight routeB. s
• C. Internet servers across a metropolitan area
• D. The organisation of computer memory

5. Starting at '0' on the graph shown below, which of these sequences is given by a breadth-first search?

• A. 0458761932
• B. 0475698132
• C. 0458132967
• D. 0854169732

6. An algorithm is written to randomly visit all the nodes in the graph below at least once starting from '1'. Which of the following contains an illegal/erroneous random traversal of the graph?

• A. 124635
• B. 126453
• C. 126354
• D. 1245635

7. Which of the following techniques cannot be used to represent a graph data structure?

• A. A logic circuit diagram
• B. An adjacency matrix
• C. An object-oriented program
• D. An array/list of tuples

8. Name the data structure shown below.

• A. Binary search tree
• B. Binary tree
• C. Tree
• D. Linked list

9. Perform an in-order traversal of the binary tree shown below. What sequence of letters emerges?

• A. AGKCMZWB
• B. KMZCGBWA
• C. KGMCZAWB
• D. AGWKCBMZ

10. A directed graph is represented by the following edges, described as a list of tuples. What special property does it have? {(A,P), (A,H), (P,T), (P,L),(H,J),(H,B)}

• A. It forms a circular pathway that visits all nodes once
• B. All nodes radiate out from a central node
• C. It forms a linked list that is doubly linked
• D. It forms a binary tree