Download Extraordinario

UNIVERSIDAD DEL ISTMO
Estructuras de Datos - Evaluación Extraordinaria – 7/AGO/09
M.I.A Daniel Alejandro García López
M.C. Sergio Juárez Vázquez
Alumno: ___________________________________________________
Evaluación Escrita:
PORCENTAJE 50% CALIF_______
Evaluación Práctica (proyecto): PORCENTAJE 50% CALIF_______
Calificación final: _________________________________________
_____________________________
EVALUACIÓN ESCRITA
I.- Escriba V o F según sea verdadero o falso los siguientes enunciados. Total de la sección 10%
1.
( ) Una lista doblemente ligada es una colección de nodos, en la cual cada nodo tiene dos apuntadores, uno
apuntando a la cabeza de la lista y otro al final de la lista.
2. ( ) Todo nodo de un árbol que no es raíz ni terminal u hoja se conoce con el nombre de exterior.
3. ( ) El recorrido Enorden se visita el subárbol izquierdo, luego el derecho y finalmente la raíz.
4. ( ) La longitud de camino interno del árbol es la suma de las longitudes de camino de todos los nodos del árbol.
5. ( ) Una pila representa una estructura lineal de datos en la que se puede agregar o quitar elementos únicamente por
uno de los dos extremos. En consecuencia, los elementos de una pila se eliminan en orden inverso al que se
insertaron.
6. ( ) Todos los nodos que son descendientes directos de un mismo nodo se dice que son hermanos.
7. ( ) Una cola es una estructura lineal de datos en a que los nuevos elementos se introducen por un extremo y los ya
existentes se eliminan por el mismo extremo.
8. ( ) Las estructuras de datos lineales incluyen a las pilas, colas.
9. ( ) Una lista enlazada es una colección secuencial de elementos llamados generalmente nodos.
10. ( ) La recursión puede clasificarse en Directa e Indirecta.
11. ( ) Las pilas pueden representarse mediante el uso de arreglos y listas enlazadas.
12. ( ) Una estructura de datos es un conjunto de operaciones y procedimientos que deben seguirse para resolver un
problema.
13. ( ) Las pilas también reciben el nombre de estructuras FIFO.
14. ( ) Si la pila está llena y se intentara insertar un nuevo valor, se tendría un error conocido con el nombre de overflow.
15. ( ) La altura del árbol es el máximo número de niveles de todos los nodos del árbol.
16. ( ) En una solución recursiva de un problema el paso recursivo se utiliza como condición de parada.
17. ( ) El grado de un árbol es el número de arcos que deben recorrerse para llegar a un nodo terminal.
18. ( ) Un árbol es una estructura jerárquica aplicada sobre una colección de elementos un objetos llamados nodos, uno
de los cuales es conocido como raíz. Además de crear relaciones entre los nodos.
19. ( ) Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus
nodos difiere entre sí.
20. El factor de equilibrio de un nodo se define como la altura del subárbol derecho multiplicado por la altura del subárbol
izquierdo.
II. Resuelva los ejercicios siguientes:
Ejercicio 1. Convierta el siguiente bosque en una representación de árbol binario y desarrolle los recorridos Preorden, Enorden,
Postorden para el árbol binario resultante. ¿En cuál de los recorridos se visitan menos nodos para llegar al elemento „O‟?(15%).
Ejercicio 2. Elimine los nodos 20,50,47,42 y 81, dado el siguiente árbol balanceado AVL. Y después inserte los siguientes
elementos 15,19, 28, 3 y 99. Utilice la regla para elegir al nodo más a la derecha del subárbol izquierdo. (15%).
Ejercicio 3. Escriba el algoritmo de un método recursivo que transforme un número entero positivo a notación binaria. (5%).
Ejercicio 4. Examine que el siguiente algoritmo de búsqueda binaria sea correcto, si es incorrecto encuentre y corrija el error
completamente(5 %).
V es un arreglo unidimensional ordenado de N componentes.
X es elemento de búsqueda.
IZQ, CEN, DER son variables de tipo entero. BAN es una variable de tipo booleano.
BusquedaBinaria(V,N,X)
Hacer IZQ=1, DER=N y BAN=FALSO.
Si ((IZQ<=DER) y (BAN=FALSO) repetir
Si(X=CEN) entonces
Hacer BAN=VERDADERO
Sino
Si(X>CEN) entonces
Hacer IZQ=CEN+1
Sino
Hacer DER=CEN-1;
Si(BAN=VERDADERO) entonces
Escribir “Valor encontrado en la posición:”, DER
Sino
Escribir “La información no se encuentra en el arreglo“
EVALUACIÓN PRÁCTICA (PROYECTO)
Descripción: Diseñar un programa que calcule automáticamente los componentes necesarios para construir una red de voz y
datos cualquiera. Obténgase el número de jack‟s, jumpers, panels de parcheo, switch‟s, distribuidores de fibra óptica e hilos.
El diseño de la red será dado en dos archivos de texto. Emplee correctamente estructuras de datos para resolver el problema.
(Véase ejemplo Anexo).
Puntos evaluados:
1.
2.
3.
4.
Uso correcto y variedad de estructuras de datos (10% en total): _____________
Facilidad del uso del programa y buenas prácticas de programación (5% en total): _____________
Solución completa y correcta del problema(10% por calcular los componentes de red, 10% por calcular el tipo de switch‟s y
10% por calcular los distribuidores de fibra óptica)________________________
Código documentado completo y correcto(5% en total): __________________
ARCHIVOS ANEXOS A ESTE EXAMEN: Código fuente y Ejemplo del problema.