Taller de algoritmos y estructura de datos II Primer parcial

¿Cuál de las siguientes afirmaciones define el concepto de árbol correctamente?. Un árbol es una estructura de datos que tiene un nodo llamado raíz. Dónde a cada nodo i, exceptuando la raíz, le llega una arista desde exactamente otro nodo j, al cual se le llama padre de i. Un árbol es una estructura de datos en la que cada nodo tiene exactamente dos nodos "hijo", uno a la izquierda y otro a la derecha, y la búsqueda siempre requiere recorrer todos los nodos. Un árbol es una estructura de datos donde cada nodo está conectado a todos los demás nodos de forma bidireccional, formando al menos un ciclo (o lazo) cerrado.

¿Cuál sería la altura de un árbol vacío?. 0. 1. 2.

Cuando en un grafo se da el caso de que una arista sale y llega al mismo nodo, estamos hablando de: Un bucle. Una arista múltiple. Un camino simple.

El concepto de digrafo, esta referido a: Seleccione la respuesta correcta. Grafos dirigidos. Grafos acíclicos. Grafos ponderados.

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. Contar el número total de nodos que componen el camino. Multiplicar el costo de la arista con mayor peso por el número total de aristas.

Los árboles pueden definirse de dos maneras: de forma recursiva o no recursiva. Verdadero. Falso.

Los árboles son una estructura de datos que representa datos de forma jerárquica. ¿Cuáles son las representación más utilizadas?. Representar cada nodo como una variable en el espacio de memoria o representar el árbol con un arreglo. Representar cada nodo como una función que se ejecuta en la pila. Representar el árbol utilizando la clave principal de una base de datos relacional.

Podemos definir a los grafos Isoformos como... Diferentes representaciones gráficas de un mismo grafo. Grafos que tienen el mismo número de aristas y nodos, pero diferente secuencia de grados. Grafos conectados que contienen el mismo número de bucles y aristas paralelas.

Según la Teoria de Análisis de Caminos Críticos, en un grafo de eventos cada vértice determina. Un evento ya que un grafo de eventos cada vértice determina un evento, el cual indica la terminación de una actividad y sus actividades dependientes. Una actividad ya que un grafo de eventos cada vértice representa el tiempo consumido para completar una tarea. El camino crítico ya que es el que tiene la mayor holgura de tiempo y el vértice representa la duración de esta holgura.

Según la Teoria de Análisis de Caminos Críticos, en un grafo de eventos cara vértice indica. La terminación de una actividad y sus actividades dependientes. Una actividad ya que representa una tarea del proyecto que consume tiempo y recursos. La duración de una tarea crítica o el costo de la misma.

Según la Teoria de Grafos cambiar la forma de las aristas para mejorar la visualizacion del grafo es una acción que... No es relevante, porque sólo importa a qué vértices están unidas. Invalida el grafo, convirtiéndolo en un multigrafo. Afecta directamente la longitud del camino crítico y la conectividad del grafo.

Si definimos que en un grafo a lo sumo sólo 1 arista une dos vértices cualquiera. Entonces decimos que el grafo es... Un grafo simple. Un multigrafo. Un grafo completo.

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 grafo se considera simple si tiene bucles o aristas múltiples que unen los mismos nodos. Un ciclo hamiltoniano es aquel que recorre todas las aristas del grafo una sola vez y regresa al nodo inicial.

Estas son propiedades de un vértice: Seleccione las 3(tres) respuestas correctas. Grado de entrada. Grado de salida. Aristas adyacentes. Longitud del grafo. Raíz.

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. Acíclico.

Teóricamente podemos decir que los grafos son estructuras matemáticas que se utilizan para modelar... Relaciones binarias entre objetos de cierto tipo. Matrices de adyacencia para el almacenamiento de datos secuenciales. Solamente jerarquías y estructuras de tipo padre-hijo.

Un árbol es una estructura fundamental en las ciencias de la computación representado por los siguientes elementos: Nodos y aristas. Tablas y registros. Pilas y colas.

Un árbol es una estructura fundamental en las ciencias de la computación y está representado por los siguientes elementos: Nodos y aristas. Segmentos y sectores. Direcciones y puertos.

Un camino hamiltoniano en un grafo. Es un camino que "visita" cada vértice una y sólo una vez. Es un camino que "visita" cada arista una y solo una vez. Es el camino más corto entre dos vértices cualesquiera del grafo.

Un ciclo que visita cada vértice una y sólo una vez, es la definición de: Ciclo Hamiltoniano. Ciclo Euleriano. Bucle (o Lazo).

Un digrafo es un: Grafo dirigido. Grafo acíclico. Grafo ponderado.

Conocemos como ESTRUCTURA RECURSIVA aquella: Estructura de DATOS en la cual los elementos se definen a sí mismos. Función que se llama a sí misma de manera infinita sin una condición de parada. Estructura de datos lineal donde los elementos se acceden solo desde los extremos.

¿Cuáles de las siguientes corresponde a la definición de dos de las técnicas más comunes para recorrer árboles?. Preorden: el trabajo de un nodo se realiza antes de procesar a sus hijos, utilizando un tiempo constante en cada nodo. Postorden: donde el trabajo de un nodo se realiza después de procesar a sus hijos, también se requiere un tiempo constante por cada nodo. Inorden: Se visita cada nodo dos veces, primero para procesar la subrama izquierda y luego para la subrama derecha. Nivel de Amplitud: Se utilizan funciones recursivas para cada nivel del árbol. Postorden: Se procesa cada nodo desde el más profundo hasta la raíz. Recorrido por Profundidad: Se utiliza un arreglo para almacenar los nodos pendientes de visitar.

