graphs and trees

Question 1

graphs consist of…

Answer 1

nodes connected ny edges

Question 2

path

Answer 2

a route from a starting node to a destination node

Question 3

graph theory

Answer 3

a field of math that studies graphs, their properties, and their application

Question 4

connected graphs

Answer 4

for any pair of nodes u and v, there is a path from u to v

Question 5

connected graphs <->

Answer 5

disconnected

Question 6

directed graphs

Answer 6

directed edges

Question 7

weakly connected

Answer 7

there is a path between every pair of vertices in the undirected version of the graph

Question 8

strongly connected

Answer 8

for every pair of vertices u and v, there is a directed path from u to v and a directed path from v to u.

Question 9

cyclic

Answer 9

contains one or more cycles

Question 10

acyclic

Answer 10

contains no cycles

Question 11

weighted

Answer 11

edges have numerical values, called weight

Question 12

DAG

Answer 12

directed acyclic graph

Question 13

edges in non-weighted graphs carry binary information:

Answer 13

they do exist or they don’t

Question 14

tree

Answer 14

and undirected graph in which any two nodes are connected by exactly one path, or equivalently a connected acyclic undirected graph

Question 15

directed tree

Answer 15

DAG whose underlying undirected graph is a tree

Question 16

binary trees

Answer 16

a tree data structure in which each node has at most 2 children

Question 17

root

Answer 17

node that has no parent nodes

Question 18

leaf

Answer 18

node that has no children

Question 19

perfect binary tree

Answer 19

all nodes have either 0 or 2 children and all leaf nodes are at the same distance from the root

Question 20

degenerate tree

Answer 20

opposite of balanced, each parent node has only one associated child node

Question 21

worst case complexity for searching a tree

Answer 21

O(N)

Question 22

binary search tree

Answer 22

a binary tree whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree

Question 23

quadtrees

Answer 23

each node can have up to four child nodes, allowing both dimensions to be split in half