Aplicaciones de Pilas y Colas

Vista previa del material en texto

UNIVERSIDAD TECNOLÓGICA DE PANAMÁ 
FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES 
DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE 
SISTEMAS 
ESTRUCTURAS DE DATOS I 
Taller N. 2 Aplicaciones de las Estructuras de Datos de Pilas y Colas 
 
 Nombre de la Asignatura: Estructura de Datos I 
 Módulo 1: Estructura de Datos Fundamentales y Lineales 
 Capítulo 2: Estructura de Datos Lineales y Recursividad 
 Docente Responsable: Yolanda de Miguelena 
 Fecha: Semana 11 
 Objetivo: 
✓ Resolver problemas, aplicando los algoritmos de las estructuras de datos de pilas y colas. 
 Recursos: Plataforma virtuales de apoyo académico, Internet, Computador. Instrucciones: 
Recursos: Plataforma virtuales de apoyo académico, Internet, Computador. Instrucciones: 
✓ Resolver en grupo de 3-4 estudiantes. Para obtener nota es necesario 
 estar presente en el salón de clase para el desarrollo del taller. 
✓ El trabajo debe ser entregado a través de la plataforma Moodle en 
http://ecampus.utp.ac.pa/moodle/ en un archivo con Formato pdf. Solo lo sube uno (1) del 
grupo). 
✓ El archivo con formato pdf debe tener lo siguiente: 
1. Hoja de presentación (Utilice el formato dado). 
2. Cada problema con sus respuestas (Sólo coloque la solución). 
Rúbrica: 
Este Taller tendrá una puntuación total de 100, donde la evaluación se basa en los aspectos de: No 
cumple (1), Cumple con menos de la mitad (2), Cumple con más de la mitad (3) y Cumple en su 
totalidad (4). Los puntos que se evaluará en la rúbrica se muestran en la tabla: 
 
Michael Aparicio – Omar Sánchez – Rubén Rivera – Luis Murcia 
ENUNCIADOS 
 
 Problema N. 1 
 
Mostrar paso a paso cada una de las sentencias que se escribe en el siguiente segmento de código. 
La pila es una estructura de datos que almacenará datos tipo enteros, P, Q y R son variables enteras. 
 
CRITERIOS PARA EVALUAR 
 
CATEGORÍAS 
 1 2 3 4 
1. Presentación (0 – 5 pts.) 
 El trabajo es ordenado y estructurado, buena ortografía, sigue 
 las indicaciones y cumple con el formato de la portada. 
 
2. Contenido (0 – 75 pts.) 
 Se presenta lo solicitado en el enunciado del trabajo (Grupal 65 pts.) 
 Cada participante del grupo debe presentar la solución (Individual 10 pts.) 
 
 
3. Entrega del Trabajo en la Plataforma Moodle (20 pts.) 
 
 Entrega el trabajo el día y la hora en la plataforma. 
 
Por cada operación muestre el diagrama de la pila y el valor de la variable Tope. La pila está 
inicialmente vacía (tope = 0) y que tiene la capacidad de almacenamiento libre. 
 
P = 5 
Q = 0 
R = 4 
 Insertar (PILA, R) 
 Insertar (PILA, P) 
 Insertar (PILA, P + R) 
 Eliminar (PILA, Dato) 
P = Dato 
 Insertar (PILA, R) 
 Insertar (PILA, Q) 
 Eliminar (PILA, Dato) 
Q = Dato 
 Insertar (PILA, 3) 
 Eliminar (PILA, Dato) 
 Insertar (PILA, 8 + 2) 
R = Dato 
Imprimir (“P = “, 9) 
Imprimir (“Q = “, 0) 
Imprimir (“R = “, 10) 
FIN 
 
Problema N. 2 
 
Convertir las siguientes expresiones infijas a Prefija y Postfija. (Muestre los pasos de la solución) 
 
