14018736
| Questão | Responda |
|
Pilas y colas (estáticas)
Inserciones y eliminaciones en una pila
Image:
Pila (binary/octet-stream)
|
Los elementos se añaden o se borran por un extremo (cima).
Estructura LIFO
Image:
Libros (binary/octet-stream)
|
| Pilas y colas (estáticas) Inserciones y eliminaciones en una cola | Los elementos se añaden por un extremo (frente) y se eliminan por el otro (final). Estructura FIFO |
| Pilas y colas (estáticas) Pila vacía y pila llena |
Image:
1 (binary/octet-stream)
|
| Pilas y colas (estáticas) Código para insertar en una pila | Cima := Cima + 1 Pila[Cima] := nuevo_elemento |
| Pilas y colas (estáticas) Código para eliminar en una pila | Eliminar := Pila[Cima] Cima := Cima - 1 |
| Pilas y colas (estáticas) Tipo registro para una pila | Pila = record Cima: 0..MaxPila; Elementos: array[1..MaxPila] of TipoElementoPila end; |
| Pilas y colas (estáticas) Inicializar una pila | Pila.Cima := 0 |
| Pilas y colas (estáticas) Comprobar si la pila está llena | PilaLlena := Pila.Cima >= MaxPila |
| Pilas y colas (estáticas) Operación para obtener la cima de la pila | La cima debe de ser > 0 CimaPila := Pila.Elementos[Pila.Cima] |
| Pilas y colas (estáticas) ¿Qué tipo de array usarías para leer una palabra y visualizarla en orden inverso? | Una pila. 1. Crear pila vacía de caracteres. 2. Meter cada carácter en la pila. 3. Sacar cada carácter y visualizarlo. 4. Indicar si la pila está vacía o llena |
| Pilas y colas (estáticas) Ventaja cola con array circular | Evita el desplazamiento de los elementos a la izquierda que hay que realizar cuando vamos insertando elementos y llegamos al final. |
| Pilas y colas (estáticas) Tipo registro cola | TipoCola = record ini, fin: 0..MaxCola; elemento: ArrayCola end; |
| Pilas y colas (estáticas) Inicializar Cola | Q.ini := 0 Q.fin := 0 |
| Pilas y colas (estáticas) Comprobar que la cola está vacía | ColaVacia := (Q.ini = Q.fin) |
| Pilas y colas (estáticas) Comprobar que la cola está llena | if Q.ini + 1 = MaxCola then Siguiente := 0 else Siguiente := Q.fin + 1 ColaLlena := Siguiente = Q.Frente Se mantiente una posición vacía para diferenciarlo de la Cola Vacía |
| Pilas y colas (estáticas) Código para insertar elemento en una cola | (with Q do) Elementos[fin] := nuevo fin := Siguiente |
| Pilas y colas (estáticas) Código para eliminar elemento en una cola | (with Q do) elemento := Elementos[ini] ini := (ini + 1) mod MaxCola |
| Pilas y colas (estáticas) Cola de prioridad | 1. Se asocia una prioridad con cada elemento. 2. Los elementos con mayor prioridad están cerca del frente. 3. Si dos elementos tienen misma prioridad, se procesan según el orden en el que se añadieron. |
| Pilas y colas (estáticas) ¿En qué tipo de programas se usan? | 1. Las pilas se utilizan en aplicaciones de recursividad y conversión de expresiones y notaciones. 2. Las colas se utilizan para realizar listas de espera y problemas de simulación. |
| Diferencia memoria estructura de datos estática y estructura de datos dinámica | En las estáticas tenemos una memoria fija, mientras que en las dinámicas el tamaño de memoria varía según las necesidades. |
| Punteros ¿Para qué son necesarios los punteros? | Permiten la creación de estructuras de datos dinámicas |
| Punteros ¿Cuándo se almacenan y se liberan las variables dinámicas? | Durante la ejecución. |
| Punteros ¿Cómo es una estructura de datos dinámica? | Colección de elementos (nodos) que se enlazan asociando con cada nodo un puntero que apunta al nodo siguiente. |
| Punteros Diferencia variable puntero y variable dinámica | La variable puntero (P) contiene la dirección de la posición de memoria donde está la variable dinámica (^P). La variable dinámica contiene un elemento de cualquier tipo. |
| Punteros Declaración de un puntero | Puntero: ^TipoElementoApuntado Sintaxis: P |
| Punteros Inicializar un puntero | New (Puntero) Crea espacio para el tipo de la variable dinámica. |
| Punteros ¿Por qué debemos usar la operación New si ya hemos declarado el puntero? | La declaración de un puntero no crea un nodo para apuntar a él. Con New, se crea una variable dinámica para que sea apuntada por la variable puntero. |
| Punteros ¿Dónde se almacenan las variables dinámicas? | Se almacenan en el montículo (heap) y debe de haber espacio suficiente para que no aparezca un error. |
| Punteros Valor basura de una variable dinámica | Cuando hacemos un New, el contenido de la variable dinámica se desconoce. Cuando hacemos un Dispose, el puntero no sabemos hacia dónde queda apuntando. |
| Punteros ¿Cuándo escribir el circunflejo a la izquierda o a la derecha de una variable dinámica? | Se escribe a la izquierda cuando declaramos su tipo, como ^char Se escribe a la derecha en una sentencia que accede al nodo que se está apuntando, como puntero^ |
| Punteros ¿Es posible que más de un puntero esté apuntando a la misma variable dinámica? | Sí. p := q |
| Punteros ¿Pueden tener el mismo contenido dos variables dinámicas? | Sí. p^ := q^ |
| Punteros ¿Un puntero de tipo integer puede apuntar a otro puntero de tipo real? | No. Un puntero siempre debe apuntar a un elemento del mismo tipo. |
| Punteros Eliminar una variable dinámica | Dispose (P) Destruye la variable referenciada por P y libera dicho espacio. El valor de P queda indefinido. |
| Punteros Valor nulo en una variable puntero | p := nil El puntero no apunta a ninguna posición de memoria. |
| Punteros Comparación de variables puntero | Comparados solo en expresiones de igualdad. if (PunteroA = PunteroB) if (PunteroA <> PunteroB) |
| Punteros Comparación de variables dinámicas | No existe ningún problema para comparar. if (PunteroA^ <= PunteroB^) ... |
| Punteros ¿Cuándo pasamos un puntero como parámetro? | En caso de listas enlazadas, por ejemplo, pasamos el puntero que apunta a su primer elemento. |
| Listas enlazadas (dinámicas) Definición lista enlazada | Secuencia de nodos que están enlazados con el siguiente mediante un puntero. |
| Listas enlazadas (dinámicas) Campos del registro para cada nodo | 1. L^.Dato. 2. L^.Siguiente. |
| Listas enlazadas (dinámicas) ¿Cómo sabemos que hemos llegado al último elemento de la lista? | L^.siguiente := nil |
| Listas enlazadas (dinámicas) Punteros adicionales en una lista | 1. Cabeza (apunta al primer nodo de la lista) 2. Ultimo (apunta al último nodo de la lista) |
| Listas enlazadas (dinámicas) Crear Lista | Una vez creado el primer nodo: 1. Utilizar puntero Aux para asignar espacio. 2. Situar los nuevos datos en la posición Aux y fijar Siguiente a nil. 3. Añadir el elemento a la lista. 4. Hacemos que Ultimo apunte al nuevo elemento. |
| Listas enlazadas (dinámicas) Recorrer lista | 1. Hacemos que Aux apunte a Cabeza. 2. Mientras el puntero actual no sea nil: 2.1. Escribir campo dato del nodo. 2.2. Hacemos que Aux apunte al siguiente. |
| Listas enlazadas (dinámicas) Eliminar nodo de la lista (excepto el primero) | Anterior^.siguiente := Actual^.siguiente |
| Listas enlazadas (dinámicas) Borrado del primer nodo de la lista | Cabeza := Actual^.Siguiente |
| Listas enlazadas (dinámicas) ¿Es necesario usar dispose en el proceso de borrado? | No necesario, pero es conveniente ya que sino no se libera ese espacio. |
| Listas enlazadas (dinámicas) Insertar un nodo entre nodos | Nuevo^.Siguiente := Actual Anterior^.Siguiente := Nuevo new(nuevo) |
| Listas enlazadas (dinámicas) Insertar un nodo al principio de la lista | Nuevo^.Siguiente := Cabeza Cabeza := Nuevo |
| Listas enlazadas (dinámicas) Insertar un nodo al final de la lista | Actual := nil Nuevo^.Siguiente := Actual Anterior^.Siguiente := Nuevo |
| Listas enlazadas (dinámicas) Inicializar lista | Lista := nil |
| Listas circulares (dinámicas) Concepto de lista circular | El puntero Siguiente al último nodo apunta hacia el primer nodo. No existe ni primero ni último elemento. |
| Listas circulares (dinámicas) Ventajas e inconvenientes de una lista circular | Ventaja: Cada nodo es accesible desde cualquier nodo. Desventaja: Es fácil caer en un bucle infinito. |
| Listas circulares (dinámicas) Insertar un nodo | Si la lista está vacía: if Despues = nil then Despues := Nuevo Si la lista no está vacía: Nuevo^.Enlace := Despues^.Enlace Despues^.Enlace := Nuevo |
| Listas circulares (dinámicas) Eliminar un nodo | if Despues <> nil then Aux := Despues^.Enlace if Despues = Aux then Despues := nil else Despues^.Enlace := Aux^.Enlace Dispose (Aux) |
| Listas circulares (dinámicas) ¿Qué inconveniente de las listas enlazadas resuelve una lista circular? | En las listas enlazadas no se pueden alcanzar ninguno de los nodos que preceden al que nos interesa por lo que, para recorrer una lista, el puntero original al principio de la lista debe ser guardado para poder referenciar de nuevo la lista. |
| Listas doblemente enlazadas (dinámicas) Diferencia de lista enlazada y lista doblemente enlazada | La lista doblemente enlazada tendrá un campo más en sus nodos, que corresponderá con el puntero Anterior, por lo que se puede recorrer en los dos sentidos. |
| Listas doblemente enlazadas (dinámicas) Tipos de listas doblemente enlazadas | 1. Lineal. 2. Circular. 3. Circular con un nodo cabecera. |
| Pila (dinámica) ¿Qué inconveniente de las pilas estáticas resuelven las pilas dinámicas? | En las pilas estáticas, se pierde tiempo de compilación al tener que especificar el tamaño del array, lo cual es una limitación importante por el frecuente uso de ésta. |
| Pila (dinámica) Concepto de una pila dinámica | Es una lista enlazada en la cual se realizan las inserciones y eliminaciones en la cabecera de la lista. |
| Pila (dinámica) Poner un dato en la pila | new (NuevoPunteroCima) NuevoPunteroCima^.Item := NuevoItem NuevoPunteroCima^.Siguiente := Pila |
| Pila (dinámica) Quitar un dato de la pila | PunteroCima := Pila Pila := Pila^.Siguiente dispose (PunteroCima) |
| Pila (dinámica) Obtener el dato de la cima | CimaPila := Pila^.Item |
| Colas (dinámicas) Crear una cola | Q.frente := nil Q.final := nil |
| Colas (dinámicas) Comprobar que la cola está vacía | if (Q.frente = nil) then ColaEsVacia := true |
| Colas (dinámicas) Obtener el dato del frente de la cola | Item := Q.frente^.item |
| Colas (dinámicas) Insertar nodo | New(NuevoPunteroFrente) NuevoPunteroFrente^.Item := NuevoItem NuevoPunteroFrente^.Siguiente := nil if ColaEsVacia(Q) then Q.frente := NuevoPunteroFrente else Q.final^.siguiente := NuevoPunteroFrente Q.Final := NuevoPunteroFrente |
| Colas (dinámicas) Eliminar nodo | PunteroFrente := Q.frente Item := PunteroFrente^.item Q.frente := Q.frente^.siguiente if Q.frente = nil then Q.final := nil dispose (PunteroFrente) |
| Técnicas de programación ¿Se pueden realizar operaciones aritméticas sobre punteros? | No. Hay que recordar que los punteros solo contienen una dirección de memoria de otra variable. |
| Técnicas de programación ¿Pueden leerse o visualizarse los punteros? | No, puesto que su contenido es una dirección de memoria de otra variable. |
| Árboles (dinámicos) Tipos de nodos en un árbol | 1. Padre 2. Hijo 3. Hermano 4. Raíz 5. Hoja |
| Árboles (dinámicos) Subárbol | Un subárbol de un árbol es cualquier nodo del árbol junto con todos sus descendientes. Un subárbol de un nodo es un subárbol enraizado en un hijo del nodo. |
| Árboles (dinámicos) Camino | Secuencia de nodos conectados dentro de un árbol. |
| Árboles (dinámicos) Longitud del camino | Número de nodos menos uno (r - 1) |
| Árboles (dinámicos) Altura o nivel del árbol | Longitud del camino desde la raíz hasta la hoja más lejana. |
| Árboles (dinámicos) Altura de un nodo | Longitud del camino desde el nodo hasta la hoja más lejana + 1 |
| Árboles (dinámicos) Grado (aridad) de un nodo | Número de hijos que tiene el nodo |
| Árboles (dinámicos) Nodos hermanos | Son dos nodos que tienen el mismo padre y se llamarán hermano izquierdo y hermano derecho, respectivamente. |
| Árbol binario Concepto | Es un árbol en el que cada nodo no puede tener más de dos hijos. |
| Árbol binario Estructura | Nodo raíz cuyos descendientes serán un subárbol izquierdo y un subárbol derecho. |
| Árbol binario ¿En qué nivel se encontrará la raíz? | En el nivel 1. |
| Árbol binario ¿Cuándo se dice que un árbol binario está equilibrado? | Cada nodo tiene exactamente dos hijos o ninguno y todas las están al mismo nivel. |
| Árbol binario ¿Cuál es el tipo de estructura de datos que utiliza? | Recursiva, pues cada subárbol se define como un árbol más simple. |
| Árbol binario Árbol binario completo | Cada nodo tiene o bien dos hijos o ningún hijo. |
| Árbol binario Comprobar altura de un árbol binario | altura(T) = 1 + max(altura(TIzq), altura(TDer)) |
| Árbol binario Árbol binario lleno | Todos los nodos que están a un nivel menor que la altura del árbol tienen dos hijos. Siempre será completo y estará totalmente equilibrado. |
| Árbol binario Tipos de recorrido | 1. Preorden: raíz-izq-der 2. Enorden: izq-raíz-der 3. Postorden: izquierdo-derecho-raíz |
| Árbol binario Campos de un nodo | 1. Dato 2. Puntero Izquierdo 3. Puntero Derecho |
| Árbol binario Crear nueva hoja | new (NuevoItemPuntero) NuevoItemPuntero^.Dato := Num NuevoItemPuntero^.Izdo := nil NuevoItemPuntero^.Dcho := nil |
| Árbol binario Comprobar si un nodo es una hoja | EsHoja := (Nodo^.Izdo = nil) and (Nodo^.Dcho = nil) |
| Árbol binario Recorrido enorden | EnOrden(A^.HijoIzdo) writeln(A^.Nombre) EnOrden(A^.HijoDcho) |
| Árbol binario Recorrido preorden | 1. Ver datos en raíz 2. preorden (subárbol izquierdo de la raíz) 3. preorden (subárbol derecho de la raíz) |
| Árbol binario Recorrido postorden | 1. postorden (subárbol izquierdo de la raíz) 2. postorden (subárbol derecho de la raíz) 3. Ver datos en raíz |
| Árbol binario de búsqueda Concepto | Dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus propios datos. |
| Árbol binario de búsqueda Crear un nodo con dos hijos nil | new(P) P^.Info := simbolo P^.Izdo := nil P^.Dcho := nil SubArbol := P |
| Árbol binario de búsqueda Insertar nodo como hijo izquierdo | P^.Izdo := Subarbol(simbolo) |
| Árbol binario de búsqueda Insertar nodo como hijo derecho | P^.Dcho := SubArbol(simbolo) |
| Árbol binario de búsqueda Tipo de recorrido | Usaremos el recorrido enorden. Enorden(P^.Izdo) write(P^.Clave) Enorden(P^.Dcho) |
| Árbol binario de búsqueda Generar ABB | SubArbol(Simbolo) ArbolIzdo(P) ArbolDcho(P) |
| Árbol binario de búsqueda Contar nodos | if P = nil then Nodos := 0 else Nodos := 1 + Nodos(P^.Izdo) + Nodos(P^.Dcho) |
| Árbol binario de búsqueda Búsqueda de un nodo | 1. Se compara la clave buscada con la clave del nodo raíz. 2. Si las claves son iguales, la búsqueda se detiene. 3. Si la clave buscada es mayor que la raíz, la búsqueda se reanuda en el subárbol derecho. 4. Si la clave buscada es menor que la raíz, la búsqueda se reanuda en el subárbol izquierdo. |
| Árbol binario de búsqueda Inserción de un nodo | 1. Asignar memoria para el nuevo nodo. 2. Buscar en el árbol la posición donde se va a insertar, como nodo hoja. 3. Enlazar el nuevo nodo al árbol. |
| Árbol binario de búsqueda Eliminación de un nodo | 1. Buscar la posición del nodo a eliminar. 2. Si el nodo a suprimir tiene menos de dos hijos, reajustamos los punteros de sus antecesores. 3. Subir a la posición del nodo a eliminar el nodo más próximo en clave. |
| Árbol binario de búsqueda ¿Cuándo es ineficaz? | En casos en los que el árbol es degenerado (no tiene ningún equilibrio) |
| Árbol binario de búsqueda Comprobar altura | if T = nil then Altura := 0 else Altura := 1 + Max(Altura(T^.Izdo), Altura(T^.Dcho)) |
| Memoria ¿En qué dos lugares de la memoria almacenamos datos? | En la pila y el montículo. |
| Memoria ¿Quién determina el tamaño del código y de los datos estáticos? | El compilador |
| Memoria ¿Puede variar el tamaño de la pila y del montículo? | Sí, de hecho varía en el tiempo de ejecución |
| Memoria ¿Hacia qué dirección crecen la pila y el montículo generalmente? | La pila suele crecer hacia abajo y el montículo hacia arriba, aunque hay excepciones en las que pueden estar intercambiados. |
| Memoria Cuando llamamos a una función o procedimiento, ¿dónde se reserva el espacio para ella? | En la pila |
| Tipos abstractos de datos (TAD) Definición | Es un tipo definido por el programador, con una determinada especificación e implementación asociadas. |
| Árboles equilibrados AVL Definición | ABB en los que para cada nodo la diferencia de altura de sus subárboles nunca es mayor que uno. |
| Árboles equilibrados AVL Factor de equilibrio | Fe(N)= h nodo dcho - h nodo izdo |
| Árboles equilibrados AVL Diferencia con un ABB | Para las operaciones de inserción y eliminación necesitará realizar también rotaciones para mantener al árbol equilibrado. |
| Árboles equilibrados AVL Rotación II | Arbol^.izdo:= Aux1^.dcho Aux1^. dcho := Arbol Arbol:= Aux1 |
| Árboles equilibrados AVL Rotación DD | Arbol^.dcho:= Aux1^.izdo Aux1^.izdo := Arbol Arbol:= Aux1 |
| Árboles equilibrados AVL Rotación ID | 1. Aux2:= Aux1^.dcho 2. Arbol^.izdo:= Aux2^.dcho 3. Aux1^.dcho:= Aux2^.izdo 4. Aux2^.dcho := Arbol 5. Aux2^.izdo := Aux1 6. Arbol:= Aux2 |
| Árboles equilibrados AVL Rotación DI | 1. Aux2:= Aux1^.izdo 2. Arbol^.dcho := Aux2^.izdo 3. Aux1^.izdo := Aux2^.dcho 4. Aux2^.izdo := Arbol 5. Aux2^.dcho := Aux1 6. Arbol := Aux2 |
Quer criar seus próprios Flashcards gratuitos com GoConqr? Saiba mais.