Inserción Binaria

1) En el Código 1 se muestra la implementación de la inserción binaria. En el lugar indicado como (1), debe incluirse la operación:
A) i=R
B) a[m] <= x
C) a[m] >= x
D) Ninguna de las anteriores

2) En el Código 1 se muestra la implementación de la inserción binaria. En el lugar indicado como (2), debe incluirse la operación:
A) j:=j+1;
B) j:=j-1;
C) a[j]:=a[j+1];
D) Ninguna de las anteriores

3) En el Código 1 se muestra la implementación de la inserción binaria. En el lugar indicado como (3), debe incluirse la operación:
A) a[R]:=x;
B) L:=x;
C) R:=x;
D) Ninguna de las anteriores

4) En el Código 1 se muestra la implementación de la inserción binaria. El número de movimientos en el peor caso es (se utiliza la misma notación que en el texto base):
A) 1+2+…+n
B) 1+2+ … +n-1
C) 1+2+…+n-2
D) Ninguna de las anteriores

5) En el Código 1 se muestra la implementación de la inserción binaria. El número de movimientos en el caso promedio es (se utiliza la misma notación que en el texto base):
A) El mismo que el número de comparaciones en el caso promedio
B) De orden log n
C) De orden nlogn
D) Ninguna de las anteriores

Clasificación y Tablas de Dispersión

6) Determinar cuál de las afirmaciones siguientes es cierta:
I. Para clasificar un arreglo siempre es más adecuado la clasificación rápida (quicksort).
II. Es posible combinar un método de clasificación de memoria secundaria con uno de memoria primaria para mejorar el rendimiento general.
A) I: sí, II: sí
B) I: sí, II: no
C) I: no, II: sí
D) I: no, II: no

7) En las tablas de dispersión (hash) se dice que se ha producido desbordamiento cuando:
A) Dos llaves distintas se aplican sobre la misma celda.
B) Toda la tabla está llena.
C) Una celda contiene un registro
D) Ninguna de las anteriores

8) En las tablas de dispersión (hash) se dice que se ha producido colisión cuando:
A) Una celda contiene un registro.
B) Toda la tabla está llena.
C) Dos llaves distintas se aplican sobre la misma dirección de memoria.
D) Ninguna de las anteriores

9) En las tablas de dispersión (hash) el factor de carga (o densidad de carga) es:
A) El cociente entre el número de llaves en uso y el número total de llaves posibles
B) El cociente entre el número de llaves en uso y el número total de registros almacenables
C) El cociente entre el número de llaves no ocupadas y el número total de llaves posibles
D) Ninguna de las anteriores

10) En las tablas de dispersión (hash) la densidad de llaves es:
A) El cociente entre el número de llaves en uso y el número total de llaves posibles
B) El cociente entre el número de llaves en uso y el número total de registros almacenables
C) El cociente entre el número de llaves no ocupadas y el número total de llaves posibles
D) Ninguna de las anteriores

Listas Multireferenciadas

11) Determinar cuál de las afirmaciones siguientes es cierta, en relación con las listas multireferenciadas:
I. El nodo que vertebra la estructura no contiene la información directamente sino un puntero a la misma.
II. La información se almacena en una variable referenciada a la que se añade un contador que lleva la cuenta de cuántos punteros (listas) están apuntando en cada momento a la mencionada información.
A) I: sí, II: sí
B) I: sí, II: no
C) I: no, II: sí
D) I: no, II: no

TDAs y Colas

12) Se está desarrollando una aplicación en la que es necesario decidir qué TDA utilizar para almacenar los datos que entran por un dispositivo de entrada-salida serie. Los datos son información de una máquina industrial y están formados por secuencias separadas por el carácter $. Cada secuencia tiene como máximo 20 elementos. Una vez almacenados en el TDA se tratarán uno a uno con el mismo orden en que han llegado. El número de secuencias puede considerarse infinito ya que la máquina funciona 24 horas al día. Entonces el TDA adecuado es:
A) Un arreglo
B) Una pila.
C) Una cola.
D) Ninguna de las anteriores.

13) Para el desarrollo de la pregunta anterior, la implementación de la estructura elegida debe ser:
A) Estática
B) Dinámica
C) Es indiferente que sea estática o dinámica.
D) Ninguna de las anteriores.

Árboles

14) Determinar cuál de las afirmaciones siguientes es cierta, en relación a los árboles binarios:
I. Un árbol perfectamente balanceado siempre tiene mejor coste que cualquier otro.
II. Los árboles AVL siempre tienen peor coste que los árboles que tienen sus algoritmos (inserción, búsqueda,…) implementados con el criterio de árbol perfectamente balanceado.
A) I: sí, II: sí
B) I: sí, II: no
C) I: no, II: sí
D) I: no, II: no

15) Determinar cuál de las afirmaciones siguientes es cierta, en relación a los árboles AVL:
I. La inserción de un nodo puede producir como máximo una rotación, simple o doble.
II. La eliminación de un nodo puede producir como máximo una rotación, simple o doble.
A) I: sí, II: sí
B) I: sí, II: no
C) I: no, II: sí
D) I: no, II: no

16) Determinar cuál de las afirmaciones siguientes es cierta, en relación a la eliminación en los árboles AVL:
I. Cuando que se elimina un nodo por la derecha será necesario rebalanceo si el balance de un nodo N es -1 y el rebalanceo es LL.
II. Cuando que se elimina un nodo por la derecha será necesario rebalanceo si el balance de un nodo N es -1 y el rebalanceo es RL.
A) I: sí, II: sí
B) I: sí, II: no
C) I: no, II: sí
D) I: no, II: no

17) Se dispone de un árbol B de orden 2 formado por la introducción sucesiva de los siguientes elementos: 32, 62, 47, 10, 24, 37, 6, 30, 54, 35, 15, 41, 43, 45, 26, 27, 17. Determinar cuál de las afirmaciones siguientes es cierta:
I. Antes de insertar el 17 la página que contiene el 47 también contiene el 43 y el 45.
II. En la situación final la página que contiene al 32 es la raíz y apunta por la izquierda a una página que contiene el 15 y el 26.
A) I: sí, II: sí
B) I: sí, II: no
C) I: no, II: sí
D) I: no, II: no

18) En el árbol anterior se elimina la llave 32. Determinar cuál de las afirmaciones siguientes es cierta:
I. En la situación final la página raíz contiene las llaves 15, 30, 41, 47.
II. En la situación final la página que contiene al 24 también contiene el 17, 26 y 27.
A) I: sí, II: sí
B) I: sí, II: no
C) I: no, II: sí
D) I: no, II: no

19) El árbol BBS resultante de la inserción consecutiva de los enteros 11, 8, 13, 9, 12:
A) Tiene un grafo equivalente al árbol de búsqueda formado por la inserción sucesiva de 11, 8, 9, 13, 12
B) En el resultado final, el nodo con valor 9 apunta horizontalmente al de valor 8 por la izquierda y 12 por la derecha
C) El nodo de valor 8 es la raíz
D) Ninguna de las anteriores

20) El árbol BBS resultante de la inserción consecutiva de los enteros 21, 23, 22, 24
A) Ha necesitado un rebalanceo quedando finalmente el 23 como raíz
B) Ha necesitado rebalanceo quedando finalmente el 21 como raíz
C) No ha necesitado rebalanceo
D) Ninguna de las anteriores