Download DEPARTAMENTO DE ELECTRONICA ELO320 Estructuras de

UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
1. En un arreglo con cinco ítems, dar un ejemplo de datos que permita mostrar que heapsort
no es un algoritmo de ordenamiento estable.
Solución.
Para encontrar un ejemplo de datos, se requiere al menos tener dos o más elementos iguales
en el arreglo original que desea ordenarse.
Se tiene el arreglo: 3, 1a, 2, 4, 1b, no ordenado representado en un heap:
Los unos repetidos, se han marcado con a y b.
3
2
1a
4
last
1b
La formación del heap: por subárboles o por recorridos desde las hojas, produce el heap:
1a
2
1b
4
3
last
Heapsort repetidamente intercambia la raíz con la posición del último, y hace descender la
nueva raíz en un heap de largo disminuido en uno. El arreglo queda ordenado en forma
descendente: 4, 3, 2, 1b, 1a. Entonces el orden de los elementos repetidos, en el arreglo
original no se conserva, lo cual muestra que el ordenamiento no es estable.
2. Se tienen los enteros: 1, 2, 3, 4 y 5. Determinar el orden en que deben ser ingresados a un
heap para que el número de intercambios sea:
a) Mínimo. Indicar el número de intercambios necesarios.
b) Máximo. Indicar el número de intercambios necesarios.
Solución.
a) Si llegan en orden ascendente, no es necesario efectuar intercambios.
Ya que siempre se inserta en la posición final, y se preserva el heap mediante el ascenso del
último insertado.
Leopoldo Silva Bijit.
14-10-2006
1
UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
1
3
2
4
last
5
Otros órdenes de llegada, con intercambios mínimos son: 1, 2, 3, 5, 4; 1, 2, 4, 3, 5;
1, 2, 4, 5, 3; 1, 2, 5, 3, 4; 1, 2, 5, 4, 3; 1, 3, 2, 5, 4; 1, 3, 2, 4, 5;
b) Si llegan en forma descendente, la inserción del 5, no requiere intercambios. La
inserción del 4, requiere un intercambio. La inserción del 3 requiere un intercambio. El
heap queda:
3
last
5
4
Al agregar el 2, se requieren dos intercambios para cumplir con las propiedades de un heap.
El heap queda, luego de insertado el 1:
2
4
3
5
1
last
Se requieren dos intercambios adicionales, para el ascenso del 1. En total se necesitan 6
intercambios.
3. Se tiene una doble cola, en la que se permiten inserciones y descartes en ambos
extremos, con complejidad constante.
a) Definir los tipos de datos de los nodos y de los punteros a las colas.
b) Ilustrar, mediante un diagrama, una cola doble vacía, y con dos elementos.
c) Diseñar función insertar y descartar, dando un ejemplo de uso.
Solución.
Para que sean de costo constante las inserciones y descartes, en ambos extremos, la lista
debe ser doblemente enlazada.
Existen numerosas soluciones, se ilustra una de las posibles.
Leopoldo Silva Bijit.
14-10-2006
2
UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
a)
typedef struct moldecelda
{
int clave;
struct moldecelda *nx; //next
struct modecelda *pr; // previo
} nodo, *pnodo;
nx
pr
clave
Cola vacía:
pnodo Cabeza=NULL;
pnodo Cola=NULL;
cabeza
cola
Cola, sin cabecera, con dos elementos:
cabeza
cola
pnodo inscabeza(int valor)
{ pnodo t;
if( (t=getnodo(valor))!=NULL)
{ if (cabeza==NULL)
{cabeza=t; cola=t;}//doble cola queda con un elemento
else
{t->nx=cabeza;
cabeza->pr=t;
cabeza=t;
}
return(t);
}
else
{ //printf(" Error en inserción.\n");
return (NULL); }
}
Leopoldo Silva Bijit.
14-10-2006
3
UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
pnodo delcabeza(void)
{ pnodo t;
if (cabeza !=NULL)
{ t=cabeza;
if (cabeza->nx!=NULL)
{cabeza->nx->pr=NULL;
cabeza=cabeza->nx;
}
else
{cola=NULL;
cabeza=NULL;
//printf("queda vacía por la cabeza\n");
}
free(t);
return(cabeza);
}
else
{ //printf(" Error en descarte. Cola vacía\n");
return (NULL);
}
}
Las funciones para insertar y descartar por el otro extremo:
Se intercambian cabeza por cola, y nx por pr.
pnodo inscola(int valor)
{ pnodo t;
if( (t=getnodo(valor))!=NULL)
{
if (cola==NULL)
{cabeza=t; cola=t;}
else
{cola->nx=t;
t->pr=cola;
cola=t;
}
return(t);
}
else
{ //printf(" Error en inserción.\n");
return (NULL);
}
}
Leopoldo Silva Bijit.
14-10-2006
4
UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
pnodo delcola(void)
{ pnodo t;
if (cola !=NULL)
{ t=cola;
if (cola->pr!=NULL)
{cola->pr->nx=NULL;
cola=cola->pr;
}
else
{cola=NULL;
cabeza=NULL;
//printf(" cola queda vacía\n");
}
free(t);
return(cabeza);
}
else
{ //printf(" Error en descarte. Cola vacía\n");
return (NULL);
}
}
Se pedía diseñar sólo las funciones en uno de los extremos.
4. En un árbol AVL vacío, se insertan nodos con claves en el siguiente orden de llegada: 5,
8, 4, 7.
a) Dibujar un diagrama del árbol, antes y después de insertar un nodo con valor 6;
indicando los factores de balance y la forma de corrección, si es necesaria.
b) Luego de insertado el nodo con valor 6, dibujar un diagrama del árbol, antes y después
de descartar el nodo con valor 4; indicando los factores de balance y la forma de
corrección, si es necesaria.
Solución.
a) Después de insertar el 6, y en el ascenso se modifica a -1 el factor de balance del nodo
con valor 7, luego el nodo con valor 8 queda con factor de balance -2 (espejo de caso c). Se
corrige con rotación simple a la derecha y no debe continuarse la revisión de los factores de
balance en el ascenso
Leopoldo Silva Bijit.
14-10-2006
5
UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
+1
5
0
4
8
-1
8
7
6
Antes de insertar 6
+1
5
0
4
0
7
+1
5
-2
4
0
-1
0
7
6
8
0
0
0
Después de insertar 6
Después del rrot
Notar que los factores de balance se incrementan o decrementan en el ascenso. Por esta
razón se deja, en la figura central, el factor de balance del nodo con valor 5 queda en 1.
b) Se descarta la hoja con valor 4, en el ascenso deben seguir revisándose los factores de
balance; el nodo con valor 5, queda con factor de balance 2. Se corrige con rotación simple
a la izquierda (caso c) y no debe continuarse la revisión en el ascenso.
5
4
+1
0
5 +2
7
6
0
Antes de descartar el 4
0
8
7
7
0
6
0
0
8
5
0
Después de descartar el 4
+1
0
8
6
0
0
Después de rleft
5. Diseñar función que ordene los valores enteros almacenados en un árbol binario de
búsqueda, apuntado por root, en un arreglo estático.
a) en forma ascendente
b) en forma descendente.
Solución.
Se tiene un arreglo estático a, que debe tener igual o mayor tamaño que el número de
elementos que están en el árbol. Se emplea una variable i para ir avanzando en el arreglo
que se desea llenar:
static int a[N];
static int i=0;
Leopoldo Silva Bijit.
14-10-2006
6
UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
El ordenamiento ascendente se logra con un recorrido en orden:
void ordenarasc(pnodo T)
{ if (T != NULL) {
ordenarasc(T->left);
a[i++]=T->valor;
ordenarasc(T->right);
}
}
El ordenamiento descendente con recorrido postorden.
void ordenardes(pnodo T)
{ if (T != NULL) {
ordenardes(T->right);
a[i++]=T->valor;
ordenardes(T->left);
}
}
Ejemplos de uso:
i=0; ordenarasc(root);
Es importante iniciar la estática i en 0, previo al llamado.
i=0; ordenardes(root);
Como se recorre el árbol completo se requieren nlog(n) operaciones.
6. Se desea colocar 1000 items en una tabla de hash y se desea que en una búsqueda exitosa
el número promedio de accesos sea cercano a 2.
a) De que tamaño debe ser el arreglo si se emplea hash cerrado con rehash lineal (linear
probing).
b) De que tamaño debe ser el arreglo de punteros si se emplea hash abierto y se supone que
la función de hash produce distribución uniforme.
Solución.
a) Con EB = número promedio de intentos para insertar m elementos en la tabla, se tienen:
n +1 ⎛ n +1 ⎞
ln(1 − α )
EB =
ln ⎜
⎟=−
m
α
⎝ n +1− m ⎠
m
α=
n +1
EB =2, m =1000
Para EB =2, se tiene, mediante la gráfica: α =0,8. Esto implica n ≈ 1249.
Leopoldo Silva Bijit.
14-10-2006
7
UNIVERSIDAD TECNICA FEDERICO SANTA MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
Segundo Certamen. Segundo semestre 2006.
El valor exacto, de la ecuación no lineal: α EB + ln(1 − α ) = 0 es n= 1254,000975.
b) En un caso ideal, la función h produce distribución uniforme; en este caso las listas
resultan de largo promedio n/B.
Con n=1000 y n/B=2, se tiene: B= 500.
Leopoldo Silva Bijit.
14-10-2006
8