Discrete Struc 2

Question 1

What is the general meaning of a graph?

Answer 1

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

Question 2

What is the technical meaning of a graph?

Answer 2

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

Question 3

What are some applications of graphs?

Answer 3

Networking scheduling

Question 4

What is a simple graph?

Answer 4

A graph that corresponds to symmetric irreflexive binary relations.

Question 5

What is a multigraph?

Answer 5

A graph that allows multiple edges between two nodes.

Question 6

What is a pseudograph?

Answer 6

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

Question 7

What is a directed graph?

Answer 7

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

Question 8

What is a directed multigraph?

Answer 8

A graph that allows multiple directed edges between two nodes.

Question 9

Give an example of a simple graph.

Answer 9

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

Question 10

What do simple graphs represent?

Answer 10

Relationships between people such as acquaintanceship and friendship.

Question 11

What is a multigraph?

Answer 11

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

Question 12

What distinguishes a pseudograph from other graphs?

Answer 12

A graph that represents networks with multiple lines

Question 13

What do directed graphs represent?

Answer 13

Relationships with direction such as one-way streets.

Question 14

What is a directed multigraph?

Answer 14

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

Question 15

What is the Handshaking Theorem?

Answer 15

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

Question 16

What is the degree of a vertex?

Answer 16

The number of incident edges connected to that vertex.

Question 17

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

Answer 17

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

Question 18

What are adjacent vertices?

Answer 18

Vertices that are connected by an edge.

Question 19

What is a simple graph?

Answer 19

A graph that has no loops or multiple edges.

Question 20

What is the degree of a vertex in a graph?

Answer 20

The sum of in-degree and out-degree.

Question 21

What does the Directed Handshaking Theorem state?

Answer 21

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

Question 22

What are some examples of social network graphs?

Answer 22

Acquaintanceship, friendship

Question 23

What types of graphs are used in communication networks?

Answer 23

Call graphs and message graphs.

Question 24

What are web graphs and citation graphs examples of?

Answer 24

Information networks.

Question 25

What do module dependency graphs represent?

Answer 25

Software design applications.

Question 26

What types of graphs are used in transportation networks?

Answer 26

Airline routes and road networks.

Question 27

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

Answer 27

Tournaments.

Question 28

What is an edge list in graph representation?

Answer 28

A list of all edges in the graph.

Question 29

What does an adjacency matrix represent?

Answer 29

The presence or absence of edges between vertices.

Question 30

What is an adjacency list?

Answer 30

A list of adjacent vertices for each vertex.

Question 31

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

Answer 31

O(E).

Question 32

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

Answer 32

O(V).

Question 33

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

Answer 33

O(degree(v)).

Question 34

What are pointers in C++?

Answer 34

Variables that store memory addresses of other variables.

Question 35

What is dynamic memory allocation?

Answer 35

Requesting memory at runtime using the new operator.

Question 36

How do you deallocate memory in C++?

Answer 36

By using the delete operator.

Question 37

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

Answer 37

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

Question 38

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

Answer 38

Extracts the address of a variable.

Question 39

What does the dereference operator (*) do?

Answer 39

Accesses the value that a pointer variable points to.

Question 40

What is the relationship between the & and * operators?

Answer 40

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

Question 41

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

Answer 41

By dereferencing the pointer and assigning a new value

Question 42

What does the new operator do in C++?

Answer 42

Allocates memory on the heap.

Question 43

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

Answer 43

Allocates memory for a single integer.

Question 44

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

Answer 44

Use 'int *arr = new int[10];'.

Question 45

What is one advantage of dynamic memory allocation?

Answer 45

Use 'int *arr = new int[10];'.

Question 46

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

Answer 46

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

Question 47

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

Answer 47

The 'delete' operator.

Question 48

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

Answer 48

The 'delete[]' operator.

Question 49

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

Answer 49

Use 'int **array = new int *[rows];'.

Question 50

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

Answer 50

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

Question 51

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

Answer 51

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

Question 52

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

Answer 52

To deallocate memory allocated for an array.

Question 53

What is a permutation?

Answer 53

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

Question 54

How can permutations be calculated using the Fundamental Counting Principle?

Answer 54

By multiplying the number of choices for each position.

Question 55

What is the factorial notation for permutations of n items?

Answer 55

n! (n factorial).

Question 56

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

Answer 56

nPr = n! / (n - r)!

Question 57

What is a combination?

Answer 57

An arrangement of items where order does not matter.

Question 58

How can combinations be calculated using the combination formula?

Answer 58

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

Question 59

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

Answer 59

3 choices.

Question 60

What is the formula for total permutations of n items?

Answer 60

n! (n factorial).

Question 61

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

Answer 61

6 (3!)

Question 62

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

Answer 62

120 (5!).

Question 63

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

Answer 63

210 (7 * 6 * 5).

Question 64

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

Answer 64

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

Question 65

How many ways can a basketball starting lineup be selected?

Answer 65

120 (2 * 10 * 6).

Question 66

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

Answer 66

std::vector and std::algorithm.

Question 67

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

Answer 67

std::next_permutation.

Question 68

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

Answer 68

Using a specific combination generator code.

Question 69

What technique is used to generate combinations?

Answer 69

Recursion.

Question 70

What is the purpose of backtracking in combination generation?

Answer 70

To explore different combinations.

Question 71

How is the current combination stored during generation?

Answer 71

In a vector.

Question 72

What are permutations?

Answer 72

Arrangements of items in a specific order where order matters.

Question 73

What is the formula for permutations?

Answer 73

nPr = n! / (n - r)!

Question 74

What are combinations?

Answer 74

Arrangements of items where order does not matter.

Question 75

What is the formula for combinations?

Answer 75

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

Question 76

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

Answer 76

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

Question 77

How many ways can medals be awarded to 12 athletes?

Answer 77

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

Question 78

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

Answer 78

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

Question 79

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

Answer 79

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

Question 80

What is the formula for permutations?

Answer 80

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

Question 81

What is the formula for combinations?

Answer 81

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

Question 82

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

Answer 82

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

Question 83

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

Answer 83

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

Question 84

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

Answer 84

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

Question 85

What does the C++ function generatePermutations do?

Answer 85

It generates all permutations of a given vector of integers.

Question 86

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

Answer 86

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

Question 87

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

Answer 87

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

Question 88

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

Answer 88

It generates the next lexicographical permutation of a sequence.

Question 89

What is the key difference between permutations and combinations?

Answer 89

In permutations order matters; in combinations

Question 90

What is the formula to calculate permutations?;

Answer 90

Use the appropriate formula based on the problem context.

Question 91

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

Answer 91

120 ways (5!).

Question 92

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

Answer 92

120 combinations (10 choose 3).

Question 93

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

Answer 93

10000 combinations (10^4).

Question 94

with repetition allowed?

Answer 94

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

Question 95

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

Answer 95

1 365 ways (15 choose 4).