Discrete Structure Final Exam Reviewer
Studied by 0 people
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/260
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
|---|
No study sessions yet.
261 Terms
From the word " H O P E ", how many three letter words can be formed with the letters from the given word?
Group of answer choices
24
No Answer
36
12
24
In a Volleyball game, how many teams of 4 can be produced from a pool of 12 volleyball players?
Group of answer choices
No Answer
400
450
495
495
How many different number-plates for bus can be made if each numberplate contains three of the digits(from 0 to 9) and followed by a letter (from A to Z). Take note that repetition of digits is allowed.
Group of answer choices
No Answer
30,000
2,600
26,000
26,000
The school held a programming contest and there are ten CS students who will participate in that contest and from that contest they will choose the top three who will get a prize. Determine the possible ways in order to get the prize from the said contest?
Group of answer choices
400
700
720
No Answer
720
In Binomial Coefficients, The value (a + b)2 = a2 + 2ab + b2 .
Group of answer choices
Valid
Invalid
Valid
From the letters of the word "SEVENTY", How many different ways can you arrange them?
Group of answer choices
2520
2000
No Answer
2500
2520
In Binomial Coefficients, the value (a + b)4 the final value will be: a4 + 4a3b + 6a2b2 + 4ab3 + b4
Group of answer choices
Valid
Invalid
Valid
In the new organization they need to form a committee for the upcoming event, out of 5 CS students and 7 IT students, a committee consisting of 2 CS students and 3 IT students is to be formed. In how many ways can this be done if any CS students and any IT students can be included?
Group of answer choices
150
350
No Answer
300
350
Inside the grocery, how many ways can a supervisor display 6 brands of milk in 4 spaces on a shelf?
Group of answer choices
360
330
300
No Answer
360
How many different sets of 4 digits can be selected from the numeric values from (0 to 9)?
Group of answer choices
No Answer
120
240
200
No Answer
Mrs. Villanueva went to the bank and open a new account and she need to choose 4digit PIN number for their security password in the office and each digit can be chosen from the number range (0 to 4). How many possible PIN numbers can be chosen if repetition is allowed?
Group of answer choices
No Answer
625
652
600
625
By counting, how many four-digit numbers can be made from the digits 1 to 5 if repetition is allowed?
Group of answer choices
625
565
No Answer
645
625
There are 80 students inside the campus in which 25 of them take CS101 subject only, 20 take CS102 only. Find the number of students who take up subjects both CS101 and CS102.
Group of answer choices
15
35
45
No Answer
35
The company will award a 32 inches size SMART TV either to a full-time employees or part-time employees. How many different choices are there, if there are 265 full-time employee or 75 part-time employees?
Group of answer choices
350
335
340
360
340
How many different license plates are there that contain 3 combinations : two English letters and one numeric value (from 0 to 9)?
Group of answer choices
No Answer
6760
6800
17,576
6760
In the bookshelf, there are three C++ programming books, one Python programming books and four Java programming books. How many ways can we arrange if all the book of the same subjects can stand together?
Group of answer choices
764
847
864
No Answer
864
Find the minimum number of CS students enrolled in CS103- Java Programming course guaranteed at least seven will receive the same grade, if the possible grades are as follows: (A, B, C, D).
Group of answer choices
25
20
28
No Answer
25
Find the number of ways can we seat the group of students if there are only 6 seats available. The 6 students from CS Club want to sit in a row at the Auditorium.
Group of answer choices
620
520
750
No Answer
No Answer
In the cabinet, there are four English101 books, two Math102 books and three CS103 books. How many ways can we arrange if all the book of the same subjects can stand together?
Group of answer choices
No Answer
1700
1728
2000
1728
By counting, how many six-digit numbers can be made from the digits 1 to 4 if repetition is allowed?
Group of answer choices
4096
No Answer
4212
4024
4096
Question with Images
https://docs.google.com/document/d/1uZUoymzuBGwK0XqkjW2bTtoATYmWhl1mc3Q16afCRh0/edit?usp=sharing
A vertex is called simple if it does not contain the same edge more than once.
Group of answer choices
Valid
Invalid
Invalid
There is a simple path between every pair of distinct vertices of a connected undirected graph.
Group of answer choices
Valid
Invalid
Valid
A ____________ G = (V, E) consists of a set V of vertices, a set E of edges, and a function f from E to {(u, v) | u, v ÎV}.
Group of answer choices
Multigraph
Directed Multigraph
Directed Graph
No Answer
Directed Multigraph
The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes ________ to the degree of that vertex.
Group of answer choices
No Answer
thrice
ones
twice
twice
A simple graph is just like a __________ , but with no specified direction of its edges.
Group of answer choices
Undirected Graph
No Answer
Multigraph
Directed Graph
Multigraph
The graph is special, it denotes this path by its vertex sequence x0, x1, ..., xn, since it uniquely determines the path
Group of answer choices
Valid
Invalid
Invalid
Dijkstra's algorithm is an iterative procedure that finds the shortest path between to vertices a and z in a weighted graph.
Group of answer choices
Invalid
Valid
Valid
A directed graph is strongly connected if there is a path from a to b and from b to a whenever a and b are vertices in the graph.
Group of answer choices
Invalid
Valid
Invalid
G = (V, E) consists of a set V of vertices, a set E of edges, and a function f from E to {{u, v} | u, v Î V}.
Group of answer choices
Pseudograph
Multigraph
No Answer
Undirected Graph
Pseudograph
To model multiple connections between vertices, we have to use the multigraph.
Group of answer choices
Invalid
Valid
Valid
A path or circuit is called simple if it does not contain the same edge more than once.
Group of answer choices
Invalid
Valid
Valid
The term directed Edges is part of _____________.
Group of answer choices
No Answer
Multigraph
Simple graph
Special graph
Special graph
A pseudograph G = (V, E) consists of a set V of vertices and a set E of edges that are ordered pairs of elements in V. ... leading to a new type of graph.
Group of answer choices
Invalid
Valid
Invalid
A simple graph is called ________________.
Group of answer choices
Multigraph
No Answer
Undirected Graph
Directed Graph
Undirected Graph
The properties that two isomorphic simple graphs don't need to have the same number of edges.
Group of answer choices
Invalid
Valid
Valid
Two vertices u and v in an undirected graph G are called ________ in G if {u, v} is an edge in G.
Group of answer choices
horizontal
No Answer
parallel
adjacent
adjacent
A directed graph G = (V, E) consists of a set V of vertices, a set E of edges, and a function f from E to {(u, v) | u, v ÎV}.
Group of answer choices
Invalid
Valid
Valid
Another term for multiple edges is called.
Group of answer choices
Parallel
Adjacent
No Answer
Horizontal
Parallel
An undirected graph is called connected if there is a path between every pair of distinct vertices in the graph.
Group of answer choices
Valid
Invalid
Invalid
The directed graph is called connected if there is a path between every pair of distinct vertices in the graph.
Group of answer choices
Valid
Invalid
Invalid
Parallel and multiple edges are the same.
Group of answer choices
Valid
Invalid
Valid
A simple graph G = (V, E) consists of V, a nonempty set of vertices, and E, a set of unordered pairs of distinct elements of V called edges.
Group of answer choices
Valid
Invalid
Valid
A ____________ G = (V, E) consists of a set V of vertices, a set E of edges, and a function f from E to {(u, v) | u, v ÎV}.
Group of answer choices
Directed Graph
Directed Multigraph
Multigraph
No Answer
Directed Graph
The path is a circuit if it begins and ends at the same vertex.
Group of answer choices
Invalid
Valid
Valid
The two graphs that differ in any of these invariants are not isomorphic, but two graphs that match in all of them are not necessarily isomorphic.
Group of answer choices
Invalid
Valid
Valid
An edge e is a ________ if f(e) = {u} (which is a better way to denote {u, u}) for some uÎ
Group of answer choices
vertex
loop
No Answer
edges
loop
To model multiple connections between vertices, we have to use the __________.
Group of answer choices
Directed Graph
Undirected Graph
No Answer
Multigraph
Multigraph
A simple graph G = (V, E) consists of V, a nonempty set of vertices, and E, a set of unordered pairs of distinct elements of V called _______.
a. edges
b. graph
c. vertices
d. none of the above
Group of answer choices
A
B
D
C
A
A simple graph is just like a multigraph, but with no specified direction of its edges.
Group of answer choices
Valid
Invalid
Invalid
The properties that two isomorphic simple graphs must both have the same number of edges.
Group of answer choices
Invalid
Valid
Valid
The properties that two isomorphic simple graphs must only one graph with same number of vertices.
Group of answer choices
Valid
Invalid
Invalid
The properties that two isomorphic simple graphs must have only one degree of vertices.
Group of answer choices
Invalid
Valid
Valid
The edge is a circuit if it begins and ends at the same vertex.
Group of answer choices
Invalid
Valid
Valid
The properties that two isomorphic simple graphs must both have the same degrees of vertices.
Group of answer choices
Valid
Invalid
Valid
Two vertices are adjacent if and only if the bit strings that they represent differ in exactly one bit position.
Group of answer choices
Invalid
Valid
Valid
A multigraph is called ____________.
Group of answer choices
Special Graph
Directed Graph
No Answer
Undirected Graph
No Answer
No ________ are allowed in multigraphs (u ¹ v).
Group of answer choices
loops
edges
No Answer
vertices
loops
Edges in multigraphs are not necessarily define as pairs, but can be of any type.
Group of answer choices
Invalid
Valid
Valid
Two vertices u and v in an __________ graph G are called adjacent or neighbors in G if {u, v} is an edge G.
Group of answer choices
Directed
Undirected
No Answer
Multiple
Undirected
A graph consisting of two vertices which is always connected, because it does not contain any pair of distinct vertices.
Group of answer choices
Valid
Invalid
Invalid
The properties that two isomorphic simple graphs must both have the same number of vertices.
Group of answer choices
Invalid
Valid
Valid
The simple graphs G1 = (V1, E1) and G2 = (V2, E2) are not conisder isomorphic if there is a bijection (an one-to-one and onto function) f from V1 to V2 with the property that a and b are adjacent in G1 if and only if f(a) and f(b) are adjacent in G2, for all a and b in V1.
Group of answer choices
Invalid
Valid
Invalid
To define loops, it need the following graphs such as
Group of answer choices
No Answer
directed and multigraph
Pseudograph and edge
directed and undirected
Pseudograph and edge
The edges e1and e2 are called double edges if f(e1) = f(e2).
Group of answer choices
Valid
Invalid
Invalid
A pseudograph graph is considered as ___________________.
Group of answer choices
No Answer
Undirected Graph
Directed Graph
Multigraph
Undirected Graph
__________ in multigraphs are not necessarily define as pairs, but can be of any type.
Group of answer choices
vertices
loops
edges
No Answer
edges
A vertex of degree 0 is called ________, since it is not adjacent to any vertex.
Group of answer choices
remote
No Answer
isolated
pendant
isolated
The edges e1and e2 are called ________ edges if f(e1) = f(e2).
Group of answer choices
double
triple
multiple
No Answer
multiple
No loops are allowed in multigraphs (u ¹ v).
Group of answer choices
Invalid
Valid
Valid
From the given array for merge sort use the Divide-and-Conquer method : 2,1,4,7,6,3
Group of answer choices
123674
132476
123467
No Answer
123467
The term about the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
Group of answer choices
No Answer
Conquer
Divide
Combine
Conquer
In solving recurrence, the recurrence relation Pn = (1.05)Pn-1is a linear homogeneous recurrence relation of degree one.
Group of answer choices
Invalid
Valid
Valid
The initial conditions give the first term(s) of the sequence, before the recurrence part can take over.
Group of answer choices
Invalid
Valid
Valid
From the given array for merge sort use the Divide-and-Conquer method : from the first strep:Divide the array into two parts: 8,5,6,2,4,3
Group of answer choices
No Answer
856 342
856 234
856 243
856 342
This technique is called _______________. It can use recurrence relations to analyze the complexity of such algorithms.
Group of answer choices
Divide and Conquer
No Answer
Combine
Recurrence
Divide and Conquer
The recurrence relation an = an-5 is a linear homogeneous recurrence relation of degree five.
Group of answer choices
Invalid
Valid
Valid
The recurrence relation an = an-5 is a linear homogeneous recurrence relation of degree four.
Group of answer choices
Valid
Invalid
Invalid
In Divide and Conquer, the algorithm divides a problem (input) of size n into a subproblems, where each subproblem is of size n/b.
Group of answer choices
Invalid
Valid
Valid
Find a recurrence relation and initial conditions for 4,6,8,10 and so on.
a. an=an-1 + 3 c. an=an-1 * 3
b. an=an-21 + 3 d. none of the above
Group of answer choices
B
C
D
A
D
The formula f(n) = f (n/5) + 5n2. The positive value by 5, and note f(1) = 8. Find the value of f(5).
Group of answer choices
135
144
133
No Answer
133
The divide and conquer is an algorithm design paradigm based on one branched recursion.
Group of answer choices
Invalid
Valid
Invalid
In conquer the subproblems by solving them recursively. If they are small enough, do not solve the subproblems as base cases.
Group of answer choices
Valid
Invalid
Invalid
The term about the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
Group of answer choices
Combine
Conquer
Divide
No Answer
Conquer
The _________________in programming breaks a problem into subproblems that are similar to the original problem.
Group of answer choices
Combine
Divide and Conquer
No Answer
Conquer
Divide and Conquer
From the following method below, which method was used in parting the value from the method?
Group of answer choices
Merging
Selecting
Partition
No Answer
Partition
The binary search algorithm recursively divides the input into two halves and eliminates the irrelevant half until only one relevant element remained.
Group of answer choices
Valid
Invalid
Valid
The divide and conquer algorithm allow that two comparisons are needed to perform this reduction.
Group of answer choices
Valid
Invalid
Valid
In divide-and-conquer algorithm it needs the proper balancing steps in solving the algorithm.
Group of answer choices
Valid
Invalid
Valid
The binary search algorithm recursively divides the input into two halves and it will not eliminate the irrelevant half until only one relevant element remained.
Group of answer choices
Valid
Invalid
Invalid
The divide and combine use in programming allows to cut a problem into subproblems that are similar to the original problem.
Group of answer choices
Valid
Invalid
Invalid
The divide and combine use in programming allows to cut a problem into subproblems that are not similar to the original problem.
Group of answer choices
Invalid
Valid
Invalid
Mr. Castillo invest 120,000 from his savings account and 5% per year with interest compounded annually. How much money will be in the account after 4 years?
Group of answer choices
142,000
No Answer
149,000
145,860.75
145,860.75
Mrs. Villanueva has a loan 30,000 in a bank yielding 5% per year with interest compounded annually. How much money she will pay for her loan after 5 years?
Group of answer choices
38,288.44
No Answer
38,300.44
38,000.55
38,288.44
The recurrence relation fn = fn-1 + fn-2 is a linear homogeneous recurrence relation of degree two.
Group of answer choices
Invalid
Valid
Valid
From the recurrence relation: a1=4, an=5n+a n-1. What is the value of a 32 is _____.
a.10399 c. 10500
b.10400 d. none of the above
Group of answer choices
B
C
A
D
D
A recurrence relation for the sequence {an} is an equation that expresses an is terms of one or more of the previous terms of the sequence.
Group of answer choices
Invalid
Valid
Valid
Mr. Reyes deposits 20,000 in a savings account at a bank yielding 5% per year with interest compounded annually. How much money will be in the account after 3 years?
Group of answer choices
23,152.50
23,500.70
No Answer
23,150.50
23,152.50
The formula that f satisfies the recurrence relation f(n) = af(n/b) + g(n).
This is called a ______________________recurrence relation.
a. greedy algorithm
b. divide and conquer
c. brute force
d. none of the above
Group of answer choices
D
C
A
B
B
In the algorithm of divide and conquer we don't need to divide the problem and then recombine the solution.
Group of answer choices
Invalid
Valid
Invalid