Taller de Algoritmo y Estructuras de Datos II

Preguntero Primer parcial

Alfabético, al 29 oct. 2021 – 17:29 Hs.

 ¿A cuál de los 4 casos de desequilibrio en un árbol AVL soluciona este pseudocódigo:

static BinaryNode doubleRotateWihtLeftChild(k3.left)
{
k3.left = rotateWithRightChild(k3.left);
return rotateWithLeftChild(k3);
}
o Una inserción en el subárbol derecho del hijo izquierdo de Y.

 A la secuencia de vértices en un grafo se le define como:

o Camino.

 ¿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

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

 ¿A qué tipo de recorrido recursivo hace referencia el siguiente código?:

public void printTree( )
{
if (left != null)
left.printTree();

System.out.println(element);

if (right != null)
right.printTree();
}
o Recorrido en orden.

 BFS significa:
o Breadth First Search.

 Conocemos como ESTRUCTURA RECURSIVA aquella:

o Estructura de DATOS en la cual los elementos se definen a sí mismos.

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

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

 ¿Cual algoritmo usaría para conocer el CAMINO MINIMO desde un único punto de origen en un GRAFO sin
PESOS?
o BFS.

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

 ¿Cuál de las siguientes afirmaciones no define las propiedades principales de un arbol?

o Estructura lineal y dinámica de datos.

 ¿Cuál de las siguientes operaciones es soportada en tablas hash?.

o Find.

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

 ¿Cuál de los siguientes árboles binarios se puede considerar como árbol de búsqueda y cuál no? ¿Por qué?

o El árbol 1 puede ser considerado como árbol binario de búsqueda porque satisface la propiedad de
búsqueda ordenada.

 ¿Cuál de los siguientes códigos es correcto para el método constructor de la clase HuffmanTree si se le pasa como
parámetro [..]?
public HuffmanTree(CharCounter cc)
{
theCounts = cc;
root = null;
createTree();
}
o

 ¿Cuál de los siguientes es el código correcto para el método findMax en un subárbol?

 private BinaryName<AnyType> findMax(BinaryName<AnyType> t)
{
if (t != null)
While(t.right != null)
t = t.right;

return t;
}
o

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

 ¿Cuál es el algoritmo que utiliza una COLA como estructura auxiliar?

o Algoritmo BFS.

 ¿Cuál es el algoritmo que utiliza una PILA como estructura auxiliar?

o Algoritmo DFS.

 ¿Cuál es la longitud del camino de la ruta más corta entre V3, y V11 en siguiente grafo?

o La longitud del camino es 3.

 ¿Cuál es la longitud del siguiente árbol?:

o La longitud del camino es 3.

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

 ¿Cuál es la secuencia de celdas analizadas para una búsqueda sin éxito de un elemento X en un sondeo lineal?.
o La misma secuencia que la de inserción del elemento.

 ¿Cuál sería la altura de un árbol vacío?

o 0.

 ¿Cuáles algoritmos de recorridos van a encontrar todos los vértices que se encuentran conectados al vértice
origen?
o BFS y DFS.

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

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

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

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

 ¿Cuándo es necesario hacer rehashing?

o Cuando el factor de carga alcance el valor 0,5.

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

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

 ¿Cuándo se produce una colisión?

o Cuando a dos elementos distintos le corresponde la misma dirección.

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

 Dado el siguiente grafo:

Si aplicamos el algoritmo de Diksjtra partiendo del vértice S. ¿Cuál de los siguientes resultados es correcto?.
o D(s,a ) =9 ; D(s,b ) = 17; D(s,c ) = 7; D(s,d ) = 20;.

 Dado el siguiente grafo identifique su lista de adyacencia.

o Repuesta:

 Dado el siguiente grafo identifique su matriz de adyacencia.

o Repuesta:

 Dados los siguientes árboles. ¿Cuales son árboles binarios de búsqueda?

 o B,C

 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?
o Sí, el 15 colisiona con el 13.

 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?
o No se producen colisiones.

 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

 Definimos como CAMINO en una estructura de tipo ARBOL a:

o Una sucesión de enlaces que conectan dos nodos.

 Durante el sondeo lineal se forman grandes... Seleccione la respuesta correcta.

o Agrupamientos de celdas.

 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 INCORRECTA: Detecta si contiene un ciclo de coste total negativo....

 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

 El algoritmo de Dijkstra determina:.

