Taller 2 de Aplicaciones de las Estructuras de Árboles PDF

Preview

Summary

UNIVERSIDAD TECNOLÓGICA DE PANAMÁFACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALESDEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMASTALLER N. 2: Aplicaciones de las Estructuras de Árboles (2) Nombre de la Asignatura: Estructuras de Datos II Módulo 1: Técnicas De Estructuración de Datos No Lineale...

Description

UNIVERSIDAD TECNOLÓGICA DE PANAMÁ FACULTAD DE INGENIERÍA DE SISTEMAS COMPUTACIONALES DEPARTAMENTO DE COMPUTACIÓN Y SIMULACIÓN DE SISTEMAS TALLER N. 2: Aplicaciones de las Estructuras de Árboles (2) Nombre de la Asignatura: Estructuras de Datos II Módulo 1: Técnicas De Estructuración de Datos No Lineales Capítulo 1: Estructura de Datos Tipo Árbol Docente Responsable: Yolanda de Miguelena Fecha: Semana 6 Objetivos • Resolver problemas de estructura de árbol utilizando el algoritmo de Montón Max y/o Min. • Diseñar árboles binarios a partir de dos recorridos dados. • Resolver problemas de estructura de árbol utilizando el algoritmo de Huffman. • Resolver problemas de estructura de árbol que dado una expresión aritmética obtenga el diagrama del árbol. • Resolver problemas de estructura de árbol que dado un diagrama de un árbol de expresión obtenga la expresión. Recursos: Plataforma virtuales de apoyo académico, lápiz, borrador, papel, marcadores y tablero Instrucciones Entregar la Rúbrica en forma individual. Trabajar en grupo de 2 estudiantes. El trabajo debe ser evaluado y calificado antes de la terminación de la clase. Enunciados Dado los siguientes problemas resuelva según lo indicado. 1. Dadas las siguientes secuencias de nodos obtenidas por los recorridos Preorden, Inorden y Postorden dibuje el árbol binario correspondiente. Realice paso a paso cada proceso. Utilice los dos pasos aprendido en clase. PREORDEN INORDEN POSTORDEN

PRACHTOM ARHCPOTM AHCROMTP

2. De acuerdo a las siguientes claves: 35, 10, 24, 15, 16, 5, 28, 88, 77, 3. Ordene utilizando el Algoritmo en Montón Min . Realice paso a paso cada proceso. Muestre la tabla y el diagrama. 3. A partir de las siguientes expresiones obtenga el dibujo del árbol binario .Realice paso a paso. a. b.

x * y / [ (a + b) * c] (a + e + (b – c) * d / c)

4. Utilizando el algoritmo de Huffman para reducir el espacio de almacenamiento requerido para almacenar la frase: “ORO ROJO JORDA”. a. Paso a paso muestre la creación del árbol, utilizando el algoritmo. b. Muestre el código binario. c. Cantidad de Byte empacado (encriptado).

5.

a)

De acuerdo a los diagramas obtenga la expresión:

b) 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.

c)

d)

20.

Universidad Tecnológica de Panamá

Facultad de Ingeniería de Sistemas Computacionales

Licenciatura en Desarrollo de Software

II Año I Semestre

Estructura de Datos II

Taler #2

J.A. / K.P.

Fecha de entrega: 05/Mayo/2018

Índice 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00 Tema 1———————————————————-00

Taller #2

Arias | Parker

Desarrollo 1.! PREORDEN: PRACHTOM INORDEN: ARHCPOTM POSTORDEN: AHCROMTP

P R E O R D E N

INORDEN A

R

H

C

P

P

O

T

P

R

R

A A C

C

H

H

T

T

O

O

M

P O S T O R D E N

M

M

INORDEN A

R

H

C

P

P

O

T

M

M

O

O R

C H

M

P

T

R

T

C H

A A

Taller #2

1

11.35, 10, 24, 15, 16, 5, 28, 88, 77, 3 35 35

10

10

35

10

35

24

10

35

24

15

10

15

24

35

10

15

24

35

16

10

15

24

35

16

5

10

15

5

35

16

24

5

15

10

35

16

24

5

15

10

35

16

24

28

5

15

10

35

16

24

28

88

5

15

10

35

16

24

28

88

77

5

15

10

35

16

24

28

88

77

3

5

15

10

35

3

24

28

88

77

16

5

3

10

35

15

24

28

88

77

16

3

5

10

35

15

24

28

88

77

16

3

5

10

35

15

24

28

88

77

16

Taller #2

2

3. !

a)!

x*y/[(a+b)*c]

!

!

xy*/(ab+)*c

!

!

xy*/ab+c*

!

!

xy*ab+c*/

y x

x

y

x

b

/

* *

c

a

c + *

+ a

* +

b a *

a *

*

*

*

x

b

y

c +

a

!

b)!

(a+e+(b-c)*d/c)

!

!

(ae+bc - *dc/)

!

!

ae+bc-dc/*

!

!

ae+bc-dc/* a

e a

+

c b +

b +

a

b

d +

-

e

b

c d +

c *

/ +

/ d

-

c

b

/ e

c d

+ * +

+

*

a

e -

/

b

Taller #2

c

3

d

c

4) “ORO ROJO JORDA” O=

5

R=

3

J=

2

D=

1

A=

1

BLANCO =

2

O=

0

R=

111

J=

110

D=

1001

A=

1000

BLANCO =

101

Taller #2

BIN

110101

11101100

10111001

11100110

00000000

Byte

1

2

3

4

5

4

5)!

a)!

10+1

!

!

((10+1)*3)-20

!

!

((10+1)*3)-20 + (3*2)

!

!

(10+1)*3 - 20 + 3*2

!

b)!

b*c

!

!

b*c + a / (d-(d/f))

!

!

a + b*c / (e/f - d)

!

c)!

(b+c)

!

!

a*(b+c)

!

!

[a*(b+c)]+d

!

!

a*(b+c)+b

!

d)!

(b-c)

!

!

(b-c)*d/c

!

!

a+(b-c)*d/c

Taller #2

5...