Estructura de datos

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.