taller de algoritmos 2

¿Cuál de las siguientes afirmaciones define el concepto de árbol correctamente?. o 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. o Un árbol es una estructura de datos que tiene un nodo llamado base. 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.

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

(1.1) Cuando en un grafo se da el caso de que una arista sale y llega al mismo nodo, estamos hablando de: o Un bucle. o Un ciclo.

(1.1) El concepto de digrafo, esta referido a: Seleccione la respuesta correcta. o Grafos dirigidos. o Grafos adaptados.

(1.1) En el caso de los grafos ponderados, la forma correcta de obtener la longitud de un camino con pesos, es: Seleccione La respuesta correcta. o Realizar la suma del costo de las aristas del camino. o Realizar la multiplicacion del costo de las aristas del camino.

● (1.1) Estas son propiedades de un vértice: Seleccione las 3(tres) respuestas correctas. o Grado de entrada. o Grado de salida. o Aristas adyacentes. o Grado de egreso. o Aristas subsecuentes.

(1.1) Las definiciones correctas en el contexto de grafos son: Seleccione las 2 (dos) respuestas correctas. o Un árbol es un grafo conexo simple acíclico. o Un camino eureliano en un grafo es un camino que usa cada arista una y sólo una vez. o Un camino eureliano en un grafo es un camino que usa cada arista la cantidad minima de veces. o Un árbol es un grafo conexo simple cíclico.

(1.1) Los árboles pueden definirse de dos maneras: de forma recursiva o no recursiva. v. f.

(1.1) Los árboles son una estructura de datos que representa datos de forma jerárquica. ¿Cuáles son las representación más utilizadas?. o Representar cada nodo como una variable en el espacio de memoria o representar el árbol con un arreglo. o Representar cada nodo como una constante en el espacio de memoria o representar el árbol con un arreglo.

(1.1) Podemos definir a los grafos Isoformos como... o Diferentes representaciones gráficas de un mismo grafo. o Iguales representaciones gráficas de un mismo grafo.

(1.1) Según la Teoria de Análisis de Caminos Críticos, en un grafo de eventos cada vértice determina. o 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. o Un hito 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.

(1.1) Según la Teoria de Grafos cambiar la forma de las aristas para mejorar la visualizacion del grafo es una acción que... o No es relevante, porque sólo importa a qué vértices están unidas. o Es relevante, porque sólo importa a qué vértices están unidas.

(1.1) Si definimos que en un grafo a lo sumo sólo 1 arista une dos vértices cualquiera. Entonces decimos que el grafo es... o Un grafo simple. o Un grafo complejo.

(1.1) 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: o Conexo. o Concreto.

(1.1) Según la Teoria de Análisis de Caminos Críticos, en un grafo de eventos cara vértice indica. o La terminación de una actividad y sus actividades dependientes. o El inicio de una actividad y sus actividades dependientes.

(1.1) Teóricamente podemos decir que los grafos son estructuras matemáticas que se utilizan para modelar... o Relaciones binarias entre objetos de cierto tipo. o Relaciones paritarias entre objetos de cierto tipo.

(1.1) Un árbol es una estructura fundamental en las ciencias de la computación representado por los siguientes elementos: o Nodos y aristas. o Nodos y artistas.

(1.1) Un árbol es una estructura fundamental en las ciencias de la computación y está representado por los siguientes elementos: o Nodos y aristas. o Nodos y nucleos.

● (1.1) Un camino hamiltoniano en un grafo. o Es un camino que "visita" cada vértice una y sólo una vez. o Es un camino que "visita" cada vértice sólo 2 veces.

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

(1.1) Un digrafo es un: o Grafo dirigido. o Grafo apuntado.

(1.2) Conocemos como ESTRUCTURA RECURSIVA aquella: o Estructura de DATOS en la cual los elementos se definen a sí mismos. o Estructura de DATOS en la cual los elementos se refieren a sí mismos.

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

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

(1.2) 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?. o 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. o Los estados son tres: A punto de realizar una llamada recursiva al árbol derecho. A punto de realizar una llamada recursiva al árbol izquierdo. A punto de procesar el nodo actual.

(1.2) El problema de la RECURSION es: o Generar un ciclo infinito. o Generar un ciclo finito.

(1.2) El recorrido por niveles: o 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. o Se implementa utilizando una cola donde se almacenan los nodos que han sido visitados. Cuando se visita un nodo se colocan sus hijos al final de la cola.

