Test algoritmos y estructura de datos ii - 1°parcial

TEST BORRADO, QUIZÁS LE INTERESE: Algoritmos y estructura de datos II - 1°Parcial - Parte 1

COMENTARIOS	ESTADÍSTICAS	RÉCORDS

REALIZAR TEST

Título del Test:
Algoritmos y estructura de datos II - 1°Parcial - Parte 1

Descripción:
1° parcial algoritmos y estructura de datos II

Autor:
Pepe Pompin
OTROS TESTS DEL AUTOR

Fecha de Creación:
23/08/2023

Categoría: Ciencia

Número Preguntas: 79

COMPARTE EL TEST

COMENTAR

No hay ningún comentario sobre este test.

Temario:

Si hablamos de un camino que "visita" cada vértice una y sólo una vez, estamos hablando de: un camino hamiltoniano. un camino euleriano.
Cuando en un grafo se da el caso de que una arista que sale y llega al mismo nodo, estamos hablando de: Un bucle. Un ciclo.
Un grafo en general está definido por: Seleccione la respuesta correcta. Un conjunto de aristas y un conjunto de vértices. Un conjunto de aristas sin peso y un conjunto de aristas con peso.
En el caso de los grafos ponderados, la forma correcta de obtener la longitud de un camino con pesos, es: Seleccione la respuesta correcta. Realizar la suma del costo de las aristas del camino. Realizar la suma del costo de los nodos y de los vértices del camino.
El caso típico de los puentes de Königsberg: Seleccione 3 (tres)respuestas correctas. Fue resuelto por Euler, en 1735, dando lugar a la Teoría de Grafos y a la Topología. Se refiere a la actualidad Kaliningrado, que es atravesada por el río Pregel, cuyos brazos forman 2 islas. Y estas islas estaban unidas con la ciudad a través de 7 puentes. Consistía en encontrar una ruta a través de la ciudad que cruzara cada puente exactamente una sola vez. Fue resuelto por Warshall, en 1735, dando lugar a la Teoría de Grafos y a la Topología. Se demostró que no era posible. La explicación es la siguiente: si un nodo tiene un número par de líneas que inciden en él, necesariamente ha de ser el primer o último nodo del recorrido.
A veces una arista tiene un tercer componente llamado: Seleccione la respuesta correcta. Coste. Importe.
El concepto de dígrafo, está referido a: Seleccione la respuesta correcta. Grafos dirigidos. Grafos divergentes.
Si en un grafo existe por lo menos un camino que conecta un par de vértices, es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b, diremos que el grafo es: Conexo. Completo.
En un ejemplo de la vida real, podemos modelar mediante un grafo un sistema de aeropuertos. Según este ejemplo, podemos decir que: Cada aeropuerto es un vértice Los vuelos son las aristas.
El Grado de un vértice, se refiere a: Seleccione la respuesta correcta. La cantidad de aristas que conecta. El peso del vértice.
Según la Teoría de Grafos, cambiar la forma de las aristas para mejorar la visualización del grafo es una acción que: No es relevante, porque sólo importa a qué vértices están unidas. Cambiaría el peso del grafo.
En un grafo, el número de caminos que inciden en el vértice permite determinar: Seleccione la respuesta correcta. El Grado del Nodo. El Camino del Grafo.
Un camino en un grafo no dirigido es una secuencia de vértices P=(v1, v2. vn) tal que todo vértice vi es adyacente con el vértice vi+1. Un camino P se dice que es de longitud n si va desde v1 hasta vn. Verdadero Falso.
Un camino euleriano en un grafo: Es un camino que usa cada arista una y sólo una vez. Es un camino que usa cada arista una y sólo una vez pero puede usar más de una vez a un vértice.
Un bucle o lazo: En un grafo o dígrafo es una arista que conecta al vértice consigo mismo. En un grafo o dígrafo son 2 aristas que conectan a 2 vértices entre si.
Un ciclo es: Seleccione la respuesta correcta. Un camino w1,.,wN donde w1 y wN son el mismo vértice. Un camino w1,.,wN donde w1 y wN son vértices distintos y no vecinos. Un camino w1,.,wN donde w1 y wN son vértices distintos pero vecinos.
William Rowan Hamilton plantea: Seleccione las 4(cuatro) respuestas correctas. El problema de encontrar un ciclo (o camino) en un grafo arbitrario es NP-completo. Un juego que consistía en encontrar un ciclo en las aristas de un grafo de un dodecaedro. Un grafo que contiene un ciclo hamiltoniano se dice grafo hamiltoniano. Un ciclo es hamiltoniano si pasa por cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). El famoso problema de los puentes de Königsberg.
Un camino hamiltoniano es un camino que usa cada arista una y sólo una vez. Verdadero Falso.
Un ciclo que usa cada arista una y sólo una vez. Es la definición de: Ciclo Euleriano. Ciclo Hamiltoniano.
Los grafos que aceptan más de una arista entre dos vértices se llaman: Multígrafos. Grafos compuestos.
Un camino hamiltoniano en un grafo: Es un camino que "visita" cada vértice una y sólo una vez. Es un camino que usa cada arista una y sólo una vez. Es un camino que usa cada arista una y sólo una vez pero puede usar más de una vez a un vértice.
Estas son propiedades de un vértice: Seleccione las 3(tres) respuestas correctas. Grado de entrada. Aristas adyacentes. Grado de salida. Ciclo.
Un dígrafo es un: Grafo dirigido. Grafo divergente. Grafo disconexo.
Las definiciones correctas en el contexto de grafos son: Seleccione las 2 (dos) respuestas correctas. Un árbol es un grafo conexo simple acíclico. Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Un camino hamiltoniano en un grafo es un camino que usa cada arista una y sólo una vez. Una arista o arco es una relación matemática que conecta varios vértices.
Un ciclo que visita cada vértice una y sólo una vez. Es la definición de: Ciclo Hamiltoniano. Ciclo Euleriano.
Un multigrafo o pseudografo es: El que acepta más de una arista entre dos vértices. El que acepta mas de un nodo entre dos aristas.
En la mayoría de los casos prácticos los vértices tienen nombre en vez de ser denotados por números, esto representa un problema para su manejo, obligándonos a encontrar una solución. Esta solución consiste en: Transformar los nombres en números. No existe ninguna solución para este tipo de situaciones. Usar una lista de adyacencia.
Si el grafo que queremos representar es DENSO ,la estructura más conveniente que deberíamos usar para representarla es: Una Matriz de Adyacencia. Un Arreglo Unidimensional. Una Pila.
Un grafo se puede representar con: Seleccione la respuesta correcta. Una matriz de adyacencia usando un espacio cuadrático. Un par de vectores adyacentes usando un espacio cuadrático. Un árbol dinámico de adyacencia usando un espacio logarítmico.
Cuando hablamos de grafos dispersos la forma de representación sugerida es: Seleccione la respuesta correcta. Las listas de adyacencias. Las matrices de adyacencias. Los árboles de adyacencias.
Si definimos que en un grafo a lo sumo sólo 1 arista une dos vértices cualesquiera. Entonces decimos que el grafo es: Un grafo simple. Un grafo con distinto número de vértices. Un grafo complementario.
Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Verdarero Falso.
Una Matriz de adyacencia: Es una matriz cuadrada que representa la interconexión de los vértices. Es una matriz rectangular que representa la interconexión de los vértices.
Un grafo se puede representar con: Una Lista de Adyacencia o una Matriz de Adyacencia, dependiendo su densidad. Una tabla hash.
Una Matriz de incidencia: Es una matriz normalmente rectangular que representa la interconexión de los vértices con las aristas. Es una matriz cuadrada que representa la interconexión de los vértices.
El cálculo de la longitud del camino sin pesos en un grafo se obtiene: Por el número de aristas. Por el número de ciclos.
En el problema del camino mínimo sin pesos, el punto de atención: Seleccione la respuesta correcta. Se mueve de vértice a vértice acumulándose las distancias de los vértices adyacentes. Se mueve de vértice a vértice acumulándose las distancias de los vértices no adyacentes.
La búsqueda en anchura (Breadth first search) está referido a: Seleccione la respuesta correcta. Que procesa los vértices por niveles, los vértices más cercanos al origen se calculan primero. Que procesa los vértices por niveles, los vértices más lejanos al origen se calculan primero.
El problema del camino mínimo sin pesos: Seleccione la respuesta correcta. Es un caso especial del problema del camino mínimo con pesos. Es un caso especial del problema de árbol binario de búsqueda. .
En el problema del camino mínimo sin pesos: Seleccione la respuesta correcta. El algoritmo sugerido de recorrido es el Primero en Anchura. El algoritmo sugerido de recorrido es Pre orden.
En la Búsqueda en Profundidad: Seleccione las 4(cuatro) respuestas correctas. Es necesario llevar la cuenta de los nodos visitados (y no visitados). El recorrido no es único: depende del vértice inicial y del orden de visita de los vértices adyacentes. El orden de visita de unos nodos puede interpretarse como un árbol. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking). Intuitivamente, se elige un nodo de comienzo y se exploran todos los vecinos de este nodo.
En la Búsqueda en Anchura: Seleccione las 4(cuatro) respuestas correctas. Intuitivamente, se elige un nodo de comienzo y se exploran todos los vecinos de este nodo. Para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el grafo. El algoritmo no usa ninguna estrategia heurística. Su nombre se debe a que expande uniformemente la frontera entre lo descubierto y lo no descubierto. Consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto.
El Problema del Camino más Corto, en teoría de grafos: Es el problema que consiste en encontrar un camino entre dos vértices de tal manera que la suma de los pesos de las aristas que lo constituyen sea mínima. Es el problema que consiste en encontrar un camino entre el vértice inicial y el vértice final.
El Problema del Camino más Corto, en teoría de grafos: Puede ser definido para grafos no dirigidos, dirigidos o mixtos. Puede ser definido para grafos no dirigidos y dirigidos.
En Grafos, DFS significa: Depth First Search. Dual First Search. Depth Fit Search.
En Grafos, BFS significa: Breadth First Search. Bit First Search. Back First Search.
La principal limitación del algoritmo de Dijkstra: Seleccione la respuesta correcta. El coste negativo de una arista. El costo nulo de una arista.
El algoritmo que resuelve el problema de caminos mínimos no negativos es: Seleccione la respuesta correcta. Dijkstra. Primero en Anchura.
En 1959, el holandés Edsger Dijkstra describió un algoritmo. Seleccione la respuesta correcta. Para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos positivos en cada arista. Para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo sin pesos en cada arista.
El algoritmo de Dijkstra: Seleccione 4 (cuatro)respuestas correctas. Es un algoritmo que resuelve el problema del camino más corto en un grafo Es una especialización de la búsqueda de costo uniforme. Se encuadra en los algoritmos de búsqueda en grafos. Realiza O(n^2) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices. El algoritmo consiste en n+1 iteraciones como máximo. En cada iteración se añade un vértice al conjunto distinguido.
El algoritmo de Floyd-Warshall, descrito en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados que contengan ciclos negativos Falso Verdadero.
En el caso de los grafos ponderados, para obtener la longitud de un camino con pesos se debe: Obtener la suma del costo de las aristas del camino. Contar el número de bucles.
El algoritmo de Dijkstra consiste en: Seleccione la respuesta correcta. Explorar todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices y se detiene. Ir explorando todos los caminos más cortos que llegan al vértice destino y que vienen de todos los demás vértices.
Este es un algoritmo voraz (greedy) que sirve para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos sólo positivos en cada arista: Dijkstra. Floyd-Warshall. Bellman- Ford. Búsqueda A*. Johnson.
Dijkstra: Seleccione la respuesta correcta. Es un algoritmo voraz (greedy) que sirve para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos sólo positivos en cada arista. Es un método que normalmente se utiliza cuando hay aristas con peso negativos.
Floyd-Warshall: Seleccione la respuesta correcta. Es un algoritmo que determina la ruta más corta entre dos nodos cualquiera de la red (lo que significa que calcula la ruta más corta entre todos los pares de nodos). Es un método que normalmente se utiliza cuando hay aristas con peso negativos.
Este algoritmo resuelve el problema de los caminos más cortos entre un par de vértices usando la heurística para intentar agilizar la búsqueda: Búsqueda A*. Bellman - Ford.
Si las aristas del grafo poseen costes negativos, el algoritmo que se debe utilizar es: Seleccione la respuesta correcta. Bellman-Ford. Dijkstra.
En el caso que elegiremos Bellman-Ford en vez de Dijkstra, es: Seleccione la respuesta correcta. Cuando algunas aristas tengan costes negativos. Cuando algunas aristas tengan costes negativos y necesitemos performance. .
El Algoritmo de Bellman-Ford .Seleccione 4(cuatro) respuestas correctas. Es un buen ejemplo para aplicar a grafos con costes negativos. Es un buen ejemplo de una reducción del problema del camino hamiltoniano que es NP-completo. En una de sus variantes es utilizado por el Protocolo de encaminamiento de información (RIP) de los routers. Sirve para costes negativos ya que no son simplemente una curiosidad matemática. Detecta si contiene un ciclo de coste total negativo "ciclos" y asegura encontrar el camino más corto que no repite ningún vértice.
Al algoritmo de Bellman-Ford se debe tener en cuenta para usar porque: Los pesos negativos no son simplemente una curiosidad matemática, surgen de una forma natural en la reducción a problemas de caminos más cortos. Los pesos negativos son solo una curiosidad matemática, pero sirven para estudiar en forma teórica el problema de caminos más cortos.
Bellman - Ford: Seleccione la respuesta correcta. Es un método que normalmente se utiliza cuando hay aristas con peso negativos. Es un algoritmo voraz (greedy) que sirve para la determinación del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos sólo positivos en cada arista. Es un lgoritmo que determina la ruta más corta entre dos nodos cualquiera de la red (lo que significa que calcula la ruta más corta entre todos los pares de nodos).
Este método, normalmente se utiliza cuando hay ciclos con peso negativos: Bellman - Ford. Floyd-Warshall. Búsqueda A*.
La ventaja de tener un grafo acíclico es: Seleccione la respuesta correcta. Que el problema del camino mínimo es más sencillo si el grafo no contiene ciclos. Que el problema del camino mínimo es más complejo, pero resuelve todos los problemas de pesos.
Un grafo acíclico es: Seleccione la respuesta correcta. Aquel que no posee ciclos. Aquel que no posee ciclos ni costes negativos.
El Algoritmo de caminos mínimos: Nos permite con la ordenación topológica, su ejecución en tiempo lineal y funcionará aún en presencia de aristas negativas. Nos permite con la ordenación topológica, su ejecución en tiempo lineal y funcionará en ausencia de aristas negativas.
En un grafo: Seleccione 4(cuatro) respuestas correctas). La ordenación topológica encuentra todos los órdenes topológicos de un grafo acíclico. Por lo general contiene varios órdenes topológicos. Que se le aplica el algoritmo de ordenamiento topológico, podemos afirmar que un grafo contiene ciclos si existen vértices aún no visitados, y ninguno tiene grado 0. El algoritmo de ordenamiento topológico simple se implementa en tiempo lineal, ya que procesa cada vértice sólo una vez. Un algoritmo de ordenación topológica sencillo consiste, tomar de un vértice v que sea destino, imprimirlo y borrar de manera lógica todas sus aristas, y seguir aplicando ésta estrategia con el resto del grafo.
El algoritmo de ordenamiento topológico puede implementarse: En tiempo lineal usando una cola para todos los vértices no procesados de grado de entrada cero. En tiempo lineal usando una tabla hash para todos los vértices no procesados de grado de entrada cero.
Un orden topológico: No podrá existir si el grafo tiene ciclos. Sólo podrá existir si el grafo tiene ciclos.
Si un grafo dirigido posee los vértices V1, V2, V3 y V4. La siguiente enumeración de vértices V1, V3, V4, V2 corresponde a: El orden topológico para del grafo. Un camino cíclico.
Un orden topológico: Ordena los vértices de un grafo dirigido acíclico de tal forma que si hay un camino u a v, entonces v aparece después de u en la ordenación. Ordena los vértices de un grafo dirigido acíclico de tal forma que si hay un camino u a v, entonces u no aparece en la ordenación.
En el Análisis de caminos críticos: Seleccione 2(dos) respuestas correctas. Cada vértice determina un evento. Implica trabajar con grafos acíclicos. Sólo se tienen en cuenta los tiempos tardíos, ignorando los tiempos tempranos. Este camino implica las holguras que se tienen para las posibles desviaciones.
Según la teoría de Análisis de Caminos Críticos, un grafo de actividades se define como: Seleccione la respuesta correcta. Un grafo acíclico en el que cada vértice representa una actividad a ser realizada y las aristas representan relaciones de precedencia entre las actividades. Un grafo acíclico en el que cada vértice representa una actividad a ser realizada y las aristas representan muestras que la actividad debe ser completada para avanzar de un vértice al siguiente.
Uno de los datos más relevantes que podemos calcular en un grafo de eventos es: El tiempo de terminación mínimo de un proyecto dado. El número de nodos del grafo.
Según la teoría de Análisis de Caminos Críticos, en un grafo de eventos cada vértice indica: La terminación de una actividad y sus actividades dependientes Una relación de precedencia entre las actividades.
CPM: Seleccione las 4 (cuatro) respuestas correctas. Es un método para el cálculo de tiempos y plazos en la planificación de proyectos. Es un método de camino crítico. Es un método que al calcular la ruta crítica determina la duración del proyecto entero. Es un método desarrollado en 1957 en USA, por las firmas Dupont y Remington Rand. Es un método que tiene en cuenta los tiempos pesimistas y optimistas.
Teniendo en cuenta la teoría de caminos críticos, el tiempo de espera: Es la cantidad de tiempo que una actividad puede retrasarse sin retrasar la terminación total. Es la cantidad de tiempo que debe esperar antes de realizar las actividades.
Hay grafos que permiten contestar varias preguntas importantes en proyectos, tales como: ¿Cuál es el menor tiempo de terminación del proyecto? ¿Qué actividades se pueden retrasar, y por cuanto tiempo, sin afectar el tiempo mínimo de terminación? Para ello: Debemos transformar el grafo de actividades en un grafo de eventos. Transformar un grafo acíclico en un grafo cíclico.
Program Evaluación and Review Technique o PERT es: Un método de camino crítico que se basa en la probabilidad de la duración de las actividades. Un método de camino crítico determinista en cuanto a la duración de las actividades.

Denunciar Test

▲