Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Exam Midterms > Discrete Struc 2 > Flashcards

Discrete Struc 2 Flashcards

1
Q

What is the general meaning of a graph?

A

A plot or chart of numerical data using a coordinate system.

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

What is the technical meaning of a graph?

A

A discrete structure used to represent relations with a web-like graphical representation.

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

What are some applications of graphs?

A

Networking scheduling

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

What is a simple graph?

A

A graph that corresponds to symmetric irreflexive binary relations.

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

What is a multigraph?

A

A graph that allows multiple edges between two nodes.

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

What is a pseudograph?

A

A graph that allows self-loops (edges connecting a node to itself).

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

What is a directed graph?

A

A graph where edges have a direction (e.g. one-way streets).

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

What is a directed multigraph?

A

A graph that allows multiple directed edges between two nodes.

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

Give an example of a simple graph.

A

Vertices: States in the southeastern U.S.; Edges: Pairs of states that are adjacent.

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

What do simple graphs represent?

A

Relationships between people such as acquaintanceship and friendship.

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

What is a multigraph?

A

A graph that represents networks with multiple lines such as computer networks.

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

What distinguishes a pseudograph from other graphs?

A

A graph that represents networks with multiple lines

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

What do directed graphs represent?

A

Relationships with direction such as one-way streets.

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

What is a directed multigraph?

A

A graph that represents networks with multiple one-way connections like telephone networks.

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

What is the Handshaking Theorem?

A

The sum of the degrees of all vertices in a graph is twice the number of edges.

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

What is the degree of a vertex?

A

The number of incident edges connected to that vertex.

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

What is the difference between in-degree and out-degree?

A

In-degree is the number of edges going to a vertex while out-degree is the number of edges coming from a vertex.

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

What are adjacent vertices?

A

Vertices that are connected by an edge.

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

What is a simple graph?

A

A graph that has no loops or multiple edges.

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

What is the degree of a vertex in a graph?

A

The sum of in-degree and out-degree.

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

What does the Directed Handshaking Theorem state?

A

The sum of the in-degrees of all vertices equals the sum of the out-degrees which is equal to the number of edges.

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

What are some examples of social network graphs?

A

Acquaintanceship, friendship

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

What types of graphs are used in communication networks?

A

Call graphs and message graphs.

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

What are web graphs and citation graphs examples of?

A

Information networks.

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

What do module dependency graphs represent?

A

Software design applications.

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

What types of graphs are used in transportation networks?

A

Airline routes and road networks.

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

What are round-robin and single-elimination examples of?

A

Tournaments.

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

What is an edge list in graph representation?

A

A list of all edges in the graph.

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

What does an adjacency matrix represent?

A

The presence or absence of edges between vertices.

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

What is an adjacency list?

A

A list of adjacent vertices for each vertex.

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

What is the time complexity for edge queries using an edge list?

A

O(E).

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

What is the time complexity for neighbor queries using an adjacency matrix?

A

O(V).

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

What is the time complexity for edge queries using an adjacency list?

A

O(degree(v)).

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

What are pointers in C++?

A

Variables that store memory addresses of other variables.

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

What is dynamic memory allocation?

A

Requesting memory at runtime using the new operator.

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

How do you deallocate memory in C++?

A

By using the delete operator.

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

How do you declare a pointer to an integer in C++?

A

Using the syntax: typename pointername; e.g. int ptr;

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

What does the address-of operator (&) do?

A

Extracts the address of a variable.

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

What does the dereference operator (*) do?

A

Accesses the value that a pointer variable points to.

40
Q

What is the relationship between the & and * operators?

A

They are inverses of each other; *&x cancels out.

41
Q

How do you modify the value at a pointer’s address?

A

By dereferencing the pointer and assigning a new value

42
Q

What does the new operator do in C++?

A

Allocates memory on the heap.

43
Q

What does ‘int *p = new int;’ do in C++?

A

Allocates memory for a single integer.

44
Q

How do you allocate memory for an array of 10 integers in C++?

A

Use ‘int *arr = new int[10];’.

45
Q

What is one advantage of dynamic memory allocation?

A

Use ‘int *arr = new int[10];’.

46
Q

How do you create a dynamic array in C++?

A

Use ‘int *array = new int[n];’ after getting the size from user input.

47
Q

What operator is used to free memory allocated for a single variable?

A

The ‘delete’ operator.

48
Q

What operator is used to free memory allocated for an array?

A

The ‘delete[]’ operator.

49
Q

How do you declare a dynamic 2D array in C++?; Use ‘int **array = new int *[rows];’.

A

Use ‘int **array = new int *[rows];’.

50
Q

What additional step is needed after declaring a dynamic 2D array?

A

Allocate memory for each row using ‘array[i] = new int[cols];’.

51
Q

How do you access and modify elements in a 2D array in C++?

A

