Un árbol binario de altura 3 (4 niveles) y 8 nodos puede ser
completo. Verdadero Falso. Dado el siguiente árbol AVL, la inserción del 13 requiere
una rotación doble tipo 3.
11
/ \
5 15
/ \ /
1 8 12
\
9 Verdadero Falso. Una lista doblemente enlazada permite realizar búsquedas
binarias en tiempo O(log n) si los datos se encuentran ordenados. Verdadero Falso. Es posible que sea necesario seguir el proceso de búsqueda
en una tabla hash con dispersión cerrada y cubetas de tamaño
5 cuando se llega a una cubeta con 3 datos. Verdadero Falso. En un par de horas se han contabilizado 20 búsquedas y
3 inserciones en un sistema de ficheros con un índice simple y
dos índices secundarios, sin embargo el fichero de datos no ha
modificado su tamaño, lo que resulta imposible. Verdadero Falso. La función de djb2 de Dan Bernstein es una función de
dispersión utilizada normalmente para cadena de caracteres Verdadero Falso. Si se implementa el padrón electoral de todos los ciudadanos de cara a las elecciones mediante un conjunto disjunto del
tipo <municipio, dni>, siendo municipio un entero de 0 a numMunicipios y dni un valor alfanumérico, entonces la operación
para saber si hay duplicidades, es decir, si una persona ya está empadronada en otro municipio puede resolverse en tiempo
constante. Verdadero Falso. Es posible que una casilla de una malla regular esté vacía,
al igual que un nodo de un quadtree represente un área vacia Verdadero Falso. En el siguiente código C++ se produce una fuga de
memoria o memory leak:
int *k = new int[100];
for (i = 0; i <= 100; ++i) { k[i] = 0; }
...
delete[] k;
Verdadero Falso. Las implementación normal de un vector dinámico
implementa una reducción del tamaño físico tamf a la mitad
cuando el tamaño lógico taml cae por debajo de tamf/2. Verdadero Falso. Una clase que implementa una lista circular no incluye
un puntero al nodo cabecera de la misma, al contrario que las
listas simple y doblemente enlazadas. Verdadero Falso. Para simular una cola circular dinámica (p.e. procesos de un S.O)
en el que los datos entran siempre por el mismo lugar pero salen en
cualquier momento es igualmente eficiente utilizar una lista (list) que
un vector de STL. Verdadero Falso. Se ha pensado en implementar una matriz para almacenar todos
los jugadores convocados en todos los partidos de todas las jornadas
de la liga de fútbol. Esta sería una posible estructura de datos para
crear dicha tabla: vector vector vector Jugador jugadores.
Verdadero Falso. Trasferir todos los nodos de una lista simplemente
enlazada l1 al final de otra lista enlazada l2 requiere tiempo
O(n) (nota: l1 queda vacía tras esta operación). Verdadero Falso. Un árbol binario es un grafo normalmente dirigido,
conexo y libre de ciclos, donde el grado de salida de todos los
nodos es igual o inferior a 2. Verdadero Falso. El cambio de posición de los nodos en una rotación
simple de un árbol AVL se implementa con únicamente 4
asignaciones de punteros. Verdadero Falso. En dispersión abierta puede ocurrir que un dato no
quede guardado en la posición indicada inicialmente por la
función de dispersión. Verdadero Falso. Sea Complejo una clase que implementa número complejos de la forma (a + ib) tal como se muestra a continuación.
La declaración de un conjunto de números complejos mediante la declaración STL set(Complejo) complejos; es correcta.
class Complejo {
public:
float real, imag;
Complejo(float real, float imag):
real(real), imag(imag) {}
};
Verdadero Falso. El borrado lógico de un registro en un fichero de datos
puede hacerse con 3 accesos si hay que mantener una lista de
registros borrados o únicamente 1 si no existe dicha lista Verdadero Falso. La profundidad de todas las hojas de un árbol B es la
misma. Verdadero Falso. El tiempo requerido para iterar sobre un vector y
una lista enlazada es el mismo, ya que el orden en ambos
casos es O(n). Verdadero Falso. La intersección de dos conjuntos implementados mediante vectores dinámicos requiere tiempo O(n^2). Verdadero Falso. Una matriz dispersa es una estructura adecuada para
representar la conectividad en un grafo dirigido: ni - nj
si la posición (i, j) contiene 1. Verdadero Falso. El puntero cola en una lista simplemente enlazada
permite que la inserción y el borrado por el final tengan
tiempo constante. Verdadero Falso. El orden de un árbol representa el número de hijos
que obligatoriamente tiene cada nodo en un árbol. Verdadero Falso. Para que un árbol binario permita búsquedas efi-
cientes en tiempo O(log n) debe cumplir la propiedad de
que el dato en cada nodo tenga un valor inferior (o superior) a los de sus dos hijos. Verdadero Falso. En un árbol AVL tras una inserción el proceso de
ajuste requiere a lo sumo una única rotación simple o doble. Verdadero Falso. Una tabla de dispersión con cubetas disminuye el
riesgo de colisiones pero aun así requiere una estrategia de
resolución de colisiones Verdadero Falso. En un fichero con registros de longitud variable no
siempre es posible reutilizar del hueco liberado por un registro borrado anteriormente para nuevas inserciones. Verdadero Falso. Un árbol B utiliza rotaciones para mantener el equilibrio en altura. Verdadero Falso. Una estructura de datos implementada sobre un
array que soporte inserciones en cualquier posición es
considerada al mismo tiempo como O(n) y Ω(1) Verdadero Falso. Un dato almacenado en un vector dinámico que
permanece en dicha estructura de datos a lo largo de todo
su ciclo de vida nunca cambia su posición de memoria. Verdadero Falso. La clase A tiene como atributo un mapa de punteros a objetos tipo B, entonces entre ellos puede existir
una relación de composición. Verdadero Falso. Una matriz definida como (int a[3][5]) se almacena
en una zona contigua de memoria Verdadero Falso. Si se utilizara un vector como contenedor para un
árbol AVL almacenando los hijos del dato (i) en las posiciones (2i) y (2i+1), las inserciones y borrados se realizarían necesariamente en tiempo O(n) aún utilizando vectores de apoyo Verdadero Falso. No es más eficiente implementar una cola dinámica usando una lista de STL (list) que utilizando un vector (vector). Verdadero Falso. Si se introducen datos ordenados de forma ascendente en un AVL, el tipo de rotación que se realizaría siempre sería el caso 4. Verdadero Falso. Si la tabla hash T1 tiene un λ=0.8 significa que
tiene más casillas vacias que T2 con un λ=0.7 Verdadero Falso. Las operaciones siguientes: it=miMap.find(7);
(*it).first = 8; son válidas, siendo map<int, int> miMap; Verdadero Falso. Es posible que un árbol B de orden 20 tenga
menos altura que otro árbol B con orden 22 albergando
exactamente los mismos datos. Verdadero Falso. Todo mapa puede convertirse en un set si a la clase de
objetos que contiene se le dotan de los operadores de comparación necesarios Verdadero Falso. Los datos dentro de un nodo de un árbol B deben estar
necesariamente ordenados. Verdadero Falso. Dada la siguiente definición de un multimapa:
multimap (Fecha, Reserva, greater(Fecha) ) reservas;
la clase Fecha necesita la definicion del operator menor que. Verdadero Falso. La operación de inserción en una lista simplemente enlazada en la posición anterior al nodo apuntado por el iterador it es una operación en tiempo constante. Verdadero Falso. Es más eficiente un quadtree que una malla regular a nivel de consumo de memoria para almacenar todos los códigos
postales de EEUU Verdadero Falso. El número de accesos a disco que se necesita para localizar
un dato mediante un sistema de ficheros con un índice símple,
depende o es directamente proporcional al tamaño de dicho
índice. Verdadero Falso. Mediante la siguiente definición: int **p; p puede ser
una matriz bidimensional, un vector o nada de lo anterior. Verdadero Falso. Una cola con prioridad siempre tendrá un push() en O(1)
independientemente de la implementación concreta (vectores,
vector de listas o listas de listas) Verdadero Falso. Averiguar las aristas de entrada a un nodo en un grafo dirigido implementado mediante listas invertidas es más costoso
que implementado sobre una matriz de adyacencia Verdadero Falso. Es peligroso usar un vector dinámico de objetos (no de
punteros) si otra clase va a tener una asociación con estos
objetos. Mirar el siguiente ejemplo, en el que la relación de
composición entre A y B se implementa como: vector(B). Verdadero Falso. Tanto si una matriz de 100x100 enteros se crea en la pila (int m[100][100]) como si se crea en memoria dinamica (int **m), el acceso al elemento situado en la posicion (20, 20) se realiza de la misma manera: print(m[20][20]) Verdadero Falso. Si no es necesario respetar el orden de los elementos de un vector dinamico, entonces el borrado de un dato en una posicion arbitraria tiene el mismo orden de complejidad que el borrado en una lista doblemente enlazada. Verdadero Falso. Invertir el orden de los elementos de una lista simplemente enlazada requiere tiempo O(n^2) Ejemplo: 1-2-3-4 a 4-3-2-1 Verdadero Falso. El recorrido de un arbol binario (inorden, preorden o postorden) requiere una pila para su implementacion de forma que pueda volverse hacia atras, es decir al nodo ancestro tras visitar los descendientes. Verdadero Falso. Todas las estructuras de datos de la familia de los arboles sirven para realizar busquedas eficientes, con distintos grados de eficiencia y diversos ambitos de aplicacion Verdadero Falso. El factor maximo de carga recomendado 0.7 es solo para las tablas de dispersion cerrada, donde las colisiones tienen un gran impacto en la eficiencia. Verdadero Falso. El principal problema de las mallas regulares es su incapacidad para adaptarse a conjuntos de datos espaciales que no se distribuyan de manera homogenea (zonas con mucha densidad frente a otras vacias). Verdadero Falso. Como un arbol es un grafo conexo sin ciclos entonces un recorrido en anchura (BFS) empezando en la raiz es un recorrido del arbol por niveles. Verdadero Falso. Si en un fichero indexado el indice en memoria se desactualiza por algun problema en la aplicacion, la operacion de borrado puede realizar un borrado de un registro incorrecto. Verdadero Falso. La insercion de una clave en un arbol B puede implicar duplicaciones de nodos en todos los niveles del arbol. Verdadero Falso. Una cola con prioridad es siempre una eedd lineal, de acceso secuencial y dinámica. Verdadero Falso. Un patrón de clase instanciado para el tipo T=int puede que no compile al instanciarlo para T=MiClase Verdadero Falso. Si la clase A tiene como atributo un vector dinámico de objetos tipo B entonces entre ambas clases debe existir una relación de composición. Verdadero Falso. Un dato almacenado en un vector dinámico, que no sufre ningún tipo de modificación, puede que cambie su posición
de memoria. Sin embargo no ocurre lo mismo si se insertara en una lista enlazada Verdadero Falso. Si P y Q son dos conjuntos de bits de tamaños 7 y 15 respectivamente, entonces P.interseccion(Q) puede tener tamaño 10. Verdadero Falso. Dado el siguiente árbol B, una inserción de un dato en los subárboles B o C implica una rotación doble, primero a izquierdas y luego a derechas. Verdadero Falso. En una tabla hash que contiene casillas vacías y disponibles, la búsqueda no para cuando se encuentra una casilla
disponible. Verdadero Falso. Averiguar los ejes de entrada a un nodo en un grafo dirigido implementado mediante listas invertidas es más
eficiente que implementado sobre una matriz de adyacencia Verdadero Falso. Si un nodo de un árbol B de orden 21 se queda con 10 elementos, entonces el nodo siempre desaparece reubicando sus datos en los nodos hermanos. Verdadero Falso. Para almacenar millones de estrellas se ha optado por utilizar una malla regular. Para implementar la función de búsqueda de una estrella conocida su ascensión y declinación sólo es necesario visitar una casilla de la malla.
Verdadero Falso. Una matriz definida como (int **a) se almacena en una zona contigua de memoria Verdadero Falso. No hay ningún método que permita accesos eficientes por clave en un contenedor lineal Verdadero Falso. La operación de inserción de un nodo al final de una lista simplemente enlazada implementada con cola y cabecera necesita un tiempo O(1)
Verdadero Falso. Esta sentencia es correcta usando STL y produce los resultados esperados:
vector<int> v;
v.insert(v.begin() + 5,100);
Verdadero Falso. La altura del árbol es la altura del nodo raíz Verdadero Falso. Un heap es un árbol binario equilibrado en altura. Verdadero Falso. Un dato almacenado en una lista dinámica que no sufre ningún tipo de modificación puede que cambie su posición de memoria Verdadero Falso. La inserción de un dato en una matriz dispersa puede implicar añadir dos nodos a la estructura de datos Verdadero Falso. La utilidad de las cubetas en dispersión es minimizar el número de elementos reasignados a otras posiciones Verdadero Falso.
|