• Author / Uploaded
• lautarovill

Citation preview

TRABAJO PRÁCTICO Nº 5: ARBOLES -ALGEBRA II 2011

TRABAJO INDIVIDUAL: 1. En un texto se encontró que la frecuencia de uso de cada uno de los siguientes caracteres: Carácter Frecuencia O 20 L 8 U 15 S 6 A 23 N 6 I 25 B 10 E 19 a) ¿Cuál es el árbol óptimo para el código de Huffman? b) Con el árbol obtenido, codificar: SOLOUNABUENAILUSION 2. En un documento se encontró que la frecuencia con la que ocurren los caracteres es: Carácter Frecuencia A 80 E 72 F 55 G 28 H 19 I 78 L 33 M 43 O 69 S 36 U 48 47 ∅ a) b)

¿Cuál es el árbol óptimo para el código de Huffman? Con dicho árbol codificar: HOLA AMIGOS

3. Para cada uno de los siguientes grafos determinar el árbol generador, partiendo del nodo 1 y prioridad en orden ascendente; por medio de búsqueda a lo ancho y en profundidad. a) b) c)

1

TRABAJO PRÁCTICO Nº 5: ARBOLES -ALGEBRA II 2011 4. Considerar los siguientes árboles, ¿Cuál es el recorrido en orden 1º, 2º y final? a) b)

5. Sea la siguiente expresión

a) b) c)

(a + b) − b.c : a d .c + c b

Determinar el árbol binario que representa dicha expresión El recorrido en orden 1º, 2º y final Si a=6, b=2, c=3 y d=4 ¿Cuál es la forma en que se lleva a cabo la evaluación en orden 1º y final?

6. Para cada una de las siguientes expresiones determinar: a) El árbol binario que representa la expresión b) El recorrido en orden 1º, 2º y final c) Si a=8, b=4, c=2, d=1, e=-2, f=6 ¿Cuál es la forma en que se lleva a cabo la evaluación en orden 1º y final?

i)

iii)

a + d .c b−c d +a c− b

c + d c.a − b.c + e a c+d

ii)

( a − b.c).d e (b + a ).c.e +f b

iv)

(e + d ).a + c.a − e b+ f a + b a.d . f − c e

7. Sea el recorrido en orden 1º +a--*bcd/e+fg a) Construir el árbol binario b) ¿Cuál es el recorrido en orden 2º y final? c) Si a=1, b=2, c=3, d=5, e=4, f=-3 y g=5 ¿Cuál es la forma en la cual se lleva a cabo la evaluación en orden 1º y final? 8. Sea el recorrido en orden: a) Final: db*b-cab*/+a*db) Final: ab+cd/ef-gh+*-*

2

TRABAJO PRÁCTICO Nº 5: ARBOLES -ALGEBRA II 2011 c) d)

1º: /a+*+bc-ec/d-ba 1º: *+/c*+abfde Para cada inciso determinar: i) El árbol binario ii) El recorrido en orden 1º, 2º Evaluar en orden 1º y final si a=3, b=2, c=-1, e=4, f=6, g=-3, h=4 iii)

3

APU 2008 - FACULTAD DE INGENIERIA - UNJU