Quiz 4 Flashcards

1
Q

Path or branch

A

Moving from one node to another in a tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Tree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Binary tree (BST)

A

A tree with nodes that have only two children each.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What level is the root node of a tree?

A

Level 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Leaf

A

Node with no left or right children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Length of a path

A

Number of branches on a path

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Height of a binary tree

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Inorder traversal

A

Visits all the nodes in a tree in ascending order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Preorder traversal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Postorder traversal

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Graphs

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Edge

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Connected graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Non connected graph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Directed graphs

A

When edges have a direction for traversal between edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Non directed graphs

A

When the edges can be traversed in either direction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Weighted graphs s

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

ADT

A

Abstract data type

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Adjacency Matrix

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Adjacency list

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Depth-First searches

A

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.

22
Q

Breadth-first searches

A

Implemented with queues

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

23
Q

Minimum Spanning Trees(MST)

A

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

24
Q

Topological sort

A

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

Can only be done on graphs without cycles

25
Q

Graphs with no cycles?

A

Trees

26
Q

MST and shortest path answer which respective questions?

A

Can we get there from here? (MST)

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

27
Q

Whose is more efficient? W or Floyd?

A

Floyd

28
Q

Standard Template Library (STL)

A

Components:

Containers, iterators and algorithms

29
Q

Container types

A

Sequence (sequential) containers
Associative containers
Container adapters

30
Q

Sequence container

A

Every object in the container had a specific position

Types:
Vector (array)
Deque (double ended queue)
List

31
Q

Vector

A

include

Basic operations:
Item insertion
Item deletion
Stepping thru elements

32
Q

Deque

A

Double ended queue

Need #include

Can expand in either direction

33
Q

List

A

Implemented like doubly linked lists

34
Q

Iterators

A

Points to the elements of a container

++
*

35
Q

Input iterators

A

Have read access;

Step forward element by element

36
Q

Output operators

A

Have write access;

Step forward element by element

37
Q

Forward iterators

A

Have all functionality of input and almost all of output iterators

Can traverse forward or backward

38
Q

Bidirectional iterators

A

Allows you to start and end anywhere

39
Q

Random access iterators

A

Bidirectional iterators that can randomly process the elements of a container

40
Q

Associative Containers

A

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

41
Q

Predefined associative containers

A

Sets - unique
Multi sets - have duplicates
Maps
Multimaps

42
Q

Container adapters

A

Containers to accommodate special situations

3 types:
Stacks
Queues
Priority queues

43
Q

Algorithm classifications

A

Nonmodifying
Modifying
Numeric
Heap

44
Q

Nonmodifying algorithms

A

Do not modify the elements of the container

45
Q

Modifying algorithms

A

Modify the elements of the container

46
Q

Numeric algorithms

A

Perform numeric calculations on elements of a container

47
Q

Heap algorithms

A

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

48
Q

Function object

A

Contains a function that can be treated as such using the operator ()

Class template that overloads the function call operator

49
Q

Predicates

A

Special types of function objects that return Boolean values

Unary or binary

50
Q

Predicate restriction

A

Must always return the same result for the same value.

Functions that modify their internal states cannot be considered predicates