EEDD Lecciones 8-13

El contendedor list<T> de STL implementa el operador [ ] para acceder directamente al dato almacenado en una posición arbitraria. 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.

Para simular una lista circular (p.e. procesos de un S.O) en el que los datos entran siempre por el miso lugar pero salen en cualquier momento es igualmente eficiente utilizar una lista (list) que un vector de STL. Verdadero. Falso.

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. Verdadero. Falso.

Sean dos conjuntos a y b de palabras, implementados usando dos vectores de STL instanciados al tipo string. Entonces obtener el vector c = a AND b (palabras que están en ambos conjuntos) requiere un tiempo cuadrático. Verdadero. Falso.

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). Verdadero. Falso.

Un vector estático puede implementar eficientemente a las pilas y colas estáticas. Verdadero. Falso.

Una lista simplemente enlazada puede implementar eficientemente a pilas y colas dinámicas. Verdadero. Falso.

Una deque puede implementar eficientemente a pilas y colas dinámicas. Verdadero. Falso.

Se usa una pila para resolver aquellos procesos recursivos que agotan la pila. 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.

Una stack o una queue se implementa por defecto sobre un std:list pero puede cambiar en ambos casos el contenedor. Verdadero. Falso.

Para hacer que una priority_queue de STL considere como dato más prioritario al mayor, se debe definir con el operator greater. Verdadero. Falso.

Necesito una pila para eliminar la recursividad de la sucesión de la sucesión de Fibonacci. Verdadero. Falso.

Conocer la altura de un ABB da información sobre el número de datos que contiene. Verdadero. Falso.

Dos árboles ABB equivalentes pueden tener diferente altura, raíz y ojas. Verdadero. Falso.

Un árbol binario que representa expresiones matemáticas se resuelve mediante un recorrido en postorden. Verdadero. Falso.

Para obtener los datos ordenados de un ABB se hace un recorrido en preorden. Verdadero. Falso.

Todo proceso recursivo que opere sobre un ABB se puede resolver de forma iterativa mediante una pila de punteros a nodos de tipo ABB. Verdadero. Falso.

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 borra Min(). Verdadero. Falso.

Para recorrer un árbol binario por niveles se necesita una cola. Este recorrido pasaría primero por la raíz, luego por la raíz->izq, lugo por raíz->der, raíz->izq->izq, raiz->izq->der, etc... Verdadero. Falso.

Los recorridos recursivos Preorden, Inorden, y Postorden permiten iterar sobre los árboles hacia delante y detrás. Verdadero. Falso.

Dado el siguiente árbol AVL, la inserción de 10 requiere un rotación doble a derecha. 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.

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.

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

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. Verdadero. Falso.

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

En los árboles AVL las rotaciones garantizan que el número de descendientes por la izquierda y derecha de un nodo difiere a los sumo en 1. Verdadero. Falso.

Es posible que exista una secuencia de datos que al ser insertada en un árbol AVL no provoque rotaciones. Verdadero. Falso.

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. Verdadero. Falso.

La operación pop() es más eficiente en un heap que en una cola con prioridad montada mediante una lista de listas. Verdadero. Falso.

La siguiente tabla referente a la eficiencia de las distintas implementaciones de una cola con prioridad es correcta (n es el número de datos y p el número de valores de prioridad distintos). Verdadero. Falso.

Un heap permite obtener el dato con menor prioridad en O(1). Verdadero. Falso.

Un heap es un árbol binario equilibrado en altura. Verdadero. Falso.

La unión de dos conjuntos disjuntos de tamaños n y m puede llevarse a cabo mediante una operación en O(1). Verdadero. Falso.

La unión de dos conjuntos disjuntos de tamaños n y m puede llevarse a cabo mediante una operación en O(1). Verdadero. Falso.

La operación busca() en conjuntos disjuntos es O(n) y Ω(1). Verdadero. Falso.

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. Verdadero. Falso.

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. Verdadero. Falso.

El objeto mc se define como: map <int, miClase> mc; ¿se podría utilizar la siguiente operación sobre mc? map<int, miClase>::iterator it = mc.begin(); *(it).first = 5;. Verdadero. Falso.

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>. Verdadero. Falso.

La correspondiente definición de una matriz dispersa en STL según la lección 7 es: vector<list <int> > matrizDis. Verdadero. Falso.

La siguiente sentencia: v["María"] = dato; es válida si v representa a un deque. Verdadero. False.

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. Verdadero. Falso.

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 comparaClaseA una clase de comparación para ClaseA. Verdadero. Falso.