¿Cuáles de las siguientes palabras se usan para definir un árbol? Seleccione las 4 (cuatro) respuestas correctas. Arista. Nodo. Raíz. Hoja. Pila.

El algoritmo de recorrido postorden se utiliza una pila para almacenar el estado actual. ¿Por cuántos estados pasa un nodo y cuáles son?. Los estados son tres: A punto de realizar una llamada recursiva al árbol izquierdo. A punto de realizar una llamada recursiva al árbol derecho. A punto de procesar el nodo actual. Los estados son dos: Encontrado e Impreso. Los estados son cuatro: Raíz, Izquierda, Derecha y Procesado.

El problema de la RECURSION es: Generar un ciclo infinito. Reducir drásticamente el espacio de memoria del disco duro. No poder implementar soluciones para estructuras de datos no lineales.

El recorrido por niveles: Se implementa utilizando una cola donde se almacenan los nodos que no han sido visitados. Cuando se visita un nodo se colocan sus hijos al final de la cola. Se implementa utilizando una pila y se utiliza el principio LIFO (Último en Entrar, Primero en Salir). Se utiliza para encontrar el camino más largo del grafo y requiere que todos los nodos se visiten de forma recursiva.

Para implementar un árbol ¿Qué dos enlaces son fundamentales? Seleccione las 2 (dos) respuestas correctas: Al hijo situado más a la izquierda. Hermano situado a la derecha. Al padre situado inmediatamente arriba. A la arista de mayor peso.

¿Qué resuelve el siguiente fragmento de código? public int XYZ (int n){if(n=0) return 1 else return n * XYZ (n1);}. Factorial. Serie de Fibonacci. Máximo Común Divisor (MCD).

¿Qué usos tiene un árbol binario? Selecciona 4(cuatro) respuestas correctas. Colas de prioridad. Árbol de codificación de Huffman. Árbol de expresión. Árbol de búsqueda binaria. Matrices de Adyacencia.

Si una ESTRUCTURA RECURSIVA no tiene la CONDICION DE CORTE puede ocurrir: Un loop infinito. Que la función devuelva un valor nulo. Que la función se convierta en una estructura iterativa.

¿A qué operación de árbol binario de búsqueda hace referencia esta descripción? Comenzamos por la raíz y vamos bifurcando repetidamente a la izquierda hasta que deje de haber un único hijo izquierdo. FindMin. DeleteMax. Insert.

¿Cuál de los siguientes es el código correcto para el método findMax en un subárbol?. Esta imagen es la opción correcta. .............

¿Cuáles son las operaciones que podemos aplicar sobre árboles binarios de búsqueda?. Las operaciones son: find, findMax, findMin, Remove, removeMax, removeMin, insert. Las operaciones son: Rearrange y Sort. Las operaciones son: Merge y Reduce.

Cuando INSERTAMOS en un ARBOL BINARIO un valor menor que el RAIZ, se inserta en: El subárbol izquierdo. Se coloca directamente como hoja de la raíz. El subárbol derecho.

¿Cuándo se produce una excepción en el método de inserción para un árbol binario de búsqueda?. Cuando el nodo que intentamos insertar ya se encuentra en el árbol. Cuando el valor que intentamos insertar es igual al valor de la raíz. Cuando la profundidad del árbol aumenta después de la inserción.

Definimos como CAMINO en una estructura de tipo ARBOL a: Una sucesión de enlaces que conectan dos nodos. La distancia de la raíz a cualquier nodo hijo. Una trayectoria que visita cada nodo una y solo una vez.

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 que visite cada vértice una y solo una vez, asegurando que el costo sea el mínimo. Es el problema que consiste en encontrar un camino que recorra todas las aristas sin repetirlas, maximizando el peso total.

En grafos, DFS significa: Depth First Search. Direct File System. Double Fast Sequence.

En un ARBOL se puede realizar su recorrido por ANCHURA, el cual se realiza: Horizontalmente desde la RAIZ a todos los hijos pasar antes de pasar a la descendencia. Verticalmente desde la RAIZ y hacia abajo por la rama izquierda hasta llegar a una hoja. Desde la hoja hasta la RAIZ, visitando primero el hijo derecho y luego el izquierdo.

¿Qué clases fundamentales se utilizan en Java para representar un árbol binario?. BinaryNode, BinaryTree, AnyType. Scanner, Math, File. LinkedList, ArrayList, Stack.

Según la búsqueda en árboles binarios de búsqueda, si deseamos hacer una búsqueda del elemento mínimo del árbol, la operación que realiza el algoritmos es... Recorrer el árbol yendo siempre a través del subárbol izquierdo, hasta llegar a un nodo que no tenga hijo izquierdo. Recorrer el árbol yendo siempre a través del subárbol derecho, hasta llegar a un nodo que no tenga hijo derecho. Realizar un recorrido en preorden e imprimir el primer elemento encontrado.

Un ÁRBOL BINARIO tiene como característica fundamental que: El número de hijos está limitado como mucho a dos. El nodo raíz siempre debe ser el elemento más pequeño de todo el árbol. Todos los nodos que no son hojas deben tener exactamente el mismo número de hijos.

Un árbol es binario de búsqueda cuando: Cada nodo puede tener un máximo de 2 hijos. La altura del subárbol izquierdo y la del subárbol derecho en cualquier nodo difieren como máximo en uno. Todos los nodos internos tienen exactamente dos hijos, y todas las hojas están en el mismo nivel.

¿Cuál de las siguientes operaciones pueden implementarse en árboles de búsqueda binaria? Seleccione las 4 (cuatro) respuestas correctas. Findmax. Insert. Find. FindMin. Bubble Sort.

De un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), formamos un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i') y como hijo derecho contruimos un nuevo árbol que tendrá como raíz la raiz del árbol (r), el hijo derecho de i (d') será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d). La descripción anterior a que método pertenece?. Rotación simple a derecha. Rotación simple a izquierda. Recorrido en Postorden.