(1.2) Para implementar un árbol ¿Qué dos enlaces son fundamentales? Seleccione las 2 (dos) respuestas correctas: o Al hijo situado más a la izquierda. o Al hijo situado más a la derecha. o Hermano situado a la izquierda. o Hermano situado a la derecha.

(1.2) ¿Qué resuelve el siguiente fragmento de código? public int XYZ (int n){if(n=0) return 1 else return n * XYZ (n-1);}. o Factorial. o Exponencial.

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

(1.2) Si una ESTRUCTURA RECURSIVA no tiene la CONDICION DE CORTE puede ocurrir: o Un loop infinito. o Un loop finito.

(1.3) ¿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. o FindMin. o FindMax.

(1.3) ¿Cuáles son las operaciones que podemos aplicar sobre árboles binarios de búsqueda?. o Las operaciones son: find, findMax, findMin, Remove, removeMax, removeMin, insert. o Las operaciones son: find, findMax, findMin, Remove, removeMax, excert, removeMin, insert. o Las operaciones son: find, findMax, findMin, Remove left, removeMax, removeMin, insert. o Las operaciones son: find node, findMax, findMin, Remove right, removeMax, removeMin, insert.

(1.3) Cuando INSERTAMOS en un ARBOL BINARIO un valor menor que el RAIZ, se inserta en: o El subárbol izquierdo. o El subárbol derecho.

● (1.3) ¿Cuándo se produce una excepción en el método de inserción para un árbol binario de búsqueda?. o Cuando el nodo que intentamos insertar ya se encuentra en el árbol. o Cuando el nodo que intentamos insertar no se encuentra en el árbol.

(1.3) Definimos como CAMINO en una estructura de tipo ARBOL a: o Una sucesión de enlaces que conectan dos nodos. o Una sucesión de enlaces que conectan tres nodos.

(1.3) El problema del Camino más Corto, en teoría de grafos: o 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. o 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 maxima.

(1.3) En grafos, DFS significa: o Depth First Search. o Death First Search.

(1.3) En un ARBOL se puede realizar su recorrido por ANCHURA, el cual se realiza: o Horizontalmente desde la RAIZ a todos los hijos pasar antes de pasar a la descendencia. o Verticalmente desde la RAIZ a todos los hijos pasar antes de pasar a la descendencia.

(1.3) ¿Qué clases fundamentales se utilizan en Java para representar un árbol binario?. o BinaryNode, BinaryTree, AnyType. o Binaryforth, BinaryTree, AnyType.

(1.3) 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... o Recorrer el árbol yendo siempre a través del subárbol izquierdo, hasta llegar a un nodo que no tenga hijo izquierdo. o Recorrer el árbol yendo siempre a través del subárbol derecho, hasta llegar a un nodo que no tenga hijo izquierdo.

(1.3) Un ÁRBOL BINARIO tiene como característica fundamental que: o El número de hijos está limitado como mucho a dos. o El número de hijos está limitado como mucho a tres.

(1.3) Un árbol es binario de búsqueda cuando: o Cada nodo puede tener un máximo de 2 hijos. o Cada nodo puede tener un máximo de 4 hijos.

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

(1.4) 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?. o Rotación simple a derecha. o Rotación simple a izquierda.

(1.4) 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. v. f.

(1.4) El BALANCE de un ARBOL se realiza cuando: o Se INSERTA o ELIMINA un elemento del ARBOL. o Se INSERTA o ELIMINA un elemento del NODO.

(1.4) 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?. o 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. o Una inserción en el árbol izquierdo del hijo izquierdo de Y. Una inserción en el árbol derecho del hijo de derecho de Y.

(1.4) En un árbol AVL ¿Pueden diferir las alturas de los subárboles derecho e izquierdo? ¿Por qué?. o Sí, pueden diferir cuanto mucho en un elemento porque es difícil insertar nuevos elementos al mismo tiempo para mantener el equilibrio. o No, pueden diferir cuanto mucho en un elemento porque es facil insertar nuevos elementos al mismo tiempo para mantener el equilibrio.

(1.4) 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. o Dijkstra. o Hoffman.

(1.4) 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?. o Rotación Doble. o Rotación Triple.

(1.4) ¿Qué significa en un árbol AVL que el factor de equilibrio de un nodo es 0?. o Que el nodo está equilibrado y sus subárboles tienen exactamente la misma altura. o Que el nodo está desequilibrado y sus subárboles tienen exactamente la misma altura.

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

