EDP ULPGC Tema 1

En una tabla de dispersión con resolución de colisiones por direccionamiento abierto, ¿qué solución cabe adoptar en la extracción a pesar de hacer más larga de lo necesario la secuencia de colisiones en la búsqueda?. Cada posición debe admitir las marcas de libre, ocupado y liberado —cuando es extraído. Las posiciones que se marcan como liberado, se consideran: libres para las inserciones y ocupadas por una clave estúpida para las búsquedas. Cada posición debe admitir las marcas de libre y ocupado. Basta con marcar el lugar como vacío. Ninguna de las otras respuestas es verdadera.

¿Con qué objetivo se introduce la dispersión? Seleccione una: Conocer dónde se encuentra un dato: es una operación con coste O(nʌ2). Conocer dónde se encuentra un dato: es una operación con coste O( n ). Conocer inmediatamente dónde se encuentra o se debe ubicar un dato: son operaciones con coste O(1). Conocer dónde se encuentra un dato: es una operación con coste O(log2 n).

Respecto a la implementación una cola, ¿qué respuesta considera verdadera?. Cuando se representa por una lista simplemente encadenada, las extracciones se hacen por el final por su menor coste. No debe jamás adoptar la ubicación contigua de un array. Puede usarse como estructura de representación una lista simplemente encadenada. Nunca se puede representar con una lista simplemente encadenada.

En una cola, ¿qué régimen de funcionamiento se consigue?. Primero en entrar primero en salir. Último en entrar primero en salir. Primero en entrar último en salir. Último en entrar penúltimo en salir.

Supóngase una tabla vacía de tamaño 7 (índices de 0 a 6) y la función de hash f(k) = (7*k + 3) mod 4. ¿Cómo queda la tabla después de insertar las claves 1, 3, 8, 10 usando direccionamiento abierto para resolver las colisiones? ("--" indica una posición vacía). 3, 10, 1, 8, --, --, --. 1, --, 3, --, 8, --, 10. 3, 10, __, 8, 1, --. --. 1, 3, 8, 10, --, --, --.

¿Qué respuesta se adecua a la función de dispersión en el método de la división o módulo?. Dividir la pseudoclave en un cierto número de partes, cada una de las cuales tiene la misma longitud que la dirección requerida, excepto quizá la última y se suman ignorando el acarreo nal. Cada valor de la pseudoclave se multiplica por sí mismo. Se obtiene una dirección por selección de un número apropiado de bits o dígitos hacia la mitad del cuadrado. Mediante un estudio del conjunto de claves, se seleccionan una serie de dígitos de la pseudoclave para construir la dirección deseada. H(x) = x mod (tamaño de la tabla).

Según su iterabilidad, ¿qué caracteriza a las listas con acceso directo?. Que usan políticas en las que no encaja bien un recorrido. Ninguna de las otras respuestas se considera verdadera. Que incorporan su mecanismo propio de iteración que no permite mantener más de un recorrido a la vez. Que no necesitan de un iterador especial.

H_ij(x)=((ix+j) mod p) mod (tamaño de la tabla); F={H_ij / 1 <= i < p y 1 <= j < p}, ¿es una clase universal de funciones de dispersión?. Si p es un número no primo mayor o igual que el cardinal del conjunto de las pseudoclaves. Si p es un cualquier número mayor o igual que el cardinal del conjunto de las pseudoclaves. Si p es un número primo mayor o igual que el cardinal del conjunto de las pseudoclaves. Si p es un número primo menor que el cardinal del conjunto de las pseudoclaves.

En una tabla de dispersión con resolución de colisiones por direccionamiento abierto, la exploración de la tabla de dispersión hasta encontrar una posición vacía, ¿qué condiciones debe cumplir?. Eficiente y repetible. Eficiente, no hace falta que sea repetible. Importa más la eficiencia que la repetibilidad. Ninguna de las otras respuestas es verdadera.

