Pre Sol

Universidad Diego Portales Facultad de Ingenier´ıa ´ tica Escuela de Informa

Curso: Estructura de Datos ´n Ayudante: Jaime Guzma

Simulacro Solemne II Estructuras de datos

Duracin: 90 minutos. 1. [ Pregunta 1 ] El esquema de hashing compuesto consiste en usar una tabla de hash primaria de tama˜ no N , donde cada posici´ on de la tabla contiene otra tabla de hash de tama˜ no M . De esta forma se tiene una tabla primaria, y a lo m´ as N tablas secundarias. El esquema utiliza dos funciones de hash, h1 y h2 . Para almacenar un elemento, se calcula la posici´ on usando h1 , y luego, dentro de la tabla secundaria que se encuentra en esa posici´on, se aplica la funci´ on h2 , y se almacena el valor en esa posici´on. Si dentro de esta tabla secundaria se produce una colisi´ on, entonces se resuelve por encadenamiento. Considerando N = 7, M = 10, h1 (x) = x + 5 mod N , y h2 (x) = (3x + 2) mod M , inserte los siguientes valores en una tabla de este tipo, y muestre el estado final de la tabla. h40, 30, 35, 4, 2, 82, 63, 9, 7i. Solucion En este esquema la tabla de hash primaria tiene tama˜ no N = 7, y cada tabla secundaria contiene una tabla de tama˜ no M = 10. Para saber en qu´e posiciones de cada tabla se debe ingresar el dato, se necesita calcular h1 y h2 para todos los valores de x: x 40 30 35 4 2 82 63 9 7

h1 (x) 3 0 5 2 0 3 5 0 5

h2 (x) 2 2 7 4 8 8 1 9 3

De esta manera la tabla de hash construida queda de la manera que se muestra en la figura 1.

2. [ Pregunta 2 ] a) Considere un heap que contiene ms de 3 elementos. El valor m´as alto contenido en el heap siempre se encuentra en la posici´ on 0. En qu´e posiciones se puede encontrar el segundo valor m´ as alto?, En qu´e posiciones puede encontrarse el tercer valor m´as alto? Solucion El segundo valor m´ as alto en un heap tiene exactamente un valor mayor que ´el, por lo tanto tiene que ser un hijo directo de la ra´ız del heap. Puede ser el hijo izquierdo o el hijo derecho, por lo tanto puede estar en las posiciones 1 ´ o 2. 1

El tercer valor m´ as alto tiene que tener exactamente dos valores mayores que ´el. Como no hay relaci´ on entre los hijos directos de la ra´ız, podr´ıa estar en la posici´on 1 o en la 2. Como no puede estar a distancia mayor que 2 de la ra´ız, entonces tambi´en puede estar entre las posiciones 3 a la 6. b) Considere un arreglo de N elementos, ordenado de mayor a menor. Corresponde este arreglo a heap?. Si la respuesta es s´ı, demuestre por qu´e (no sirve poner un ejemplo) ; si la respuesta es no, entonces muestre un contraejemplo y explique por qu´e no corresponde a un heap. Soluci´ on La respuesta es s´ı. Por qu´e?, considere un arreglo de N elementos A = ha1 , a2 , a3 , . . . , aN i. Si el arreglo est´ a ordenado de mayor a menor, entonces se cumple que a1 > a2 > a3 > . . . > aN . La relaci´ on de heap implica que todo elemento es mayor que sus hijos ; esto es ai > a2i+1 y ai > a2i+2 . Como el arreglo est´ a ordenado de mayor a menor, entonces la propiedad de heap se cumple trivialmente.

3. [ Pregunta 3 ] Considere la siguiente estructura para representar un ´arbol binario de b´ usqueda (ABB): class ArbolBin { NodoBin raiz; ArbolBin() { raiz = null; } void insert(int k) { if(raiz != null) raiz.insert(k); else raiz = new NodoBin(k); } void delete(int k) { if(raiz != null) raiz.delete(k); } void modify(int k) { if(raiz != null) raiz.modify(k); } void maxDepth() { if(raiz != null) raiz.maxDepth(); } int previous() { if(raiz != null) return raiz.previous(); } } class NodoBin { int key; NodoBin hijos[2]; NodoBin(int k) { key = k; hijos[0]=hijos[1]=null; } void insert(int k) { ... ... } // inserta un nodo con llave k en el rbol void delete(int k) { ... ... } // borra el nodo con llave k del rbol }

2

(a) a) Escriba el m´etodo int previous(), para la clase NodoBin. El m´etodo debe retornar el valor de la llave del nodo que antecede a aqu´el sobre el cual se ejecuta el m´etodo. Indique la complejidad de su soluci´ on.

