Hazhz

ESTRUCTURAS DE DATOS GUIA DE ESTUDIO – SEGUNDO PARCIAL PARTE TEORICA 1. ¿Qué es un tipo de datos abstracto (TDA)? 2. Mencione los tipos abstractos de dato planteados en las prácticas de laboratorio computacional que se le han asignado. 3. Defina los conceptos de: a. Pila. b. Cola c. Lista ligada. 4. Represente gráficamente y cómo se operan los siguientes TDAs: a. Pila. b. Cola. c. Lista enlazada.5. ¿Qué operaciones están asociadas a a. una pila b. Una cola? 6. Explique las diferentes notaciones para escribir una expresión aritmética. 7. Explique en qué consiste la representación en memoria de una lista ligada? 8. ¿Qué características tiene la representación de una lista enlazada mediante nodos? 9. Si un nodo no tiene sucesor, su enlace se hace igual al valor _______. 10. Cada elemento deuna lista enlazada tiene dos partes: una parte: ________ y otra parte: _____________. 11. ¿Es verdadero o falso que una de las ventajas de las listas enlazadas es el acceso directo a cada nodo? 12. ¿Qué operaciones están asociadas a la lista enlazada? 13. Haga el diagrama de flujo del algoritmo de cada operación asociada a la TDA Lista Enlazada. 14. ¿En qué consiste el mecanismo para actualizaruna lista enlazada? 15. ¿Qué casos comunes hay que considerar cuando se inserta un nodo en una lista enlzada?. Explique cada caso mediante un diagrama nodal. Ing. Ricardo J. Woolery Cintra, MCSc 1

ESTRUCTURAS DE DATOS GUIA DE ESTUDIO – SEGUNDO PARCIAL 16. ¿Cómo puede implementar una lista enlazada mediante la TDA Cola?. Investigue. 17. ¿Por qué hay dos ceros (valores NULO) en el campo ENLACE dela siguiente representación en memoria de la siguiente lista ligada: I 1 2 3 4 5 6 7 8 9 10 INFO 11 41 60 2 9 63 16 85 32 22 18. ¿Qué está mal en la siguiente lista enlazada? COMIENZO = 10 I 1 2 3 4 5 6 7 8 9 10 PARTE PRACTICA PROBLEMA 1 Supóngase que PILA tiene N = 6 celdas de memoria y que inicialmente está vacía o, en otras palabras, que CIMA =0. Mediante la prueba de escritorio, encuentre lasalida del siguiente segmento de programa: INFO 32 12 17 101 46 57 98 12 12 14 DISP = 4 ENLACE 5 9 1 2 6 7 0 7 8 3 ENLACE 3 6 5 7 0 8 9 0 2 1

Ing. Ricardo J. Woolery Cintra, MCSc

2

ESTRUCTURAS DE DATOS GUIA DE ESTUDIO – SEGUNDO PARCIAL 1. Hacer AAA:= 2 y BBB:=5. 2. Llamar POP(PILA, AAA). Llamar METER(PILA, 4). Llamar PUSH(PILA, BBB + 2) Llamar METER(PILA, 9). Llamar METER(PILA, AAA +BBB). 3. Repetir mientras CIMA ≠ 0: Llamar SACAR(PILA, ITEM). Escribir: ITEM. {Fin del Bucle}.. 4. Volver. PROBLEMA 2 Traduzca, cada expresión infija en su equivalente expresión sufija y postfija: a. (A – B)* (D/E) b. (A + B**D)/(E – F) + G c. A * (B + D)/E – F*(G + H/K). PROBLEMA 3 Muestre, mediante una representación nodal y usando el algoritmo adecuado, cómo afectaría a la lista enlazada alrealizarse la operación indicada: INSERTAR 17 COMIENZO = 4 DISP = 3 I 1 2 3 4 5 6 7 8 9 10 INFO 12 19 8 6 14 32 67 95 68 11 ENLACE 0 5 2 10 1 7 9 0 8 6

Ing. Ricardo J. Woolery Cintra, MCSc

3

ESTRUCTURAS DE DATOS GUIA DE ESTUDIO – SEGUNDO PARCIAL PROBLEMA 4 Muestre, mediante una representación nodal y usando el algoritmo adecuado, cómo afectaría a la lista enlazada al realizarse la operaciónindicada: ELIMINAR 105 COMIENZO = 6 DISP = 2 I 1 2 3 4 5 6 7 8 9 10 PROBLEMA 5 Muestre, mediante una representación nodal y usando el algoritmo adecuado, cómo afectaría a la lista enlazada al realizarse la operación indicada: INSERTAR 42; SUPRIMIR 11 COMIENZO = 7 I 1 2 3 4 5 6 7 8 9 10 INFO 5 17 35 92 76 43 11 12 57 42 DISP = 8 ENLACE 0 3 6 0 4 9 2 10 5 1 INFO 65 85 95 25 35 15 45 55 75 105 ENLACE 95 10 7 8 4 1 0 3 0

Ing. Ricardo J. Woolery Cintra, MCSc

4

ESTRUCTURAS DE DATOS GUIA DE ESTUDIO – SEGUNDO PARCIAL PROBLEMA 6 Escriba en lenguaje pseudocódigo un algoritmo para imprimir (además, haga la prueba de escritorio) la siguiente lista enlazada cuya representación en memoria es: COMIENZO = 6 I 1 2 3 4 5 6 7 8 9 10 PROBLEMA 7 ¿Cuáles son los clientes de cada abogado?. Haga la...