(1.4) Si queremos ELIMINAR en un ARBOL BINARIO DE BUSQUEDA un NODO que es una HOJA, debemos: o Eliminarlo y no necesita hacer otra operación. o Eliminarlo y necesita hacer otra operación.

● (1.4) Un ARBOL BINARIO DE BUSQUEDA BALANCEADO (AVL) tiene como propiedad adicional que: o Las ALTURAS de los subárboles izquierdo y derecho pueden diferir en solo una unidad. o Las ALTURAS de los subárboles izquierdo y derecho pueden diferir en mas de una unidad.

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

(1.5) El objeto vertex mantiene 4 piezas de información para cada vértice. Identifique cuáles son: o Las piezas son: name, adj, dist y prev. o Las piezas son: name, date, dist y prev.

(1.5) Este método, normalmente se utiliza cuando hay aristas con peso negativos: o Bellman-Ford. o Bell-Ford.

(1.6) El algoritmo de caminos mínimos. . o Nos permite con la ordenación topológica, su ejecución en tiempo lineal y funcionará aún en presencia de aristas negativas. o Nos permite con la ordenación topológica, su ejecución en tiempo exponencial y funcionará aún en presencia de aristas negativas.

(1.6) La ordenación topológica se emplea para ordenar vértice en los grafos cíclicos dirigidos y acíclicos dirigidos. f. v.

● (1.6) Si hablamos de grafos, ¿Cuál de los siguientes se considera un problema tipo?. o Problema del camino más corto con ponderaciones positivas. o Problema del camino más largo con ponderaciones positivas.

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

● (1.7) ¿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. o Recorrido. o Camino.

● (1.7) 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: o El orden topologico para el grafo. o El orden topografico para el grafo.

(1.7) En un grafo: Seleccione 4 (cuatro) respuestas correctas. o La ordenación topológica encuentra todos los órdenes topológicos de un grafo acíclico. o Por lo general contiene varios órdenes topológicos. o 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. o El algoritmo de ordenamiento topológico simple se implementa en tiempo lineal, ya que procesa cada vértice sólo una vez. o 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.

(1.8) 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. o Búsqueda en anchura. o Búsqueda en profundidad.

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 largo con ponderaciones negativas.

¿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 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 menos 1.

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. Implica trabajar con grafos cíclicos.

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 transformar el grafo de eventos en un grafo de actividades.

(1.9) 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 evento.

(1.9) 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 hay entre una actividad y otra.

(2.1) A la secuencia de vértices en un grafo se la define como: Camino. Actividades.

(2.1) ¿Cuál algoritmo usaría para conocer el CAMINO MINIMO desde en único punto de origen en un GRAFO CON PESOS POSITIVOS?. DIJKSTRA. DIMITRI.

● (2.1) ¿Cuál algoritmo usaría para conocer el CAMINO MINIMO desde un único punto de origen en un GRAFO sin PESOS?. BFS. BTS.

● (2.1) ¿ Cuál de las siguientes afirmaciones no define las propiedades principales de un arbol?. Estructura lineal y dinámica de datos. Estructura dinámica.

● (2.1) ¿Cuál de las siguientes operaciones es soportada en tablas hash?. Find. End.

● (2.1) ¿Cuándo se produce una colisión?. Cuando a dos elementos distintos le corresponde la misma dirección. Cuando a dos elementos distintos le corresponde la dirección opuesta.

● (2.1) En un árbol: Todos los hijos de la raíz son hermanos. Todas las hojas son hermanos.

● (2.1) En un GRAFO decimos que el vértice V es ADYACENTE al vértice W cuando: Existe una ARISTA que los une. Existe un VÉRTICE que los une.

● (2.1) Entendemos como GRAFO NO DIRIGIDO al que: Sus ARISTAS no tienen un sentido dado. Sus ARISTAS tienen el mismo sentido.

● (2.1) 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 trayectoria del Grafo mas larga.

● (2.1) 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 la media de las profundidades de sus nodos.

● (2.1) ¿Que método en java realiza la resolución del sondeo cuadrático?. FindPos. PosNet.

● (2.1) Según la definición formal, un grafo esta formado por... Un conjunto de vértices V y un conjunto de aristas E. Un conjunto de lados L y un conjunto de vértices V.