o La RUTA más corta desde un NODO origen hacia los demás NODOS.

 El algoritmo de Dijkstra es utilizado para resolver qué problema tipo de grafos:

o Problema del camino más corto con ponderaciones positivas.

 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.
o Verdadero.

 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.
 El algoritmo de Shannon-Fano:
o En el que se construye un código sin prefijo basado en un conjunto de símbolos y sus probabilidades.

 El árbol de la siguiente figura no está completo ¿Qué podemos realizar para que lo esté?

o Situando G más arriba reemplazando a su padre.

 El árbol de la siguiente figura no está completo ¿Qué podemos realizar para que lo esté?

o Situando G más arriba reemplazando a su padre.

 El atributo de un árbol es:

o Altura.

 El BALANCE de un ARBOL se realiza cuando:

o Se INSERTA o ELIMINA un elemento del ARBOL.

 El concepto de digrafo, esta referido a: Seleccione la respuesta correcta.

o Grafos dirigidos.

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

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

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

 El ordenamiento externo: Seleccione 4 (cuatro) respuestas correctas.

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

 El problema de la RECURSION es:

o Generar un ciclo infinito.
 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...
o El número de aristas.

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

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

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

 El siguiente algoritmo resuelve un tipo de problema que surge al intentar encontrar el camino más corto. ¿Cuál
de ellos?
public void unweithed( String startName )
{
clearAll( );

Vertex start = vertexMap.get( startName );

if( start == null )
throw new NoSuchElementExcepction( "Start vertex not found" );

Queue<vertex> q = new LinkedList<Vertex>( );

q.add( start ); start.dist = 0;

while( !q.isEmpty( ) )
{
Vertex v = q.remove( );

for( Edge e : v.add )

{
Vertex w = e.dist;

if( w.dest == INFINITY )

{
w.dist = v.dist + 1;
w.prev = v;
???.add ???? ;
}
}
}
}
o Problema del camino más corto no ponderado.

 ¿El siguiente árbol podemos considerarlo como árbol completo?

 o 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

 El siguiente código es la implantación del algoritmo de Josephus mediante una lista enlazada. ¿Este algoritmo
funciona?
public static int josephus (int people){

Collection<Integer> theList = new LinkedList<Integer>();

//Construir lista
for (int i = 1; i<=people; i++)
theList.add(i);

//Jugar la partida:
Iterador<Integer> itr = theList.Iterator();
while(people-- != 1)
{
for (int i=0; i<=passes; i++)
{
if(!itr.hashNext())
itr = theList.Iterator();

itr.next();
}
itr.remove();
}
itr = theList.Iterator();
return itr.next();
}
o No, porque se debe pasar como parámetro el número de pases a realizar.

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

 ¿En cuál de los siguientes gráficos se marcan correctamente todos los nodos que están desequilibrados?

 En el Análisis de caminos crítico: Seleccione 2(dos) respuestas correctas:

o Cada vértice determina un evento.
o Implica trabajar con grafos acíclicos.

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

 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:
o 0.5.
 En el Sondeo Cuadrático: Seleccione las 3 (tres) respuestas correctas.
o Elimina el problema de agrupamiento primario que presenta el sondeo lineal.
o Se puede implementar sin multiplicaciones.
o Se puede implementar sin Operaciones Módulos.

 En grafos, DFS significa:

o Depth First Search.

 En Java cada objeto String almacena internamente el valor de su hashCode. ¿Cómo se denomina esta técnica?
o Almacenamiento en caché del código Hash

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

 En la genealogía familiar (representación gráfica de los antepasados y los descendientes de un individuo) es un

claro ejemplo de estructura de (TDA) árbol binario.
o Falso.

 En la implementación del sondeo cuadrático en java, la tabla Hash contiene una matriz de referencias HashEntry,
cada referencia puede ser:
o Null o un objeto.

 En la rutina add de HashSet ¿Qué sucede si la llamada a findPos consigue encontrar X?

o Retornamos false.

 En la siguiente porción de código del algoritmo de Dijkstra una de las líneas es incorrecta. ¿Cuál de ellas?
