Hoja de ejercicios de Estructuras de datos con soluciones

En la representación de un grafo mediante listas de adyacencia, ¿qué se almacena para cada vértice?

1. AUna lista de sus vértices vecinos
2. BUna fila de V valores booleanos
3. CEl número total de aristas del grafo
4. DEl camino más corto a todos los demás vértices

¿Qué almacena un mapa (diccionario)?

1. ASolo valores en orden de inserción
2. BPares de claves iguales
3. CValores ordenados por tamaño
4. DPares clave-valor con claves únicas

En un árbol, ¿qué es una hoja?

1. AUn nodo sin padre
2. BUn nodo con exactamente un hijo
3. CUn nodo sin hijos
4. DEl nodo con el valor más grande

Un recorrido en orden (in-order) de un árbol binario de búsqueda visita las claves en:

1. AOrden ascendente
2. BSiempre orden descendente
3. COrden de inserción
4. DOrden por niveles

Una red de carreteras tiene 100,000 cruces, cada uno conectado con unos 4 más. ¿Qué representación es la más adecuada?

1. ALista de adyacencia
2. BMatriz de adyacencia
3. CUn único arreglo ordenado de vértices
4. DUn montículo binario de aristas

En un montículo binario almacenado en un arreglo que empieza en el índice 0, ¿dónde está el padre del nodo del índice i?

1. AEn el índice ⌊(i − 1) / 2⌋
2. BEn el índice ⌊i / 2⌋ + 1
3. CEn el índice 2i + 1
4. DEn el índice i − 1

Para que una tabla hash funcione correctamente, ¿qué regla deben cumplir el hash y la igualdad?

1. ALas claves iguales deben tener valores hash iguales
2. BValores hash iguales implican claves iguales
3. CLos valores hash deben ser números primos
4. DLas claves distintas deben tener valores hash distintos

¿Qué afirmación sobre heapsort es correcta?

1. AEs estable y necesita O(n) de memoria adicional
2. BNecesita un árbol binario de búsqueda como almacenamiento adicional, así que usa O(n) de memoria extra
3. CSe ejecuta en tiempo O(n) con cualquier entrada
4. DOrdena en el sitio con un tiempo O(n log n) en el peor caso, pero no es estable