EEDD Lección 3 - 17

La siguiente declaración: int** p permite crear la siguiente 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.

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

Sea m1 una matriz declarada como int m1[10][20] y m2 un puntero declarado como int **m2 e iniciado mediante el siguiente código: m2=new int*[10] for (int c = 0; c < 10; ++c){ m2[c] = new int[20] } Entonces el elemento existente en la posición (3,7) se accede de igual manera con ambas estructuras de datos: m1[3][7] y m2[3][7]. V. F.

El siguiente código presenta memory leaks: int *p = new int[1000]; for (int c = 0; i<=1000; ++c){ p[c] = 0; }. V. F.

El siguiente código presenta heap overflow: int *p; for (int c = 0; c<=10; ++c){ p[c] = 0; }. V. F.

Una plantilla de clase instanciable para el tipo T = int puede que no lo sea para el tipo T = MiClase, es decir, que una plantilla puede no aceptar cualquier tipo como parámetro. V. F.

A través del puntero int **m podemos manejar una matriz creada en memoria dinámica con un número de filas y columnas arbitrario. 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.

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 camia su posición de memoria. V. F.

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

La misma clase anterior 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.

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 implementación normal de un vector dinámico implementa una reducción del tamaño fisico a tamf a la mitad cuando el lógico taml cae por debajo de tamf/2. 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 de conjunto -1. Para convertirlo en un ID genérico se necesita de 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 opración: char mascara = 1 << (580%8): es 0000100. V. F.

El tiempo para eliminar un dato en una posición arbitraria de una lista es 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. V. F.

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.

Un dato que permanece en una lista cambia su posición a veces al sufrir la lista insecciones y borrados. V. F.

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

Iterar sobre un vector dinámico es siempre más rápido que sobre una lista enlazada (simple o doble). 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 noto 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.

Transferir todos los nodos de una lista doblemente enlazada l1 al final de toda lista enlazada l2 requiere tiempo O(1) (l1 queda vacía tras esta operación). 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 EEDD para crear dicha tabla: vector<vector<vector<Jugador>>> jugadores. V. F.

Para simular una lista circular en el que los datos entra siempre por el mismo lugar pero salen en cualquier momento es igualmente eficiente una lista(list) que un vector 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 STL, instanciados al tipo string. Entonces obtener el vector c = a intersección b 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 pilar 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.

Para hacer una priority_queue de STL, considere como dato más prioritario al mayor, se debe definir con el operador 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.

Dos árboles ABB equivalentes pueden tener diferente altura, raíz y hojas. 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.

Para 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 su izq, luego raiz->izq->izq,raiz->izq->der ...etc. V. F.

Los recorridos recursivos Preorden, Inorden y PostOrden permiten iterar sobre los árboles hacia delante y hacia detrás. V. F.

Dado el siguiente árbol AVL, la inserción de 10 requiere una rotación doble a derecha. V. F.

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

En un árbol AVL, tras una inserción, el proceso de ajuste requiere a lo suma de una única rotación simple o doble. 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 a otra 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 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.

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): 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.

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

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

Si la clase ClassA tiene el siguiente atribut: map<string,*ClassB> atributo; entonces necesariamente la relación entre claseA y claseB 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 un vector <list<int>> matrizDis;. V. F.

La siguiente sentencia v["Maria"] = 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 comparaClaseA, una clase de comparación para ClaseA. V. F.

Toda función de dispersión debe acabar con %tamaTabla. V. F.

El dbj2 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 tiene más datos que la A. 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 sabe que la función de dispersión es buena conociendo el tamaño de las listas de las entradas. V. F.

El dbj2 diferencia las posiciones de las letras 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 un posición disponible. V. F.

Una tabla de dispersión cerrada con cubetas disminuye el riesgo de colisiones, pero aún así necesita una estrategia de resolución de colisiones. V. F.

Para evitar tanto el agrupamiento 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. V. F.

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.

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 de á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 salidad de todos los nodos es menos o igual a 2. V. F.

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

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 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 muchos más largas que otras. V. F.

Dada una codificación del nodo del nodo: 00-10-11-01-11-10, se puede conocer exactamente el área del plano a la que representa. V. F.

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

El siguiente orden es correcto en relación a la velocidad de acceso de los dispositivos: DVD, CD, Memoria Flash, HHD, SSD. V. F.

Es conveniente conocer el tamaño del bloque del ordenador para ajustar correctamente el número de campos por registro. 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 al 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 al disco. V. F.

Aunque un índice simple es una técnica para acceder eficientemente a un fichero en memoria secundaria, éstos se mantiene íntegramente en memoria primaria mientras está siendo utilizado. V. F.

Si un fichero indexado el índice en memoria de 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(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.

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

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

Un árbol B de orden cinco que está indexando 500 datos puede tener altura 3 (4 niveles). 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.