● (2.1) 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=par.

● (2.1) Un GRAFO ACICLICO es aquel es: DIRIGIDO y sin CICLOS. NO DIRIGIDO y sin CICLOS.

● (2.1) Un GRAFO es un conjunto de: VERTICES o NODOS unidos por ARISTAS o ARCOS. VÉRTICES unidos por NODOS.

● (2.1) Una tabla Hash es: Una estructura de datos. Find.

● (2.2) 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. Si, el 36 coliciona con el 23. No.

(2.2) 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. Si, entre el 15 y el 28.

● (2.2) El atributo de un árbol es: Altura. Ancho.

● (2.2) 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. Almacenamiento en caché en Find.

● (2.2) En un árbol de Altura=2. El nivel máximo es igual a 3. El nivel máximo es igual a 2. El nivel máximo es mayor a 2.

● (2.2) La cantidad de hojas en un árbol, es: El peso. El número.

● (2.2) La cantidad máxima de aristas en un árbol binario de Altura 2 es: 6. 8. 3. 2.

● (2.2) ¿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 los objetos String son mutables.

● (2.2) ¿Qué resuelve el algoritmo de ordenamiento topológico?. Orden de actividades. Orden de ejercicios.

● (2.2) ¿Qué tipos de operación Find podemos encontrar?. Las que tienen éxito y las que no. Las de almacenamiento.

● (2.2) Si hay demasiadas colisiones, el rendimiento de la tabla hash se verá: Enormemente afectado. No se vera afectado.

● (2.2) Un nodo interno es cualquier nodo que posea hijos. Verdadero. Falso.

● (2.3) ¿Cuál es el algoritmo que utiliza una COLA como estructura auxiliar?. Algoritmo BFS. Algoritmo DFS.

● (2.3) ¿Cuál es el algoritmo que utiliza una PILA como estructura auxiliar?. Algoritmo DFS. Algoritmo BFS.

● (2.3) ¿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. La misma secuencia que la de búsqueda de otro elemento.

● (2.3) ¿Cuáles algoritmos de recorridos van a encontrar todos los vértices que se encuentran conectados al vértice origen?. BFS y DFS. BTS y NFT.

● (2.3) El algoritmo de Dijkstra determina:. La RUTA más corta desde un NODO origen hacia los demás NODOS. La RUTA más óptima desde un NODO origen hacia los demás NODOS.

● (2.3) 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+2/(1-A)²)/2.

● (2.3) 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. El número de nodos.

● (2.3) 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. Elimina el problema de agrupamiento primario que presenta el sondeo curvo.

● (2.3) 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. La Tabla Find es de gran tamaño.

● (2.3) La agrupación primaria es un problema para factores con cargas... Seleccione la respuesta correcta. Altas. Bajas.

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

● (2.3) La representación de un sistema de archivos de un sistema operativo (E,: FAT, NTFS, ext4, etc), es un claro ejemplo de: Árbol Nario. Árbol de Huffman.

● (2.3) 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. Inserciones más económicas.

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

(2.3) ¿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. Occupied es el tamaño lógico del HashSet y currentsize la cantidad total de celdas ocupadas.

● (2.3) ¿Qué nos indica el factor de carga de una tabla hash?. La fracción de la tabla que está llena. La fracción de la tabla que está incompleta.

● (2.3) ¿Qué rutina de la clase HashSet cambia el tamaño de la colección a cero.?. Clear. Find.

● (2.3) ¿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 pares.

● (2.4) ¿Cuándo es necesario hacer rehashing?. Cuando el factor de carga alcance el valor 0,5. Cuando el factor de carga sea menor al valor 0,5.

● (2.4) Durante el sondeo lineal se forman grandes... Seleccione la respuesta correcta. Agrupamientos de celdas. Combinación de celdas.

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

● (2.4) 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,5.

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

(2.4) 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.

● (2.4) 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. Falso. Verdadero.

● (2.4) 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. Add.

● (2.4) En la rutina add de HashSet ¿Qué sucede si la llamada a findPos consigue encontrar X?. Retornamos false. Retornamos true.

● (2.4) ¿En qué consiste la técnica del doble Hash?. En aplicar una segunda función de Hash. En aplicar dos funciones de Hash.

● (2.4) La colisión de dos o más elementos en una tabla hash es... Inevitable. Evitable.

