Quiz 4

Question 1

Path or branch

Answer 1

Moving from one node to another in a tree

Question 2

Tree

Answer 2

Nonlinear data structure used to store data in a hierarchical manner.

Question 3

Binary tree (BST)

Answer 3

A tree with nodes that have only two children each.

Question 4

What level is the root node of a tree?

Answer 4

Level 0

Question 5

Leaf

Answer 5

Node with no left or right children

Question 6

Length of a path

Answer 6

Number of branches on a path

Question 7

Height of a binary tree

Answer 7

Number of nodes on the longest path from the root to a leaf

Question 8

Inorder traversal

Answer 8

Visits all the nodes in a tree in ascending order

Question 9

Preorder traversal

Answer 9

Visits the root node first, then the subtree nodes from left to right

Question 10

Postorder traversal

Answer 10

Visits the subtree nodes left to right first, then the root node

Question 11

Graphs

Answer 11

Similar to trees, except they have vertices in place of nodes

Question 12

Edge

Answer 12

Represents the interaction between vertices and could contain data significant to the vertices

Question 13

Connected graph

Answer 13

When there is at least one path to every vertex in the graph

Question 14

Non connected graph

Answer 14

When there is at least one vertex that cannot be reached via edges

Question 15

Directed graphs

Answer 15

When edges have a direction for traversal between edges

Question 16

Non directed graphs

Answer 16

When the edges can be traversed in either direction

Question 17

Weighted graphs s

Answer 17

When the edges have a value that relates the connection between two vertices

Question 18

ADT

Answer 18

Abstract data type

Question 19

Adjacency Matrix

Answer 19

2D array listing all of the vertices in rows and columns, each intersection indicates if there is an edge between the two vertices

Question 20

Adjacency list

Answer 20

A linked list for each vertex showing the vertices connected to it

Question 21

Depth-First searches

Answer 21

Implemented with stacks.
Attempts to go as far away from the starting point as fast as possible.

If the edges are recording during this search you will get a MST.

Question 22

Breadth-first searches

Answer 22

Implemented with queues

Attempts to stay as close to the starting point as possible (find the shortest path to the vertex as possible)

Question 23

Minimum Spanning Trees(MST)

Answer 23

Navigates to each vertex only once. # of edges in an MST will always equal the number of connected vertices - 1.

Question 24

Topological sort

Answer 24

Maps all the paths that can be traversed constrained by the edge direction.

Can only be done on graphs without cycles

Question 25

Graphs with no cycles?

Answer 25

Trees

Question 26

MST and shortest path answer which respective questions?

Answer 26

Can we get there from here? (MST) What is the shortest way to get there from here? (Shortest path)

Question 27

Whose is more efficient? W or Floyd?

Answer 27

Floyd

Question 28

Standard Template Library (STL)

Answer 28

Components: Containers, iterators and algorithms

Question 29

Container types

Answer 29

Sequence (sequential) containers Associative containers Container adapters

Question 30

Sequence container

Answer 30

Every object in the container had a specific position Types: Vector (array) Deque (double ended queue) List

Question 31

Vector

Answer 31

#include Basic operations: Item insertion Item deletion Stepping thru elements

Question 32

Deque

Answer 32

Double ended queue Need #include Can expand in either direction

Question 33

List

Answer 33

Implemented like doubly linked lists

Question 34

Iterators

Answer 34

Points to the elements of a container ++ *

Question 35

Input iterators

Answer 35

Have read access; | Step forward element by element

Question 36

Output operators

Answer 36

Have write access; | Step forward element by element

Question 37

Forward iterators

Answer 37

Have all functionality of input and almost all of output iterators Can traverse forward or backward

Question 38

Bidirectional iterators

Answer 38

Allows you to start and end anywhere

Question 39

Random access iterators

Answer 39

Bidirectional iterators that can randomly process the elements of a container

Question 40

Associative Containers

Answer 40

Stores elements automatically sorted according to some criteria (Default ascending order)

Question 41

Predefined associative containers

Answer 41

Sets - unique Multi sets - have duplicates Maps Multimaps

Question 42

Container adapters

Answer 42

Containers to accommodate special situations 3 types: Stacks Queues Priority queues

Question 43

Algorithm classifications

Answer 43

Nonmodifying Modifying Numeric Heap

Question 44

Nonmodifying algorithms

Answer 44

Do not modify the elements of the container

Question 45

Modifying algorithms

Answer 45

Modify the elements of the container

Question 46

Numeric algorithms

Answer 46

Perform numeric calculations on elements of a container

Question 47

Heap algorithms

Answer 47

Sorts array data (which is viewed as a binary tree)

Question 48

Function object

Answer 48

Contains a function that can be treated as such using the operator () Class template that overloads the function call operator

Question 49

Predicates

Answer 49

Special types of function objects that return Boolean values Unary or binary

Question 50

Predicate restriction

Answer 50

Must always return the same result for the same value. Functions that modify their internal states cannot be considered predicates