El algoritmo de Floyd-Warshall, descripto en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para enconbar el camino mínimo en grafos dirigidos ponderados que contengan ciclos negativos. VERDADERO. FALSO (sin ciclos negativos).

El BALANCE de un ARBOL se realiza cuando: Se INSERTA o ELIMINA un elemento del ARBOL. Se realiza un recorrido en Inorden para garantizar que los nodos estén ordenados. Se realiza la operación de FindMin para verificar la existencia del elemento más pequeño.

El equilibrio de un árbol AVL se restaura mediante rotaciones si el nodo qué se tiene que re-equilibrar es Y, pueden producirse cuatro casos de pérdida desequilibrio ¿En cuáles se emplean la rotación simple?. Una inserción en el subárbol izquierdo del hijo izquierdo de Y. Una inserción en el subárbol derecho del hijo de derecho de Y. Una inserción en el subárbol derecho del hijo izquierdo de Y. Una inserción en el subárbol izquierdo del hijo derecho de Y. Solo cuando la profundidad del subárbol izquierdo de Y excede la profundidad del subárbol derecho de Y en dos o más.

¿En cuál de los siguientes gráficos se marcan correctamente todos los nodos que están desequilibrados?. Esta es la imagen con la opción correcta. ............

En un árbol AVL ¿Pueden diferir las alturas de los subárboles derecho e izquierdo? ¿Por qué?. Sí, pueden diferir cuanto mucho en un elemento porque es difícil insertar nuevos elementos al mismo tiempo para mantener el equilibrio. No, nunca pueden diferir. Si lo hacen, deja de ser un árbol de búsqueda binaria. Sí, pueden diferir en cualquier cantidad, ya que la altura solo se utiliza para calcular la operación FindMax.

Este es un algoritmo voraz (greedy) que sirve para la determinacion del camino más corto dado un vértice origen al resto de los vértices en un grafo con pesos solo positivos. Dijkstra. Algoritmo de Prim. Algoritmo de Floyd-Warshall.

Pueden ocurrir "desequilibrios en zig-zag", es decir, desequilibrios que no son ni a la derecha ni a la izquierda. ¿Para llegar a un equilibrio qué rotación se debe usar?. Rotación Doble. Rotación Simple a la Derecha. Recorrido en Preorden.

¿Qué significa en un árbol AVL que el factor de equilibrio de un nodo es 0?. Que el nodo está equilibrado y sus subárboles tienen exactamente la misma altura. Que el nodo requiere una rotación doble para corregir un desequilibrio. Que el nodo tiene un hijo a la izquierda y ningún hijo a la derecha.

Si el factor de equilibrio de un nodo en un árbol AVL es: Selecciona 4 (cuatro) respuestas correctas. Si el factor de equilibrio es ">=2" o "<=-2" es necesario reequilibrar. "1" entonces el nodo está equilibrado y su subárbol derecho es un nivel más alto. "0" entonces el nodo está equilibrado y sus subárboles tienen exactamente la misma altura. "-1" entonces el nodo está equilibrado y su subárbol izquierdo es un nivel más alto. "0" entonces el nodo está desequilibrado.

Si queremos ELIMINAR en un ARBOL BINARIO DE BUSQUEDA un NODO que es una HOJA, debemos. Eliminarlo y no necesita hacer otra operación. Reemplazarlo por el nodo más grande de su subárbol derecho. Mover el nodo raíz del subárbol izquierdo a la posición del nodo eliminado.

Un ARBOL BINARIO DE BUSQUEDA BALANCEADO (AVL) tiene como propiedad adicional que: Las ALTURAS de los subárboles izquierdo y derecho pueden diferir en solo una unidad. Todos los nodos internos tienen exactamente el mismo número de aristas que las hojas. La inserción de un elemento se realiza exclusivamente en el subárbol derecho de la raíz.

El algoritmo de Bellman-Ford: Seleccione 4(cuatro) respuestas correctas. Es un buen ejemplo para aplicar a grafos con costes negativos. Sirve para costes negativos ya que no son simplemente una curiosidad matemática. En una de sus variantes es utilizado por el Protocolo de encaminamiento de información (RIP) de los routers. Es un buen ejemplo de un reducción del problema del camino hamiltoniano que es NP-Completo. Detecta si contiene un ciclo de coste total negativo...

El objeto vertex mantiene 4 piezas de información para cada vértice. Identifique cuáles son: Las piezas son: name, adj, dist y prev. Las piezas son: weight, length, color, size. Las piezas son: rows, columns, capacity, pointer.

Este método, normalmente se utiliza cuando hay aristas con peso negativos: Bellman-Ford. Dijkstra. Kruskal.

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 encontrar el Árbol de Expansión Mínima (MST) del grafo en tiempo polinómico. Se ejecuta en tiempo constante $(\mathcal{O}(1))$ y solo puede usarse si el grafo está representado por una matriz de adyacencia.

La ordenación topológica se emplea para ordenar vértice en los grafos cíclicos dirigidos y acíclicos dirigidos. Falso. Verdadero.

Si hablamos de grafos, ¿Cuál de los siguientes se considera un problema tipo?. Problema del camino más corto con ponderaciones positivas. Problema del cálculo de la raíz cuadrada de matrices de adyacencia. Problema de la búsqueda secuencial en listas enlazadas doblemente.

Un grafo Acíclico. Seleccione 4(cuatro) respuestas correctas. Es simplemente un grafo dirigido y que no contiene ciclos. Sirve para modelar muchas situaciones de la vida real como proyectos. Implica que para cada vértice v, no hay un camino directo que empiece y termine en v. Implica que su longitud, es la longitud (número de arcos) del camino directo más largo. Se utiliza para encontrar el Árbol de Expansión Mínima (MST) de un grafo.

