EDP primer parcial 1.2

En el método de dispersión extensible basado en división lineal, ¿con qué función de dispersión se actúa en las dos zonas de la tabla?. Si el punto de entrada en la tabla para buscar, insertar o extraer es menor que la dirección que marca el puntero de división, se aplica la función de dispersión Hi+1(K)=Hi(K)+(2i ó 0). Ninguna de las otras respuestas es verdadera. Con independencia de que el punto de entrada en la tabla para buscar, insertar o extraer sea menor o mayor que la dirección que marca el puntero de división, se aplica indistintamente las funciones de dispersión Hi(K) o Hi+1(K). Si el punto de entrada en la tabla para buscar, insertar o extraer es mayor o igual que la dirección que marca el puntero de división, se aplica la función de dispersión Hi+1(K)=Hi(K)+(2i ó 0).

En al método de dispersión extensible basado en directorio, ¿qué se hace en relación con la profundidad de la celda sobrecargada?. Si es igual que la del directorio, la extensibilidad de la estructura se consigue duplicando la capacidad del directorio por incremento de su profundidad, bit a bit. Si es menor que la del directorio, la extensibilidad de la estructura se consigue duplicando la capacidad del directorio por incremento de su profundidad, bit a bit. Si es igual o mayor que la del directorio, la extensibilidad de la estructura se consigue desdoblando celdas. Si es mayor que la del directorio, la extensibilidad de la estructura se consigue desdoblando celdas.

En el régimen secuencial de una cola respecto a una lista secuencial ¿qué respuesta considera verdadera?. En una cola la secuencia almacenada y el orden de acceso no guardan relación alguna con el orden de inserción. En una lista secuencial los elementos no se pueden almacenar en cualquier lugar, sus posiciones dependen exclusivamente del orden en que se insertan. En la lista secuencial el localismo no tiene ninguna importancia en el sentido de que se penaliza que la siguiente operación se realice en la misma posición o en una cercana a la última realizada. En una cola se separan la inserción y el acceso/extracción ambos se realizan en un orden absolutamente secuencial correspondiente al rden en que los elementos han llegado.

¿Qué se entiende por colisión en la dispersión?. Cuando se intenta extraer una clave que no existe. Cuando se intenta insertar una clave que ya existe. Cuando la función de dispersión arroja diferentes resultados para dos valores de clave distintos. Cuando la función de dispersión arroja el mismo resultado para dos valores de clave distintos.

¿Qué respuesta se adecua a la función de dispersión en el método de análisis de dígitos?. H(x) = x mod (tamaño de la tabla). 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. 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 final.

Hij(x)=((ix+j) mod p) mod (tamaño de la tabla); F= {Hij / 1≤i<p y 1≤j<p}, ¿es una clase universal de funciones de dispersión?. Si p es un cualquier número mayor o igual que el cardinal del conjunto de las pseudoclaves. Si p es un número no primo 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, ¿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. Ninguna de las otras respuestas es verdadera. Cada posición debe admitir las marcas de libre y ocupado. Basta con marcar el lugar como vacío.

La ejecución de los distintos subprograma de una aplicación se realiza con una política "último en ser llamado, primero en completarse" bajo la batuta de llamada pila de ejecución. ¿en qué punto se contrará la ejecución del algoritmo cuando retorne al final el proceso S3 señalado por la flecha en la pila de ejecución?. b. d. c. a.

¿Qué problema entraña el tamaño de la tabla en una dispersión estática?. Una estimación alta provoca redispersiones. Una estimación alta no provoca un gasto adicional de espacio mientras no se ocupen sus posiciones. Una estimación baja sólo puede resolverse mediante la subdivisión de las tablas. Una estimación baja sólo puede resolverse con un proceso costoso de redispersión.

¿Qué problema se puede presentar en una tabla de dispersión cuando se procede a resolver las colisiones por direccionamiento abierto?. Ninguna de las otras respuestas es verdadera. Que la tabla tenga un factor de carga por encima de 0.8. Cada colisión se resuelve con una secuencia diferente. Que la tabla tenga un factor de carga por debajo de 0.8.

Respecto al método de dispersión extensible basado en directorio, ¿cuántos accesos se requieren para la recuperación de un registro?. En general, uno para obtener la entrada del directorio y dos para acceder a la celda correspondiente. 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 otro para acceder a la celda correspondiente. En general, dos para obtener la entrada del directorio y dos para acceder a la celda correspondiente.

En una tabla de dispersión con resolución de colisiones por direccionamiento abierto, ¿dónde se sitúa la clave que colisiona?. En un lugar fuera de la tabla de dispersión que se define como área de sobrecarga. Siempre en un lugar anterior de la tabla de dispersión del que le corresponde. Siempre en un lugar posterior de la tabla de dispersión del que le corresponde. En algún lugar de la tabla de dispersión distinto del que le corresponde.

