Download Descargar

Carrera: Lic. en Sistemas de Información
Asignatura: Algoritmos y Estructuras de Datos II
Año: 2012
Serie Práctica Nº 4
Listas, Pilas, Colas y Árboles implementadas con Punteros
Objetivo
• Que el alumno se familiarice con los conceptos de punteros y memoria
dinámica.
• Soluciona problemas complejos al dividirlos en subprogramas.
• Realice práctica sobre contenidos de las variables utilizando punteros.
• Aprenda a implementar listas, pilas, colas y árboles con punteros.
• Continúe en la práctica de las operaciones que se pueden realizar con
listas, pilas, colas y árboles independientemente de su implementación.
• Distinga en la práctica sobre la utilización de manejo de listas, pila y/o
colas.
• Implementar la soluciones de problemas con un enfoque estructurado
Metodología
• Lectura de la conceptualización de punteros, memoria dinámica e
implementación de listas, pilas, colas y árboles con punteros.
• El alumno deberá resolver individualmente los ejercicios propuestos
• Se podrá realizar trabajos en grupos para consolidar conceptos,
comprensión de lo solicitado y alternativas de solución.
• El alumno deberá codificar las soluciones que proponga de cada uno de
los ejercicios propuestos en las clases prácticas de laboratorio.
• Interactuar en el aula virtual de la asignatura.
Duración
Según planificación de la asignatura se deberán utilizar para la resolución de los
ejercicios de la serie numero 4, no más de dos (2) clases prácticas.
Ejercicios propuestos sobre práctica de punteros
Ejercicio Nº 1: Dadas las siguiente declaraciones:
a) Qué contiene entonces ApuntI ?
Carrera: Lic. en Sistemas de Información
Asignatura: Algoritmos y Estructuras de Datos II
Año: 2012
Serie Práctica Nº 4
b) Si en seguida ejecutamos la codificación:
qué contendrá entonces ApuntI ? Qué contendrá ApuntI^ ?
Ejercicio Nº 2: Después de ejecutarse el fragmento de codificación
cuáles de las siguientes variables contienen basura?
Ejercicio Nº 3: Supongamos que:
Será entonces legal llamar a New(Eso^) ? Y llamar a New(Eso) ? Explícalo.
Carrera: Lic. en Sistemas de Información
Asignatura: Algoritmos y Estructuras de Datos II
Año: 2012
Serie Práctica Nº 4
Ejercicio Nº 4: Supongamos que:
Cuál de los siguientes enunciados serán legales?
Ejercicio Nº 5: Qué exhibe el siguiente programa?
Ejercicio Nº 6: Dadas las siguientes definiciones y declaraciones
Carrera: Lic. en Sistemas de Información
Asignatura: Algoritmos y Estructuras de Datos II
Año: 2012
Serie Práctica Nº 4
cuál es la salida de los siguientes fragmentos?
Ejercicios de lista enlazada
Ejercicio Nº 7: El departamento de alumnado necesita trabajar con los datos
de los alumnos de la materia Algoritmos y Estructuras de datos II, para ello
implementa una lista simplemente enlazada, donde cada nodo guardará el nro
de libreta universitaria.
a) Crear una función que genere la lista
b) Crear un procedimiento que permita insertar nodos a la lista (para
insertar cada nodo debe verificar que la lista no se encuentre vacía)
c) Crear un procedimiento que permita insertar nodos al final de la lista
(para insertar cada nodo debe verificar que la lista no se encuentre
vacía)
d) Crear un procedimiento que permita Recorrer e imprimir en la pantalla
cada elemento de la lista desde el primero al último.
Carrera: Lic. en Sistemas de Información
Asignatura: Algoritmos y Estructuras de Datos II
Año: 2012
Serie Práctica Nº 4
e) Crear una función que permita calcular la longitud de la lista (número de
elementos que contiene).
f) Crear un procedimiento que permita eliminar un nodo al final de la lista
que coincida con un determinado nro de libreta.
g) Crear un procedimiento que permita eliminar el último o el primer nodo
de la lista.
h) Crear un procedimiento que permita buscar un determinado nro de
libreta en la lista.
i) Crear un procedimiento que permita eliminar todos los elementos de la
lista.
j) Crear un menú principal que contenga todos los ítems anteriormente
solicitado.
Ejercicio Nº 8: En un Centro terapéutico se necesita procesar los datos de los
pacientes que concurren al mismo, para esto implementan una lista enlazada,
donde cada nodo está compuesto por nombre y apellido, edad.
Se debe:
a) Generar la lista
b) Cargar la lista con los datos de los pacientes
c) Recorrerla, calcular y mostrar por pantalla el promedio de edades de los
pacientes que concurren al Centro terapéutico
d) Recorrerla, calcular y mostrar por pantalla el porcentaje de menores de 5
años que concurren, respecto del total de pacientes.
e) Hallar y mostrar por pantalla el nombre y apellido y la edad del paciente
con menor edad.
f) Hallar y mostrar por pantalla el nombre y apellido y la edad del paciente
con mayor edad.
g) Crear un menú principal que contenga todos los ítems anteriormente
solicitado.
Pilas implementada mediante punteros
Ejercicio 9: Desarrolle un programa que permita almacenar en una pila
implementada con punteros, los precios de la compra de productos de un
cliente
a) Crear una función que verifique si la Pila se encuentra vacía.
b) Crear una función que verifique si la Pila se encuentra llena.
Carrera: Lic. en Sistemas de Información
Asignatura: Algoritmos y Estructuras de Datos II
Año: 2012
Serie Práctica Nº 4
c) Crear una función que devuelva la cima de la pila. Verificar que la pila no
esté vacía.
d) Crear un procedimiento que permita Apilar un elemento a la pila, para
ello verificar que la pila no esté llena.
e) Crear un procedimiento que permita Desapilar un elemento de la pila,
para ello verificar que la pila no esté vacía.
f) Crear un procedimiento que permita Mostrar todos los elementos de la
Pila. Verificar que si la pila está vacía.
g) Al final mostrar el valor total de la compra y la cantidad de productos
comprados por el cliente.
h) Crear un menú principal que contenga todos los ítems anteriormente
solicitado.
Colas implementadas mediante punteros
Ejercicio 10: En la mesa de entradas del Banco Patagonia la asesora va dando
números de atención a los clientes que van llegando a la cola
a) Crear una función que verifique si la Cola está vacía.
b) Crear una función que verifique si la cola está llena.
c) Crear una función que devuelva el primer elemento de la Cola. Verificar
que la Cola no esté vacía.
d) Crear un procedimiento que permita Poner un elemento a la cola.
Verificar que si la está llena.
e) Crear un procedimiento que permita Quitar un elemento de la pila.
Verificar que la cola no esté vacía.
f) Crear un procedimiento que permita Mostrar todos los elementos de la
cola. Verificar que si la Cola está vacía.
g) Al final, Informar la cantidad de clientes que fueron atendidos.
h) Crear un menú principal que contenga todos los ítems anteriormente
solicitado.
Arboles implementadas mediante punteros
Ejercicio Nº 11: Crear un Árbol con su nodo raíz, inserte un primer elemento y
verificar con una función si el árbol está vacío, implementar un menú interactivo
con el siguiente diseño.
1. Crear Árbol.
2. Insertar un Elemento.
Carrera: Lic. en Sistemas de Información
Asignatura: Algoritmos y Estructuras de Datos II
3. Estado del Árbol.
Año: 2012
Serie Práctica Nº 4
Ejercicio Nº 1 2: Construir un árbol binario correspondiente a la lista
de números:
4 19 –7 49 100 0 22 12
a) Nodo raíz del árbol: primer elemento de la lista
b) Los siguientes nodos serán descendientes derechos si son mayores y
descendientes izquierdo si son menores. (Tener en cuenta el orden de la lista
dada)
Ejercicio Nº 1 3: Recorrido de un árbol. Indique el recorrido en pre-orden,
in- orden y post-orden del árbol del ejercicio anterior (Ejercicio Nº 2).
Mostrar el recorrido por pantalla
Ejercicio Nº 1 4: C r e a r una función que busque un dato “X” en el árbol
completo, por ramas y hojas. Mostrar por pantalla si el elemento fue
encontrado. Utilizar el árbol del ejercicio 2.
Ejercicio Nº 1 5: Agregue PROCEDIMIENTO que elimine un nodo con un
contenido “X” y luego muestre por pantalla el árbol ya actualizado.
Ejercicio Nº 1 6: Crear un PROCEDIMIENTO que elimine todos los nodos del
árbol e implementar al algoritmo escrito en los puntos anteriores.