Exámenes

Una matriz definida como (int **a) se almacena en una zona contigua de la memoria. V. F.

No hay ningún método que permita accesos eficientes por clave en un contenedor lineal. V. F.

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). V. F.

Esta sentencia es correcta usando STL y produce los resultados esperados: vector<int> v; v.insert(v.begin() + 5, 100);. V. F.

La altura del árbol es la altura del nodo raíz. V. F.

Un heap es un árbol binario equilibrado en altura. V. F.

Un grid no es una estructura espacil adecuada si la mayoría de los puntos se dispersan en una parte concreta de la escena. V. F.

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. V. F.

La inserción de un dato en una matriz dispersa puede implicar añadir dos nodos a la estructura de datos. V. F.

La utilidad de las cubetas en dispersión es minimizar el número de elementos reasignados a otras posiciones. V. F.

Una lista doblemente enlazada y circular puede considerarse una eedd lineal, de acceso secuencial y dinámica. V. F.

Un dato almacenado en una lista dinámica nunca cambia en su ubicación en memoria, aunque se inserten o eliminen más datos en dicha lista. V. F.

Si la clase A tiene como atributo un vectr de punteros a objetos tipo B, entonces entres ellos solo puede existir una relación de asociación. V. F.

Si P y Q son dos conjuntos de bits de tamaño 7 y 15 respectivamente, entonces PUQ puede tener tamaño 10. V. F.

La operación pop() de un heap montado sobre un vector se puede mejorar eligiendo una lista de listas para dicha implementación del heap. V. F.

Borrar un nodo de un árbol ABB de tamaño 1000 puede tener tan solo un coste de T(1000)=2, es decir, visitando tan solo 2 nodos. V. F.

Elisa lleva razón cuando dice que no va a usar una tabla hash para su implementación porque, aunque necesita realizar búsquedas eficientes, también necesita realizar listado ordenados de datos. V. F.

Un grafo que representa carreteras nacionales puede considerar un grafo ponderado, no dirigido y posiblemente cíclico. V. F.

Un árbol B de orden 5 y altura 3 puede indezar 100 datos. V. F.

Una estructura de datos implementada sobre un array que soporte inserciones en cualquier posición es considerada al mismo tiempo como O(n) y O(1). V. F.

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. V. F.

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. V. F.

Una matriz definida como int a[3][5] se almacena en una zona contigua de memoria. V. F.

Si se utiliza 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 utlizando vectores de apoyo. V. F.

No es más eficiente implentar una cola dinámica usando una lista de STL (list) que utilizando un vector (vector). V. F.

Si se introduce datos ordenados de forma ascendente en un AVL, el tipo de rotación que se ralizaría siempre sería el caso 4. V. F.

Si la tabla hash T1 tiene un gamma=0'8 significa que tiene más casillas vacías que T2 con un gamma=0'7. V. F.

Las operaciones siguientes: it=mimap.find(7); (*it).first=8; son válidas, siendo map<int, int> mimap;. V. F.

Es posible que un árbol B de orden 20 tenga menos altura que otro árbol B con orden 22 albergando exactamente los mismo datos. V. F.

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). V. F.

La intersección de dos conjuntos implementados mediante vectores dinámicos requiere tiempo O(n2). V. F.

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. V. F.

El orden de un árbol representa el número de hijos que obligatoriamente tiene cada nodo en un árbol. V. F.

Para que un árbol binario permita búsquedas eficientes 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. V. F.

En un árbol AVL tras una inserción el proceso de ajuste requiere a lo sumo una única rotación simple o doble. V. F.

Una tabla de dispersión con cubetas disminuye el riesgo de colisiones pero aun así requiere una estrategia de resolución de colisiones. V. F.

En un fichero con registros de longitud variable no siempre es posible reutilizar del hueco liberado por un registro borrado anteriormente para nuevas inserciones. V. F.

Un árbol B utiliza rotaciones para mantener el equilibrio en altura. V. F.

La siguiente definición de vector estático necesita de constructor copia y operador de asignación: template<typename T> class MiVect{ int tama; T *v; public: MiVec(int n){ v=new T[tama=n]; } .... };. V. F.

La misma clase anterior (MiVec) debe definir así el operador corchete "[ ]" para que funcione correctamente (se obvian las comprobaciones de rango): T operator[ ](unsigned i) { return v[i]; }. V. F.

Si se ha instanciado en la clase Biblioteca a MiVect para implementar una relación de asociación con la clase Libro como: MiVect<Libro*> estante; Entonces el destructor de Biblioteca debe entonces eliminar estante ejecutando: delete[ ] estante;. V. F.

