EDP primer parcial 1.

En una cola ¿qué respuesta considera verdadera?. El extremo en que se inserta y extrae recibe el nombre de frente. Los extremos final y frente se intercambian alternativamente. El extremo en que se inserta recibe el nombre de final y el extremo donde se extrae se denomina frente.

Se define una estructura lineal recursiva: a. Una lista no lineal. b. Una lista no vacía sin Primero ni Resto. c. Una estructura lineal vacía o un par formado por un elemento seguido de una estructura lineal. d. Una lista sin correspondencia entre el sucesor del primero y el primero del resto.

En el cuadro resumen de la clasificación de los contenedores, ¿qué casillas aparecen rellenas?. a. Las correspondientes a regímenes de operaciones de inserciones y extracciones consecutivas. b. Las correspondientes a regímenes de operaciones corrientes. c. Todas. d. Las correspondientes a regímenes de operaciones menos frecuentes.

La ejecución de los distintos subprogramas de una aplicación se realiza con una política "último en ser llamado primero en completarse", ¿bajo qué batuta?. Ninguna de las otras respuestas se considera verdadera. La de la pila de compilación. La de la pila de ejecución. La de la pila de listado.

Una cola de prioridad podría definirse como: a. Una cola cuyos elementos se extraen según una propiedad asociada a los elementos y el orden de inserción sólo actúa en caso de igualdad en la propiedad. b. Una cola cuyos elementos se extraen siempre según el orden en que se insertaron y no según una propiedad asociada a los elementos. c. Ninguna de las otras respuestas se considera verdadera. d. Una cola cuyos elementos se extraen siempre según una propiedad asociada a los elementos y nunca influye el orden en que se insertaron.

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

Respecto al método de dispersión extensible basado en directorio, ¿cuántos accesos se requieren para la recuperación de un registro si se mantiene el directorio completo en memoria principal?. Dos: uno para para acceder a la celda correspondiente y otro para actualizarla. Uno solo para acceder a la celda correspondiente. Ninguno. Dos: uno para comprobar la posición del directorio y otro para acceder a la celda correspondienteuno.

¿Qué requiere una clave para poder aplicarle una función de dispersión?. Una representación numérica denominada pseudoclave. Proporcionar resultados diferentes para distintos valores de clave. Poder pasar de una complejidad de búsqueda de O(n) a O(log2n). Una gran cantidad de valores para poder aplicar la búsqueda dicotómica.

¿Qué se entiende por clase universal de funciones de dispersión?. Una tal que la probabilidad de que H(x)=H(y) para x distinto de y es como máximo 1/(tamaño de la tabla). Una tal que la probabilidad de que H(x)=H(y) para x distinto de y es como máximo el tamaño de la tabla. Una tal que la probabilidad de que H(x)=H(y) para x distinto de y es como máximo 1/(H(x)+H(y)). Una tal que la probabilidad de que H(x)=H(y) para x distinto de y es como máximo 1/H(x)+1/H(y).

Respecto a la resolución de colisiones por el método de cadenas separadas, ¿qué respuesta considera verdadera?. Los registros con igual valor de función de dispersión se encadenan en una lista. Todos los registros se encadenan en una sola lista. La búsqueda en las listas se hace con un esquema de búsqueda dicotómica implícita. Desaparece el problema de las colisiones.

Durante la inserción, en el método de dispersión extensible basado en división lineal, ¿cómo se reparten al hacer la división los datos contenidos en la dirección que marca el puntero de división?. Entre la entrada que direcciona el puntero de división y la que marca el puntero de división más 2i*N aplicando Hi+1. Ninguna de las otras respuestas es verdadera. Entre la entrada que direcciona el puntero de división y la que direcciona el punto de inserción. Entre todas las entradas que figuran entre el puntero de división y el punto de inserción.

Se define una estructura lineal recursiva: a. Una lista no lineal. b. Una lista no vacía sin Primero ni Resto. c. Una estructura lineal vacía o un par formado por un elemento seguido de una estructura lineal. d. Una lista sin correspondencia entre el sucesor del primero y el primero del resto.

En el método de dispersión extensible basado en división lineal, ¿cómo se resuelve la sobrecarga de una celda?. Reparte la celda en dos. La mantiene en la propia celda. Siempre reubica de inmediato la sobrecarga en otra zona de la tabla. La sobrecarga en las celdas de la tabla se coloca en una zona de sobrecarga donde se mantiene una lista de celdas para absorber la sobrecarga.

Dada una tabla de dispersión de tamaño 1000, el factor de carga es: 1000. Ninguna de las otras respuestas es verdadera. Depende del número de claves en uso. 2000.

