Programación II con Pascal

Question	Answer
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

Next up

Programación II con Pascal

Description

Resource summary

Similar

	Created by Ana A almost 6 years ago