Respecto a la resolución de colisiones por el método de cadenas separadas, ¿qué respuesta considera verdadera?. La capacidad de almacenamiento total se encuentra limitada únicamente por el área de sobrecarga. Las cadenas se forman en el interior de la tabla. Las cadenas se forman en un área de sobrecarga separada de la tabla. La capacidad de almacenamiento total se encuentra limitada únicamente por la tabla.

Respecto a la resolución de colisiones por direccionamiento abierto, en una resolución de colisiones por el método de cadenas fundidas, ¿qué se mantiene en la lista encadenada de claves sinónimas?. El problema de la mezcla de listas de sinónimos diferentes. La búsqueda dicotómica implícita. Desaparece el problema de las colisiones. Los desplazamientos debidos a las posiciones liberadas durante la extracción.

Respecto a las pilas ¿qué respuesta considera verdadera?. El fondo se confunde con la cima debido a su estructura circular. Se denomina fondo de la pila a la posición más accesible de la misma - la que ocupa el último elemento que se insertó. Ninguna de las otras respuestas se considera verdadera. Se denomina fondo de la pila a la posición menos accesible de la misma - la que ocupe el primero que se insertó.

En una tabla de dispersión con resolución de colisiones por direccionamiento abierto con doble dispersión, pk(x)=(H1(x)+k*H2(x))mod (tamaño de la tabla), respecto a la secuencia de búsqueda en la tabla de dispersión hasta encontrar una posición vacía, ¿qué usa como desplazamiento?. Un valor aleatorio. Ninguna de las otras respuestas es verdadera. Un valor dependiente de la clave. El valor 1.

El método de dispersión extensible basado en división lineal, ¿en qué se basa?. En que la tabla está dividida en tres zonas y que en cada una se aplica una función de dispersión particular. En que se compone de una sola tabla sin división alguna por zonas que soporta múltiples funciones de dispersión. En que la tabla está dividida en dos zonas y que en cada una se aplica la misma función de dispersión. En que la tabla está dividida en dos zonas y que en cada una se aplica una función de dispersión particular.

Respecto a la implementación de una cola mediante un array con una estructura lógica circular como estructura de representación, ¿qué respuesta considera verdadera?. a. En ocasiones es necesario desplazar elementos. b. En ningún caso se origina sobrecarga. c. Se puede producir una falsa sobrecarga. d. Se produce sobrecarga cuando al incrementar el indicador de final coincide con el del frente.

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 que suponga un alto costo?. Desplazar la secuencia de colisión desde la posición anterior a la extraída hasta su principio en búsqueda del próximo registro liberado para tapar el hueco. No permitir extracciones. Desplazar la secuencia de colisión desde la posición siguiente a la extraída hasta su final en búsqueda de un registro para tapar el hueco. Ninguna de las otras respuestas es verdadera.

Respecto al método de dispersión extensible basado en directorio, ¿qué respuesta considera verdadera?. La capacidad de la celda es variable. El tamaño de la celda coincide con la profundidad del directorio. Las celdas discriminan en qué directorio se debe encontrar un registro, en función de los d primeros bits de la pseudoclave. El directorio discrimina en qué celda se debe encontrar un registro, en función de los d primeros bits de la pseudoclave.

Respecto a las operaciones en las listas secuenciales ¿qué respuesta considera verdadera?. Ninguna de las respuestas es correcta. Las operaciones que permiten cambiar la posición actual suponen una variación de la lista. La operación Avanzar no conlleva variación de la lista. La operación Retroceder no convella variación en la lista.

Respeto a listas con acceso directo ¿que respuesta considera verdadera?. Las posiciones no contiguas están separadas por huecos. Las posiciones ocupadas en una lista debe ser continua. Los huecos juegan el papel de posiciones próximas a ser ocupadas. Se permite dejar huecos con posiciones no ocupadas.

¿Con qué objetivo se introduce la dispersió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(log2n). Conocer dónde se encuentra un dato: es una operación con coste O(n2). Conocer dónde se encuentra un dato: es una operación con coste O(n).

En el método de dispersión extensible basado en división lineal, ¿qué criterio resulta más razonable para realizar una división?. Siempre que se sobrecargue la última celda. Cuando el volumen de la zona de sobrecarga sea muy pequeño. Cada vez que se cree una nueva celda de sobrecarga. Siempre que se sobrecargue la primera celda.

Las pilas y las listas recursivas ¿son isomorfas?. La operación Apilar se corresponde con Destruir, Examinar con Último, Desapilar con Resto, las demás operaciones no se tienen en cuenta. La operación Examinar se corresponde con Primero, Apilar y Desapilar se corresponden con sus homónimas. La operación Apilar se corresponde con Crear, Examinar con Primero, Desapilar con Resto y las demás se corresponden con sus homónimas. La operación Apilar se corresponde con Primero, Examinar con Resto y las demás se corresponden con sus homónimas.