En dispersión abierta, al no tener tanto impacto las colisiones, es recomendable usar
tamaños de tablas iguales o menores al número de elementos a insertar para limitar el
consumo de memoria V F. Iterar sobre un vector dinámico es siempre más rápido que sobre una lista enlazada V F. Una matriz definida como int **a se almacena en una zona contigua de memoria F V. La inserción de un dato en una matriz dispersa puede implicar añadir dos nodos a la
estructura de datos F V. En una tabla hash que contiene casillas vacías y disponibles, la búsqueda no para cuando
se encuentra una casilla disponible V F. Tanto árboles binarios de búsqueda como árboles AVL son sensibles al orden de
introducción de un conjunto de datos, pudiendo haber una diferencia grande de rendimiento
entre una situación y otra V F. Si el conjunto de enteros A:{1,2,4,8,16,32,64,128,256,512,1024,2018} es representado
mediante un conjunto de bits necesitamos un vector con más de 2000 bytes para almacenarlo V F. Cuando un índice simple es modificado, los cambios son inmediatamente reflejados en el
fichero donde se guarda el índice V F. Si la posición de una estrella en el firmamento queda determinada por su ascensión y
declinación, un árbol AVL es una estructura de datos adecuada para localizar aquellas
situadas en una ventana rectangular de la bóveda celeste. V F. La utilidad de las cubetas en dispersión es minimizar el número de elementos
reasignados a otras posiciones V F. En una lista simplemente enlazada el borrado del último elemento requiere tiempo lineal
incluso si se mantiene permanentemente un puntero al mismo V F. Una vez localizado un nodo en un árbol ABB, su borrado requiere tiempo constante V F. Un grafo que representa carreteras nacionales puede considerarse un grafo ponderado,
no dirigido y posiblemente cíclico V F. No hay ningún método que permita accesos eficientes por clave en un contenedor lineal V F. Una lista doblemente enlazada permite realizar búsquedas binarias en tiempo O(log n)
si los datos se encuentran ordenados 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. Una lista doblemente enlazada y circular puede considerarse un eedd lineal, de acceso
secuencial y dinámica 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. Todo árbol binario puede representarse mediante un vector. Si el vector está compacto,
entonces el árbol es completo V F. Un vector dinámico es una estructura de datos básica que puede ser utilizada en la
implementación de asociaciones y composiciones múltiples cuando no hay restricciones o
necesidades especiales en las mismas V F. Si se usa un mapa de STL para representar un índice simple en memoria, entonces
puede localizarse cualquier registro del fichero de datos con O(log n) accesos a disco V F. Elisa lleva razón cuando dice que no va a usar una tabla hash para su aplicación porque,
aunque necesita realizar búsquedas eficientes, también necesita realizar listados ordenados
de datos 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. Una cola con prioridad es siempre una eedd lineal, de acceso secuencial y dinámica V F. Si P y Q son dos conjuntos de bits de tamaños 7 y 15 respectivamente, entonces
P.intersección(Q) puede tener tamaño 10 V F. La dispersión abierta tiene una implementación más sencilla y un rendimiento más
predecible que la dispersión cerrada 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. Un árbol B de orden 5 y altura 3 puede indexar 100 datos V F. La altura del árbol es la altura del nodo raíz V F. Si la clase A tiene como atributo un vector de punteros a objetos de tipo B, entonces
entre ellos sólo puede existir una relación de asociación V F. 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 V F. La técnica de dispersión doble evita la aparición de agrupamientos primarios pero no
secundarios V F. Si P y Q son dos conjuntos de bits de tamaños 7 y 15 respectivamente, entonces PUQ
puede tener tamaño 10 V F. Un dato almacenado en una lista dinámica nunca cambia su ubicación en memoria,
aunque se inserten o eliminen más datos en dicha lista V F. Un árbol B utiliza rotaciones para mantener el equilibrio en altura V F. Dos árboles ABB equivalentes pueden tener diferente altura, diferente raíz y diferentes
hojas V F. Al igual que los índices simples, los árboles B se mantienen permanentemente en
memoria. Su ventaja respecto a los índices es la mayor eficiencia en la búsqueda de una
clave: O(Log2 n) de los índices frente a O(Logm n) de los árboles B, siendo m el orden del
mismo y siempre mucho mayor que 2 V F. En los árboles AVL las rotaciones garantizan que el número de descendientes por la
izquierda y derecha de un nodo difiere a lo sumo en 1 V F. Un heap permite obtener el dato con menor prioridad en O(1) V F. Un patrón de clase instanciado para el tipo T=int puede que no compile al instanciarlo
para T=MiClase V F. Un heap es un árbol binario equilibrado en altura V F. La unión, intersección y diferencia de conjuntos de bits requiere O(n) siendo n el valor
máximo que puede ser guardado en dichos conjuntos V F. 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 V F. Esta sentencia es correcta usando STL y produce los resultados esperados: vector{int}
v; v.insert(v.begin0 t 5, 100); V F. Una tabla de dispersión construida correctamente permite localizar un dato por su clave
de manera más eficiente que un árbol AVL V F. Los agrupamientos secundarios se producen cuando claves que son dispersadas a
posiciones diferentes siguen la misma secuencia de búsqueda para localizar una posición
disponible V F. La intersección de dos conjuntos implementados mediante vectores dinámicos requiere
tiempo O(n^2) 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 puntero cola en una lista simplemente enlazada permite que la inserción y el borrado
por el final tengan tiempo constante. 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 aún 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. 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. V F. 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. V F. 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. 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 ᘯ(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. Una matriz definida como (int a[3][5]) se almacena en una zona contigua de memoria V F. 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 V F. No es más eficiente implementar una cola dinámica usando una lista de STL (list) que
utilizando un vector (vector) F V. Si se introducen datos ordenados de forma ascendente en un AVL, el tipo de rotación
que se realizaría sería el caso 4 V F. Si la tabla hash T1 tiene un λ = 0.8 significa que tiene más casillas vacías que T2 con un
λ = 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 mismos datos. V F. El operador de asignación de la clase Matriz<T>::operator= debe siempre destruir la
matriz destino de la asignación V F. El operador de la clase Matriz<T>::operator+= devuelve el objeto resultado por copia V F. La implementación de conjuntos mediante vectores realiza la intersección en tiempo
lineal V F. El problema que poseen los conjuntos de bits es que el ID de un elemento debe ser un
entero desde 0 hasta el tamaño del conjunto -1. Para convertirlo en un ID genérico se necesita
otra EEDD V F. Para almacenar 3841 datos en un conjunto de bits, debo crear un buffer de 480 bytes V F. a.intersec(b+a) ==a es correcto V F. El resultado de realizar esta operación: char mascara = 1 << (500%8); es 0000100 V F. El tiempo para eliminar un dato en una posición arbitraria de una lista en lineal V F. El tiempo para eliminar un dato en una posición apuntada por un iterador es lineal V F. Para eliminar e insertar un dato en posiciones intermedias de una lista se necesita un
puntero a la posición anterior al dato que se va a insertar/borrar F V. Se puede realizar la operación merge_sort entre dos listas ordenadas en tiempo O(n+m),
siendo n y m los tamaños respectivos de ambas listas V F. Transferir todos los nodos de una lista doblemente enlazada L1 al final de otra lista
enlazada L2 requiere tiempo O(1) (nota: L1 queda vacía tras la operación) V F. El siguiente código inserta correctamente en un caso genérico (lista con datos), un nuevo
nodo apuntado por p delante de la posición del nodo apuntado por q en una lista doblemente
enlazada y circular:
p→siguiente = q;
p→anterior = q→anterior;
q→anterior = p;
p→anterior→siguiente = q; V F. El contenedor list<T> de STL implementa el operador [ ] para acceder directamente al
dato almacenado en una posición arbitraria 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. Para simular una lista circular (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 utilizado la siguiente estructura de datos para implementar un editor de texto
interactivo: list<vector<char>> texto. La implementación de la operación pulsarTecla(char c)
sería la siguiente: i->insert(i->begin() + pos, c), siendo i un iterador de la lista que apunta a la
línea donde se encuentra el cursor y pos un entero positivo que indica la posición del cursor
en dicha línea. 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 inserción de un dato d al principio de un vector v de STL mediante v.insert(v.begin(),
d) requiere tiempo O(1). V F. Un vector estático puede implementar eficientemente a pilas y colas estáticas. V F. Una lista simplemente enlazada puede implementar eficientemente a pilas y colas
dinámicas. V F. Una deque puede implementar eficientemente a pilas y colas dinámicas. V F. Se usa una pila para resolver aquellos procesos recursivos que agotan la pila. 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. Una stack o una queue se implementa por defecto sobre un std:list pero se puede cambiar
en ambos casos el contenedor. V F. Para hacer que una priority_queue de STL considere como dato más prioritario al mayor,
se debe definir con el operator greater V F. Necesito una pila para eliminar la recursividad de la sucesión de Fibonacci V F. Conocer la altura de un ABB da información sobre el número de datos que contiene V F. Un árbol binario que representa expresiones matemáticas se resuelve mediante un
recorrido en postorden V F. Para obtener los datos ordenados de un ABB se hace un recorrido en preorden V F. Todo proceso recursivo que opere sobre un ABB se puede resolver de forma iterativa
mediante una pila de punteros a nodos de tipo ABB V F. Al insertar la siguiente secuencia en un ABB: {4, 3, 7, 12, 2, 6, 5, 13}, el borrado del 12
implica una llamada a la función borraMin() V F. Para recorrer un árbol binario por niveles se necesita una cola. Este recorrido pasaría
primero por la raíz,luego por raíz-> izq, luego por raiz->der, raiz->izq->izq, raíz->izq->der,
etc... V F. Los recorridos recursivos Preorden, Inorden y Postorden permiten iterar sobre los
árboles hacia delante y detrás. 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. Se pueden listar los datos de un árbol AVL o ABB en orden inverso a su definición sin
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. En los árboles AVL las rotaciones garantizan que el número de descendientes por la
izquierda y derecha de un nodo difiere a lo sumo en 1. V F. Es posible que exista una secuencia de datos que al ser insertada en un árbol AVL no
provoque rotaciones 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. La operación pop( ) es más eficiente en un heap que en una cola con prioridad montada
mediante una lista de listas. V F. Un heap permite obtener el dato con menor prioridad en O(1). V F. Un heap es un árbol binario equilibrado en altura. 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. Si esta sentencia es válida:
int nuevoValor = 7;
it=micontainer.find(clave);
(*it).second[i] = &nuevoValor;
Entonces micontainer puede tener esta definición: map <int, vector<int> >micontainer; V F. El objeto mc se define como: map <int, miClase> mc; ¿se podría realizar la siguiente
operación sobre mc? map<int, miClase>:: iterator it = mc. begin(); *(it).first = 5; V F. El contenedor de STL más adecuado para albergar las reservas de un restaurante para
tener acceso a éstas por fecha es un mapa de la siguiente forma: multimap <Fecha, Reserva> V F. La correspondiente definición de una matriz dispersa en STL según la Lección 7 es:
vector <list <int> > matrizDis; V F. La siguiente sentencia: v["María"] = dato; es válida si v representa a un deque. V F. Un map definido como: <int, ClaseA> puede sustituirse por un set<ClaseA> si ClaseA
tiene sobrecargado el operator< y la clave entera forma parte de la clase ClaseA V F. Si en el caso anterior el operator< ya está usándose para otro tipo de ordenación sobre
ClaseA, entonces se puede usar la definición: set<ClaseA, comparaClaseA>, siendo compara
ClaseA una clase de comparación para ClaseA V F. Toda función de dispersión debe acabar con %tamaTabla V F. El djb2 no es una función de dispersión de cadenas V F. Si la tabla A tiene un lambdaλ= 0.5 y en la tabla B,λ= 0.75, entonces la tabla B está
porcentualmente más llena que la A V F. En STL la dispersión abierta se define como un list< list <Entrada <T> > > V F. El djb2 diferencia las posiciones de las letras de CASA y SACA mediante
desplazamientos a nivel de bits con la cadena entrante V F. Los agrupamientos secundarios se producen cuando claves que son dispersadas a
posiciones diferentes siguen la misma secuencia de búsqueda para localizar una posición
disponible. V F. Una tabla de dispersión cerrada con cubetas disminuye el riesgo de colisiones, pero
aun así necesita una estrategia de resolución de colisiones. V F. Para evitar tanto agrupamientos primarios como secundarios es preferible utilizar
dispersión cuadrática que dispersión doble. V F. Una tabla de dispersión cerrada construida correctamente permite localizar un dato por
su clave de manera más eficiente que un árbol AVL. V F. La técnica de dispersión doble permite evitar agrupamientos primarios pero no
secundarios. F V. Las posiciones vacías y disponibles (contuvieron un dato en el pasado pero fue borrado)
se manejan de igual forma a la hora de insertar un dato en una tabla de dispersión cerrada. 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. Como un árbol es un grafo conexo sin ciclos entonces un recorrido en anchura (BFS)
empezando en la raíz es un recorrido del árbol por niveles V F. Averiguar las aristas de entrada a un nodo en un grafo dirigido implementado mediante
listas invertidas es más eficiente que implementado sobre una matriz de adyacencia. V F. El recorrido en profundidad de un grafo usa normalmente una cola mientras que en
anchura su implementación es con pila o recursiva. V F. Un árbol binario es un grafo normalmente dirigido, conexo y libre de ciclos donde el
grado de salidas de todos los nodos es menor o igual a 2 V F. Encontrar el punto más cercano a otro en una malla regular puede suponer recorrer
más de 20 casillas. F V. Una malla regular en 3D requiere más tiempo de acceso para localizar un punto que
una en 2D. V F. Si la malla regular albergara una simulación de partículas en el espacio que se mueven
despacio (menos del tamaño de una celda por quantum de tiempo), entonces localizar hacia
dónde se dirige una partícula del instante t1 al t2 es un tiempo constante. V F. Se permite que un quadtree esté desequilibrado, es decir, que unas ramas sean mucho
más largas que otras. V F. Dada una codificación del nodo del modo: 00-10-11-01-11-10, se puede conocer
exactamente el área del plano a la que representa. V F. Un octree es la representación 3D del quadtree y en este caso cada nodo tiene (4x4)
nodos hijos. V F. Un octree es la representación 3D del quadtree y en este caso cada nodo tiene (4x4).
nodos hijos. V F. Es preferible el uso de ficheros de texto como ficheros internos a las aplicaciones y los
binarios como ficheros de intercambio entre aplicaciones. V F. Los registros con longitud fija permiten acceder mediante un acceso al dato posicionado
en la posición lógica k, mientras que los de longitud variable necesitan algún mecanismo de
indexación. V F. Para eliminar un registro en un fichero que maneja pila de borrados se necesita un
número indeterminado de accesos a disco. V F. El proceso de lectura de todos los registros de un fichero de manera secuencial no
necesita mover explícitamente el apuntador del fichero. V F. El proceso de compactación de un fichero que maneja pila de borrados para borrar
definitivamente los huecos,se puede llevar a cabo sin necesidad de recorrer los borrados en
modo pila y sobre el mismo fichero. V F. Cuando un índice simple es modificado, los cambios son inmediatamente reflejados en
el fichero donde se guarda el índice. V F. Si se usa un mapa de STL para representar un índice simple en memoria, entonces
puede localizarse cualquier registro del fichero de datos con O(logn) accesos a disco. V F. Aunque un índice simple es una técnica para acceder eficientemente a un fichero en
memoria secundaria, éste se mantiene íntegramente en memoria primaria mientras está
siendo utilizado. V F. Si un fichero indexado el índice en memoria se desactualiza por algún problema en la
aplicación, la operación de borrado puede realizar un borrado de un registro incorrecto. V F. Al arrancar la aplicación, es necesario siempre reconstruir el índice simple a partir del
correspondiente fichero de datos. V F. Al contrario que en un índice primario, en un índice secundario pueden existir múltiples
claves repetidas. V F. Al igual que los índices simples, los árboles B se mantienen permanentemente en
memoria. Su ventaja respecto a los índices es la mayor eficiencia en la búsqueda de una
clave: O(log2n) de los índices frente a O(logmn) de los árboles B, siendo m el orden del mismo
y siempre mucho mayor que 2. V F. En el proceso de inserción de un dato en un árbol B se puede repartir la carga de datos
con nodos hermanos en el caso de que dicho dato no quepa en el nodo asignado. V F. En un árbol B de orden 256 no puede ocurrir nunca que la raíz tenga menos de 128
claves/punteros a descendientes. V F.
|