Parcial 2 1 Noviembre 2020, preguntas y respuestas PDF

Preview

Summary

Taller de Algoritmos y Estructura de Datos II Preguntero Parcial Nº1 (26-10-2020) ¡LOS QUE ESTAN EN ROJO NO ESTAN VERIFICADOS CON CAPTURAS ACTUALES!(1) ¿Cuál de las siguientes afirmaciones define el concepto de árbol correctamente? ○ Un árbol es una estructura de datos que tiene un nodo llamado raiz...

Description

Taller de Algoritmos y Estructura de Datos II Preguntero Parcial Nº1 (26-10-2020) ¡LOS QUE ESTAN EN ROJO NO ESTAN VERIFICADOS CON CAPTURAS ACTUALES! (1.1) ¿Cuál de las siguientes afirmaciones define el concepto de árbol correctamente? ○ Un árbol es una estructura de datos que tiene un nodo llamado raiz. Dónde a cada nodo i, exceptuando la raiz, le llega una arista desde exactamente otro nodo j, al cual se le llama padre de i. (1.1) Los árboles pueden definirse de dos maneras: de forma recursiva o no recursiva. ○ Verdadero (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... ○ Un grafo simple (1.1) Cuando en un grafo se da el caso de que una arista sale y llega al mismo nodo, estamos hablando de: ○ Un bucle (1.1) Un ciclo que visita cada vértice una y sólo una vez, es la definición de: ○ Ciclo Hamiltoniano (1.1) Un digrafo es un: ○ grafo dirigido (1.1) El concepto de digrafo, esta referido a: Seleccione la respuesta correcta ○ Grafos dirigidos (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: ○ Conexo (1.1) Estas son propiedades de un vértice: Seleccione las 3(tres) respuestas correctas ○ Grado de entrada ○ Grado de salida ○ Aristas adyacentes (1.1) En el caso de los grafos ponderados, la forma correcta de obtener la longitud de un camino de pesos: Seleccione la respuesta correcta ○ Realizar la suma del costo de las aristas del camino (1.1) Según la Teoria de Grafos cambiar la forma de las aristas para mejorar la visualizacion del grafo es una accion que... ○ No es relevante, porque sólo importa a qué vértices están unidas (1.1) Según la Teoria de Análisis de Caminos Críticos, en un grafo de Actividades cada arista representa... ○ Relaciones de precedencia entre las actividades (1.1) 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 (1.1) 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 (1.1) Los árboles son una estructura de datos que representa datos de fo rma jerárquica ¿Cuales son las representaciones más utilizadas?: ○ Representar cada nodo como una variable en el espacio de memoria o representar el arbol con un arreglo. (1.1) Las definiciones correctas en el contexto de grafos son: Selecciones las 2 (dos) respuestas correctas: ○ Un arbol es un grafo conexo simple aciclico ○ Un camino euleriano en un grafo es un camino que usa cada arista una y sólo una vez. (1.1) Un árbol es una estructura fundamental en las ciencias de la computación y está representado por los siguientes elementos: ○ Nodos y aristas. (1.1) Podemos definir a los grafos Isoformos como... ○ Diferentes representaciones gráficas de un mismo grafo (1.1) Teóricamente podemos decir que los grafos son estructuras matemáticas que se utilizan para modelar... ○ Relaciones binarias entre objetos de cierto tipo. (1.1) Un camino hamiltoniano en un grafo ○ Es un camino que “visita” cada vértice una y sólo una vez (1.1) ¿Cuál seria la altura de un árbol vacio?: ○0 (1.2) Conocemos como ESTRUCTURA RECURSIVA aquella: ○ Estructura de DATOS en la cual los elementos se definen a si mismos. (1.2) Si una ESTRUCTURA RECURSIVA no tiene la CONDICION DE CORTE puede ocurrir: ○ Un loop infinito. (1.2) El problema de la RECURSION es: ○ Generar un ciclo infinito (1.2) 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. (1.2) ¿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. (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);} ○ Factorial

(1.2) 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. (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? ○ 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. (1.2) ¿Cuáles de las siguientes palabras se usan para definir un árbol? Seleccione las 4 (cuatro) respuestas correctas. ○ Arista. ○ Nodo. ○ Raíz. ○ Hoja. (1.2) ¿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. (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. ○ FindMin (1.3) ¿Qué clases fundamentales se utilizan en Java para representar un árbol binario? ○ BinaryNode, BinaryTree, AnyType (1.3) ¿Cuáles son las operaciones que podemos aplicar sobre árboles binarios de búsqueda? ○ Las operaciones son: find, find Max, find Min, Remove, removeMax, removeMin, insert. (1.3) Definimos como CAMINO en una estructura de tipo ARBOL a: ○ Una sucesión de enlaces que conectan dos nodos (1.3) Un ARBOL BINARIO tiene como caracteristica fundamental que: ○ El numero de hijos esta limitado como mucho a dos (1.3) 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 (1.3) Un árbol es binario de búsqueda cuando: ○ cada nodo puede tener un máximo de 2 hijos (1.3) En grafos, DFS significa: ○ Depth First Search BFS significa: Breadth First Search (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 algoritmo es: ○ recorrer el árbol yendo siempre a trravés del subárbol izquierdo, hasta llegar a un nodo que no tenga hijo (1.3) Un ARBOL se puede realizar su recorrido por ANCHURA, el cual se realiza: ○ Horizontalmente, desde la RAIZ a todos los hijos antes de pasar a la descendencia (1.3) ¿Cuando INSERTAMOS en un ARBOL BINARIO un valor menor que el RAIZ, se inerta en: ○ El subárbol izquierdo (1.3) ¿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. (1.3) ¿Cuál de los siguientes es el código correcto para el método findMax en un subárbol?

○ (1.4) Si queremos ELIMINAR en un ARBOL BINARIO DE BUSQUEDA un NODO que es una HOJA, debemos: ○ Eliminarlo y no necesita hacer otra operación (1.4) 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 (1.4) El BALANCE de un ARBOL se realiza cuando: ○ Se INSERTA o ELIMINA un elemento del ARBOL (1.4) El algoritmo de Floyd-Warshall descrito en 1959 por Bernard Roy, es un algoritmo sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados que contengan ciclos negativos ○ FALSO (sin ciclos negativos) (1.4) En un árbol AVL ¿Pueden diferir las alturas de los subárboles derecho e izquierdo? ¿Por qué? ○ Si, pueden diferir cuanto mucho en un elemento porque es difícil insertar nuevos elementos al mismo tiempo para mantener el equilibrio. (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? ○ 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. (1.4) De un árbol de raiz (r) y de hijos izquierdo (i) y derecho (d), formamos un nuevo árbol cuya raíz sea la raíz del hijo izquiedo colocamos el hijo izquierdo de i (nuestro i') y como hijo derecho construímos un nuevo árbol que tendrá como raíz, la raíz 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 (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 que rotación se debe usar? ○ Rotación doble (1.4) ¿Cuál de las siguientes operaciones pueden implementarse en árboles de búsqueda binaria? Seleccione las 4 (cuatro) respuestas correctas.

○ Findmax. ○ Insert. ○ Find. ○ Find Min. (1.4) Si el factor de equilibrio de un nodo en un árbol AVL es: Selecciona 4 (cuatro) respuestas correctas. ○ "1" entonces el nodo está equilibrado y su subárbol derecho es un nivel más alto. ○ Si el factor de equilibrio es ">=2" 0 "...