La asignación dinámica de variables en el heap es más rápida y sencilla que la asignación de variables en la pila de la aplicación. V F. Es posible eliminar una posición de un vector dinámico en tiempo O(1) si no es necesario preservar el orden de los datos. V F. La siguiente implementación del constructor copia de una lista enlazada no contiene errores:
ListaEnlazada<T>::ListaEnlazada(
const ListaEnlazada<T> &lista) {
cabecera = lista.cabecera;
cola = lista.cola;
} V F. La implementación de las matrices dispersas es completamente distinta de la de las matrices ordinarias, estando basada en el uso de las listas enlazadas. V F. El contenedor list<T> de STL implementa el operador [] para acceder directamente al dato almacenado en una posición arbitraria. V F. El procedimiento de borrado de un nodo de un árbol binario de búsqueda con dos hijos es el siguiente:
// Borrar el nodo apuntado por *p
Nodo<T> *borrar = *p;
*p = borrar->izq;
*p->der = borrar->der
delete borrar; V F. Si en la implementación de un sistema se usan únicamente 3 niveles de prioridad en una cola de prioridad para organizar una lista de trabajos, entonces una implementación mediante un vector de listas puede ser más eficiente que heap. V F. La dispersión cerrada con cubetas es una técnica especialmente indicada para la implementación de ficheros dispersos, es decir para la implementación de tablas de dispersión en ficheros en memoria secundaria. (FICHEROS DISPERSOS YA NO SE DA) V F Esto ya ni se da ( es verdadera). Aunque un índice simple es una técnica para acceder eficientemente a un fichero en memoria secundaria, éste se mantiene integramente en memoria primaria mientras está siendo utilizado. V F. El número mínimo de datos que puede indexar un árbol B de orden 3 y dos niveles es 6 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. La función de djb2 de Dan Bernstein es una función de dispersión utilizada normalmente para cadena de caracteres 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 num-Municipios 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. Los dos fragmentos de código mostrados a continuación reservan memoria para 10000 enteros pero el primero lo hace de una manera mas rápido que el segundo.
a) int* a = new int[10000];
b) int* = a[100];
for (int i = 0; i< 100; ++i) a[i] = new int[100]; V F. La siguiente implementación de insertarFinal() en un vector dinámico es correcta:
void VectorDin<T>::insertarFinal (const T& dato) {
if (tamLog == tamFis) {
tamFis == 2;
T* tmp = new[tamFis];
for(int c = 0; c < tamFis; ++c) {
tmp[c] = mem[c];
}
mem = tmp;
}
mem[tamLog++] = dato;
}
V F. Dadas dos listas simplemente enlazadas l1 y l2 de enteros ordenados de menor a mayor, es posible construir una lista l3 también ordenada con todos los elementos de l1 y l2 en tiempo O(n). V F. Implementar un conjunto de enteros para el rango 100-10000 mediante un bitset requiere 1238 bytes. V F. La operación para determinar la hoja con mayor profundidad en un ABB no se puede implementar iterativamente.
V F. Dado el siguiente subárbol de un árbol AVL, para decidir si hay que realizar una rotación a izquierdas a nivel del nodo a (y el tipo, simple o doble) tras insertar un dato por su derecha es necesario conocer el factor de equilibrio del nodo a y el valor del dato almacenado en el nodo b.
...
\
a
/ \
... b
/ \
... ... V F. El tipo de ordenación existente en los nodos en un ABB y en un heap es la misma. La diferencia es que los nodos del segundo se empaquetan en un vector en lugar de crearse individualmente en memoria dinámica. V F. Las operaciones de borrado e inserción a posteriori no deterioran una tabla de dispersión abierta, en contraste con lo que ocurre con la dispersión cerrada. V F. Supongamos que utilizamos una rejilla regular para indexar espacialmente los restaurantes y bares de una ciudad, utilizando celdas de tamaño 500m. Localizar los establecimientos situados a 100 m. a la redonda de la posición actual (x, y) de un usuario se reduce a filtrar todos aquellos elementos situados en la celda que contiene la posición (x, y) situados a una distancia menor de 100m. de esta posicion. V F. Una búsqueda de un registro utilizando un índice simple es mas eficiente que utilizando un árbol B. V F. La siguiente declaración: int** p permite crear las siguientes estructuras de datos en memoria:
V F. Si la declaración del puntero anterior p se realiza como se muestra a continuación entonces p es creado como una variable residente en la pila de aplicación:
void f() {
int **p;
...
}
V F. Supongamos que una lista enlazada tuviera además del puntero cabecera y cola otro denominado antcola, que apunta al nodo anterior al último nodo de la lista enlazada. Entonces la operación borrarUltimo() se podría implementar en tiempo O(1) en lugar de O(n). V F. Sean dos conjuntos a y b de palabras, implementados usando dos vectores de STL instanciados al tipo string. Entonces obtener el vector c = a ∩ b (palabras que están en ambos conjuntos) requiere un tiempo cuadrático. V F. La expresión (a + 5) * b - 3 * c puede representarse en un ordenador mediante un árbol binario de altura 3. V F. Durante las operaciones de borrado en los árboles AVL no se producen desequilibrios, y por tanto no hacen falta rotaciones para resolver estos desequilibrios. V F. Implementar un heap mediante nodos y punteros al igual que el resto de árboles binarios tiene dos graves inconvenientes: consume mucha más memoria y la inserción en la siguiente posición libre del último nivel (durante los push) o el borrado de la última posición del último nivel (durante los pop) no podría implementarse en tiempo constante.
V F. Supongamos que quisieramos guardar las posiciones de unos puntos de interés (POIs) de una ciudad en una tabla de dispersión, dados por dos coordenadas UTM (longitud y latitud) con la forma ddddd.dd. Entonces la siguiente función de dispersión sería adecuada: long hash(float lon, float lat, long tamTabla) { return ( (long)(lon + lat) ) % tamTabla; } V F. Siguiendo con el ejemplo de la pregunta anterior, la tabla de dispersión permitiría obtener el POI existente en una coordenada concreta, pero no los POIS existente en los alrededores de una posición dada (p. ej. a menos de 1 km.).
LA PREGUNTA ANTERIOR:
Supongamos que quisieramos guardar las posiciones de unos puntos de interés (POIs) de una ciudad en una tabla de dispersión, dados por dos coordenadas UTM (longitud y latitud) con la forma ddddd.dd. Entonces la siguiente función de dispersión sería adecuada: long hash(float lon, float lat, long tamTabla) { return ( (long)(lon + lat) ) % tamTabla; } V F. En un árbol B de orden 256 no puede ocurrir nunca que la raiz tenga menos de 128 claves/punteros a descendientes. V F.