Soluci´ on El predecesor de un nodo se puede dividir en dos casos: si el nodo tiene hijo izquierdo, entonces el predecesor es el m´ aximo nodo de esa rama ; si el nodo no tiene hijo izquierdo, entonces es el primer padre al que se puede llegar a traves de una rama derecha. int previous() { if(hijo[0] != null) { return hijo[0].maximo(); } p = padre(); h = this; while(p != null) { if(p.hijo[1] == h) { return h.key; } p = p.padre(); h = h.padre(); } return -1; } int maximo() { NodoBin m = this; while(m.hijo[1] != null) { m = m.hijo[1]; } return m.key; } Esta soluci´ on, suponiendo que el ´arbol esta balanceado, implica recorrer toda una rama completa del ´ arbol para encontrar el m´aximo, o bien subir por una rama llegando, en el peor caso, hasta la ra´ız. La complejidad por lo tanto es O(log n). (b) b) Escriba el m´etodo void modify(int k), para la clase NodoBin. El m´etodo debe sumar el valor k a cada una de las llaves almacenadas en el ´arbol. Indique la complejidad de su soluci´ on. Soluci´ on Para recorrer una sola vez cada una de las nodos del ´arbol, se puede utilizar uno de los algoritmos de recorrido, por ejemplo, inOrder: void modify(int k) { if(hijo[0] != null) { hijo[0].modify(k); } key += k; if(hijo[1] != null) { hijo[1].modify(k); } } Esta soluci´ on debe recorrer todos los nodos del ´arbol exactamente una vez, por lo tanto su complejidad es O(n). (c) c) Escriba el m´etodo void maxDepth(), para la clase NodoBin. El m´etodo debe imprimir en pantalla la llave de ´el o los nodos que tienen la mayor profundidad en el ´arbol. Soluci´ on

3

Esta soluci´ on se puede implementar efectuando dos recorridos sobre el ´arbol. En el primero se determina cu´ al es la m´ axima profundidad que hay en el ´arbol, lo que se puede lograr haciendo un recorrido inOrder. En el segundo recorrido, una vez identificada la profundidad m´axima, se imprimen todos los nodos que tienen esa profundidad. void maxDepth() { int d = searchMaxDepth(); printMaxDepth(0,d); } int searchMaxDepth(int d) { int h1depth = 0; int h2depth = 0; if(hijo[0] != null) { h1depth = hijo[0].searchMaxDepth() + 1; } if(hijo[0] != null) { h2depth = hijo[1].searchMaxDepth() + 1; } if(h1depth > h2depth) { return h1depth; } return h2depth; } void printMaxDepth(int currentDepth, int d) { if(hijo[0] != null) { hijo[0].printMaxDepth(currentDepth+1, d); } if(currentDepth == d) { print("Nodo: "+key); } if(hijo[1] != null) { hijo[1].printMaxDepth(currentDepth+1, d); } } 4. [ Pregunta 4 ] Se tiene la siguiente clase: NodoArbol { int info; int menores; NodoArbol izq, der; } En este ´ arbol los nodos tienen adem´ as de la clave, la cantidad actualizada de nodos que hay en el sub-´ arbol izquierdo (o sea, con claves menores). Esto ayuda a encontrar rapidamente el k-esimo elemento de un ´ arbol con el siguiente algoritmo: • si el nodo tiene k-1 menores, lo hemos encontrado (retornar puntero) • si el nodo tiene una cantidad de elementos menores mayor que el k buscado, retornamos lo que resute de buscar el k´esimo elemento en el subarbol izquierdo • si el nodo tiene menos cantidad de menores que lo buscado entonces se retorna lo que de como resultado de buscar el (k-menores1)-´esimo en el ´arbol derecho.

4