¿A qué se refiere esta definición? Se parte de un nodo dado y se visitan los vértices del grafo de manera ordenada y sistemática, pasando de un vértice a otro a través de las aristas del grafo. Recorrido. Inserción. Ponderación.

Si un grafo dirigido posee los vértices V1; V2, V3,V4. La siguiente enumeración de vértices V1,V3,V4,V2 corresponde a: El orden topologico para el grafo. Un camino euleriano para el grafo. La lista de adyacencia de la matriz de adyacencia del grafo.

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

Dada la siguiente secuencia de pasos, ¿Qué algoritmo estamos describiendo? 1. Designamos a v como vértice activo y como raíz del árbol T que se construirá. Se le asigna a v la etiqueta 0. 2. Sea i=0 y S={v}. 3. Hallar el conjunto M de todos los vértices no etiquetados que son adyacentes a algún vértice de S. 4. Si M es vacío el algoritmo termina. En caso contrario, se etiquetan todos los vértices de M con i+1, se añaden a T las aristas entre cada vértice de S y su vecino en M y se hace S=M. 5. i=i+1 y volver al paso 3. Búsqueda en anchura. Búsqueda en profundidad (DFS). Ordenación Topológica.

El algoritmo de Dijkstra es utilizado para resolver qué problema tipo de grafos: Problema del camino más corto con ponderaciones positivas. Problema del camino más corto con ponderaciones negativas. Problema del Árbol de Expansión Mínima (MST).

¿Qué nos demuestra el siguiente teorema fundamental de grafos? Si un camino hasta el vértice v tiene un coste Dv y w es adyacente a v entonces existe un camino a w de coste Dw = Dv + 1. Que si w es adyacente a v y existe un camino hasta v, también hay un camino a w, con coste igual al coste del camino de más 1. Que D_v es el camino más largo hacia v, y que el camino a w siempre será más corto. Que solo se cumple si las ponderaciones del grafo son negativas.

Un árbol con raíz tiene ciertas propiedades. Seleccione 3 (tres) correctas. Uno de los nodos se distingue de los demás por estar designado como raíz. Todo nodo c, excepto la raíz, está conectado mediante exactamente una arista a otro nodo p, denominado padre de c. Existe un camino único que recorre el árbol desde la raíz a cada nodo. El número de aristas que hay que recorrer se denomina longitud del camino. Todo nodo c, excepto la raíz, está conectado mediante exactamente una arista a otro nodo p, el nodo c se denomina padre de p. Todo árbol debe tener la misma cantidad de hijos del lado derecho y del lado izquierdo.

En el Análisis de caminos crítico: Seleccione 2(dos) respuestas correctas: Cada vértice determina un evento. Implica trabajar con grafos acíclicos. El camino más largo de la red siempre tiene una holgura de tiempo mayor a cero. Se utiliza el Algoritmo de Dijkstra para determinar el camino crítico, ya que solo trabaja con ponderaciones positivas.

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. Debemos convertir el grafo a un árbol de expansión mínima (MST) para calcular la longitud del camino más corto. Debemos usar el algoritmo de Búsqueda en Profundidad (DFS) para encontrar todos los caminos posibles y sumarlos.

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. El tiempo total que requiere el proyecto para ser completado. Una actividad real del proyecto que consume tiempo y recursos.

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 el tiempo que transcurre desde el inicio del proyecto hasta que la actividad crítica comienza. Es la duración total de la ruta más larga (el camino crítico).

A la secuencia de vértices en un grafo se la define como: Camino. Arista. Bucle.

¿Cuál algoritmo usaría para conocer el CAMINO MINIMO desde en único punto de origen en un GRAFO CON PESOS POSITIVOS?. Dijkstra. Bellman-Ford. Kruskal.

¿Cuál algoritmo usaría para conocer el CAMINO MINIMO desde un único punto de origen en un GRAFO sin PESOS?. BFS. Dijkstra. Floyd-Warshall.

¿ Cuál de las siguientes afirmaciones no define las propiedades principales de un arbol?. Estructura lineal y dinámica de datos. Estructura jerárquica con una única raíz que no tiene antecesor. Es un grafo conexo acíclico donde existe un único camino simple entre cualquier par de vértices.

¿Cuál de las siguientes operaciones es soportada en tablas hash?. Find. Rotación simple a izquierda. Recorrido en Postorden.

¿Cuándo se produce una colisión?. Cuando a dos elementos distintos le corresponde la misma dirección. Cuando la tabla hash está completamente llena y no se puede insertar un nuevo elemento. Cuando se intenta buscar un elemento que no existe dentro de la estructura.

En un árbol: Todos los hijos de la raíz son hermanos. Todos los hermanos deben tener un factor de balance de ±1 o 0. Todos los nodos del mismo nivel son hermanos.

En un GRAFO decimos que el vértice V es ADYACENTE al vértice W cuando: Existe una ARISTA que los une. Son vértices que pertenecen a diferentes componentes conexas. Ambos vértices tienen el mismo grado de entrada.

Entendemos como GRAFO NO DIRIGIDO al que: Sus ARISTAS no tienen un sentido dado. Sus aristas solo pueden tener pesos positivos. Es un grafo acíclico y conexo que siempre tiene un nodo raíz.

La longitud del camino externo de un árbol. Es lo que se utiliza para calcular el coste de una búsqueda sin exito. Es la cantidad de nodos internos que tiene el árbol. Es el número de aristas del camino más largo desde la raíz a cualquier hoja interna.

