Examen Parcial 1 - Nat S C

Vista previa del material en texto

Examen parcial 1 
Estructura de Datos y Algoritmos II 
 
1. ¿Qué es una lista enlazada? ¿Cuál es la diferencia entre una lista enlazada 
simple y una lista enlazada doble? Respuesta: Una lista enlazada es una 
estructura de datos que consiste en una secuencia de nodos, donde cada 
nodo contiene un valor y un puntero al siguiente nodo en la lista. Una lista 
enlazada simple tiene un solo puntero en cada nodo, que apunta al 
siguiente nodo. Una lista enlazada doble tiene dos punteros en cada nodo, 
uno que apunta al siguiente nodo y otro que apunta al nodo anterior. 
2. ¿Cuál es la complejidad temporal del algoritmo de ordenamiento de 
burbuja? ¿Es eficiente para ordenar grandes conjuntos de datos? Respuesta: 
La complejidad temporal del algoritmo de ordenamiento de burbuja es 
O(n^2), lo que lo hace ineficiente para ordenar grandes conjuntos de datos. 
3. ¿Qué es un árbol binario? ¿Cuál es la diferencia entre un árbol binario 
completo y un árbol binario balanceado? Respuesta: Un árbol binario es una 
estructura de datos en la que cada nodo tiene como máximo dos hijos. Un 
árbol binario completo es un árbol binario en el que cada nivel está 
completamente lleno, excepto posiblemente el último nivel, que puede estar 
parcialmente lleno. Un árbol binario balanceado es un árbol binario en el 
que la altura de los subárboles izquierdo y derecho de cualquier nodo 
difiere en como máximo una unidad. 
4. ¿Cuál es la complejidad temporal del algoritmo de búsqueda binaria en un 
arreglo ordenado? ¿Cómo funciona este algoritmo? Respuesta: La 
complejidad temporal del algoritmo de búsqueda binaria es O(log n). Este 
algoritmo divide repetidamente el arreglo por la mitad y compara el 
elemento buscado con el elemento en el medio. Si el elemento buscado es 
menor que el elemento en el medio, se busca en la mitad inferior del 
arreglo. Si es mayor, se busca en la mitad superior del arreglo. Este proceso 
se repite hasta que se encuentre el elemento o se agote el arreglo. 
5. ¿Qué es un grafo? ¿Cuáles son las dos formas comunes de representar un 
grafo en una computadora? Respuesta: Un grafo es una estructura de datos 
que consta de un conjunto de nodos (vértices) y un conjunto de aristas que 
los conectan. Las dos formas comunes de representar un grafo en una 
computadora son mediante una matriz de adyacencia y una lista de 
adyacencia. La matriz de adyacencia es una matriz booleana que indica si 
hay una arista entre dos nodos. La lista de adyacencia es una lista de vecinos 
para cada nodo. 
6. ¿Qué es un algoritmo de búsqueda en profundidad (DFS) en un grafo? ¿Cómo 
funciona? Respuesta: El algoritmo de búsqueda en profundidad es un 
algoritmo de búsqueda que recorre un grafo de manera exhaustiva. Comienza 
en un nodo inicial y sigue cada rama lo más lejos posible antes de retroceder. 
El algoritmo utiliza una pila para realizar el seguimiento de los nodos visitados 
y sus vectores 
7. Claro, aquí te dejo las siguientes 10 preguntas con sus respuestas: 
8. 
9. 11. ¿Qué es la complejidad temporal de un algoritmo y cómo se calcula? 
10. Respuesta: La complejidad temporal de un algoritmo se refiere a la cantidad de 
tiempo que tarda un algoritmo en ejecutarse en función del tamaño de entrada. Se 
calcula mediante la notación de orden de crecimiento de la función, que se expresa 
en términos de n (tamaño de entrada) y se utiliza para medir el rendimiento de un 
algoritmo en el peor de los casos. 
11. 
12. 12. ¿Qué es un árbol AVL y cuál es su principal ventaja en comparación con un árbol 
binario de búsqueda? 
13. Respuesta: Un árbol AVL es un árbol binario de búsqueda equilibrado en el que la 
diferencia de altura entre los subárboles izquierdo y derecho de cada nodo es como 
máximo 1. Su principal ventaja sobre un árbol binario de búsqueda es que se mantiene 
equilibrado automáticamente, lo que garantiza un tiempo de búsqueda y modificación 
en tiempo logarítmico. 
14. 
15. 13. ¿Qué es la complejidad espacial de un algoritmo y cómo se calcula? 
16. Respuesta: La complejidad espacial de un algoritmo se refiere a la cantidad de 
memoria que utiliza el algoritmo para resolver un problema. Se calcula sumando la 
cantidad de espacio utilizado por cada variable y estructura de datos que utiliza el 
algoritmo. 
17. 
18. 14. ¿Qué es un grafo y cómo se representan en la memoria de una computadora? 
19. Respuesta: Un grafo es una estructura de datos que consta de un conjunto de nodos 
(vértices) y un conjunto de aristas que los conectan. Se pueden representar en la 
memoria de una computadora utilizando dos enfoques: la matriz de adyacencia, que 
representa los nodos como filas y columnas de una matriz y las aristas como valores 
booleanos que indican si hay una conexión, o la lista de adyacencia, que representa 
cada nodo como una lista de sus aristas adyacentes. 
20. 
21. 15. ¿Qué es el algoritmo de ordenamiento QuickSort y cuál es su complejidad 
temporal en el peor caso? 
22. Respuesta: QuickSort es un algoritmo de ordenamiento recursivo que divide un 
arreglo en dos subarreglos alrededor de un pivote elegido y luego ordena cada 
subarreglo recursivamente. Su complejidad temporal en el peor caso es O(n^2), 
aunque en promedio es O(n log n), lo que lo convierte en uno de los algoritmos de 
ordenamiento más eficientes en términos de tiempo. 
23. 
24. 16. ¿Qué es un árbol de segmentos y cuál es su principal uso? 
25. Respuesta: Un árbol de segmentos es una estructura de datos que se utiliza para 
realizar consultas de intervalos en una matriz. Divide la matriz en segmentos más 
pequeños y almacena información sobre cada segmento en un árbol binario. Su 
principal uso es en la resolución de problemas relacionados con intervalos en los que 
se necesitan consultas eficientes. 
26. 
27. 17. ¿Qué es la programación dinámica y cuál es su principal objetivo? 
28. Respuesta: La programación dinámica es una técnica de diseño de algoritmos que se 
utiliza para resolver problemas que se pueden dividir en subproblemas más pequeños 
y solucionarlos de manera recursos 
29. ¿Qué es una tabla hash y cómo funciona? Una tabla hash es una estructura 
de datos que se utiliza para almacenar y recuperar datos utilizando una 
clave. Es esencialmente una matriz que asigna claves a valores utilizando una 
función hash. La función hash toma la clave y la transforma en un índice en 
la matriz. Luego, el valor correspondiente se almacena en la posición de la 
matriz indicada por el índice. Cuando se busca un valor utilizando su clave, 
la función hash se aplica nuevamente a la clave y se usa el índice resultante 
para buscar en la matriz. 
30. ¿Qué es un árbol AVL y cuál es su utilidad? Un árbol AVL es un árbol binario 
de búsqueda que se equilibra automáticamente para mantener una altura 
equilibrada. Es decir, para cada nodo, la altura de su subárbol izquierdo y el 
de su subárbol derecho difieren en uno o menos. Esto se logra a través de 
rotaciones de nodos. La utilidad de un árbol AVL es garantizar que las 
operaciones de búsqueda, inserción y eliminación tengan una complejidad 
O(log n) en el peor de los casos, lo que lo hace ideal para aplicaciones 
donde el tiempo de respuesta rápido es esencial. 
31. ¿Qué es un árbol B y cuál es su utilidad? Un árbol B es un árbol de búsqueda 
donde cada nodo puede tener varios hijos (generalmente un número fijo). 
Estos nodos se llaman nodos internos, mientras que los nodos que no 
tienen hijos se llaman nodos hoja. La utilidad de un árbol B es que se puede 
utilizar para almacenar grandes cantidades de datos en memoria secundaria 
(como en un disco duro) de manera eficiente. Esto se debe a que los nodos 
internos tienen una gran cantidad de hijos, lo que permite que se almacene 
más información por nivel. 
32. ¿Qué es un grafo dirigido y cuáles son sus componentes? Un grafo dirigido 
es un tipo de grafo donde las aristas tienen una dirección. Es decir, cada 
arista se extiende desde un nodode inicio a un nodo de destino. Los 
componentes de un grafo dirigido incluyen: 
1. Nodos o vértices: puntos individuales en el grafo. 
2. Aristas: conexiones entre nodos que pueden tener una dirección. 
3. Camino: una secuencia de nodos y aristas que conectan un par de 
nodos en el grafo. 
4. Ciclo: un camino en el que el nodo de inicio y el de destino son el 
mismo. 
5. Grado de entrada: el número de aristas que entran en un nodo. 
6. Grado de salida: el número de aristas que salen de un nodo. 
33.