UNIVERSIDAD AUTONOMA DE MADRID
DEPARTAMENTO DE INGENIERIA INFORMATICA
ESTRUCTURAS DE DATOS Y ALGORITMOS

Curso 2007-08	Examen parcial
APELLIDOS:
NOMBRE:												
	1	2	3	4	5	6	7	8	9	10	TOTAL	

1.	¿Qué es un tipo abstracto de datos?

2.	¿Qué diferencia hay entre un algoritmo y un programa?

3.	¿Cuáles son las desventajas de utilizar una tabla o array para implementar una lista?

4.	¿Por  qué se utiliza un nodo cabecera en las listas?

5.	Para la expresión en notación sufija AB-CDE+FG-^-*, dar la evolución sobre una pila de la aplicación del algoritmo de evaluación de una expresión en notación sufija.
6.	Explica el procedimiento que se sigue para procesar los elementos en una cola de prioridad.
7.	Para una lista enlazada definida en C de la siguiente forma
typedef struct Nodo *PNodo;
typedef struct Nodo {
   int dato;
   Pnodo siguiente;
} Nodo;
typedef struct Nodo *Lista;

        Escribir en C las siguientes funciones:
a.	Función resto que devuelve un puntero al segundo elemento de la lista
b.	Función modifica que cambia la información del primer elemento de la lista
c.	Función cuenta que devuelve el número de elementos de la lista
8.	Para una bicola definida en C de la siguiente forma
typedef struct Nodo *PNodo;
typedef struct Nodo{
   int dato;
   PNodo siguiente;
   PNodo anterior;
} Nodo;
typedef struct {
   PNodo izquierdo;
   PNodo derecho;
} Bicola;

Escribir en C  la función borrar_derecho que borra el último elemento de una bicola
9.	Definir los siguientes conceptos:  altura de un árbol, profundidad de un nodo
10.	Para un árbol binario definido en C de la siguiente forma
typedef struct  Nodo *PNodo;
typedef struct  Nodo *Arbol;
typedef struct Nodo {
	int dato;
	Arbol izqdo;
	Arbol dcho;
} Nodo;

Escribir en C una función que permita contar el número de hojas que tiene un árbol binario.