Fundamentals of Software Engineering Quiz 5

0.0(0)
Studied by 15 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/57

flashcard set

Earn XP

Description and Tags

58 Terms

1
New cards

Why is a tree considered nonlinear?

They are not stored sequentially, but instead arranged on levels.

2
New cards

What is the height of a tree?

The maximum level of the tree, starting from 0.

3
New cards

For a tree, how do you calculate the maximum number of nodes given N levels?

2^N

4
New cards

For a tree, how do you calculate the minimum number of levels required to hold N nodes?

log2(N)

5
New cards

How many parents can a node of a tree have?

1

6
New cards

How many child nodes can a parent node have for a binary tree?

2

7
New cards

How many child nodes can a parent node have for a ternary tree?

3

8
New cards

How many child nodes can a parent node have for a N-nary tree?

N

9
New cards

What is a full tree?

A tree where every node either has 0 or 2 children.

10
New cards

What is a complete tree?

A tree where every level is filled (2 child nodes) except for the last. The last level may have 0 or 1 node.

11
New cards

What is a degenerate tree?

A tree with one node on each level except for the last. Can be skewed left or right.

12
New cards

What is a perfect tree?

A tree that is filled completely on every level except for the last level. The last level has no single nodes.

13
New cards

What is a balanced tree?

A tree with depth <= 1

14
New cards

What two trees can a perfect tree also be considered?

Complete and Full

15
New cards

What is depth?

The difference in levels along the left and right nodes. |height of the left nodes - height of right nodes|

16
New cards

What are the requirements for a binary search tree?

The left node contains values less than the parent node.

The right node contains values greater than the parent node.

The left and right nodes are binary search trees.

17
New cards

What are the basic operations of a binary search tree?

Size

Length

Insert

Delete

Search

Traverse

18
New cards

What is the order of In-Order Traversal?

Left, Root, Right. If each value is listed in order, it will be from least to greatest.

19
New cards

What is the order of Pre-Order Traversal?

Root, Left, Right

20
New cards

What is the order of Post-Order Traversal?

Left, Right, Root

21
New cards

Will binary search tree traversal ever start with a right node?

No

22
New cards

What are the steps for a binary search tree Search operation?

1.) Compare the target node to the current node starting from the root.

If matched, return target location.

If target < root, move to left subtree.

If target > rootm move to right subtree.


2.) Repeat recursively until matched.


3.) Return NULL if not found.

23
New cards

What are the steps for a binary search tree Insertion operation?

1.) Conduct a Search operation for a leaf node.

2.) The new node is added as a child of the leaf node.

24
New cards

What are the steps for a binary search tree Delete operation?

1.) Conduct a Search operation for the target.

2.)

If the target is a leaf node, deallocate (set to NULL).

If the target has 1 child node, replace the target node with the child node.

If the target has 2 child nodes, replace the target with the in-order successor and delete the original in-order successor,

25
New cards

What are the steps for finding an in-order successor?

1.) Reach a node in a tree

2.)

If right child ≠ NULL, return leftmost child

If the node is the rightmost in the tree, return NULL

3.) Travel up tree and repeat until right child ≠ NULL


26
New cards

What is a heap?

A type of binary tree with 2 more properties: shape and order

27
New cards

What are the operations of a heap?

Insertion, deletions, arrange

28
New cards

What is the insertion operation for a heap?

1.) Add the new node as a leaf node on the leftmost open spot.
2.) Is parent > new node?

3.) Is it the right order? If not, rearrange and loop to step 2.

29
New cards

What is the root node deletion operation for a heap?

1.) Swap with the leaf on the rightmost bottom level
2.) Delete original root.
3.) Child > new root?
4.) Is it the right order? If not, rearrange and loop to step 3

30
New cards

What is the term for the arrange method for a heap?

Heapify

31
New cards

What two kinds of heaps are there?

Minimum and maximum

32
New cards

What type of shape must a heap be?

A complete binary tree

33
New cards

How can heaps be represented as an array?

Set the root to index 0. Parent nodes are each element after.
Left children have an index of (2i + 1) and right children have an index of (2i + 2).

34
New cards

What is the process for a min heapify function?

1.) Is (index of left node) < size and (key of left node) < (key of right node)? Then smallest node = left node.
2.) Is (index of right node) < size and (key of right node) < (key of smallest node)? Then smallest node = right node.
3.) Is the smallest node ≠ current node? Then swap current node with the smallest node and repeat for the smallest node.

35
New cards

What is a graph?

A non-linear data structure consisting of vertices and edges.

36
New cards

What is weight?

The cost associated with an edge.

37
New cards

Can a graph have a negative weight?

No. Not usually.

38
New cards

What is the “weight” for edges of unweighted graphs?

The same weight. Value doesn’t matter.

39
New cards

When is a graph considered connected?

When every vertex has some path between them..

40
New cards

When is a graph considered strongly connected?

When every vertex has a way of reaching every other vertex.

41
New cards

What is a directed graph?

A graph with directions defined for edges.

42
New cards

What is the equation for the maximum number of edges given vertices on a directed graph?

e <= v(v-1)

43
New cards

Given a directed graph with 4 vertices, what is the maximum number of edges the graph can have?

12

44
New cards

What is the equation for the maximum number of edges given vertices on a undirected graph?

e <= v(v-1)/2

45
New cards

Given a undirected graph with 4 vertices, what is the maximum number of edges the graph can have?

6

46
New cards

When is a graph sparse?

When it has too few edges.

47
New cards

When is a graph dense?

When it has too many edges.

48
New cards

What is a path?

A sequence of edges from a vertex to another/

49
New cards

What is the degree for a vertex?

The number of edges touching a vertex.

50
New cards

What is a simple path?

A path with no repeated vertices.

51
New cards

What is a trial path?

A path with no repeated edges.

52
New cards

When are 2 vertices considered neighbors/adjecent?

When they are connected by an edge.

53
New cards

What is the edge list representation of a graph?

A list of the origin and destination vertices side-by-side.

54
New cards

What is an adjacency matrix?

A 2D array of equal length, where the side length is the number of vertices. Edges that exist between the vertex on each axis is 1, and those that don’t are 0.

55
New cards

What is a weighted adjacency matrix?

A 2D array of equal length, where the side length is the number of vertices. Edges that exist between the vertex on each axis is the edge weight, and those that don’t are infinity.

56
New cards

What is an adjacency list?

A 2D list where each level of the list is an origin vertex, and the further across a level of the list correlates to a destination vertex. Edges across a list level BEFORE the final destination vertex are 0, and those that exist are 1.

57
New cards

Should a weighted adjacency matrix be used for dense graphs?

No. It has a time complexity of O(n²)

58
New cards

Where are edge lists commonly used?

Linked-list graphs.