Download ESTRUCTURAS DE DATOS - TEORÍA FECHA APELLIDOS

ESTRUCTURAS DE DATOS ‐ TEORÍA APELLIDOS FECHA NOMBRE 1. Insertar un nodo con valor 20 en el árbol balanceado que muestra la figura. Indicar que tipo de rotación se produce y mostrar gráficamente el árbol resultante. ¿Qué nodos participan en la rotación (nodo, nodo1 y nodo2)? 2. Dado el montículo binario de la siguiente figura dibujar el montículo después de realizar una operación que decremente en 620 el valor del elemento de la posición 18. Explicar brevemente el proceso. A
3. Dibuja un árbol binario sabiendo que su recorrido en preorden es “1234” y en orden “1342”. Razona brevemente tu respuesta. 4. Explica brevemente que mejora introduce el método de clasificación polifase respecto del de intercalación múltiple. 5. La figura muestra un árbol B+ de orden 3. Dibujar el árbol que resulta después de eliminar la clave con valor 19. Explicar brevemente el proceso. 17 19 20 5 9 12 17 35 60 60 90 95
35 45 50
ESTRUCTURAS DE DATOS ‐ TEORÍA APELLIDOS FECHA NOMBRE 1. Insertar un nodo con valor 60 en el árbol balanceado que muestra la figura. Indicar que tipo de rotación se produce y mostrar gráficamente el árbol resultante. ¿Qué nodos participan en la rotación (nodo, nodo1 y nodo2)? 2. Dado el montículo binario de la siguiente figura dibujar el montículo después de realizar una operación que decremente en 400 el valor del elemento de la posición 17. Explicar brevemente el proceso. B
3. Dibuja un árbol binario sabiendo que su recorrido en preorden es “1234” y en orden “3421”. Razona brevemente tu respuesta. 4. Explica brevemente que mejora introduce el método de clasificación polifase respecto del de intercalación múltiple. 5. La figura muestra un árbol B+ de orden 3. Dibujar el árbol que resulta después de eliminar la clave con valor 45. Explicar brevemente el proceso. 17 19 20 5 9 12 17 35 60 60 90 95
35 45 50
ESTRUCTURAS DE DATOS ‐ PRÁCTICAS FECHA APELLIDOS NOMBRE 1) Utilizando la representación de árboles binarios mediante punteros implementar en lenguaje C una función que sume el contenido de todos los nodos del árbol y devuelva el resultado de esta suma. La función implementada debe ser recursiva y su prototipo será el siguiente: int suma (ARBOL A); Donde: i)
ARBOL es un tipo predefinido como puntero a nodos de árboles binarios según las declaraciones que muestra el cuadro adjunto. ii) El parámetro A es un puntero a la raíz del árbol cuyo contenido se desea sumar. typedef struct tagnodo { int info; struct tagnodo *izq,*der; } nodo; typedef nodo *ARBOL; 2) El siguiente párrafo muestra en lenguaje C el código que permite determinar el camino mínimo desde un vértice al resto de los vértices del grafo utilizando el algoritmo de Dijkstra y mostrar el camino mínimo desde un vértice inicial a otro vértice final. Teniendo en cuenta este código y suponiendo que un grafo dirigido ponderado se representa mediante las declaraciones que se muestran en el cuadro adjunto, implementar la función CosteyTrayectoria que aparece en negrita incluyendo su prototipo. GRAFO *vGrafo;
PILA P=NULL;
int v_ini=1,v_fin=6;
typedef struct tagARCO
{int v;
int coste;
struct tagARCO *sig;
}ARCO;
typedef struct
{int alcanzado;
int distancia;
int anterior;
ARCO *lista;
}VERTICES;
typedef struct
{VERTICES directorio[N];
int orden;
}GRAFO
..........
init(vGrafo);
dijkstra(vGrafo,v_ini);
printf("\n COSTE CAMINO v%d a v%d es %d",
v_ini,v_fin, CosteyTrayectoria(v_ini,v_fin,vGrafo,&P));
printf("\nLa secuencia de vértices que forman el camino es:");
while (P!=NULL) printf(" %d ", tope(&P));
..........
NOTA: NO hay que implementar el algoritmo de Dijkstra, hay que interpretar el resultado de su aplicación. 3) Dado un archivo (alumnos.hash) organizado mediante el Método de Dispersión según los siguientes criterios: •
•
•
•
El fichero está organizado en cubos con CAPACIDAD para 5 registros de tipoAlumno cada uno. Se han considerado 20 CUBOS inicialmente y 4 CUBOS DE DESBORDE más para almacenar los registros asignados a cubos LLENOS. Cada cubo almacena además el número de registros que se le han asignado, incluyendo los que no haya podido almacenar porque estaba lleno. Los tres criterios anteriores se reflejan en las definiciones que se proporcionan a continuación #include <stdio.h>
#define C 5
#define CUBOS 20
prima
#define CUBOSDESBORDE
desborde
// Capacidad del cubo
// Número de cubos en el area
4
//
Número
de
cubos
area
de
typedef struct {
char dni[9];
char nombre[19];
char ape1[19];
char ape2[19];
char provincia[11];
} tipoAlumno;
typedef struct {
tipoAlumno reg[C];
int numRegAsignados;
}tipoCubo;
•
•
Los registros desbordados se han almacenando secuencialmente en el área de DESBORDE. Los 5 primeros registros desbordados en el primer cubo de desborde, los 5 siguientes al siguiente cubo de desborde, etc. Se ha utilizado como clave el campo DNI de los registros de tipoAlumno y como función hash para asignar un registro a un cubo la función Módulo. Previamente habrá que convertir el DNI a entero, por tanto la función que se aplica para obtener el cubo asignado a un registro será f(k)=atoi(K)%CUBOS Implementar una función int buscaReg(tipoAlumno *reg, char *dni) que busque un registro en este archivo a partir de su clave, parámetro dni de entrada a la función. Si el registro se encuentra en el archivo la función debe devolver el número de CUBO en que está almacenado y el registro completo en el parámetro reg. Si el registro no está en el archivo la función debe devolver el valor ‐1 indicando que no existe un registro con esa clave.