INF-134 Estructuras de Datos, 2024-1

DI – UTFSM
Profesores: Elizabeth Montero, Andrés Navarro, Roberto Dı́az,
José Miguel Cazorla, Ricardo Salas

Certamen 3
04 de Julio de 2024

Lea con cuidado los enunciados. Solo se permiten preguntas de enunciado directo al profesor en voz alta. Sea claro y
prolijo en sus respuestas, de lo contrario no habrá posibilidad de apelación. Escriba sus respuestas de cada pregunta en
hojas separadas, cada una con nombre, rol y paralelo.

Hashing (30 pts)

1. Dada una tabla de hashing cerrado con M = 7 (inicialmente vacı́a) y usando la siguiente estrategia de
resolución de colisiones (de acuerdo con la terminologı́a usada en clases):

p(k, i) = i · h2(k);

Considere que en la tabla de hashing se insertan los elementos AB, BC, CD, DE, EF, FG, GH, en ese
orden suponiendo que se ha definido:

h(AB) 5 h2(AB) 3
h(BC) 1 h2(BC) 5
h(CD) 1 h2(CD) 3
h(DE) 3 h2(DE) 1
h(EF) 5 h2(EF) 5
h(FG) 3 h2(FG) 3
h(GH) 5 h2(GH) 1

Muestre la tabla de hashing resultante y el desarrollo para obtenerla mostrando la secuencia de colisiones
al insertar cada elemento. Junto a cada ranura, indique el número de colisiones que ocurrieron para insertar
el elemento que ocupa dicha ranura.

Puntaje Asignado

Correcta inserción del elemento en la tabla (16 pts)

Se indica la cantidad de colisiones que ocurrieron al intentar insertar el elemento (14 pts)
 Solución:
AB → r0 = h(AB) = 5
BC → r0 = h(BC) = 1
CD → r0 = h(CD) = 1
→ r1 = (r0 + p(CD, 1)) %7 = 4
DE → r0 = h(DE) = 3
EF → r0 = h(EF ) = 5
→ r1 = (r0 + p(EF, 1)) %7 = 3
→ r2 = (r0 + p(EF, 2)) %7 = 1
→ r3 = (r0 + p(EF, 3)) %7 = 6
FG → r0 = h(F G) = 3
→ r1 = (r0 + p(F G, 1)) %7 = 6
→ r2 = (r0 + p(F G, 2)) %7 = 2
GH → r0 = h(GH) = 5
→ r1 = (r0 + p(GH, 1)) %7 = 6
→ r2 = (r0 + p(GH, 2)) %7 = 0

GH BC FG DE CD AB EF

0 1 2 3 4 5 6
(2) (0) (2) (0) (1) (0) (3)

Colas de Prioridad (30 pts)

2. Una estructura de datos que se puede utilizar para ordenar los elementos de un arreglo de menor a mayor
son las colas de prioridad. Para esto, primero es necesario transformar el arreglo en un min-heap. Existe un
procedimiento denominado heapify, que consiste en solo reordenar los elementos del arreglo para cumplir
la propiedad de “parcialmente ordenado”. Su código en C++ se muestra a continuación:
void heapify ( int * arreglo , int size ) // size es la cantidad de elementos del arreglo
{
for ( int i = size ; i >0; i - -)
hundir ( arreglo , i ) ; // hunde el nodo del elemento en la posici ó n i del arreglo
return ;
}

Considerando el siguiente árbol binario casi-lleno:

4 7

8 9 2 5

a) Muestre el paso a paso de la función heapify que transforma al arreglo asociado al árbol anterior en
un min-heap.

X 6 4 7 8 9 2 5 3
0 1 2 3 4 5 6 7 8

2
 En cada paso muestre el árbol y el arreglo. Hint! Recuerde que las hojas no se pueden hundir.
b) A partir del min-heap obtenido, muestre el proceso de eliminación de cada elemento. Además, veri-
fique que la secuencia extraı́da efectivamente esté ordenada de menor a mayor.

Puntaje Asignado
a) cuatro hojas + cinco hundimientos correctos (15 pts.)
b) seis remociones con hundimientos (15 pts.)
Solución:

3
 Algoritmos sobre grafos (40 pts)
