¿De dónde viene la palabra «algoritmo»?
Respuesta : Del matemático al-Khwarizmi
La palabra viene de la latinización del nombre del matemático al-Khwarizmi, autor en el siglo IX de tratados sobre cálculo.
Preguntas y respuestas: Algoritmos y estructuras de datos
Repasa Algoritmos y estructuras de datos: aquí tienes una selección de preguntas de todos los niveles, con respuesta y explicación. Para ponerte a prueba sin ver las respuestas, juega a los quizzes.
Jugar a los quizzes de Algoritmos y estructuras de datosFácil
En un programa, ¿qué designa una variable?
Respuesta : Una posición de memoria con nombre cuyo valor puede cambiar
Una variable es una posición de memoria identificada por un nombre, cuyo valor puede leerse y modificarse durante la ejecución.
¿Qué estructura permite ejecutar un bloque de instrucciones solo si una condición es verdadera?
Respuesta : La instrucción si (if)
La instrucción si (if) evalúa una condición y solo ejecuta el bloque asociado cuando es verdadera.
¿Qué ocurre con un bucle mientras cuya condición sigue siendo siempre verdadera?
Respuesta : No se detiene sin una interrupción forzada
Un bucle mientras se ejecuta mientras su condición sea verdadera: si nada la vuelve falsa, el bucle gira sin fin.
¿Qué es el pseudocódigo?
Respuesta : Una descripción de un algoritmo en un lenguaje cercano al natural, independiente de cualquier lenguaje
El pseudocódigo describe un algoritmo en un lenguaje cercano al español, sin depender de un lenguaje de programación concreto.
En la ordenación de burbuja, ¿qué se hace en cada pasada sobre la tabla?
Respuesta : Se comparan dos vecinos y se intercambian si están mal ordenados
En cada pasada se comparan vecinos mal ordenados y se intercambian, lo que hace subir hacia el final el mayor elemento restante.
En una búsqueda secuencial sobre una tabla no ordenada de 100 elementos, ¿cuántas comparaciones hacen falta como máximo?
Respuesta : 100
En el peor caso hay que recorrer toda la tabla: la búsqueda secuencial compara el elemento buscado con cada casilla, es decir, 100 comparaciones.
En una pila (LIFO), ¿qué elemento se retira primero?
Respuesta : El último elemento añadido
Una pila funciona como una pila de platos: siempre se retira el elemento que está encima.
Medio
En una lista enlazada, ¿qué une dos elementos consecutivos?
Respuesta : Una referencia (un puntero) al elemento siguiente
Cada elemento contiene una referencia, o puntero, al siguiente, lo que evita tener un bloque de memoria continuo.
¿Cuál es la complejidad de acceder al i-ésimo elemento de un arreglo mediante acceso directo?
Respuesta : O(1)
En un arreglo, la dirección del elemento i se calcula directamente, sea cual sea el tamaño del arreglo: es un acceso en tiempo constante.
En un árbol binario de búsqueda, ¿dónde están los valores menores que el de un nodo?
Respuesta : En el subárbol izquierdo
En un árbol binario de búsqueda, los valores inferiores están en el subárbol izquierdo y los superiores en el subárbol derecho.
En un montículo mínimo (min-heap), ¿qué contiene la raíz?
Respuesta : El elemento más pequeño del conjunto
En un montículo mínimo, cada padre es menor que sus hijos, así que la raíz guarda el valor más pequeño.
¿Para qué sirve la función hash en una tabla hash?
Respuesta : Para calcular, a partir de la clave, la posición donde guardar el valor
La función hash transforma una clave en un índice, que indica la posición donde guardar o recuperar el valor.
¿Qué estructura de datos utiliza el recorrido en anchura (BFS) de un grafo?
Respuesta : Una cola
El recorrido en anchura visita los vértices nivel por nivel, gestionando los que quedan por tratar en el orden en que llegaron.
¿Cuál es la complejidad en el peor caso de la ordenación por mezcla?
Respuesta : O(n log n)
La ordenación por mezcla divide el arreglo en mitades y luego fusiona las partes: hay un número logarítmico de niveles, y cada nivel cuesta n.
¿Cuándo alcanza la ordenación rápida (quicksort) su complejidad del peor caso, de O(n²)?
Respuesta : Cuando cada pivote solo separa un elemento de un lado
Si cada pivote solo separa un elemento a un lado, hacen falta unas n particiones sucesivas: es el caso de un pivote ingenuo sobre un arreglo ya ordenado.
Difícil
¿Cuál es la complejidad en memoria auxiliar de una ordenación por mezcla clásica sobre n elementos?
Respuesta : O(n)
La ordenación por mezcla clásica copia los datos en un arreglo temporal durante la fusión, lo que exige un espacio proporcional a n.
¿Cuál es el principal requisito de una ordenación por conteo (counting sort)?
Respuesta : Los valores deben ser enteros dentro de un intervalo conocido y de tamaño razonable
La ordenación por conteo cuenta las apariciones de cada valor entero: necesita, por tanto, claves enteras dentro de un intervalo conocido.
En el algoritmo de Dijkstra, ¿qué condición deben cumplir los pesos de las aristas?
Respuesta : Los pesos deben ser positivos o nulos
Dijkstra fija las distancias en orden creciente, lo que solo es correcto si ningún peso es negativo.
¿En qué propiedades se apoya principalmente la programación dinámica?
Respuesta : Subproblemas que se solapan y una subestructura óptima
Resuelve un problema a partir de subproblemas que se repiten, memorizando sus resultados para no recalcularlos.
¿De qué obra de referencia sobre algoritmia es autor Donald Knuth?
Respuesta : « The Art of Computer Programming »
Donald Knuth escribió « The Art of Computer Programming », cuyo primer volumen se publicó en 1968.
En un árbol AVL, ¿qué propiedad se mantiene para cada nodo?
Respuesta : Las alturas de los dos subárboles difieren como máximo en 1
Un árbol AVL es un árbol binario de búsqueda que reequilibra sus subárboles para que sus alturas difieran como máximo en una unidad.
En un árbol rojo-negro, ¿qué dice la regla sobre los nodos rojos?
Respuesta : Los hijos de un nodo rojo son obligatoriamente negros
En un árbol rojo-negro no pueden encadenarse dos nodos rojos: los hijos de un nodo rojo son negros.
¿Cuál es el papel de la función heurística en el algoritmo A*?
Respuesta : Estimar el coste restante hasta el objetivo para guiar la búsqueda
A* ordena los vértices según el coste ya recorrido más una estimación del coste restante, lo que orienta la búsqueda hacia el objetivo.
Temas relacionados
Jugar a los quizzes de Algoritmos y estructuras de datos