Download Estructuras de datos y algoritmos 14 de septiembre de

Estructuras de datos y algoritmos
Ingeniería en Informática
14 de septiembre de 2007
Centro Politécnico Superior, Universidad de Zaragoza
Ejercicio 1 (1/3). Un Árbol Par Derecho (APD) es un árbol binario con cero nodos o con un número par de
nodos distribuidos de la forma siguiente: una raíz, un subárbol izquierdo que es una hoja y un subárbol derecho
que es un APD. Escribir una especificación algebraica de APD’s de números naturales (en los que cada nodo es
un natural) que incluya al menos las operaciones generadoras, las operaciones necesarias para obtener la raíz, el
subárbol izquierdo y el subárbol derecho de un APD y una operación que diga si un APD es un ABB (árbol
binario de búsqueda, es decir, si todo nodo es mayor o igual que los nodos –si existen– de su subárbol
izquierdo y menor que los nodos –si existen– de su subárbol derecho).
Ejercicio 2 (1/3). Dado un árbol binario de búsqueda (ABB, es decir, un árbol binario tal que todo nodo es
mayor o igual que los nodos –si existen– de su subárbol izquierdo y menor que los nodos –si existen– de su
subárbol derecho), una operación necesaria a veces es conocer la k-ésima clave más pequeña del árbol. Es decir,
si el árbol contiene las claves c1 ≤ c2 ≤ … ≤ ck-1 ≤ ck ≤ ck+1 ≤ … ≤ cn, se trata de devolver ck. Para hacerlo
eficientemente, se almacena en cada nodo, además de la clave, un campo que guarda el número de nodos de su
subárbol izquierdo. Diseñar las siguientes operaciones (dados los tipos de datos que se definen):
tipos abb = ↑nodo
nodo = registro clave:tpclave; numizq:natural; izq,der:abb freg
{numizq de un nodo guarda el nº de nodos del subárbol izquierdo de ese nodo}
función k_ésimo (a:abb; k:natural) devuelve tpclave
{Pre: a es un ABB no vacío de n datos de tipo tpclave
(que pueden compararse con los operadores ‘=’,‘<’,‘>’,‘≤’,‘≥’);
1 ≤ k ≤ n}
{Post: devuelve el valor de la k-ésima clave más pequeña de a}
algoritmo insertar (e/s a:abb; ent c:tpclave)
{Pre: a=a0 es un ABB}
{Post: a es el ABB resultante de añadir a a0 un ejemplar de c (exista o no otro igual)}
Ejercicio 3 (1/3). Desde la fábrica IdeaFac se nos solicita la implantación de un sistema de gestión de facturas.
Además de los datos de la empresa, que vendrán preimpresos ya en el papel, para dar salida a una factura se
necesita un código de factura, unos datos del cliente a quien va dirigida (NIF, nombre y domicilio social), una
serie de líneas de factura que hacen referencia a los productos solicitados (en cada línea: código artículo,
descripción, unidades y precio), y una línea final, en la que se obtiene, además de los totales, el descuento
aplicado en caso de que el cliente sea preferente. Se pide: a) hacer un esquema de las estructuras necesarias para
gestionar todos los datos necesarios de clientes, de productos y de facturas, sin repetir datos innecesariamente, y
b) definir dichas estructuras en lenguaje algorítmico (“tipo nombretipo = …”). Tener en cuenta que tanto los
clientes como los productos pueden ir aumentando con el tiempo. Explicar muy brevemente el esquema y las
decisiones tomadas.
Tiempo total: 3 horas