Esta sería una posible instrucción dentro de la función que elimina el nodo apuntado por el puntero p de una lista doblemente enlazada: p->sig->ant = p->ant;. V. F.

Un vector de listas es un contenedor válido en términos de eficiencia para implementar una cola con prioridad y un grafo aunque no tanto para una matriz dispersa. V. F.

En un árbol AVL, tanto el borrado como la inserción requieren la localización de algún nodo hoja durante el proceso. V. F.

Un árbol B de orden cinco que está indezando 500 datos puede tener altura 3 (4 niveles). V. F.

Los datos dentro de un nodo de un árbol B deben estar necesariamente ordenados. V. F.

Dada la siguiente definición de un multimapa: multimap<Fecha, Reserva, greater<Fecha> > reservas; la clase Fecha necesita la definición del operator<. V. F.

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: bool ListaEnlazada<T>::insertarAnt(const Iterador<T> &it, const T &dato);. V. F.

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. V. F.

El número de accesos a disco que se necesita para localizar un dato mediate un sistema de ficheros con un índice símple, depende o es directamente proporcional al tamaño de dicho índice. V. F.

Mediante la siguiente definición: int **p; p puede ser una matriz bidimensional, un vector o nada de lo anterior. V. F.

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). V. F.

En la dispersión abierta, el agrupamiento secundario no se produce, pero el primario sí. V. F.

La operación de liberar recursos al eliminar un árbol AVL es O(log n). V. F.

En tablas de dispersión con cubetas, si al buscar llegamos a un hueco no siempre se detiene la búsqueda. V. F.

La búsqueda de un punto es tiempre más eficiente en un amalla regular que en un quadtree. V. F.

Un grafo poco denso (con pocas aristas entre vértices) es más eficiente en espacio el implementarlo utilizando listas de adyacencia que matrices. V. F.

Un heap puede no estar balanceado si los valores se insertan en orden contrario al que se desea recuperar. V. F.

Tanto las colas como las colas con prioridad se implementan igual de eficientes con vectores que con listas enlazadas. La única diferencia viene de si conocemos el tamaño máximo o no. V. F.

El deque permite inserciones eficientes en cualquier posición. V. F.

En las listas doblemente enlazadas, la inserción en la posición anterior a la apuntada por un iterador es O(1). V. F.

Si la clase ClassA tiene el siguiente atributo: map<string, ClassB> *atributo; entonces necesariamente la relación entre ClassA y ClassB es de asociación. V. F.

Una matriz dispersa y una cola con prioridad pueden tener en común el contenedor sobre el que se montan ambas estructuras de datos. V. F.

Si esta sentencia es válida: int nuevoValor = 7; it = mieedd.find(clave); (*it).second[i] = &nuevoValor; Entonces mieedd puede tener esta defición: map<int, vector<int> > mieedd;. V. F.

Un vector estático puede implementar eficientemente a pilas y colas estáticas. V. F.

Se pueden listar los datos de un árbol AVL o ABB en orden inverso a su definición si necesidad de añadir un puntero al padre. V. F.

No es posible que un árbol AVL tenga un nodo hoja a una profundidad 4 y otra a profundidad 8. V. F.

El recorrido en profundidad de un grafo usa normalmente una cola mientras que en anchura su implementación es con una pila o recursiva. V. F.

En el proceso de inserción de un dato en un árbol B se puede repartir la carga de datos con los nodos hermanos en el caso de que dicho dato no quepa en el nodo asignado. V. F.

Dado un nodo de un quadtree cuya codificación es 00-11-01-00, se puede saber exactamente las coordenadas del área al que hace referencia. V. F.

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. V. F.

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. V. F.

Un árbol binario de altura 3 (4 niveles) y 8 nodos puede ser completo. V. F.

Dado el siguiente árbol AVL, la inserción del 13 requiere una rotación doble tipo 3. 11 / \ 5 15 / \ / 1 8 12 \ 9. V. F.

Una lista doblemente enlazada permite realizar búsquedas binarias en tiempo O(log n) si los datos se encuentran ordenados. V. F.

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. V. F.

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. V. F.

Es posible que una casilla de una malla regular esté vacía, al igual que un nodo de un quadtree represente un área vacia. V. F.

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. V. F.

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;. V. F.

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. V. F.

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. V. F.

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). V. F.

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. V. F.

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. V. F.

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. V. F.

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) {} };. V. F.

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. V. F.

La profundidad de todas las hojas de un árbol B es la misma. V. F.