Para calcular el costo medio de una búsqueda con éxito dentro de un árbol binario, de debe. Calcular el promedio las profundidades de sus nodos. Calcular el promedio de la altura de cada nodo. Calcular la suma de las longitudes de todos los caminos externos (nodos nulos).

¿Que método en java realiza la resolución del sondeo cuadrático?. FindPos. FindMin. MergeSort.

Según la definición formal, un grafo esta formado por... Un conjunto de vértices V y un conjunto de aristas E. Una matriz de adyacencia y una lista de adyacencia. Un conjunto de funciones y un conjunto de ciclos.

Si tomamos en cuenta un árbol N-ario: Un árbol binario es un caso especial para cuando N=2. Un árbol binario es un caso especial para cuando N=0. Un árbol N-ario debe ser un grafo acíclico y no conexo.

Un GRAFO ACICLICO es aquel es: DIRIGIDO y sin CICLOS. NO DIRIGIDO y con un único ciclo. DIRIGIDO y tiene un camino que visita cada vértice una sola vez.

Un GRAFO es un conjunto de: VERTICES o NODOS unidos por ARISTAS o ARCOS. Pilares de memoria enlazados por direcciones absolutas. Arreglos de datos secuenciales con una función de dispersión.

Una tabla Hash es: Una estructura de datos. Un tipo de algoritmo de ordenamiento. Una función que convierte una clave grande en un número entero pequeño.

Dados los siguientes números: 13, 15, 23, 36, 43, 55 y una tabla con 8 celdas. Si aplicamos la siguiente función hash H(k) = k div tablesize (Sólo tomando la parte entera) ¿Se produce alguna colisión?. Sí, el 15 colisiona con el 13. Sí, el 43 colisiona con el 36. No, no se produce ninguna colisión.

Dados los siguientes números: 15, 28, 36, 43, 55 y una tabla con 8 celdas. Si aplicamos la siguiente función hash H(k) = k div tablesize (Sólo tomando la parte entera) ¿Se produce alguna colisión?. No se producen colisiones. Sí, el 15 y el 28 colisionan. Sí, el 43 y el 55 colisionan.

El atributo de un árbol es: Altura. Iteración. Densidad.

En Java cada objeto String almacena internamente el valor de su hashCode. ¿Cómo se denomina esta técnica?. Almacenamiento en caché del código Hash. Sondeo cuadrático. Referencia débil.

En un árbol de Altura=2. El nivel máximo es igual a 3. El árbol tiene al menos 7 nodos. Solo se pueden realizar rotaciones simples para reequilibrarlo.

La cantidad de hojas en un árbol, es: El peso. La altura del árbol. El grado de un nodo.

La cantidad máxima de aristas en un árbol binario de Altura 2 es: 6. 3. 7.

¿Porqué es posible implementar en los objetos String la técnica de almacenamiento en cache del código hash?. Porque los objetos String son inmutables. Porque la búsqueda en la Tabla Hash utiliza sondeo lineal. Porque los objetos String se eliminan automáticamente de la memoria después de su uso.

¿Qué resuelve el algoritmo de ordenamiento topológico?. Orden de actividades. Camino más corto entre dos vértices con pesos negativos. Árbol de expansión mínima de un grafo conexo.

¿Qué tipos de operación Find podemos encontrar?. Las que tienen éxito y las que no. Las que se realizan solo en la raíz y las que se realizan en las hojas. Las que usan el algoritmo de Dijkstra y las que usan el algoritmo de Kruskal.

Si hay demasiadas colisiones, el rendimiento de la tabla hash se verá: Enormemente afectado. Ligeramente mejorado. Solo afectado en el momento de la inserción.

Un nodo interno es cualquier nodo que posea hijos. Verdadero. Falso.

¿Cuál es el algoritmo que utiliza una COLA como estructura auxiliar?. Algoritmo BFS. Algoritmo DFS. Algoritmo de Dijkstra.

¿Cuál es el algoritmo que utiliza una PILA como estructura auxiliar?. Algoritmo DFS. Algoritmo BFS. Algoritmo de Prim.

¿Cuál es la secuencia de celdas analizadas para una búsqueda sin éxito de un elemento X en un sondeo lineal?. La misma secuencia que la de inserción del elemento. Una secuencia completamente aleatoria dentro de la tabla. La secuencia generada por la función hash h(X) y luego por la lista enlazada del cubo.

¿Cuáles algoritmos de recorridos van a encontrar todos los vértices que se encuentran conectados al vértice origen?. BFS y DFS. Dijkstra y Kruskal. Sondeo Lineal y Encadenamiento.

El algoritmo de Dijkstra determina: La RUTA más corta desde un NODO origen hacia los demás NODOS. La RUTA más corta entre CUALQUIER par de NODOS en el grafo. El conjunto de aristas que conectan todos los NODOS con el COSTO total mínimo.

El número medio de celdas examinadas al buscar un elemento inexistente utilizando un sondeo lineal es aproximadamente: Seleccione la respuesta correcta. (1+1/(1-A)²)/2. (1+1/(1-A))/2. 1+A/2.

El problema del cálculo del camino mínimo en un grafo sin pesos se define como encontrar el camino más corto desde el vértice de origen hasta cualquier otro vértice del grafo. Esto se mide teniendo en cuenta... El número de aristas. La suma del costo de las aristas. El número total de nodos visitados en la ruta.

En el Sondeo Cuadrático: Seleccione las 3 (tres) respuestas correctas. Elimina el problema de agrupamiento primario que presenta el sondeo lineal. Se puede implementar sin multiplicaciones. Se puede implementar sin Operaciones Módulos. Se basa en el principio FIFO (Primero en Entrar, Primero en Salir) para la inserción. Garantiza que todos los elementos colisionados se encadenarán en la misma lista enlazada.

En un análisis simplista, para estimar el rendimiento del Sondeo Lineal, hacemos 2 suposiciones. Seleccione las 2 (dos) respuestas correctas. La Tabla Hash es de gran tamaño. Cada Sondeo de la tabla es independiente del sondeo anterior. Todas las búsquedas son búsquedas con éxito. La función hash es de muy mala calidad y produce colisiones en la primera casilla.

La agrupación primaria es un problema para factores con cargas... Seleccione la respuesta correcta. Altas. Bajas. Negativas.

La forma más simple de implementar un árbol N-ario es: Utilizar la técnica primer hijo/siguiente hermano. Utilizar un arreglo de punteros, donde el tamaño del arreglo es igual al número máximo de nodos en el árbol. Utilizar la propiedad de que N debe ser igual a 2.

La representación de un sistema de archivos de un sistema operativo (E,: FAT, NTFS, ext4, etc), es un claro ejemplo de: Árbol Nario. Grafo completo. Tabla Hash.

Mientras mayor sea el agrupamiento primario ¿Qué sucede? Seleccione las 4 (cuatro) opciones correctas. Se produce mayor agrupamiento. Se reduce el rendimiento. Más rápido crece el agrupamiento. Inserciones más costosas. Aumenta la uniformidad de la función hash.

Para la técnica de encadenamiento separado, el factor de carga es normalmente próximo al valor: "1". "0". "10".

¿Qué diferencia existe entre la variable currentsize y occupied en la clase HastSet?. CurrentSize es el tamaño lógico del HashSet y occupied la cantidad total de celdas ocupadas. CurrentSize es la cantidad de celdas ocupadas por colisiones y occupied es la cantidad de celdas que están vacías. CurrentSize es el número de la función hash y occupied es el número de veces que se realiza una búsqueda sin éxito.

¿Qué nos indica el factor de carga de una tabla hash?. La fracción de la tabla que está llena. La cantidad de veces que se utiliza la función hash. La longitud media de la secuencia de sondeo cuadrático.

¿Qué rutina de la clase HashSet cambia el tamaño de la colección a cero.?. Clear. Remove. Size.

¿Qué tipo de número se aconseja tomar para el tamaño de una tabla Hash con sondeo cuadrático?. Números primos. Números potencias de 2. Números pares mayores a 100.

¿Cuál de los siguientes son rutinas de la estructura HashSet? Seleccione las 4 (cuatro) respuestas correctas. isActive. remove. clear. add. FindMin.

¿Cuándo es necesario hacer rehashing?. Cuando el factor de carga alcance el valor 0,5. Cuando la tabla se llena al 100% de su capacidad. Cuando la función hash no puede calcular la dirección de la clave.

Durante el sondeo lineal se forman grandes... Seleccione la respuesta correcta. Agrupamientos de celdas. Listas enlazadas. Árboles AVL desbalanceados.

El Sondeo cuadrático no ha sido analizado matemáticamente aunque sabemos que elimina el fenómeno del agrupamiento primario. Verdadero. Falso.

En el caso del sondeo cuadrático, el tamaño de la tabla debe ser un número primo y el factor de carga no debe sobrepasar el valor: 0.5. 1.0. 0.9.

En la aplicación del rehashing, ¿Qué podemos afirmar?. Seleccione 4 (cuatro) opciones correctas. Se guarda una referencia a la tabla original. Se crea una nueva tabla hash vacía. Se añaden los elementos activos a la nueva tabla. Se recorre la matriz original. Se eliminan los elementos activos en la nueva tabla.

En la genealogía familiar (representación gráfica de los antepasados y los descendientes de un individuo) es un claro ejemplo de estructura de (TDA) árbol binario. Verdadero. Falso.

En la implementación del sondeo cuadrático en java, la tabla Hash contiene una matriz de referencias HashEntry, cada referencia puede ser: Null o un objeto. Solo null. Un número entero o un valor flotante.

En la rutina add de HashSet ¿Qué sucede si la llamada a findPos consigue encontrar X?. Retornamos false. Lanzamos la excepción IndexOutOfBoundsException. Continuamos con el sondeo lineal para encontrar la siguiente casilla vacía.

¿En qué consiste la técnica del doble Hash?. En aplicar una segunda función de Hash. En resolver las colisiones encadenando dos listas enlazadas. En una técnica para balancear árboles AVL que reduce la complejidad a O(log log N).

La colisión de dos o más elementos en una tabla hash es... Sólo 1 respuesta es correcta. Inevitable. Imposible. Un error de programación.

La técnica de borrado perezoso consiste en: seleccione la respuesta correcta. Marcar los componentes como borrados en lugar de eliminarlo físicamente. Eliminar los elementos de la tabla hash solo cuando la tabla alcanza un factor de carga de 0.5. Mover el nodo raíz del subárbol a la posición del elemento borrado.

La técnica del Doble Hash ¿Qué fenómeno elimina?. Agrupamiento Secundario. Agrupamiento Primario. El desbordamiento de pila.

Para la implementación Java completa de una tabla Hash con sondeo cuadrático, ¿Qué conceptos debemos tener en cuenta? seleccione las 4 (cuatro) respuestas correctas. Estructuras HashMap. Estructuras HashSet. Matriz Hash Entry. Currentsize. Lista de Adyacencia.

Para la técnica de encadenamiento separado, el factor de carga es normalmente próximo al valor: 1. 0.01. 3.

Si queremos calcular el camino mínimo podemos utilizar el ALGORITMO DE DIJKSTRA. Si los pesos de las ARISTAS son de valor 1, ¿qué algoritmo podemos utilizar para el mismo fin?. Recorrido en anchura (BFS). Algoritmo de Prim. Recorrido en profundidad (DFS).

En un árbol binario: Si X es padre de Q y U, Q es padre de S y V, podemos decir que U es es tío de S y V. S es el ancestro de X. Q y U son los descendientes de S y V.

Para buscar en un árbol binario se deberá usar: Seleccione la respuesta correcta. Preorden, Inorden, Postorden indistintamente. El algoritmo de Dijkstra, ya que permite encontrar el camino más corto. La Búsqueda Binaria, utilizando el valor de la raíz para determinar si bifurcar a la izquierda o a la derecha.

¿Qué atributos se definen en la clase Arista?. Destino y costo. Raíz y altura. Factor de carga y sondeo cuadrático.

Un árbol binario: Es un árbol en el que ningún nodo puede tener más de dos subarboles. Un árbol binario es un árbol en el que un nodo puede tener hasta tres subárboles (o hijos). Un árbol binario es un árbol en el que todos los nodos no hoja deben tener exactamente dos hijos.

Para determinar la altura de un árbol binario: Seleccione la respuesta correcta. Se deberá implementar un método recursivo que cuente los niveles y arranque desde la raíz. Se puede determinar con una sola operación al acceder al atributo N del árbol. Se deberá utilizar siempre el algoritmo de Búsqueda en Amplitud (BFS).

El recorrido de un árbol binario cuando hacemos: 1º se procesa la raíz. 2º subárbol izquierdo. 3º subárbol derecho. Se llama: Preorden. Inorden. Postorden.

Cuando nos referimos a recorrer un árbol binario en orden simétrico: Seleccione la respuesta correcta. Es similar al recorrido en postorden, excepto por el hecho de que cuando se desapila un nodo por segunda vez, se declara ya visitado. Se llama Recorrido por Profundidad y utiliza una cola para registrar los nodos visitados. Se llama Inorden (o simétrico) y sigue la secuencia: 1º subárbol izquierdo. 2º se procesa la raíz. 3º subárbol derecho.

BFS significa: Breadth First Search. Binary File System. Basic Feature Set.

La característica principal de la estructura de los árboles al igual que los grafos es que están formados por... Un conjunto de nodos y un conjunto de aristas. Un único nodo raíz y una pila de llamadas. Una función hash y un factor de carga.

Teniendo en cuenta los siguientes números (4371,1323,6173,4199,2364,2589,4489) y una función hash(h) = x mod 10, ¿Cómo quedará la tabla hash usando sondeo cuadrático sabiendo que el resultado de aplicar la función hash es el siguiente:? |Hash(h) = X mod 10 4371 |1 1323 |3 6173 |3 4199 |9 2364 |4 2589 |9 4489 |9. 0 | 2589 1 | 4371 2 | 3 | 1323 4 | 6173 5 | 2364 6 | 7 | 8 | 4489 9 | 4199. 0 | 2589 1 | 4371 2 | 3 | 1323 4 | 6173 5 | 2364 6 | 7 | 8 | 4489 9 | 4199. 0 | 2589 1 | 4371 2 | 4489 3 | 1323 4 | 2364 5 | 6173 6 | 7 | 8 | 9 | 4199.

Teniendo en cuenta los siguientes números (4371,1323,6173,4199,2364,2589,4489) y una función hash(h) = x mod 10, ¿Cómo quedará la tabla hash usando sondeo cuadrático sabiendo que el resultado de aplicar la función hash es el siguiente:?. 0 | 2589 1 | 4371 2 | 3 | 1323 4 | 6173 5 | 2364 6 | 7 | 8 | 4489 9 | 4199. 0 | 2589 1 | 4371 2 | 4489 3 | 1323 4 | 4199 5 | 6173 6 | 7 | 2364 8 | 9 |. 0 | 2589 1 | 4371 2 | 3 | 1323 4 | 6173 5 | 2364 6 | 7 | 8 | 4489 9 | 4199.

Teniendo los siguientes números (4371,1323,6173,4199,2364,2589,4489) y una función hash(h) = x mod 10, ¿Cómo quedará la tabla hash usando sondeo lineal sabiendo que el resultado de aplicar la función hash es el siguiente?: 0 | 2589 1 | 4371 2 | 4489 3 | 1323 4 | 6173 5 | 2364 6 | 7 | 8 | 9 | 4199. 0 | 2589 1 | 4371 2 | 3 | 1323 4 | 6173 5 |2364 6 |4489 7 | 8 | 9 |4199. 0 | 2589 1 | 4371 2 | 3 | 1323 4 | 2364 5 | 6 | 7 | 8 | 9 | 4199.

Teniendo una tabla Hash con 10 celdas y los siguientes valores para la función hash, ¿En qué posición se insertará 19 si usamos un sondeo cuadrático?. En la posición: 8. En la posición: 7. En la posición: 5.

Teniendo una tabla hash con 10 celdas y los siguientes valores para la función hash, ¿En qué posición se insertará 64 si usamos un sondeo lineal?. En la posición: 5. En la posición: 8. En la posición: 3.

Una función que hace referencia a un elemento y un índice pequeño es una función hash [VER ENUNCIADO]. Verdadero. Falso.

¿A cuál de los 4 casos de desequilibrio en un árbol AVL soluciona este pseudocódigo: Una inserción en el subárbol derecho del hijo izquierdo de Y. Una inserción en el subárbol izquierdo del hijo izquierdo de Y. Una inserción en el subárbol derecho del hijo derecho de Y.

¿A qué tipo de recorrido recursivo hace referencia el siguiente código?: Recorrido en orden. Recorrido en Preorden. Recorrido en Postorden.

¿Cómo mide el recorrido el sondeo cuadrático desde el punto de sondeo inicial? [VER ENUNCIADO]. 1,4,9, etc. ........

Considerando el siguiente árbol, podemos decir que el Tamaño del nodo B es: Tres. Dos. Uno.

