Algoritmos y Estructura de Datos II (1er Parcial)

Bellman-Ford: (Seleccionar respuesta). ........... ............... Es un método que normalmente se utiliza cuando hay aristas con peso negativos. .................

Un árbol en el que cada vértice tiene el mismo grado: ... Se llama regular u homogéneo. ......... ......

En el Análisis de caminos críticos: (2 Opciones correctas). Sólo se tiene en cuenta los tiempos tardíos, ignorando los tiempos tempranos. Sólo se tiene en cuenta los tiempos tempranos, ignorando los tiempos tardíos. Implica trabajar con grafos acíclicos. ............ Cada vértice determina un evento.

En Grafos, DFS significa: Depth First Search. .......... ............ ............

El concepto de dígrafo, está referido a: .......... ....... ......... Grafos dirigidos.

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. ................ ............... ...........

Un camino hamiltoniano en un grafo: ........ Es un camino que ¨visita¨ cada vértice una y sólo una vez. .... .................

Un grafo se puede representar con: .......... Una Lista de Adyacencia o una Matriz de Adyacencia, dependiendo su densidad. ....... Una lista de Adyacencia o un árbol de Adyacencia, dependiendo su densidad.

Para buscar en un árbol binario se deberá usar: Postorden. Preorden, Inorden, postorden indistintamente. Inorden. Preorden.

La forma más simple de implementar un árbol N-ario es: ...................... Utilizar la técnica primer hijo/siguiente hermano. ...... ..........

Si en un grafo existe por los 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.

Las formas de recorrer un árbol binario son: (3 Opciones correctas). Subárbol izquierdo; subárbol derecho; se procesa la raíz. Subárbol derecho; subárbol izquierdo; se procesa la raíz. ........... Se procesa la raíz; subárbol izquierdo; subárbol derecho. Subárbol izquierdo; se procesa la raíz; subárbol derecho.

Cuando nos referimos a recorrer un árbol binario en orden simétrico: Es similar al recorrido en preorden, excepto por el hecho de que cuando se desapila un nodo por segunda vez, se declara ya visitado. ................... Es similar al recorrido en postorden, excepto por el hecho de que cuando se desapila un nodo por segunda vez, se declara ya visitado. .............

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.

¿Cuál de las siguientes afirmaciones permite definir la longitud del camino interno de un árbol binario?. ...... Es Igual a la cantidad de nodos del árbol. Es igual a la suma de las profundidades de sus nodos. .........

Si hablamos de un camino que ¨visita¨ cada vértice una y sólo una vez, estamos hablando de: ............. ............. Un camino hamiltoniano. .............

Un Grafo acíclico: (4 Opcciones correctas). Es simplemente un grafo dirigido y que no contiene ciclos. Sirve para modelar muchas situaciones de la vida real como proyectos. Implica que su longitud, es la longitud (número de arcos) del camino directo más largo. No se puede resolver a través de una ordenación topológica. Implica que para cada vértice v, no hay un camino directo que empiece y termine en v.

El método de recorrido Preorden: (2 Opciones correctas). Es un método para recorrer cualquier tipo de árbol. Es un método para recorrer árboles binarios. Es una implementación de recorrido en profundidad-primero. ...............

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. ......... ......... ...........

William Rowan Hamilton plantea: (4 Opciones correctas). 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 juego que consistía en encontrar un ciclo en las aristas de un grafo de un dodecaedro. El problema de encontrar un ciclo (o camino) en un grafo arbitrario es NP-completo.