Download Primera Serie: Conteste las siguientes

Universidad Rafael Landívar
Ingeniería de Sistemas
Estructuras de Datos I
Ing. Leonel Morales Díaz
2do Examen Parcial – 19 de Abril de 2006
Nombre
No. de carné
Primera Serie: Conteste las siguientes preguntas (5 puntos cada una)
1.
2.
3.
4.
5.
¿Cuántos nodos tiene como máximo un árbol binario cuya altura es 4?
¿Qué tipos de recorridos (traversal) de árboles existen?
¿Es posible programar recorridos (traversals) no recursivos? ¿Cómo?
¿Cuáles son las características de un árbol montículo (heap)?
¿Cómo se inserta un nodo en un árbol montículo (heap)?
Segunda Serie: En base a los dibujos siguientes diga: a) qué estructura de datos representa b) su altura c) cual
sería el producto de un recorrido (traversal) in-order (15 puntos cada uno)
1.
2.
3.
19
12
56
23
18
40
21
7
11
15
24
17
18
19
30
18
29
15
5
3
23
43
30
19
8
13
56
36
19
10
35
10
25
13
3
Tercera Serie: El siguiente programa en Java implementa un árbol binario con un array. Conteste y resuelva:
1. ¿Cuál es la altura máxima para un árbol que puede lograrse en este programa? (5 puntos)
2. ¿Cuál es la cantidad máxima de nodos que puede tener? (5 puntos)
3. Construya uno de los siguientes métodos dentro de la clase: (10 puntos)
a. public void inOrder(int raiz) { //traversal o recorrido in-order del árbol
b. public void eliminar(int nodo) { //quita un nodo del árbol
c. public int altura() { //calcula la altura actual del árbol
4. Construya una aplicación que ingrese datos aleatorios al árbol y los muestre en pantalla.
public class Arrbol {
private int[] datos = new int[99];
private int siguiente = 0;
poneDato(nuevo);
return;
} else {
actual = datos[actual - 1];
}
public void poneDato(int nuevo) {
datos[siguiente++] = 0;
datos[siguiente++] = nuevo;
datos[siguiente++] = 0;
}
public void agregar(int nuevo) {
if (siguiente == 0) {
poneDato(nuevo);
return;
} else {
int actual = 1;
while (true) {
while (datos[actual] >= nuevo) {
if (datos[actual - 1] == 0) {
datos[actual - 1] = siguiente + 1;
}
while (datos[actual] < nuevo) {
if (datos[actual + 1] == 0) {
datos[actual + 1] = siguiente + 1;
poneDato(nuevo);
return;
} else {
actual = datos[actual + 1];
}
}
}
}
}
}
Puntos extra: Conteste las siguientes preguntas (5 puntos cada una)
1.
2.
¿Porqué se dice que el juego Sudoku puede resolverse con un algoritmo backtracking?
¿Porqué es más eficiente un árbol balanceado que uno no balanceado?