EXPRESIÓN INFIJA EXPRESIÓN PREFIJA EXPRESIÓN POSTFIJA 
1) (Z - (((X + 1) * 2) - 5) / Y) (Z - (((X + 1) * 2) - 5) / Y) 
(Z-((+X1)*2)-5)/Y) 
(Z-((*+X12)-5)/Y) 
(Z-(-*+X125)/Y) 
(Z-(/-*+X125Y)) 
-Z/-*+X125Y 
(Z - (((X + 1) * 2) - 5) / Y) 
(Z-(((X1+)*2)-5)/Y) 
(Z-((X1+2*)-5)/Y) 
(Z-((X1+2*5-)/Y) 
Z-X1+2*5-Y/ 
ZX1+2*5-Y/- 
1) 1 + 3 * 9 + (5 * (4 + 2)) 1 + 3 * 9 + (5 * (4 + 2)) 
1+3*9+(5*(+42)) 
1+3*9+(*5+42) 
1+*39+*5+42 
+1+*39*5+42 
1 + 3 * 9 + (5 * (4 + 2)) 
1+3*9+(5*(42+)) 
1+3*9+(542+*) 
1+39*+542+* 
139*+542+*+ 
2) (7 -3) ^ 2 + (15 – 5) / (6 – 1) (7 -3) ^ 2 + (15 – 5) / (6 – 1) 
-73 ^ 2+-155/-61 
^-732+-155/-61 
^-732+-/155-61 
+^-732-/155-61 
(7 -3) ^ 2 + (15 – 5) / (6 – 1) 
73-^2+155-/61- 
73-2^+155-/61- 
73-2^+155-61-/ 
73-2^155-61-/+ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 
 
 
 
 
5 
4 
 
 
 
 
 
9 
 
 P = 9 
 
 
 
 
4 
 
 
 
 
 
 
 
 
 
 
0 
4 
 
 
 
 
 
4 
 
Q = 0 
 
 
 
 
 
 
 
 
 
 
3 
 
 
 
 
 
10 
 
 
 
 
 
 
 
 
 
 
 
 
 
R = 10 
 
 
 
 
8 
 
 
 
 
2 
8 
 
Problema N. 3 
 
Para cada enunciado indicar si se aplica una estructura de dato tipo pila. 
 
ENUNCIADOS 
 
SI/NO 
1. Un banco quiere simular su operación de caja para ver cuánto tiempo 
de espera podría reducirse añadiendo otra caja. 
SI 
2. Un programa recibe datos que se guardan y procesan en orden inverso. NO 
3. Un programa que lleve los pacientes que han de ser chequeados en una 
clínica médica, asignando los pacientes a los doctores sobre la base de 
primero en llegar es primero en salir. 
SI 
4. Una estructura de datos ha de usarse para guardar las direcciones de 
vuelta de métodos anidados dentro de un programa que se está 
ejecutando. 
SI 
 
Problema N. 4 
 
Dada la siguiente expresión: (((5 + 1) / 2 * 4 + 10) * 3 * 5) - 6 y utilizando el algoritmo de Pila, realice lo 
siguiente: 
 
1. Transforme la expresión a Postfija. (Utilice la tabla y agregue filas si se requiere) 
CARÁCTER LEÍDO PILA EXPRESIÓN POSTFIJA 
( ( 
( (( 
( ((( 
5 ((( 5 
+ (((+ 5 
1 (((+ 51 
) (( 51+ 
/ ((/ 51+ 
2 ((/ 51+2 
* ((* 51+2/ 
4 ((* 51+2/4 
+ ((+ 51+2/4* 
1 ((+ 51+2/4*1 
0 ((+ 51+2/4*10 
) ( 51+2/4*10+ 
* (* 51+2/4*10+ 
3 (* 51+2/4*10+3 
* (* 51+2/4*10+3* 
5 (* 51+2/4*10+3*5 
) 51+2/4*10+3*5* 
- - 51+2/4*10+3*5* 
6 - 51+2/4*10+3*5*6 
 - 51+2/4*10+3*5*6 
 51+2/4*10+3*5*6- 
Expresión 
Postfija 
51+2/4*10+3*5*6- 
 
 
 
 
 
 
2. Evalué la expresión Postfija. (Utilice la tabla y agregue filas si se requiere) 
 
CARÁCTER LEÍDO PILA OPERACIÓN 
 
Op1 Op2 
5 5 “” 
1 5,1 “” 
+ 6 1+5=6 
2 6,2 “” 
/ 3 2/6=3 
4 3,4 “” 
* 12, 4*3=12 
10 12,10 “” 
+ 22 10+12=22 
3 22,3 “” 
* 66 3*22=66 
5 66,5 “” 
* 330 5*66=330 
6 330,6 “” 
- 6-330=324 
 324 
 
 
 
 
Powered by TCPDF (www.tcpdf.org)Powered by TCPDF (www.tcpdf.org)
http://www.tcpdf.org