EEDD UJA

T3: La siguiente declaración: int** p permite crear las siguientes estructuras de datos en memoria: V. F.

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

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

T3: 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. Entonces el elemento existente en la posición (3, 7) se accede de igual manera con ambas estructuras de datos: m1[3][7] / m2[3][7]. V. F.

T3: El siguiente código presenta memory leaks: V. F.

T3: El siguiente código presenta heap overflows: V. F.

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

T3: A través el puntero int **m podemos manejar una matriz creada en memoria dinámica con un número de filas y columnas arbitrario. V. F.

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

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

T4: La siguiente definición de vector estático necesita de constructor copia y operador de asignación: V. F.

T4: La misma clase anterior debe definir así el operador corchete “[ ]” para que funcione correctamente (se obvian las comprobaciones de rango): V. F.

T4: Si se ha instanciado en la clase Biblioteca a Mivect para implementar una relación de asociación con la clase Libro como: Entonces el destructor de Biblioteca debe eliminar estante ejecutando: delete[] estante;. V. F.

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

T4: La 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.

T5: El operador de asignación de la clase Matriz <T>::operator= debe siempre destruir la matriz destino de la asignación. V. F.

T5: El operador de la clase Matriz <T>::operator+= devuelve el objeto resultado por copia. V. F.

T5: La implementación de conjuntos mediante vectores realiza la intersección en tiempo lineal. V. F.

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

T5: Para almacenar 3841 datos en un conjunto de bits, debo crear un buffer de 480 bytes. V. F.

T5: a.intersec(b+a) == a es correcto. V. F.

T5: El resultado de realizar esta operación: char mascara = 1 < < (500%8): es 0000100. V. F.

T6: El tiempo para eliminar un dato en una posición arbitraria de una lista es lineal. V. F.

T6: El tiempo para eliminar un dato en una posición apuntada por un iterador es lineal. V. F.

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

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

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

T7: Una lista doblemente enlazada permite realizar busquedas binarias en tiempo O(log n) si los datos se encuentran ordenados. V. F.

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

T7: El siguiente código inserta correctamente en un caso genérico (lista con datos), un nuevo nodo apuntado por p por delante de la posición del nodo apuntado por q en una lista doblemente enlazada y circular. V. F.

T7: Transferir todos los nodos de una lista doblemente enlazada l1 al final de una lista enlazada l2 requiere tiempo O(1) (nota: l1 queda vacía tras esta operación). V. F.

T8: El contenedor list<T> de STL implementa el operador [] para acceder directamente al dato almacenado en una posición arbitraria. V. F.

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

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

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

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

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

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

T9: Una lista simplemente enlazada puede implementar eficientemente a pilas y colas dinámicas. V. F.

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

T9: Se usa una pila para resolver aquellos procesos recursivos que agotan la pila. V. F.

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

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

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

T9: Necesito una pila para eliminar la recursividad de la sucesión de Fibonacci. V. F.

T10: Conocer la altura de un ABB da información sobre el numero de datos que contiene. V. F.

T10: Dos árboles ABB equivalentes pueden tener diferente altura, raíz y hojas. V. F.

T10: Un árbol binario que representa expresiones matemáticas se resuelve mediante un recorrido en postorden. V. F.

T10: Para obtener los datos ordenados de un ABB se hace un recorrido en preorden. V. F.

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

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

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

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

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

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

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

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

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

T11: No es posible que un árbol AVL tenga un nodo hoja a una profundidad 4 y otra a profundidad 8. V. F.

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

T11: Es posible que exista una secuencia de datos que al ser insertada en un árbol AVL no provoque rotaciones. V. F.

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

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

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

T12: Un heap es un árbol binario equilibrado en altura. V. F.

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

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

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

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

T13: El objeto mc se define como: map <int, miClase> mc; ¿se podría realizar la siguienteoperación sobre mc? map<int, miClase>:: iterator it = mc. begin(); *(it).first = 5;. V. F.

T13: El contenedor de STL más adecuado para albergar las reservas de un restaurante para tener acceso a estas por fecha es un mapa de la siguiente forma: multimap <Fecha,Reserva>. V. F.

T13: La correspondiente definición de una matriz dispersa en STL según la Lección 7 es: vector <list <int> > matrizDis;. V. F.

T13: La siguiente sentencia: v["María"] = dato; es valida si v representa a un deque. V. F.

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

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

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

T14: El djb2 no es una función de dispersión de cadenas. V. F.

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

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

T14: En STL la dispersión abierta se define como un list< list <Entrada <T> > >. V. F.

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

T14: El djb2 diferencia las posiciones de las letras de CASA y SACA mediante desplazamientos a nivel de bits con la cadena entrante. V. F.

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

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

T15: Para evitar tanto agrupamientos primarios como secundarios es preferible utilizar dispersión cuadrática que dispersión doble. V. F.

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

T15: La técnica de dispersión doble permite evitar agrupamientos primarios pero no secundarios. V. F.

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

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

T16: Un grafo que representa carreteras nacionales puede considerarse un grafo ponderado, no dirigido y posiblemente cíclico. V. F.

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

T16: Averiguar las aristas de entrada a un nodo en un grafo dirigido implementado mediante listas invertidas son más eficiente que implementado sobre una matriz de adyacencia. V. F.

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

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

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

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

T17-18: 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.

T17-18: Se permite que un quadtree esté desequilibrado, es decir, que unas ramas sean mucho más largas que otras. V. F.

T17-18: 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.

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

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

T19: Es conveniente conocer el tamaño de bloque del ordenador para ajustar correctamente el número de campos por registro. V. F.

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

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

T19: Para eliminar un registro en un fichero que maneja pila de borrados se necesita un número indeterminado de accesos a disco. V. F.

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

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

T20: Cuando un índice simple es modificado, los cambios son inmediatamente reflejados en el fichero donde se guarda el índice. V. F.

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

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

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

T20: Al arrancar la aplicación, es necesario siempre reconstruir el índice simple a partir del correspondiente fichero de datos. V. F.

T20: Al contrario que en un índice primario, en un índice secundario pueden existir múltiples claves repetidas. V. F.

T21: 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 órden del mismo y siempre mucho mayor que 2. V. F.

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

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

T21: Un árbol B de orden cinco que está indexando 500 datos puede tener altura 3 (4 niveles). V. F.

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

T21: En un árbol B de orden 256 no puede ocurrir nunca que la raiz tenga menos de 128 claves/punteros a descendientes. V. F.

EX SEPT 2012- Una lista doblemente enlazada y circular puede considerarse una eedd lineal, de acceso secuencial y dinámica. V. F.

EX SEPT 2012-Un dato almacenado en una lista dinámica nunca cambia en su ubicación en memoria, aunque se inserten o eliminen más datos en dicha lista. V. F.

EX SEPT 2012-Si la clase A tiene como atributo un vector de punteros a objetos tipo B, entonces entre ellos sólo puede existir una relación de asociación. V. F.

EX SEPT 2012 - Si P y Q son dos conjuntos de bits de tamaños 7y15 respectivamente, entonces P∪Q puede tener tamaño 10. V. F.

EX SEPT 2012 - 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.

EX SEPT 2012 - Borrar un nodo de un árbol ABB de tamaño 1000 puede tener tan sólo un coste de T(1000)=2, es decir, visitando tan sólo 2 nodos. V. F.

EX SEPT 2012 - 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.

EX SEPT 2012 - Un grafo que representa carreteras nacionales puede considerarse un grafo ponderado, no dirigido y posiblemente cíclico. V. F.

EX SEPT 2012 - Un árbol B de orden 5 y altura 3 puede indexar 100 datos. 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.