CS50 > Week 5- Lecture (Data Structure) > Flashcards

Week 5- Lecture (Data Structure) Flashcards

(65 cards)

Study These Flashcards
1
Q

¿Qué es un Tipo de Dato Abstracto (ADT)?

A

Un modelo que define las operaciones y comportamiento de una estructura sin detallar su implementación técnica.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

¿Cuál es la propiedad fundamental de una cola (queue)?

A

FIFO (First In, First Out): el primer elemento en entrar es el primero en salir.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

En una cola, ¿cómo se llama la operación de ponerse en línea?

A

Enqueue.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

En una cola, ¿cómo se llama la operación de salir de la línea por el frente?

A

Dequeue.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

¿Cuál es la propiedad fundamental de una pila (stack)?

A

LIFO (Last In, First Out): el último elemento en entrar es el primero en salir.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

¿Qué término se usa para añadir un elemento a la parte superior de una pila?

A

Push.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

¿Qué término se usa para remover el elemento superior de una pila?

A

Pop.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

¿Cuál es la principal limitación de implementar colas o pilas mediante arreglos estáticos?

A

Tienen una capacidad fija determinada en el momento de la compilación.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

¿Qué significa que los valores en un arreglo sean ‘contiguos’ en memoria?

A

Que los datos se almacenan uno inmediatamente después del otro en direcciones de memoria consecutivas.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

¿Cuál es el beneficio de usar Python en lugar de C según la lección?

A

Permite resolver problemas más rápido como humanos, aunque la ejecución del código puede ser más lenta.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

¿Qué par de conceptos componen la estructura de un diccionario?

A

Llave (key) y Valor (value).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

La función malloc devuelve _____ si no puede asignar la memoria solicitada.

A

NULL

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

¿Por qué es peligroso asignar un nuevo valor a un puntero de malloc sin liberar el anterior?

A

Se produce una fuga de memoria (memory leak) al perder la dirección del bloque original.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

¿Qué hace la función realloc en C?

A

Redimensiona un bloque de memoria previamente asignado, intentando expandirlo o copiándolo a una nueva ubicación.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

¿Qué es un ‘nodo’ en el contexto de las estructuras de datos?

A

Un contenedor que incluye datos y metadatos (como punteros a otros nodos).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

¿Cuáles son los dos campos básicos de un nodo en una lista enlazada (linked list)?

A

El dato (como un entero) y un puntero al siguiente nodo (next).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

¿Cómo se indica el final de una lista enlazada en C?

A

Asignando el valor NULL al puntero next del último nodo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

¿Cuál es el tiempo de ejecución de búsqueda en una lista enlazada de tamaño $n$?

A

$O(n)$

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

¿Qué operador de C se utiliza para acceder a un campo de una estructura a través de un puntero?

A

El operador flecha (->).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

En una lista enlazada, la operación de inserción al inicio (prepend) tiene un tiempo de ejecución de _____.

A

$O(1)$

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

¿Por qué no se puede realizar una búsqueda binaria eficiente en una lista enlazada estándar?

A

Porque no se puede acceder directamente al elemento central sin recorrer la lista secuencialmente.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

¿Qué es la ‘raíz’ (root) en una estructura de árbol?

A

El nodo superior desde el cual se originan todos los demás nodos.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

¿Qué define a un Árbol Binario de Búsqueda (BST)?

A

Cada nodo tiene un hijo izquierdo menor y un hijo derecho mayor que él mismo.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

¿Cuál es el tiempo de ejecución promedio para buscar en un BST balanceado?

A

