Tipo Test Estructura de Datos

La lista STL, list, implementa el operador [ ]. V. F.

Una matriz 3D podría almacenar jugadores de un equipo. V. F.

La lista circular se puede implementar con un vector de manera eficiente. F. V.

En una lista de vectores: i->insert(i->begin()+pos, c) siendo i un puntero que apunta al vector, es una sintaxis correcta. V. F.

Sean dos conjuntos A y B, instanciados con vectores, se puede obtener el elemento c = a *union* b en tiempo cuadrático. V. F.

Añadir elementos al principio, begin(), de un vector se realiza en tiempo O(1). F. V.

El iterador (it) de una lista no se puede mover como it + el número de posiciones deseadas. V. F.

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

Una lista puede implementar eficientemente a pilas y colas dinámicas. V. F.

Un deque puede implementar eficientemente a pilas y colas dinámicas. V. F.

Se usa una estructura de datos de tipo pila para evitar la recursividad en procesos que agotan su pila. V. F.

Una cola con prioridad se puede implementar con vectores, vectores de listas o listas de listas de manera eficiente. F. V.

Un stack (pila) o queue (cola) se pueden implementar con listas de STL, además de poder cambiarse a vectores. V. F.

Para crear una cola con prioridad donde el dato más prioritario es el mayor, debe cambiar el operador por defecto de less a greater. V. F.

Una pila puede eliminar la recursividad para calcular la secuencia de Fibonacci. V. F.

Conocer la altura de un ABB nos da información sobre el número total de datos de dicho ABB. F. V.

Dos ABBs equivalentes pueden diferenciarse en la altura, raíz y hojas. V. F.

El posorden del siguiente ABB es (3·5)+(8-4). V. F.

Para obtener los datos ordenados en un ABB se recorre en preorden. F. V.

La recursividad de un ABB puede resolverse de forma iterativa, mediante una pila de punteros a nodos. V. F.

Para recorrer un ABB por niveles con el siguiente recorrido se necesita una cola: raíz, raíz->izq, raíz->der, raíz->izq->izq, raiz->izq->der. V. F.

Los recorridos recursivos preorden, inorden, y posorden permiten iterar sobre los árboles hacia delante y hacia atrás. F. V.

Dado el siguiente AVL, la inserción del dato {10} requiere una rotación a doble a la derecha. V. F.

Si se introducen datos en orden ascendente en un AVL, el tipo de rotación que se realizara siempre sería el caso 4 (rotación a la izquierda). V. F.

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

Se pueden listar los datos en un AVL de mayor a menor. V. F.

No es posible que en un AVL se tenga un nodo hoja a una profundidad de 4 y otra hoja a una profundidad de 8. V. F.

En un AVL, las rotaciones garantizan que el numero de descendientes por la izquierda y derecha de un nodo difiere a lo sumo en 1. F. V.

No es recomendable implementar un heap con punteros. V. F.

La operación pop() es más eficiente en un heap que en una cola con prioridad implementada con una lista de listas. V. F.

Un heap permite obtener el dato con menor prioridad en O(1). F. V.

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

Si esta sentencia es válida, entonces micontainer puede tener esta definición: map <int, vector<int> > micontainer. Sentencia: ___________________________ | | | Int nuevoValor = 7; | | It = micontainer.find(clave) | | (*it).second[i] = &nuevoValor; | ____________________________. F. V.

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

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

La siguiente sentencia: v[“María”] = dato; es válida si v representa a un deque. F. V.

Un map definido como: <int, ClaseA> puede sustituirse por un set<ClaseA> si ClaseA tiene sobrecargado el operador < y la clave entera forma parte de la clase ClaseA. F. V.

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 una lambda = 0.5 y en la tabla B un lambda = 0.75, entonces la tabla B tiene más datos que la A. F. V.

Si la tabla A tiene una lambda = 0.5 y en la tabla B, lambda = 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.

En dispersión abierta se sabe que la función de dispersión es buena conociendo el tamaño de las listas de entradas. 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. F. V.

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 tantos agrupamientos primarios como secundarios es preferible utilizar dispersión cuadrática que dispersión doble. F. V.

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

Las posiciones vacías y disponibles(tuvieron 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.

Un grafo que representa carreteras nacionales puede considerarse un grafo ponderado, no dirigido y posiblemente cíclico. 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. F. V.

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

Un árbol binario es un grafo normalmente dirigido, conexo y libre de ciclos donde el grado de salida de todos los nodos es menor o igual a 2. F. V.

Encontrar el punto más cercano a otro en una malla regular puede suponer recorrer más de 20 casillas. V. F.

Una malla regular en 3D tiene requiere más tiempo de acceso para localizar un punto que una en 2D. F. V.

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 donde 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.

Un octree es la representación 3D del quadtree y en este caso cada nodo tiene (4x4) nodos hijos. F. V.

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

Iterar sobre un vector dinámico es siempre más rápido que sobre una lista enlazada (simple o doble). V. F.

Transferir todos los nodos de una lista doblemente enlazada l1 al final de otra lista enlazada l2 requiere tiempo O(1). 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 futbol. Esta seria una posible estructura de datos para crear dicha tabla: vector<vector<vector<Jugador>>> jugadores. V. F.

Para simular una lista circular en el que los datos entren siempre por el mismo lugar pero salen en cualquier momento es igualmente eficiente utilizar una lista que un vector de STL. V. F.

Se ha utilizado la siguiente estructura de datos para implementar sin editor de texto interactivo: list<vector<char>> texto. La implementación de la operación pulsarTecla(char c) seria 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 requiere un tiempo cuadratico. V. F.

Un vector estático puede implementar eficientemente a pilas y a 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.

Una cola con prioridad siempre tendrá un push() en O(1) independientemente de la implementación concreta. F. V.

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

Los agrupamientos secundarios se producen cuando claves que son dispersas a posiciones diferentes siguen la misma secuencia para localizar una posición disponible. V. F.