En el análisis de las tablas de dispersión con resolución de colisiones por direccionamiento abierto con prueba lineal, supóngase que todas las claves tienen la misma probabilidad y que la función de dispersión es uniforme. Se va a insertar una nueva clave en una tabla de tamaño N que ya contiene k elementos. La probabilidad de no encontrar una dirección libre en la primera comparación, y de que se necesite una sola comparación adicional para encontrarle sitio, viene dada por: Ninguna de las otras respuestas es verdadera. (k/N)*(N-k)/(N-1). (N-k)/(N-1). (k-1)/N.

Respecto a la posicion actual en las listas secuenciales, ¿que respuesta considera verdadera?. Ninguna de las otras respuestas se considera verdadera. Nunca es posible retroceder. No puede variar de ninguna manera. Puede variarse mediante operaciones especificas.

Respecto a las listas con acceso directo, ¿que respuesta considera verdadera?. Ninguna de las otras respuestas se considera verdadera. La extraccion de un elemento en una posicion distinta del extremo inicial de una lista supone el decremento en la posicion de todos los elementos preexistentes entre esa posicion y el principio. La extraccion de un elemento en una posicion distinta de los extremos inicial o final de una lista no supone el decremento en la posicion de ningun otro elemento preexistente en la lista. La extraccion de un elemento en una posicion distinta del extremo final de una lista supone el decremento en la posicion de todos los elementos preexistentes entre esa posicion y el final.

Si se tiene una tabla vacia con 100 posiciones y las colisiones se resuelven mediante cadenas separadas, suponiendo una funcion de hash con una distribucion uniforme ¿cual es la probabilidad de que las tres primeras posiciones sigan vacias despues de tres inserciones?. (97 * 96 * 95)/100^3. (97 * 97 * 97)/100^3. (99 * 98 * 97)/100^3. Ninguna de las anteriores.

¿Que problema entraña el tamaño de la tabla en una dispersion estatica?. Una estimacion baja solo puede resolverse con un proceso costoso de redispersion. Una estimacion baja solo puede resolverse mediante la subdivision de las tablas. Una estimacion alta no provoca un gasto adicional de espacio mientras no se ocupen sus posiciones. Una estimacion alta provoca redispersiones.

Respecto de los contenedores asociativos, ¿que respuesta considera verdadera?. La linealizacion de un conjunto de elementos no depende de la implementacion del contenedor. La implementacion de un iterador es independiente del proceso de linealizacion de un conjunto de elementos. Un mismo conjunto de elementos solo puede ser linealizado de una forma. Un mismo conjunto de elementos puede ser linealizado de formas diferentes.

La tecnica de Dispersion Universal consiste en ... Encontrar una funcion de hash valida para cualquier tipo de datos. Usar funciones de hash basadas en matrices de numeros binarios. Elegir aleatoriamente una funcion de hash de una familia de funciones. .

Respecto al metodo de dispersion extensible basado en directorio, ¿cuantos accesos se requieren para la recuperacion de un registro?. En general, dos para obtener la entrada del directorio y uno para acceder a la celda correspondiente. En general, uno para obtener la entrada del directorio y dos para acceder a la celda correspondiente. En general, uno para obtener la entrada del directorio y otro para acceder a la celda correspondiente. En general, dos para obtener la entrada del directorio y dos para acceder a la celda correspondiente.

Respecto a las pilas, ¿que respuesta considera verdadera?. Ninguna de las otras respuestas se considera verdadera. El fondo se confunde con la cima debido a su estructura circular. Se denomina fondo de la pila a la posicion menos accesible de la misma —la que ocupa el primero que se inserto. Se denomina fondo de la pila a la posicion mas accesible de la misma —la que ocupa el ultimo que se inserto.

Respecto a la implementacion de una pila, ¿que respuesta considera verdadera?. No debe adoptar jamas la ubicacion contigua de un array. Cuando adopta la ubicacion contigua de un array, el indicador del numero de elementos no debe servir de referencia para localizar la cima. Si se representa como una lista simplemente encadenada, las inserciones, extracciones y accesos se hacen alternativamente en nodos opuestos. Si se representa como una lista simplemente encadenada, las inserciones, extracciones y accesos se hacen siempre en el primer nodo.