public void dijkstra(String startName)
{
PriorityQueue<Path> pq = new PriorityQueue<Path>;
Vertex start = vertexMap.get(startName);
If(start == null)
throw new No SurchElementException("Start vertex not found");

clearAll();
pq.add (new Path(start, 0)); start.dist = 0;
int nodesSeen = 0;
While(pq.esEmpty() && nodesSeen < vertexMap.size()){
Path vrec pq.remove();
...... // continuación del método de Dijkstra
}
o While(pq.esEmpty() && nodesSeen < vertexMap.size()){.

 ¿En qué consiste la técnica del doble Hash?

o En aplicar una segunda función de Hash.

 En un análisis simplista, para estimar el rendimiento del Sondeo Lineal, hacemos 2 suposiciones. Seleccione las 2
(dos) respuestas correctas.
o La Tabla Hash es de gran tamaño.
o Cada Sondeo de la tabla es independiente del sondeo anterior.

 En un árbol
o Todos los hijos de la raíz son hermanos.

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

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

 En un árbol de Altura=2.
o El nivel máximo es igual a 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.

 En un GRAFO decimos que el vértice V es ADYACENTE al vértice W cuando:

o Existe una ARISTA que los une.

 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 INCORRECTA: 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.

 Entendemos como GRAFO NO DIRIGIDO al que:

o Sus ARISTAS no tienen un sentido dado.

 Estas son propiedades de un vértice: Seleccione las 3(tres) respuestas correctas.

o Grado de entrada.
o Grado de salida.
o Aristas adyacentes.

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

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

 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 cuánto tiempo, sin afectar el
tiempo mínimo de terminación? Para ello:
o Debemos transformar el grafo de actividades en un grafo de eventos.

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

 La cantidad de hojas en un árbol, es:

o El peso.

 La cantidad máxima de aristas en un árbol binario de Altura 2 es:

o 6.

 La característica principal de la estructura de los árboles al igual que los grafos es que están formados por...
o Un conjunto de nodos y un conjunto de aristas.
 La colisión de dos o más elementos en una tabla hash es... Sólo 1 respuesta es correcta.
o Inevitable.

 La forma más simple de implementar un árbol N-ario es:

o Utilizar una pila dinámica (lista enlazada que se comporta como pila).

 La longitud del camino externo de un árbol.

o Es lo que se utiliza para calcular el coste de una búsqueda sin éxito.

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

 La representación de un sistema de archivos de un sistema operativo (E,: FAT, NTFS, ext4, etc), es un claro
ejemplo de:
o Árbol de huffman.

 La técnica de borrado perezoso consiste en: seleccione la respuesta correcta.

o Marcar los componentes como borrados en lugar de eliminarlo físicamente.

 La técnica del Doble Hash ¿Qué fenómeno elimina?.

o Agrupamiento Secundario.

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

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

o Verdadero

 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

 Mientras mayor sea el agrupamiento primario ¿Qué sucede? Seleccione las 4 (cuatro) opciones correctas.
o Se produce mayor agrupamiento.
o Se reduce el rendimiento.
o Más rápido crece el agrupamiento.
o Inserciones más costosas.

 Para buscar en un árbol binario se deberá usar: Seleccione la respuesta correcta.

o Preorden, Inorden, Postorden indistintamente

 Para calcular el costo medio de una búsqueda con éxito dentro de un árbol binario, de debe
o Calcular el promedio las profundidades de sus nodos.

 Para determinar la altura de un árbol binario: Seleccione la respuesta correcta.

o Se deberá implementar un método recursivo que cuente los niveles y arranque desde la raíz.

 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 Hermano situado a la derecha.

 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.
o Estructuras HashMap.
o Estructuras HashSet.
o Matriz Hash Entry.
o Currentsize.
 Para la técnica de encadenamiento separado, el factor de carga es normalmente próximo al valor:
o 1.

 Podemos definir a los grafos Isoformos como...

o Diferentes representaciones gráficas de un mismo grafo.

 ¿Porqué es posible implementar en los objetos String la técnica de almacenamiento en cache del código hash?.
o Porque los objetos String son inmutables.

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

 ¿Qué atributos se definen en la clase Arista?

o Destino y costo.

 ¿Qué clases fundamentales se utilizan en Java para representar un árbol binario?

o BinaryNode, BinaryTree, AnyType.

 ¿Qué diferencia existe entre la variable currentsize y occupied en la clase HastSet?

o CurrentSize es el tamaño lógico del HashSet y occupied la cantidad total de celdas ocupadas.

 ¿Que método en java realiza la resolución del sondeo cuadrático?

o FindPos.

 ¿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.
o 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.

 ¿Qué nos indica el factor de carga de una tabla hash?.

o La fracción de la tabla que está llena.

 ¿Qué resuelve el algoritmo de ordenamiento topológico?

o Orden de actividades.

 ¿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 Subfactorial.

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

o Clear.

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

 ¿Qué sucede si en un bosque de árboles tenemos dos nodos con el mismo peso? Ej.:

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

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

 ¿Qué tipos de operación Find podemos encontrar?

o Las que tienen éxito y las que no

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

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

 Según la definición formal, un grafo esta formado por...

o Un conjunto de vértices V y un conjunto de aristas E

 Según la Teoría 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.

 Según la Teoría de Análisis de Caminos Críticos, en un grafo de eventos cada vértice indica:
o La terminación de una actividad y sus actividades dependientes.

 Según la Teoría de Grafos cambiar la forma de las aristas para mejorar la visualización del grafo es una acción
que...
o No es relevante, porque sólo importa a qué vértices están unidas.

 Si consideremos A y M contantes y X0 la semilla que satisface 1 ≤ X0 < M. Un generador de congruencia lineal de

periodo completo tiene un periodo de:
o M-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.

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

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

 Si hablamos de grafos, ¿Cuál de los siguientes se considera un problema tipo?.

o Problema del camino más corto con ponderaciones positivas.

 Si hay demasiadas colisiones, el rendimiento de la tabla hash se verá:

o Enormemente afectado.

 Si nos detenemos en el nodo E y utilizando el método de primer hijo, siguiente hermano

o El nodo E tendrá solo un enlace al nodo H como firstChild.

 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?
o Recorrido en anchura (BFS).

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

 Si tomamos en cuenta un árbol N-ario:

o Un árbol binario es un caso especial para cuando N=2.

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

 Si una ESTRUCTURA RECURSIVA no tiene la CONDICION DE CORTE puede ocurrir:

o Un loop infinito.

 Teniendo en cuenta la Teoría de Caminos Críticos, el tiempo de espera:

o Es la cantidad de tiempo que una actividad puede retrasarse sin retrasar la terminación total.

 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
o Repuesta:
0 2589
1 4371
2
3 1323
4 6173
5 2364
6
7
8 4489
9 4199

 Teniendo en cuenta los siguientes números (4371,1323,6173,4199,2364,2589,4489) y una función hash(h) = x

mod 10, ¿Cómo quedará la tabla hash usando sondeo cuadrático sabiendo que el resultado de aplicar la función
hash es el siguiente:?
Hash(h) = X mod 10
4371 1
1323 3
6173 3
4199 9
2364 4
2589 9
4489 9
o Repuesta:
 0 2589
1 4371
2
3 1323
4 6173
5 2364
6
7
8 4489
9 4199

 Teniendo los siguientes números (4371,1323,6173,4199,2364,2589,4489) y una función hash(h) = x mod 10,
¿Cómo quedará la tabla hash usando sondeo lineal sabiendo que el resultado de aplicar la función hash es el
siguiente?:
Hash(h) = X mod 10
4371 1
1323 3
6173 3
4199 9
2364 4
2589 9
4489 9
o Repuesta:
0 2589
1 4371
2 4489
3 1323
4 6173
5 2364
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?
h Hash(h)
43 0
13 3
63 6
49 3
64 4
28 9
19 9
o En la posición: 8.

 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
o En la posición: 5.

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

 Un árbol binario:
o Es un árbol en el que ningún nodo puede tener más de dos subarboles.

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

 Un ÁRBOL BINARIO tiene como característica fundamental que:

o El número de hijos está limitado como mucho a dos.

 Un árbol con raíz tiene ciertas propiedades. Seleccione 3 (tres) correctas.

o Uno de los nodos se distingue de los demás por estar designado como raíz.
o Todo nodo c, excepto la raíz, está conectado mediante exactamente una arista a otro nodo p, denominado
padre de c.
o 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.
o INCORRECTA: 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.
o INCORRECTA: Todo árbol debe tener la misma cantidad de hijos del lado derecho y del lado izquierdo.

 Un árbol es binario de búsqueda cuando:

o Cada nodo puede tener un máximo de 2 hijos.

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

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

 Un camino hamiltoniano en un grafo

o 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:
o Ciclo Hamiltoniano.

 Un digrafo es un:
o Grafo dirigido.

 Un GRAFO ACICLICO es aquel es:

o DIRIGIDO y sin CICLOS.

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

 Un GRAFO es un conjunto de:

o VERTICES o NODOS unidos por ARISTAS o ARCOS.
 Un nodo interno es cualquier nodo que posea hijos.
o Verdadero.

 Una tabla Hash es:

o Una estructura de datos.