Graphs and Trees

Question 1

Connected Graph

Answer 1

a graph in which any node can be reached from any other node (no islands)

Question 2

Complete Graph

Answer 2

Every vertex is connected to every other vertex

Question 3

Cyclic Graph

Answer 3

possible to get from a point of origin and then back to that same point (without taking the same path back)

-note: vertices can be repeated, but edges cannot

Question 4

Acyclic Graph

Answer 4

No cycles

impossible to get from point of origin and then back without retracing your steps

Question 5

Define a balanced tree

Answer 5

No subtrees differ in height by more than one

Question 6

Define a complete tree

Answer 6

All levels of the tree are completely filled in, with the possible exception of the last level

Note: a heap is always a compete tree

Question 7

Most common data structure for implementing a heap

Answer 7

an array

Question 8

Equation for finding a child in a heap array

Answer 8

to find child of a parent node: (index * 2) + 1

Question 9

Describe Heapify

Answer 9

• start with parent of last node in the tree
• swap that parent node with the max value of its two children
• swap all other parent nodes at the same level
• then move up to the level above
• continue this process until you have touched every level of the heap

-efficiency of heapify: O(n log n)

Question 10

Describe Heapsort

Answer 10

-must start with a max heap

• take element from top, move to sorted portion at end of the array
• take smallest element and move to top
• sift down the small element from the top to its proper place
• repeat until finished

-efficiency of Heapsort: O(n log n)