Respecto a las pilas ¿qué respuesta considera verdadera?. Implican la política de acceso "último en entrar, último en salir". Ninguna de las otras respuesta se considera verdadera. Implican la política de acceso "primero en entrar, primero en salir". Implican la política de acceso "último en entrar, primero en salir".

En una tabla de dispersión con resolución de colisiones por direccionamiento abierto con prueba lineal, pk(x)=(H(x)+k)mod (tamaño de la tabla), ¿cuál es la secuencia de búsqueda en la tabla de dispersión hasta encontrar una posición vacía?. Si a una clave le corresponde una dirección d, se busca la primera libre en la secuencia d, d-­1, …, 2, 1, tamaño de la tabla, tamaño de la tabla-­‐1, …, d+1. Si a una clave le corresponde una dirección d, se busca la primera libre en la secuencia 1, 2,…, d-­1, d, d+1,…, tamaño de la tabla. Si a una clave le corresponde una dirección d, se busca la primera libre en la secuencia d, d+1,…,tamaño de la tabla, 1, 2,…, d-­‐1. Independiza la secuencia de prueba de la secuencia csica de posiciones en la tabla.

Respecto a la diferencia operatoria entre las listas secuenciales y las aleatorias ¿qué respuesta considera verdadera?. En unas sólo se pueden realizar las operaciones en los extremos y en las otras en cualquier posición. Ninguna de las otras respuestas se considera verdader. Reside en la forma en que se designa la posición para operar. En unas se permite insertar detrás de la última posición ocupada y en las otras no.

Respecto a listas con acceso directo ¿qué respuesta considera verdadera?. La inserción de un elemento en una posición distinta del extremo final de una lista supone el incremento en la posición de todos los elementos preexistentes entre esa posición y el final. La inserción de un elemento en una posición distinta de los extremos inicial o final de una lista no supone el incremento en la posición de ningún otro elemento preexistente en la lista. La inserción de un elemento en una posición distinta del extremo inicial de una lista supone el incremento en la posición de todos los elementos preexistentes entre esa posición y el principio. Ninguna de las otas respuestas se considera verdadera.

En una tabla de dispersión con resolución de colisiones por direccionamiento abierto, ¿qué ocurre en la secuencia de búsqueda?. Las claves con diferentes valores de la función de dispersión se ordenan descendentemente. Las claves con diferentes valores de la función de dispersión se ordenan ascendentemente. Las claves con diferentes valores de la función de dispersión aparecen consecutivamente. Se entremezclan claves con diferentes valores de la función de dispersión.

Respecto a listas con acceso directo ¿qué respuesta considera verdadera?. Que sus operaciones de inserción y extracción indican explicitamente una posición ordinal concreta donde se aplican pero no la de acceso. Que sus operaciones de inserción, acceso y extracción indican expliciamente una posición ordinal concreta donde se aplican. Que sus operaciones de inserción, acceso y extracción se realizan con independencia de una posición ordinal concreta donde se aplican. Que su operación de acceso indica explicitamente una posición ordinal concreta donde se aplica pero no las de inserción ni extracción.

El coste de recuperación de una clave aleatoria en una tabla de dispersión: I. Es del mismo orden independientemente de la función de dispersión. II. Es del mismo orden independientemente del manejo de colisiones realizado. I: sí, II: sí. I: no, II: sí. I: sí, II: no. I: no, II: no.

Respecto a la implementación de las estructuras lineales, ¿que respuesta es verdadera?. Suele bastar con una lista simplemente encadenada. Ninguna es verdadera. Siempre se debe preferir una lista doblemente encadenada. En el caso de una lista encadenada, es estructuralmente necesario un indicador del nº de elementos.

En una tabla de dispersión con resolución de colisiones por direccionamiento abierto, ¿en qué condiciones, la prueba lineal es razonablemente buena?. No depende de cuan llena se encuentre la tabla. Cuando el factor de carga de la tabla se sitúa entre 0,8 y 1,0. Cuando la tabla no se encuentra demasiado llena. Ninguna de las otras respuestas es verdadera.

Respecto a las operaciones en las listas secuencial ¿qué respuesta considera verdadera?. Fin designa como actual la última posición ocupada, da acceso al último elemento, donde se puede insertar extraer o examinar. Ninguna de las otras respuestas se considera verdadera. Fin designa como actual la posición siguiente a la última ocupada, no da acceso al último elemento sino a una posición vacía donde no se puede insertar ni extraer ni examinar. Fin designa como actual la posición siguiente a la útlima ocupada no da acceso al último elemento, sino a una posición vacía donde se puede insertar, pero no extraer o examinar.

En una resolución de colisiones por el método de cadenas fundidas, ¿qué forma estructural adoptan las claves sinónimas?. La una lista doblemente enlazada. La de una lista encadenada. La de un árbol multirrama. La de una segunda tabla de dispersión.