Respecto a la diferencia operatoria entre las listas secuenciales y las aleatorias, ¿que respuesta considera verdadera?. Ninguna de las otras respuestas se considera verdadera. En unas se permite insertar detras de la ultima posicion ocupada y en las otras no. En unas solo se pueden realizar las operaciones en los extremos y en las otras en cualquier posicion. Reside en la forma en que se designa la posicion para operar.

En los contenedores asociativos, ¿que respuesta considera verdadera?. Impera la posicion, mientras que el concepto del valor no esta presente. Impera el valor, mientras que el concepto de posicion no esta presente. El valor y la posicion tienen igual importancia. Ni el valor ni la posicion tienen importancia alguna.

Respecto a las pilas, ¿que respuesta considera verdadera?. Implican la politica de acceso de "ultimo en entrar, primero en salir". Ninguna de las otras respuestas se considera verdadera. Implican la politica de acceso de "primero en entrar, primero en salir". Implican la politica de acceso de "ultimo en entrar, ultimo en salir".

¿Que respuesta considera verdadera?. Dos contenedores lineales son iguales con independencia de los valores y del orden. Dos contenedores lineales son iguales cuando mantienen distinto orden de los valores. Dos contenedores lineales son iguales cuando tienen los mismos valores en el mismo orden. Dos contenedores lineales son iguales cuando tienen los mismos valores con independencia del orden.

¿Que elementos se pueden insertar en una cola de prioridad?. Los que dispongan de un mecanismo para evaluar la prioridad como una operacion que devuelve un valor normalmente ordinal. Pueden ser de cualquier tipo. Los que dispongan de un mecanismo para evaluar la prioridad como una operacion que devuelve un valor no necesariamente ordinal. Los que no acepten prioridades ordenables.

Respecto a la resolucion de colisiones por direccionamiento abierto, en una resolucion de colisiones por el metodo de cadenas fundidas, ¿que se mantiene en la lista encadenada de claves sinonimas?. Los desplazamientos debidos a las posiciones liberadas durante la extraccion. La busqueda dicotomica implicita. El problema de la mezcla de listas de sinonimos diferentes. Desaparece el problema de las colisiones.

Respecto a la resolucion de colisiones por el metodo de cadenas separadas, ¿que respuesta considera verdadera?. La busqueda en las listas se hace con un esquema de busqueda dicotomica implicita. Los registros con igual valor de funcion de dispersion se encadenan en una lista. Desaparece el problema de las colisiones. Todos los registros se encadenan en una sola lista.

Respecto al metodo de dispersion extensible basado en directorio, ¿que respuesta considera verdadera?. Las celdas discriminan, en funcion de los d primeros bits de la pseudoclave, en que directorio se debe encontrar un registro. La capacidad de la celda es variable. Se llama profundidad de la celda al numero de bits consecutivos iniciales iguales de las pseudoclaves almacenadas en la pagina. El tamaño de la celda coincide con la profundidad del directorio.

Segun su iterabilidad, ¿que caracteriza a las listas secuenciales?. Que incorporan su mecanismo propio de iteracion que permite mantener mas de un recorrido a la vez. Que incorporan su mecanismo propio de iteracion que no permite mantener mas de un recorrido a la vez. Que usan politicas en las que no encaja bien un recorrido. Que necesitan de un iterador especial.

Durante la insercion, en el metodo de dispersion extensible basado en division lineal, ¿como se reparten al hacer la division los datos contenidos en la direccion que marca el puntero de division?. Ninguna de las otras respuestas es verdadera. Entre todas las entradas que figuran entre el puntero de division y el punto de insercion. Entre la entrada que direcciona el puntero de division y la que direcciona el punto de insercion. Entre la entrada que direcciona el puntero de division y la que marca el puntero de division mas i+1/(2*N) aplicando H_i.

Respecto a la implementacion de una cola mediante un array con una estructura logica circular como estructura de representacion, ¿que respuesta considera verdadera?. Se evita la sobrecarga cuando los indicadores de frente y final se incrementan modulados por el tamaño del array. En ningun caso se origina sobrecarga. Se puede producir una falsa sobrecarga. Se evita desplazar elementos cuando los indicadores de frente y final se incrementan modulados por el tamaño del array.