3. Un puente es un arco de un grafo no dirigido, tal que al eliminarlo del grafo, éste se vuelve desconexo. El
grafo conexo de la figura posee dos puentes: los arcos (D, E) y (H, I).

B F J

A D E H I L

C G K

Implemente en C++ la función cantidad de puentes, la cual al recibir un grafo retorna la cantidad de
puentes que posee el grafo.
Nota: Si necesita emplear algún algoritmo visto en clases (por ejemplo, Dijkstra, Prim, Kruskal, DFS,
BFS, etc), puede emplearlos suponiendo que ya están implementados. Indique claramente toda suposición
que haga respecto al/los algoritmo/s empleado/s.

Puntaje Asignado

Correcto uso de los TDA (10 pts.)

Resolución del problema (20 pts.)
Correcto uso de algoritmos vistos en clases (10 pts.)

Solución:

int c a n t i d a d _ d e _ p u e n t e s ( tGrafo G ) {
tVertice v , w ;
bool disconnected ;
int cantidad =0;
for ( v = 0; v < G . nVertex () ; v ++) {
for ( w = v +1; w < G . nVertex () ; w ++) {
if ( G . isEdge (v , w ) ) {
disconnnected = false ;
G . deleteEdge (v , w ) ;
for ( u = 0; u < G . nVertex () ; u ++)
G . setMark (u , NOVISITADO ) ;
DFS (G , v ) ;
for ( u = 0; u < G . nVertex () ; u ++)
if ( G . getMark ( v ) == NOVISITADO )
disconnected = true ;
if ( disconnected ) cantidad ++;
G . setEdge (v , w ) ;
}
}
}
return cantidad ;
}
Formulario
TDA tColaP

class tColaP {
private :
// informaci ó n del heap
public :
// elimina todos los elementos de una cola de prioridad , dej á ndola vac ı́ a
void clearColaP ()
// encuentra el m á ximo elemento del conjunto en un max - heap
tipoElem findMax ()
// cantidad de elementos en la cola prioridad
int sizeColaP ()
// elimina el m á ximo elemento del conjunto en un max - heap
void removeMax ()
// inserta un elemento ‘ item ‘ en la cola de prioridad
void insertColaP ( tipoElem item )
};

TDA tGrafo

class tGrafo {
private :
// Depende la implementaci ó n que tiene
public :
// constructor que inicializa el grafo para n v é rtices
tGrafo ( int n ) ;
// retorna el n ú mero de v é rtices en el grafo
int nVertex () ;
// retorna el n ú mero de arcos en el grafo
int nEdges () ;
// Devuelve el primer vecino de un v é rtice v dado ( asume que los
// vecinos de un v é rtice est á n ordenados por n ú mero de v é rtice )
tVertice first ( tVertice v ) ;
// Devuelve el menor vecino de v , cuya numeraci ó n es mayor a w .
// Si no existe dicho vecino , retorna el n ú mero de v é rtices del grafo
tVertice next ( tVertice v , tVertice w ) ;
// agrega un nuevo arco al grafo entre v é rtices v1 y v2 ( no se
// pueden agregar nuevos v é rtices )
void setEdge ( tVertice v1 , tVertice v2 , int peso ) ;
// borra un arco existente entre v é rtices v1 y v2
void deleteEdge ( tVertice v1 , tVertice v2 ) ;
// dados dos v é rtices , indica si existe un arco entre ellos
int isEdge ( tVertice v1 , tVertice v2 ) ;
// devuelve el peso de un arco del grafo (0 si no existe )
int weight ( tVertice v1 , tVertice v2 ) ;
// obtiene la marca asignada a un v é rtice dado ( ciertos algoritmos
// necesitan marcar los v é rtices )
int getMark ( tVertice v ) ;
// marca un v é rtice con un valor dado
void setMark ( tVertice v , int marca ) ;
};

Algoritmos de grafos

# define NOVISITADO 0
# define VISITADO 1

// Suponiendo todos los nodos marcados como NOVISITADO

void DFS ( tGrafo & G , tVertice v ) ; // Recorrido en profundidad

void BFS ( tGrafo & G , tVertice v ) ; // Recorrido en amplitud
void Dijkstra ( tGrafo & G , int *D , tVertice s ) ; // Camino m á s corto
void Prim ( tGrafo & G , int *D , tVertice s ) ; // Á rbol recubridor m ı́ nimo .