$O(\log n)$

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
¿Qué sucede con el rendimiento de un BST si los datos se insertan en orden secuencial (por ejemplo, 1, 2, 3)?
El árbol se desbalancea y se convierte funcionalmente en una lista enlazada con tiempo de búsqueda $O(n)$.
26
¿Cuántos punteros contiene cada nodo en un Árbol Binario de Búsqueda típico?
Dos punteros: uno para el hijo izquierdo (`left`) y uno para el hijo derecho (`right`).
27
¿Qué es una función de hash (hash function)?
Un algoritmo que mapea un dominio infinito de entradas a un rango finito de índices numéricos.
28
¿Qué ocurre en una tabla hash cuando dos entradas diferentes generan el mismo índice?
Se produce una colisión.
29
¿En qué consiste la técnica de 'encadenamiento' (chaining) en tablas hash?
En almacenar múltiples elementos en el mismo índice utilizando una lista enlazada.
30
¿Cuál es el tiempo de ejecución ideal (teórico) para la búsqueda en una tabla hash?
$O(1)$
31
¿Cuál es el compromiso (trade-off) al usar una tabla hash con muchos 'buckets'?
Se reduce la probabilidad de colisiones y aumenta la velocidad, pero se utiliza mucho más espacio de memoria.
32
¿Qué es un 'Trie' (o árbol de recuperación)?
Un árbol donde cada nodo contiene un arreglo de punteros que representan letras o caracteres.
33
¿De qué depende el tiempo de búsqueda en un Trie?
De la longitud de la palabra buscada, independientemente de cuántos elementos hay en la estructura.
34
¿Cuál es la principal desventaja del uso de Tries?
El consumo masivo de memoria debido a que cada nodo contiene un arreglo completo de punteros.
35
¿Por qué es necesario liberar la memoria de una lista enlazada nodo por nodo al terminar?
Porque `free` solo libera el bloque de memoria específico de la dirección que recibe, no los nodos hijos.
36
Concepto: Nodo Hoja (leaf node)
Definición: Un nodo en una estructura de árbol que no tiene hijos (sus punteros son `NULL`).
37
¿Qué significa que una estructura de datos sea 'recursiva'?
Que la estructura se define en términos de sí misma (ej. un árbol está compuesto por sub-árboles).
38
¿A qué familia de estructuras pertenece el sistema de repisas de Sweetgreen para recoger pedidos?
Tablas Hash.
39
¿Qué ventaja ofrece el uso de una variable temporal al emplear `realloc`?
Evita perder la dirección del bloque original en caso de que `realloc` falle y devuelva `NULL`.
40
¿Cómo se calcula el índice alfabético 0-25 de una letra mayúscula 'c' en C?
Restando el valor ASCII de 'A' a la variable: `c - 'A'`.
41
¿Qué término describe el tiempo de ejecución que no cambia sin importar el tamaño de los datos?
Tiempo constante ($O(1)$).
42
En una lista enlazada, para borrar el primer nodo sin perder el resto de la lista, primero debemos _____.
guardar la dirección del segundo nodo como la nueva cabeza de la lista
43
¿Cuál es la función de la palabra clave `struct` en C?
Permite crear un tipo de dato personalizado que agrupa múltiples variables bajo un mismo nombre.
44
Un Árbol Binario de Búsqueda balanceado tiene una altura de aproximadamente _____.
$\log_2 n$
45
¿Qué es un puntero `NULL`?
Un puntero que apunta a la dirección 0, utilizado para indicar que no apunta a ninguna dirección válida.
46
¿Cuál es la diferencia entre capacidad y tamaño en un ADT de pila?
La capacidad es el límite máximo de elementos, mientras que el tamaño es el número actual de elementos presentes.
47
En una tabla hash con encadenamiento, el tiempo de búsqueda en el peor de los casos es _____.
$O(n)$
48
¿Cómo se llama el proceso de reorganizar un BST para que sea balanceado?
Rebalanceo (rebalancing).
49
¿Qué sucede con la memoria fragmentada en el contexto de listas enlazadas?
Las listas enlazadas pueden aprovecharla porque sus nodos no necesitan estar en bloques contiguos.
50
¿Qué biblioteca de C contiene las declaraciones de `malloc` y `free`?
`stdlib.h`
51
Al insertar un nodo en una lista enlazada ordenada, ¿qué paso es crítico antes de actualizar el puntero del nodo anterior?
Conectar el puntero `next` del nuevo nodo al resto de la lista existente.
52
¿Qué es un 'puntero de puntero' en el contexto de las tablas hash?
Es el tipo de dato de un arreglo de listas enlazadas (`node **`).
53
¿Por qué un arreglo es generalmente más rápido para el acceso aleatorio que una lista enlazada?
Porque permite el acceso directo mediante índices en lugar de requerir una navegación secuencial.
54
En una implementación de cola, la operación de 'dequeue' se realiza típicamente en el _____ de la estructura.
Frente (front)
55
¿Cuál es el costo en espacio de cada nodo adicional en un BST?
El tamaño del dato más el tamaño de dos punteros (típicamente 16 bytes extra en sistemas de 64 bits).
56
¿Qué propiedad del Trie lo hace ideal para autocompletado de palabras?
La estructura permite seguir prefijos letra por letra a través de los nodos.
57
Para imprimir una lista enlazada de forma recursiva, la condición de parada (base case) es _____.
cuando el puntero actual es `NULL`
58
¿Qué indica el prefijo `unsigned` en un tipo de dato `int`?
Que la variable solo puede almacenar valores positivos o cero.
59
¿Qué sucede si intentas redimensionar un arreglo estático usando `realloc`?
No se puede, ya que `realloc` solo funciona con memoria asignada dinámicamente con `malloc` o similar.
60
El operador `*` seguido de un nombre de variable en una declaración (ej. `node *n`) indica que `n` es un _____.
Puntero
61
¿Cuál es la función de la sentencia `typedef`?
Permite asignar un nombre nuevo o alias a un tipo de dato existente.
62
En un BST, ¿dónde se encontraría el valor más pequeño de todo el árbol?
En el nodo situado más a la izquierda de todos.
63
¿Cuál es la complejidad temporal de insertar un elemento en un Trie de una palabra de longitud $L$?
$O(L)$
64
¿Qué es 'syntactic sugar' en programación?
Sintaxis diseñada para ser más fácil de leer o escribir sin cambiar la funcionalidad (ej. `a[i]` en lugar de `*(a + i)`).
65
¿Por qué el orden de inserción importa en un BST pero no en una Tabla Hash con encadenamiento?
En el BST determina el balance del árbol; en la Tabla Hash el balance lo determina la función de hash.
CS50
flashcards
Decks in class (11)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions