daypo
search.php

ERASED TEST, YOU MAY BE INTERESTED ON graphs - 2

COMMENTS STATISTICS RECORDS
TAKE THE TEST
Title of test:
graphs - 2

Description:
graph theory

Author:
Mark Ganus
Other tests from this author

Creation Date: 28/08/2024

Category: Computers

Number of questions: 20
Share the Test:
New CommentNuevo Comentario
No comments about this test.
Content:
Concerning graph algorithms, relate the left column to the right column. (I) Topological Sorting (Topsort). (II) Minimal Spanning Tree (Prim). (III) Shortest Paths (Dijkstra). (IV) Strongly Connected Components (CFC). (V) Minimal Spanning Tree (Kruskal). (A) Takes as input an oriented graph, basically uses depth-first search and the concept of transposed graph to solve the problem. (B) Takes as input an unoriented graph with weights on the edges, orders the edges by weight and chooses the edges so as not to close cycles to solve the problem. (C) Takes as input an acyclic oriented graph, basically uses depth-first search and vertex labeling to solve the problem. (D) Takes as input an unoriented graph with weights on the edges, basically uses breadth-first search choosing edges with the lowest weight to solve the problem. (E) It takes as input an undirected graph with weights on the edges, and basically uses breadth-first search by choosing accumulated distances with the lowest weight to solve the problem. Select the alternative that contains the correct association. I-A, II-B, III-C, IV-D, V-E. I-C, II-D, III-E, IV-A, V-B. I-C, II-E, III-B, IV-A, V-D. I-D, II-B, III-A, IV-C, V-E. I-D, II-E, III-A, IV-B, V-C.
Let G = (V,E) be a graph in which V is the set of vertices and E is the set of edges. Based on this graph, consider the following statements. I. If G is K3,3 then the chromatic number of G is 3. II. If G is K3,3 then, by removing an edge from G, the graph becomes planar. III. If G is K2,2 then G is both an Eulerian and Hamiltonian graph. IV. If G is a Kn,n then G has a maximum independent set equal to n. Select the correct alternative. a) Only statements I and II are correct. b) Only statements I and IV are correct. c) Only statements III and IV are correct. d) Only statements I, II and III are correct. e) Only statements II, III and IV are correct.
Let G = (V,E) be an undirected connected graph with distinct edge weights and e ∈ E be a fixed edge, where |V| = n is the number of vertices and |E| = m is the number of edges in G, with n ≤ m. Regarding the generation of the minimum cost tree of G, AGMG, select the correct alternative. a) When e has the weight of the edge with the (n − 1)-th smallest weight in G then e is guaranteed to be in a MGMA. b) When e has the weight of the edge with the largest weight in G then e is guaranteed not to be in a MGMA. c) When e has a weight greater than or equal to the edge with the n-th smallest weight in G then e may be in a MGMA. d) When e has a weight different from the weight of any other edge in G then there may be more than one MGMA. e) When e is in a cycle in G and has the weight of the edge with the largest weight in this cycle then e is guaranteed not to be in a MGMA.
Consider the Control Flow Graph to the right, which represents a unit (method or function) of a program.Consider that variable X is defined at vertices 1, 3, 8 and 10; used at vertices 4, 7 and 9; used at edges (6,7) and (6,8). For this variable X, select the alternative that presents, correctly and respectively, the number of test requirements required by the all-definitions and all-uses criteria. a) 3 and 8 b) 3 and 12 c) 4 and 8 d) 4 and 12 e) 4 and 15.
Relate the software testing techniques, in the left column, with their respective criteria, in the right column. (I) Functional. (A) Mutation testing. (II) Structural. (B) MCDC. (III) Defect-based. (C) W-method. (IV) Model-based. (D) Cause-effect graph. Select the alternative that contains the correct association. a) I-B, II-D, III-A, IV-C. b) I-B, II-D, III-C, IV-A. c) I-C, II-B, III-A, IV-D. d) I-D, II-B, III-A, IV-C. e) I-D, II-C, III-B, IV-A.
Consider the following precedence graph, defined for six different transactions that access the same data item. Consider the precedence graph below, defined for six different transactions that access the same data item. Select the alternative that correctly presents the corresponding agenda. a) It is serializable. b) It is not serializable. c) It has no conflicts. d) It does not have an equivalent serial agenda. e) It has an equivalent serial agenda.
BONUS QUESTION - Suppose a three-dimensional scene composed of only two spheres contained in the viewing volume. One of these spheres is completely covered by the other in relation to the view of the virtual camera that uses parallel projection. Based on the statement and the knowledge on the subject, mark the correct alternative. a) Using the Z-Buffer algorithm, the resulting image, after rasterizing both spheres, is the same, regardless of which sphere is rasterized first. b) In the Phong lighting model, the illumination of one of the spheres depends on the color of the second sphere. c) The Gouraud lighting model describes the shadow coming from one of the spheres on the other. d) Hidden surface removal algorithms are not useful in the situation described, since both spheres are inside the viewing volume. e) The covered sphere can be larger than the visible sphere, as long as one is in front, in relation to the view of the camera, and sufficiently distant from each other.
Consider an undirected graph G = (V,E), where V is the set of vertices and E is the set of edges, in which each edge has a weight. G is an instance of the Traveling Salesman Problem (TSP), where each of its vertices is a city and each of its edges corresponds to the connection between these cities. The weight of each edge corresponds to the distance between the two endpoints. The search tree, below, corresponds to the search for the solution performed by an algorithm for the TSP. Knowing that the search for the solution occurred by depth, the nodes of the search tree are analyzed, exploring the leftmost “children” first (vertices with the lowest number). Based on the “pruning” strategy to be used to improve performance and on the analysis of the characteristics of the search tree on the instance G, assign V (true) or F (false) to the following statements. ( ) When finding the first best path, it should be recorded, so as not to analyze paths that have more vertices than this one. ( ) While opening nodes in the search tree, stop following the path when a cycle is worse than the best found so far. ( ) Keep the Hamiltonian cycle with the lowest cost found so far. If, during the search, the path analyzed exceeds this lowest cost, stop trying to follow that path. ( ) Keep the current distance of the path traveled and avoid opening nodes that exceed it. ( ) Do not take paths that are inverse to those that have already been analyzed. Select the alternative that contains, from top to bottom, the correct sequence. V, V, F, V, F. V, F, V, F, V. F, V, F, V, F. F, V, F, F, V. F, F, V, F, V.
Let G be the graph represented by the following figure. Select the alternative that correctly presents the chromatic number associated with graph G. a) 3 b) 4 c) 5 d) 6 e) 7.
Regarding graphs, consider the following representative figures. Select the correct alternative. quick and dirty tip: A connected graph has an Eulerian path if and only if exactly 0 or 2 vertices have an odd degree. a) Only graphs I and II admit an Eulerian path. b) Only graphs I and IV admit an Eulerian path. c) Only graphs III and IV admit an Eulerian path. d) Only graphs I, II and III admit an Eulerian path. e) Only graphs II, III and IV admit an Eulerian path.
BONUS QUESTION: If the initial state is also the final state in a finite automaton, then this automaton a) does not accept the empty string. b) has no other final states. c) is deterministic. d) accepts the empty string. e) is nondeterministic.
Considering that a graph has n vertices and m edges, select the alternative that correctly presents a planar graph. To determine which graph is planar, we can use the formula for planar graphs: m≤3n−6 where n is the number of vertices/NODES and m is the number of edges a) n = 5, m = 10 b) n = 6, m = 15 c) n = 7, m = 21 d) n = 8, m = 12 e) n = 9, m = 22.
Regarding basic blocks, consider the following statements. I. The first instruction can be the target of a conditional branch instruction. II. The flow of execution can start between two instructions in a block. III. The flow of execution can be interrupted in the middle of the block. IV. They are used in the construction of the control flow graph. Select the correct alternative. recall that the flow of execution within a basic block is continuous from the first to the last instruction. The execution cannot start between two instructions in a block; it must start at the beginning of the block. a) Only statements I and II are correct. b) Only statements I and IV are correct. c) Only statements III and IV are correct. d) Only statements I, II and III are correct. e) Only statements II, III and IV are correct.
Consider the graph G=(N , A) to teh right G=(N , A) is Eulerian. G=(N , A) is not connected. H=(~N ,~A) is a subgraph of G=(N , A) , where ~N ={a , c , f , h} and ~A={{a , c}, {c , f }, { f ,h}}. G=(N , A) is not planar.
Let G = (V, E) be a graph in which V is the set of vertices and E is the set of edges. Consider the representation of G as an adjacency matrix. The corresponding directed graph G is: c d e.
Consider the graphs to the right. By analyzing these graphs, it can be seen that (A) G3 and G4 are complete graphs. (B) G1 and G2 are isomorphic graphs. (C) G3 and G1 are bipartite graphs. (D) G2 and G3 are planar graphs. (E) G4 and G1 are multigraphs.
Hundreds of computational problems are expressed in terms of graphs, and the algorithms for solving them are fundamental to computing. The graph search algorithm: hint: The breadth-first search (BFS) algorithm uses a QUEUE The depth-first search (DFS) algorithm uses a stack (A) breadth-first search algorithm uses a stack, while the depth-first search algorithm uses a queue. (B) breadth-first is responsible for defining the initial vertex. (C) depth-first is used to obtain a topological ordering in an acyclic digraph. (D) breadth-first explores edges starting from the most recently visited vertex. (E) depth-first expands the boundary between known and unknown vertices uniformly.
Deadlock occurs when each transaction in a set of two or more transactions is in a waiting state for some data item that is locked by some other transaction in the set. Consider the following scenario: there are two transactions, T1 and T2, where T1 is locking data item X and T2 needs to lock X. A deadlock-handling protocol has the following characteristics: it is a deadlock-avoidance protocol; the decision of which transaction to abort does not consider the timestamp of T1 and T2; if T1 is already in a waiting state at the time T2 needs to lock X, T2 will be aborted, otherwise T2 will enter a waiting state. This protocol is called (A) timeout. (B) graph-based (wait-for). (C) cautious-waiting. (D) wait-or-die. (E) wound-wait.
The code below can be used to traverse a graph. Input: a graph G and a vertex v of G Output: all vertices reachable from v marked function DFS(G,v): mark v for all edges adjacent to v, do if vertex w is not marked, then Recursively call DFS(G,w) end if end for end function Among the various types of algorithms used to traverse graphs, this code implements the algorithm Depth-First Search. Breadth-First Search. Best-First Search. Exhaustive Search.
The following data structure is a tree type, represented by nodes 1 to 10, with node 1 being the root of the tree.If the search algorithm called Breadth-First Search (BFS) is used, the order in which the nodes are searched is: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. 1, 2, 5, 3, 6, 4, 7, 8, 9, 10. 1, 2, 5, 9, 3, 6, 4, 7, 10, 8. 9, 10, 5, 6, 7, 8, 2, 3, 4, 1. 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
Report abuse