Use nested for loops to iterate through rows and columns e.g.

52
Q

What is the purpose of the delete[] operator in C++?

A

To deallocate memory allocated for an array.

53
Q

What is a permutation?

A

An arrangement of items in a specific order where order matters.

54
Q

How can permutations be calculated using the Fundamental Counting Principle?

A

By multiplying the number of choices for each position.

55
Q

What is the factorial notation for permutations of n items?

A

n! (n factorial).

56
Q

What is the permutation formula for choosing r items from n?

A

nPr = n! / (n - r)!

57
Q

What is a combination?

A

An arrangement of items where order does not matter.

58
Q

How can combinations be calculated using the combination formula?

A

nCr = n! / (r! * (n - r)!) for combinations of n items chosen r at a time.

59
Q

In the example of arranging the letters ABC how many choices are there for the first blank?

A

3 choices.

60
Q

What is the formula for total permutations of n items?

A

n! (n factorial).

61
Q

How many total permutations are there for arranging 3 letters from the set ABC.

A

6 (3!)

62
Q

How many ways can 5 books be arranged on a shelf?

A

120 (5!).

63
Q

How many permutations are there for arranging 3 balls out of 7?

A

210 (7 * 6 * 5).

64
Q

How many combinations are there for selecting 3 essay questions out of 5?

A

10 (5 * 4 * 3 / (3 * 2 * 1)).

65
Q

How many ways can a basketball starting lineup be selected?

A

120 (2 * 10 * 6).

66
Q

What C++ standard library is used to generate permutations?

A

std::vector and std::algorithm.

67
Q

What function is used in C++ to generate the next permutation?

A

std::next_permutation.

68
Q

What is the method to generate combinations in C++?

A

Using a specific combination generator code.

69
Q

What technique is used to generate combinations?

A

Recursion.

70
Q

What is the purpose of backtracking in combination generation?

A

To explore different combinations.

71
Q

How is the current combination stored during generation?

A

In a vector.

72
Q

What are permutations?

A

Arrangements of items in a specific order where order matters.

73
Q

What is the formula for permutations?

A

nPr = n! / (n - r)!

74
Q

What are combinations?

A

Arrangements of items where order does not matter.

75
Q

What is the formula for combinations?

A

nCr = n! / (r! * (n - r)!)

76
Q

How many ways can you arrange the letters ABCD using permutations?

A

12 ways (4P2 = 4! / (4 - 2)!).

77
Q

How many ways can medals be awarded to 12 athletes?

A

1320 ways (12P3 = 12! / (12 - 3)!).

78
Q

How many ways can you fill 5 positions from a club of 24 members?

A

7920 ways (24P5 = 24! / (24 - 5)!).

79
Q

How many ways can you form a committee of 3 from 8 people?

A

56 ways (8C3 = 8! / (3! * (8 - 3)!) ).

80
Q

What is the formula for permutations?

A

nPr = n! / (n - r)! where n is the total number of items and r is the number of items to be arranged.

81
Q

What is the formula for combinations?

A

nCr = n! / (r! * (n - r)!) where n is the total number of items and r is the number of items to be chosen.

82
Q

How many permutations of 2 letters can be formed from ABCD?

A

4P2 = 4! / (4 - 2)! = 12.

83
Q

How many ways to award gold, silver, and bronze medals in an Olympic event with 12 athletes?

A

12P3 = 12! / (12-3)! = 12 * 11
* 10 = 1320

84
Q

How many ways can a committee of 3 members be formed from a group of 8 people?

A

12P3 = 12! / (12-3)! = 12 * 11
* 10 = 1320

85
Q

What does the C++ function generatePermutations do?

A

It generates all permutations of a given vector of integers.

86
Q

What is the purpose of std::sort in the generatePermutations function?

A

It sorts the array to ensure permutations are generated in lexicographical order.

87
Q

What does the do-while loop in the generatePermutations function accomplish?

A

It iterates through all permutations of the array until no more permutations are available.

88
Q

What does the C++ function std::next_permutation do?

A

It generates the next lexicographical permutation of a sequence.

89
Q

What is the key difference between permutations and combinations?

A

In permutations order matters; in combinations

90
Q

What is the formula to calculate permutations?;

A

Use the appropriate formula based on the problem context.

91
Q

How many ways can 5 people be seated in a row of 5 chairs?

A

120 ways (5!).

92
Q

How many different 3-topping pizzas can be ordered from 10 toppings?

A

120 combinations (10 choose 3).

93
Q

How many possible 4-digit combinations are there if digits can be repeated?;

A

10000 combinations (10^4).

94
Q

with repetition allowed?

A

17How many different codes are possible if a code consists of 3 letters followed by 2 digits

95
Q

How many ways can a group of 4 students be chosen from a class of 15?

A

1 365 ways (15 choose 4).

Exam Midterms (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions