AED II - Primer Parcial - Daypo + Studocu

¿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?. 1. 0. 2.

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

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

En el caso de los grafos ponderados, la forma correcta de obtener la longitud de un camino con pesos, es: Seleccione La respuesta correcta. Contar el número total de nodos que componen el camino. Realizar la suma del costo de las aristas del 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... Grafos que tienen el mismo número de aristas y nodos, pero diferente secuencia de grados. Diferentes representaciones gráficas de un mismo grafo. Grafos conectados que contienen el mismo número de bucles y aristas paralelas.

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 camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. Un árbol es un grafo conexo simple acíclico. 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. Raíz. Grado de salida. Aristas adyacentes. Longitud del grafo.

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: Completo. Conexo. 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 y está representado por los siguientes elementos: Nodos y aristas. Segmentos y sectores. Direcciones y puertos.

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

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

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

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

¿Cuáles de las siguientes corresponde a la definición de dos de las técnicas más comunes para recorrer árboles?. 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. 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. 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.

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

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 dos: Encontrado e Impreso. 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 cuatro: Raíz, Izquierda, Derecha y Procesado.

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

El recorrido por niveles: Se utiliza para encontrar el camino más largo del grafo y requiere que todos los nodos se visiten de forma recursiva. Se implementa utilizando una pila y se utiliza el principio LIFO (Último en Entrar, Primero en Salir). 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.

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

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

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

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

¿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. Insert. DeleteMax. FindMin.

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

Cuando INSERTAMOS en un ARBOL BINARIO un valor menor que el RAIZ, se inserta en: Se coloca directamente como hoja de la raíz. El subárbol izquierdo. 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 trayectoria que visita cada nodo una y solo una vez. La distancia de la raíz a cualquier nodo hijo. Una sucesión de enlaces que conectan dos nodos.

El problema del Camino más Corto, en teoría de grafos: 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 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 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?. Scanner, Math, File. BinaryNode, BinaryTree, AnyType. 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: Todos los nodos que no son hojas deben tener exactamente el mismo número de hijos. El nodo raíz siempre debe ser el elemento más pequeño de todo el árbol. El número de hijos está limitado como mucho a dos.

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. Find. FindMin. Insert. Bubble Sort. Findmax.

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?. Recorrido en Postorden. Rotación simple a izquierda. Rotación simple a derecha.

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 realiza un recorrido en Inorden para garantizar que los nodos estén ordenados. Se INSERTA o ELIMINA un elemento del ARBOL. 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?. Solo cuando la profundidad del subárbol izquierdo de Y excede la profundidad del subárbol derecho de Y en dos o más. 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. 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.

En un árbol AVL ¿Pueden diferir las alturas de los subárboles derecho e izquierdo? ¿Por qué?. No, nunca pueden diferir. Si lo hacen, deja de ser un árbol de búsqueda binaria. Sí, pueden diferir cuanto mucho en un elemento porque es difícil insertar nuevos elementos al mismo tiempo para mantener el equilibrio. 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 Simple a la Derecha. Rotación Doble. 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. "0" entonces el nodo está desequilibrado. "-1" entonces el nodo está equilibrado y su subárbol izquierdo es un nivel más alto. "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. Si el factor de equilibrio es ">=2" o "<=-2" es necesario reequilibrar.

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

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. Detecta si contiene un ciclo de coste total negativo... En una de sus variantes es utilizado por el Protocolo de encaminamiento de información (RIP) de los routers. Es un buen ejemplo para aplicar a grafos con costes negativos. Es un buen ejemplo de un reducción del problema del camino hamiltoniano que es NP-Completo. Sirve para costes negativos ya que no son simplemente una curiosidad matemática.

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. Se ejecuta en tiempo constante O(1) y solo puede usarse si el grafo está representado por una matriz de adyacencia. Nos permite encontrar el Árbol de Expansión Mínima (MST) del grafo en tiempo polinómico. Nos permite con la ordenación topológica, su ejecución en tiempo lineal y funcionará aún en presencia de aristas negativas.

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

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. Implica que su longitud, es la longitud (número de arcos) del camino directo más largo. Implica que para cada vértice v, no hay un camino directo que empiece y termine en v. Sirve para modelar muchas situaciones de la vida real como proyectos. 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. Inserción. Recorrido. 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: Un camino euleriano para el grafo. El orden topologico para el grafo. La lista de adyacencia de la matriz de adyacencia del grafo.

En un grafo: Seleccione 4 (cuatro) respuestas correctas. 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. La ordenación topológica encuentra todos los órdenes topológicos de un grafo acíclico. Por lo general contiene varios órdenes topológicos. 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. Ordenación Topológica. Búsqueda en profundidad (DFS). Búsqueda en anchura.

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

¿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 solo se cumple si las ponderaciones del grafo son negativas. Que D_v es el camino más largo hacia v, y que el camino a w siempre será más corto. 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.

Un árbol con raíz tiene ciertas propiedades. Seleccione 3 (tres) correctas. Todo árbol debe tener la misma cantidad de hijos del lado derecho y del lado izquierdo. 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, denominado padre de c. 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. Uno de los nodos se distingue de los demás por estar designado como raíz.

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. Se utiliza el Algoritmo de Dijkstra para determinar el camino crítico, ya que solo trabaja con ponderaciones positivas. El camino más largo de la red siempre tiene una holgura de tiempo mayor a cero.

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

Según la teoría de Análisis de Caminos Críticos, en un grafo de eventos cada vértice indica: Una actividad real del proyecto que consume tiempo y recursos. El tiempo total que requiere el proyecto para ser completado. La terminación de una actividad y sus actividades dependientes.

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: Bucle. Arista. Camino.

¿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?. Es un grafo conexo acíclico donde existe un único camino simple entre cualquier par de vértices. Estructura jerárquica con una única raíz que no tiene antecesor. Estructura lineal y dinámica de datos.

¿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 se intenta buscar un elemento que no existe dentro de la estructura. Cuando la tabla hash está completamente llena y no se puede insertar un nuevo elemento. Cuando a dos elementos distintos le corresponde la misma dirección.

En un árbol: Todos los hermanos deben tener un factor de balance de ±1 o 0. Todos los hijos de la raíz son hermanos. 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 solo pueden tener pesos positivos. Sus ARISTAS no tienen un sentido dado. 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 la suma de las longitudes de todos los caminos externos (nodos nulos). Calcular el promedio de la altura de cada nodo. Calcular el promedio las profundidades de sus nodos.

¿Que método en java realiza la resolución del sondeo cuadrático?. FindMin. FindPos. 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 tiene un camino que visita cada vértice una sola vez. NO DIRIGIDO y con un único ciclo. DIRIGIDO y sin CICLOS.

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: Un tipo de algoritmo de ordenamiento. Una estructura de datos. 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: Iteración. Altura. 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 árbol tiene al menos 7 nodos. El nivel máximo es igual a 3. Solo se pueden realizar rotaciones simples para reequilibrarlo.

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

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

¿Porqué es posible implementar en los objetos String la técnica de almacenamiento en cache del código hash?. Porque la búsqueda en la Tabla Hash utiliza sondeo lineal. Porque los objetos String son inmutables. 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á: Solo afectado en el momento de la inserción. Ligeramente mejorado. Enormemente afectado.

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 de Prim. Algoritmo BFS. Algoritmo DFS.

¿Cuál es la secuencia de celdas analizadas para una búsqueda sin éxito de un elemento X en un sondeo lineal?. Una secuencia completamente aleatoria dentro de la tabla. La misma secuencia que la de inserción del elemento. 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?. Sondeo Lineal y Encadenamiento. Dijkstra y Kruskal. BFS y DFS.

El algoritmo de Dijkstra determina: La RUTA más corta entre CUALQUIER par de NODOS en el grafo. La RUTA más corta desde un NODO origen hacia los demás NODOS. 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. Se puede implementar sin Operaciones Módulos. Se puede implementar sin multiplicaciones. Elimina el problema de agrupamiento primario que presenta el sondeo lineal. Garantiza que todos los elementos colisionados se encadenarán en la misma lista enlazada. Se basa en el principio FIFO (Primero en Entrar, Primero en Salir) para la inserción.

En un análisis simplista, para estimar el rendimiento del Sondeo Lineal, hacemos 2 suposiciones. Seleccione las 2 (dos) respuestas correctas. Cada Sondeo de la tabla es independiente del sondeo anterior. La Tabla Hash es de gran tamaño. 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. Bajas. Altas. 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: Tabla Hash. Grafo completo. Árbol Nario.

Mientras mayor sea el agrupamiento primario ¿Qué sucede? Seleccione las 4 (cuatro) opciones correctas. Más rápido crece el agrupamiento. Se reduce el rendimiento. Inserciones más costosas. Se produce mayor agrupamiento. 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 número de la función hash y occupied es el número de veces que se realiza una búsqueda sin éxito. CurrentSize es la cantidad de celdas ocupadas por colisiones y occupied es la cantidad de celdas que están vacías. CurrentSize es el tamaño lógico del HashSet y occupied la cantidad total de celdas ocupadas.

¿Qué nos indica el factor de carga de una tabla hash?. La cantidad de veces que se utiliza la función hash. La fracción de la tabla que está llena. 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.?. Size. Remove. Clear.

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

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

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

Durante el sondeo lineal se forman grandes... Seleccione la respuesta correcta. Listas enlazadas. Agrupamientos de celdas. Á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.9. 1.0. 0.5.

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

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: Solo null. Null o un objeto. Un número entero o un valor flotante.

En la rutina add de HashSet ¿Qué sucede si la llamada a findPos consigue encontrar X?. Lanzamos la excepción IndexOutOfBoundsException. Retornamos false. 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 Primario. Agrupamiento Secundario. 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 HashSet. Matriz Hash Entry. Currentsize. Estructuras HashMap. Lista de Adyacencia.

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?. Algoritmo de Prim. Recorrido en anchura (BFS). 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. La Búsqueda Binaria, utilizando el valor de la raíz para determinar si bifurcar a la izquierda o a la derecha. El algoritmo de Dijkstra, ya que permite encontrar el camino más corto. Preorden, Inorden, Postorden indistintamente.

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

Un árbol binario: Un árbol binario es un árbol en el que un nodo puede tener hasta tres subárboles (o hijos). 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 todos los nodos no hoja deben tener exactamente dos hijos.

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

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. Se llama Recorrido por Profundidad y utiliza una cola para registrar los nodos visitados. 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 Inorden (o simétrico) y sigue la secuencia: 1º subárbol izquierdo. 2º se procesa la raíz. 3º subárbol derecho.

BFS significa: Binary File System. Breadth First Search. 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 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 | 3 | 1323 4 | 6173 5 |2364 6 |4489 7 | 8 | 9 |4199. 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 | 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: 7. En la posición: 8. 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: 8. En la posición: 3. En la posición: 5.

Una función que asocia un elemento con un índice pequeño es una función hash. 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 derecho 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 izquierdo de Y.

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

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

El algoritmo de Shannon-Fano: En el que se utiliza una tabla hash para almacenar las frecuencias de los símbolos en O(1). En el que se construye un código sin prefijo basado en un conjunto de símbolos y sus probabilidades. 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 borrado en un árbol BST de un nodo con 2 hijos: No se puede eliminar un nodo con dos hijos, solo las hojas. La única solución es reemplazarlo por el nodo más grande de su subárbol derecho. Tiene 2 posible soluciones.

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. El tiempo de acceso al archivo es similar al tiempo de ordenamiento en memoria y por eso es tan eficaz. Usa un esquema de separación y mezcla. Es ordenamiento basado en archivos. Tiene como técnica reducir el número de acceso a archivos.

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

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

¿Qué sucede si en un bosque de árboles tenemos dos nodos con el mismo peso? Ej.: Se debe seleccionar siempre el nodo que se encuentre más a la izquierda para garantizar el camino más corto. 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 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. La rotación doble solo se aplica en el caso 3. Una rotación simple sirve para tratar los casos 2 y 3. Una rotación simple sirve para tratar los casos 1 y 4.

En un grafo, el número de aristas que inciden en un vértice permite determinar: La longitud del camino más corto que atraviesa ese vértice. El orden del vértice según la cantidad de caminos simples. El grado del vértice dentro del grafo considerado. La cantidad de componentes conexas a las que pertenece el vértice. El nivel del vértice dentro del árbol de expansión mínima.

Un multígrafo o pseudógrafo es aquel grafo que: Admite bucles pero nunca más de una arista entre dos vértices. Admite más de una arista entre un mismo par de vértices. Conecta todos sus pares de vértices con exactamente una sola arista. Solo admite aristas dirigidas y carece por completo de bucles. Puede partirse en dos conjuntos sin aristas dentro del mismo conjunto.

Un ciclo en un grafo se define formalmente como: Un camino cuya longitud coincide con el número de vértices del grafo. Un camino w1,…,wN donde todos sus vértices resultan distintos entre sí. Una secuencia de aristas donde ninguna de ellas se repite en el recorrido. Un camino w1,…,wN en el que w1 y wN son exactamente el mismo vértice. Una sucesión de vértices adyacentes que no repite ninguna arista previa.

En muchos casos prácticos los vértices tienen nombres en lugar de números, lo que dificulta su manejo. La solución habitual consiste en: Transformar los nombres en números mediante una tabla de correspondencia. Ordenar los nombres alfabéticamente y usar su posición en esa lista. Guardar los nombres en una tabla hash sin asignarles ningún índice. Recorrer el grafo con BFS y numerar los vértices según su nivel. Reemplazar cada nombre por la longitud del camino que lo conecta.

Si el grafo que queremos representar es DENSO, la estructura más conveniente para almacenarlo suele ser: Una matriz de adyacencia, porque aprovecha casi todas sus posiciones. Una lista de adyacencia, porque ocupa menos memoria en grafos densos. Un árbol binario de búsqueda, porque ordena las aristas por su peso. Una tabla hash, porque resuelve las colisiones entre vértices vecinos. Una pila, porque permite recorrer todas las aristas en orden inverso.

Una matriz de adyacencia de un grafo es: Una matriz rectangular que relaciona cada vértice con su arista de peso. Una matriz cuadrada que representa la interconexión entre los vértices. Una matriz cuadrada que almacena la longitud de cada camino simple. Una lista que guarda, para cada vértice, sus vértices adyacentes. Una matriz triangular que representa únicamente las aristas dirigidas.

La búsqueda en anchura (Breadth First Search) se caracteriza porque: Procesa los vértices por ramas, siguiendo cada camino hasta el final. Procesa los vértices por niveles, empezando por los más cercanos al origen. Procesa los vértices según el peso creciente de sus aristas de entrada. Procesa los vértices en el orden inverso en que fueron marcados como visitados. Procesa los vértices comparando sus grados de entrada y de salida.

El algoritmo de Floyd-Warshall se diferencia del de Dijkstra principalmente porque: Calcula el número mínimo de aristas entre dos nodos cuando no hay pesos. Calcula la ruta más corta desde un único origen hacia todos los demás. Calcula el árbol de expansión mínima que conecta todos los nodos. Calcula la ruta más corta usando una heurística que acelera la búsqueda. Calcula la ruta más corta entre todos los pares de nodos de la red.

¿Qué algoritmo resuelve el problema de los caminos más cortos entre dos vértices usando una heurística para agilizar la búsqueda?. El algoritmo de Bellman-Ford. El algoritmo de Dijkstra. La búsqueda A* (A estrella). El algoritmo de Floyd-Warshall. El algoritmo de ordenación topológica.

¿Cuál es la ventaja principal de trabajar con un grafo acíclico?. Que asegura que todos sus vértices tengan exactamente el mismo grado. Que permite representar el grafo con una matriz de adyacencia simétrica. Que garantiza un camino euleriano entre todo par de nodos del grafo. Que el problema del camino mínimo resulta más sencillo al no existir ciclos. Que reduce el costo de las aristas a valores siempre positivos y únicos.

Un orden topológico de un grafo dirigido acíclico es una secuencia que: Ubica cada vértice antes de todos aquellos alcanzables desde él. Ubica cada vértice después de todos aquellos alcanzables desde él. Ordena los vértices por el peso de las aristas que los unen entre sí. Ordena los vértices según la cantidad de aristas que inciden sobre cada uno. Recorre todas las aristas del grafo pasando una sola vez por cada una.

Respecto de CPM (Critical Path Method), seleccione las 4 (cuatro) respuestas correctas: Fue desarrollado en 1957 en Estados Unidos por Dupont y Remington Rand. Permite calcular tiempos y plazos dentro de la planificación del proyecto. Se basa en la probabilidad de la duración de cada una de las actividades. Determina la duración total del proyecto al calcular su ruta crítica. Es un método de camino crítico aplicado a la planificación de proyectos.

El método PERT (Program Evaluation and Review Technique) se caracteriza porque: Es un método de camino crítico que supone duraciones fijas y deterministas. Es un método de camino crítico basado en la probabilidad de duración de las actividades. Es un método que calcula la ruta más corta usando ponderaciones negativas. Es un método de ordenamiento topológico aplicado a grafos que tienen ciclos. Es un método de expansión mínima que conecta todos los nodos de la red.

Respecto de un árbol N-ario cualquiera (con N mayor que 2), es correcto afirmar que: No es posible recorrerlo en preorden, inorden o postorden como un árbol binario. Solo puede recorrerse en preorden, ya que carece de subárboles derechos. Puede recorrerse en inorden siempre que todos sus nodos tengan N hijos. Solo admite recorridos por niveles usando una pila como estructura auxiliar. No admite ningún tipo de recorrido porque deja de ser un árbol conexo.

En la definición de árbol genérico, si Z es el padre de W y W es el padre del nodo X, entonces: Z es el nieto de X y W es el abuelo de Z. Z es el abuelo de X y X es el padre de W. Z es el hermano de X y W es el abuelo de Z. Z es el padre de X y W es el abuelo de X. Z es el abuelo de X y W es el padre de X.

En un árbol, una hoja se define como: Un nodo que posee tantos hijos como la altura total del árbol. Un nodo que posee al menos un hijo y nunca puede ser la raíz. Un nodo que posee exactamente dos hijos y carece de hermanos. Un nodo que no posee hijos, pudiendo ser la propia raíz si está sola. Un nodo que posee un único hijo situado siempre a la izquierda.

En teoría de grafos, un árbol es un grafo simple no dirigido G que satisface. Seleccione las 4 (cuatro) respuestas correctas: Dos vértices cualesquiera de G están conectados por al menos dos caminos simples. Si G tiene un número finito n de vértices, entonces tiene n − 1 aristas. G no tiene ciclos y, si se añade alguna arista, se forma un ciclo. Dos vértices cualesquiera de G están conectados por un único camino simple. G es conexo y no contiene ningún ciclo entre sus vértices.

Los árboles, como estructura de datos, se clasifican como: Estructuras no lineales y dinámicas. Estructuras lineales y dinámicas. Estructuras no lineales y estáticas. Estructuras lineales y estáticas. Estructuras jerárquicas y estáticas.

Según la teoría de árboles, la altura de un árbol se define: Por la cantidad total de nodos internos del árbol considerado. Por la cantidad de hojas que posee el árbol considerado. Por la altura de la hoja más cercana a la raíz del árbol. Por la altura de la raíz del árbol considerado. Por el promedio de las profundidades de todos sus nodos.

Teniendo en cuenta el tipo abstracto de datos (TAD) árbol. Seleccione las 4 (cuatro) respuestas correctas: Todo árbol debe contener al menos un ciclo que recorra todos sus nodos. Una lista simplemente enlazada puede considerarse un caso particular de árbol. Un árbol puede ser vacío, es decir, puede no contener ningún nodo. Un camino en un árbol es una secuencia de nodos de distintos niveles conectados. Un árbol es un grafo jerárquico con raíz, padre, hijos y hermanos.

Un árbol regular u homogéneo es aquel en el que: Cada vértice posee un grado que coincide con la altura total del árbol. Cada nivel posee exactamente el mismo número de nodos que el siguiente. Cada nodo interno posee exactamente dos hijos y las hojas igual altura. Cada rama posee exactamente la misma cantidad de aristas que las demás. Cada vértice posee exactamente el mismo grado que los demás.

En un árbol, la profundidad de un nodo se define como: El número de aristas desde dicho nodo hasta la hoja más lejana. El número de nodos desde la raíz del árbol hasta dicho nodo. El número de aristas desde la raíz del árbol hasta dicho nodo. El número de hijos directos que posee el nodo considerado. El número de nodos que comparten el mismo nivel que dicho nodo.

El TDA árbol se puede usar para representar distintas problemáticas reales. Seleccione las 4 (cuatro) respuestas correctas: La estructura genealógica de una familia y sus descendientes. La implementación de un sistema de archivos con directorios y archivos. El cálculo del camino mínimo entre todos los pares de nodos de una red. La jerarquía de decisiones que describe un árbol de decisión. La representación de la sintaxis mediante las derivaciones de una gramática.

