Trees and Graphs

Question 1

trees

how does a tree organise its data

Answer 1

hierarchically

Question 2

trees

what are the entities ina tree called

Answer 2

nodes

Question 3

trees

nodes are connected by ….

Answer 3

edges

Question 4

trees

each node contains a ……

Answer 4

value or data

Question 5

trees

what are the 3 conditions a tree must be

Answer 5

• connected
• undirected
• no cycles

Question 6

trees

describe what the following terms mean:
* root node
* parent node
* child node
* leaf node

Answer 6

• root node - the topmost node where it all comes from
• parent node - node that has an edge to a child node
• child node - nodes below a parent node
• leaf node - node with no children

Question 7

trees

what is a binary tree

Answer 7

tree data structure where each node has at most two children

Question 8

trees

what are the two nodes referred to as in a binary tree

Answer 8

left node, right node

Question 9

trees

draw a binary tree for the following data:
Rose, Jasmine, George, Naomi, trever, Stanley

Answer 9

Rose
/ \
Jsmine Trevor
/ \ \Stanley
George Naomi

cant really do it

Question 10

trees

what is a tree traversal

Answer 10

process that visits all the nodes in a tree

Question 11

trees

give the 3 different types of traversal

Answer 11

• preorder - parent first, then left and right
• inorder - visit the left, then parent, then right
• postorder - visit left, right, parent

Question 12

trees

whats the trick when performing a traversal

Answer 12

pre post

in

Question 13

graphs

what is a labelled graph

Answer 13

graph with values on the edges

Question 14

graphs

what is a labelled graph sometimes called

Answer 14

weighted graph

Question 14

graphs

what is a directed graph

Answer 14

it is directed. the edges have arrows on them

Question 15

graphs

explain how to create an adjacency matrix

Answer 15

if two vertices are connected, then a 1 is placed at the positions in the m,atrix. else its a 0

Question 16

graphs

explain how to create an adjacency list

Answer 16

specifiy the vertices that are adjcent to each vertex

Question 17

graphs

when is a list more suitable than an adjacency matrix

Answer 17

when the graph is sparse