● (2.4) La técnica de borrado perezoso consiste en: seleccione la respuesta correcta. Marcar los componentes como borrados en lugar de eliminarlo físicamente. Borrar los componentes y no marcar que fue eliminado.

● (2.4) La técnica del Doble Hash ¿Qué fenómeno elimina?. Agrupamiento Secundario. Agrupamiento Primario.

● (2.4) 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. Matriz HashMap.

● (2.4) Para la técnica de encadenamiento separado, el factor de carga es normalmente próximo al valor: 1. 0. 2.

● (2.4) 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). Recorrido de anchura (DFS).

● (2.5) 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. Si X es padre de Q y U, Q es padre de S y V, podemos decir que U es es abuelo de S y V.

● (2.5) Para buscar en un árbol binario se deberá usar: Seleccione la respuesta correcta. Preorden, Inorden, Postorden indistintamente. Orden, Desorden, Reorden.

● (2.5) ¿Qué atributos se definen en la clase Arista?. Destino y costo. Nodo y Nexo.

● (2.5) Un árbol binario: Es un árbol en el que ningún nodo puede tener más de dos subarboles. Es un árbol en el que ningún nodo puede tener dos subarboles.

● (2.6) 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 deberá implementar un 2 niveles que arranque desde la raíz.

● (2.7) 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. Postorden.

● (2.9) 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. Es similar al recorrido en preorden, por el hecho de que cuando se desapila un nodo por segunda vez, se declara ya visitado.

● (2.x) BFS significa: Breadth First Search. Breth Find Search.

● (2.x) 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 conjunto de esquinas y un conjunto de lineas.

● (2.x) 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 2 4500 3 1323 4 6173 5 2364 6 7 8 4489 9 4199. 0 2589 1 4371 2 3 1323 4 5 6 4678 7 2344 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?: Hash(h) = X mod 10 4371 1 1323 3 6173 3 4199 9 2364 4 2589 9 4489 9. 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 7 4489 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? h Hash(h) 43 0 13 3 63 6 49 3 64 4 28 9 19 9. En la posicion: 8. En la posicion: 7. En la posicion: 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? h Hash(h) 43 0 13 3 63 6 49 3 64 4 28 9 19 9. En la posición: 5. En la posición: 8.

Una función que hace referencia a un elemento y 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 izquierdo de Y. Una inserción en el subárbol izquierdo del hijo izquierdo de Y.

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

¿Cómo mide el recorrido el sondeo cuadrático desde el punto de sondeo inicial?. 1,4,9, etc. 1,2,3, etc.

Considerando el siguiente árbol, podemos decir que el Tamaño del nodo B es: 3. 4.

¿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. El árbol 2 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 11.

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

¿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 en 20.

● (X.x) Dado el siguiente grafo: Si aplicamos el algoritmo de Diksjtra partiendo del vértice S. ¿Cuál de los siguientes resultados es correcto?. D(s,a ) =9 ; D(s,b ) = 17; D(s,c ) = 7; D(s,d ) = 20;. D(s,a ) =10 ; D(s,b ) = 9; D(s,c ) = 7; D(s,d ) = 3.

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). 0 2(3) 1 0(7) -> 4(5) 2 3(3) -> 1(5) 3 8(4) -> 1(1) 4 2(4).

Dado el siguiente grafo identifique su matriz de adyacencia. 0 1 2 3 4 0 3 1 2 5 2 4 7 3 1 8 4 6. 0 1 2 3 4 0 3 1 2 4 5 2 2 7 3 1 8 4 6.

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

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. Codigo basado en Hash.

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.

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.

El borrado en un árbol BST de un nodo con 2 hijos: Tiene 2 posible soluciones. Tiene un antesesor y un sucesor.

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 largo no ponderado. Problema del camino más corto ponderado.

¿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. Si, es un árbol completo porque cumple con las condiciones de que todos sus nodos sean hojas y que cada nodo tenga 2 hijos.

) 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()){. If(start**null).

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 4 y el FE del nodo derecho es <0.

¿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 puede elegir tanto A como E.

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 K tendrá solo un enlace al nodo F como firstChild.

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 3 y 4.

¿Cuál de los siguientes es el código correcto para el método findMax en un subárbol?. if t != null t=t.right. if t != null t=t.left.

) ¿En cuál de los siguientes gráficos se marcan correctamente todos los nodos que están desequilibrados?. 10 mayor que 8 y menor que 12. 10 menor que 8 y menor que 12.