¿Cuál de los siguientes árboles binarios se puede considerar como árbol de búsqueda y cuál no? ¿Por qué?. El árbol 1 puede ser considerado como árbol binario de búsqueda porque satisface la propiedad de búsqueda ordenada. ...

¿Cuál es la longitud del camino de la ruta más corta entre V3, y V11 en siguiente grafo?. La longitud del camino es 3. La longitud del camino es 4. La longitud del camino es 2.

¿Cuál es la longitud del siguiente árbol?: La longitud del camino es 3. La longitud del camino es 4. La longitud del camino es 2.

¿Cuál es la longitud ponderada del camino de la ruta más corta entre V3, y V11 en siguiente grafo?. La longitud del camino es 50. La longitud del camino es 29. La longitud del camino es 32.

Dado el siguiente grafo: D(s,a ) =9 ; D(s,b ) = 17; D(s,c ) = 7; D(s,d ) = 20;. D(s,a ) =36 ; D(s,b ) = 17; D(s,c ) = 10; D(s,d ) = 20;. D(s,a ) =9 ; D(s,b ) = 17; D(s,c ) = 7; D(s,d ) = 15;.

Dado el siguiente grafo identifique su lista de adyacencia. 0 | 2(3)| 1 | 0(2)| --> |4(5)| 2 | 3(7)| --> |1(4)| 3 | 4(8)| --> |1(1)| 4 | 2(6)|. .....

Dado el siguiente grafo identifique su matriz de adyacencia. Pregunta referida al mismo grafo que tiene forma de una "casita" (esta es la matriz de adyacencia). .........

Dados los siguientes árboles. ¿Cuales son árboles binarios de búsqueda?. B,C. A,C. A,B.

El algoritmo de Shannon-Fano: En el que se construye un código sin prefijo basado en un conjunto de símbolos y sus probabilidades. En el que se utiliza una tabla hash para almacenar las frecuencias de los símbolos en O(1). En el que el símbolo más probable es representado por la secuencia de bits más larga, y el menos probable por la más corta.

El árbol de la siguiente figura no está completo ¿Qué podemos realizar para que lo esté?. Situando G más arriba reemplazando a su padre. Situando A más arriba reemplazando a su padre. Situando F más arriba reemplazando a su padre.

El árbol de la siguiente figura no está completo ¿Qué podemos realizar para que lo esté?(Esta super borrosa, ojala en el parcial no lo este pero por las dudas, si llega a estar como esta imagen, la respuesta correcta es la que les dejo a continuación...). Situando G más arriba reemplazando a su padre. .....

El borrado en un árbol BST de un nodo con 2 hijos: Tiene 2 posible soluciones. La única solución es reemplazarlo por el nodo más grande de su subárbol derecho. No se puede eliminar un nodo con dos hijos, solo las hojas.

El ordenamiento externo: Seleccione 4 (cuatro) respuestas correctas. En un dispositivo secuencial, tal como una cinta, es mucho más lento que uno que permita acceso directo, tal como un disco. Es ordenamiento basado en archivos. Tiene como técnica reducir el número de acceso a archivos. Usa un esquema de separación y mezcla. El tiempo de acceso al archivo es similar al tiempo de ordenamiento en memoria y por eso es tan eficaz.

El siguiente algoritmo resuelve un tipo de problema que surge al intentar encontrar el camino más corto. ¿Cuál de ellos?. Problema del camino más corto no ponderado. Problema del camino más corto con pesos negativos. Problema del Árbol de Expansión Mínima (MST).

¿El siguiente árbol podemos considerarlo como árbol completo?. No es un árbol completo porque no cumple con las condiciones de que todos sus nodos sean hojas ni que cada nodo tenga 2 hijos. Sí, es un árbol completo porque todos los nodos hoja están en el mismo nivel. Sí, es un árbol completo porque el número de nodos es igual a 2^h - 1, donde h es la altura del árbol.

En la siguiente porción de código del algoritmo de Dijkstra una de las líneas es incorrecta. ¿Cuál de ellas?. While(pq.esEmpty() && nodesSeen < vertexMap.size()){. Vertex start = vertexMap.get(startName);. pq.add (new Path(start, 0)); start.dist = 0;.

En un árbol AVL, después de una insercion se aplica una RDI si: Seleccione la respuesta correcta. El FE del nodo actual es -2 y el FE del nodo derecho es >0. El FE del nodo actual es +2 y el FE del nodo izquierdo es <0 (es decir, -1). El FE del nodo actual es -2 y el FE del nodo derecho es -1.

¿Qué sucede si en un bosque de árboles tenemos dos nodos con el mismo peso? Ej.: Si tienen el mismo peso, es indistinto que árbol seleccionar. En el ejemplo en la segunda combinación se puede elegir tanto S como I. Se debe seleccionar siempre el nodo que se encuentre más a la izquierda para garantizar el camino más corto. Se debe desechar un nodo para evitar ciclos en el bosque de árboles.

Si nos detenemos en el nodo E y utilizando el método de primer hijo, siguiente hermano. El nodo E tendrá solo un enlace al nodo H como firstChild. El nodo E tendrá enlaces a los nodos B y D como nextSibling y firstChild respectivamente. El nodo E tendrá enlaces a H como firstChild y a D como nextSibling.

Weiss menciona que hay 4 casos de violación de equilibrio en inserción .1) en subárbol izq. del hijo izq. de X .2) en subárbol der. del hijo izq. de X .3) en subárbol izq. del hijo der. de X. 4) en subárbol der. del hijo der. de X. Una rotación simple sirve para tratar los casos 1 y 4. Una rotación simple sirve para tratar los casos 2 y 3. La rotación doble solo se aplica en el caso 3.