Un árbol de decisión es un claro ejemplo de: Un árbol binario de búsqueda, con orden entre sus nodos. Un árbol genérico, sin restricción en el número de hijos. Un árbol AVL, con factor de equilibrio controlado. Un árbol de expansión mínima, con costo total mínimo. Un árbol de Huffman, orientado a la compresión de datos.

Seleccione las 4 (cuatro) afirmaciones válidas sobre árboles binarios: En los árboles equilibrados, las alturas se diferencian como máximo en una unidad. En los árboles perfectamente equilibrados, los pesos de los subárboles difieren a lo sumo en uno. En los árboles equilibrados, las alturas de los subárboles difieren como mínimo en dos unidades. Dos nodos primos poseen un mismo abuelo pero distinto padre dentro del árbol. Los nodos internos poseen como mínimo un hijo dentro de la estructura del árbol.

Dos árboles binarios se denominan similares cuando: Poseen igual altura y la misma cantidad de hojas en cada uno de sus niveles. Poseen exactamente los mismos datos, aunque su estructura sea diferente. Poseen la misma estructura, aunque sus datos no sean necesariamente iguales. Poseen idéntica estructura y además idénticos datos en cada posición. Poseen el mismo recorrido inorden aunque difieran en su estructura.

La longitud del camino interno de un árbol binario: Es la suma de las longitudes de todos los caminos hacia nodos nulos. Es lo que se utiliza para calcular el coste de una búsqueda sin éxito. Es lo que se utiliza para calcular el coste de una búsqueda con éxito. Es la cantidad de nodos internos que posee el árbol considerado. Es el número de aristas del camino más largo desde la raíz a una hoja.

Seleccione 4 (cuatro) tipos válidos de árboles binarios: Árboles binarios equivalentes entre sí. Árboles binarios llenos y balanceados. Árboles binarios de expansión mínima. Árboles binarios similares en forma. Árboles binarios perfectos y completos.

Un árbol binario lleno en el que todas las hojas están a la misma profundidad se denomina: Árbol binario degenerado. Árbol binario completo. Árbol binario equivalente. Árbol binario balanceado. Árbol binario perfecto.

Un árbol binario lleno se caracteriza porque: Todos sus niveles están completos salvo, a lo sumo, el último. Cada uno de sus nodos posee exactamente un hijo, salvo las hojas. Todos sus nodos hoja se encuentran en el mismo nivel del árbol. Ninguno de sus nodos puede tener más de dos subárboles asociados. Cada uno de sus nodos posee cero o exactamente dos hijos.

¿Cómo se define de forma recursiva un árbol?. Como un conjunto de aristas que une todos los pares de nodos. Como una lista de nodos ordenados por su nivel en la jerarquía. Como un grafo conexo con una cantidad impar de aristas y nodos. Como un nodo junto con un conjunto de subárboles hijos. Como una tabla de direcciones que enlaza cada nodo con su padre.

Si necesitamos recorrer un árbol binario de forma iterativa (sin recursión), cada nodo requiere referencias a: Sus dos hijos y su padre, para poder retroceder en el recorrido. Sus dos hijos únicamente, ya que el padre se deduce del recorrido. Su padre únicamente, ya que los hijos se visitan por niveles. Sus hermanos y su abuelo, para reconstruir el camino desde la raíz. Su índice y su altura, para localizarlo dentro del arreglo del árbol.

Para determinar el tamaño (cantidad de nodos) de un árbol binario: Se implementa un método recursivo que cuenta las hojas partiendo de la raíz. Se implementa un método recursivo que cuenta los nodos partiendo de la raíz. Se recorre el árbol por niveles y se cuenta la cantidad de niveles existentes. Se calcula como 2 elevado a la altura del árbol menos una unidad. Se obtiene directamente del atributo altura almacenado en la raíz.

Respecto del método de recorrido preorden. Seleccione las 2 (dos) respuestas correctas: Es un método que procesa cada nodo después de sus dos subárboles. Es una implementación del recorrido en anchura primero. Es un método aplicable únicamente a grafos dirigidos con ciclos. Es un método aplicable para recorrer árboles binarios. Es una implementación del recorrido en profundidad primero.