El archivo [aed.zip] contiene todos los archivos fuente, compactados en un solo archivo con ``zip''. El archivo se puede abrir con unzip (Linux) (u otro utilitario zip-compatible).
void apply_map(list<int> &L, map<int,int> &M, list<int> &ML) que,
dada una lista L y una correspondencia M retorna por
ML una lista con los resultados de aplicar M a los
elementos de L. Si algún elemento de L no esta en el dominio
de M, entonces el elemento correspondiente de ML no es
incluido. Por ejemplo, si
L = (1,2,3,4,5,6,7,1,2,3) y
M= {(1,2),(2,3),(3,4),(4,5),(7,8)},
entonces, después de hacer apply_map(L,M,ML), debe quedar
ML = {(2,3,4,5,8,2,3,4)}.
[Tomado en el 1er parcial del 20/4/2006].
keywords: lista, correspondencia
int ascendente1 (list <int> &L, list<list<int> > &LL)
que, dada una lista L, genera una lista de listas LL
de tal forma de que cada sublista es ascendente.
[Tomado en el Parcial 1 20-ABR-2006].
Escribir una función
int ascendente2 (list <int> &L, vector < list<int> > &VL)
que, dada una lista L, genera un vector de listas VL
de tal forma de que cada sublista es ascendente.
[Tomado en Examen Final 29-JUL-2004].
void chunk_revert(list<int> &L,int n); que
dada una lista L y un entero n,
invierte los elementos de la lista tomados de a n.
Si la longitud de la lista no es múltiplo de n
entonces se invierte el resto también.
Por ejemplo, si L={1,3,2,5,4,6,2,7}
entonces después de hacer chunk_revert(L,3) debe
quedar L={2,3,1,6,4,5,7,2}.
Restricciones: Usar a lo sumo una estructura auxiliar.
(En tal caso debe ser lista, pila o cola).
[Tomado en el 1er parcial 21/4/2005].
keywords: lista
n números enteros positivos alrededor de una
circunferencia inicial. Construyamos ahora sucesivas
circunferencias concéntricas hacia el exterior, de igual
cantidad de elementos, los cuales son obtenidos restando (en valor
absoluto) pares consecutivos de la última circunferencia
exterior.
Entonces, dada una lista L = [ x_0, x_1, ..., x_{n-1} ] de n
números enteros que representan los valores iniciales alrededor de
la circunferencia inicial, escribir una función
int circulo(list<int> &L);
que ejecuta esta tarea y devuelva además
el número de circunferencias iteradas p
[Tomado en el 1er parcial del 21/4/2005].
keywords: lista
A<B si a<b, o bien (a=b y Ai < Bi), o
bien (a=b y Ai=Bi y Ad<Bd), donde
a, b son las raíces y Ai, Ad, Bi, Bd
son los subárboles izquierdos y derechos de A y B.
Consigna: Escribir una función
bool es_menor(tree<int> &A,tree<int> &B) que retorna
verdadero si A < B.
[Tomado en el 2do parcial 26/5/2005].
keywords: arbol binario
int count_if(tree<int> &T,bool (*pred)(int x)); que retorna
el número de nodos del árbol T que satisfacen el
predicado pred. Por ejemplo, si T=(1 2 (3 5 7 6) 4),
entonces count_if(T,odd) debe retornar 4. Escribir el
predicado bool odd(int x) que determina si un entero es
impar.
Escribir una función
void list_if(tree<int> &T,list<int> &L,bool (*pred)(int x));
que retorna en L
la lista de valores nodales en orden previo de un árbol
ordenado orientado T que satisfacen el predicado
pred. Por ejemplo, si T=(1 (-2 7 (8 -7) (3 -5 -6))),
entonces después de list_if(T,L,positive), debe quedar
L={1,7,8,3}. Escribir el predicado
bool positive(int x) que determina si un entero es mayor que 0.
[Tomado en el 2do parcial 26/5/2005].
keywords: arbol orientado
void cum_sum_cola (queue<int> &Q) que modifica a la
cola Q dejando la suma acumulada de sus elementos, es
decir, si los elementos de Q antes de llamar a
cum_sum_cola(Q) son Q = (a_0,a_1,...,a_{n-1}),
entonces después de llamar a cum_sum_cola(Q) debe
quedar Q = (a_0, a_0 a_1, ..., a_0 + a_1 + ... + a_n)+.
[Tomado en el Primer Parcial 27-ABR-2004]
keywords: cola
void cum_sum_pila (queue<int> &S) que modifica a la
pila S dejando la suma acumulada de sus elementos, es
decir, si los elementos de S antes de llamar a
cum_sum_pila(S) son S = (a_0,a_1,...,a_{n-1}),
entonces después de llamar a cum_sum_pila(S) debe
quedar S = (a_0, a_0 a_1, ..., a_0 + a_1 + ... + a_n)+.
[Tomado en el Primer Parcial 27-ABR-2004]
keywords: pila
list< set<int> > l escribir una función
void diffsym(list< set<int> > &L, set<int> &ad)
que retorna en ad el conjunto de los elementos que
pertenecen a uno y sólo uno de los conjuntos de L.
Por ejemplo, si L = ({1,2,3},{2,4,5},{4,6}) entonces
ad debe ser {1,3,5,6}. Notar que si el número
de conjuntos en l es 2 y los llamamos A y B,
entonces debe retornar ad = (A-B) union (B-A).
[Tomado en el 3er parcial 23/6/2005].
keywords: conjunto
void elimina_valor(queue<int> &Q, int n);} que elimina todos
las ocurrencias del valor n en la cola Q. Por ejemplo,
si Q = { 1,3,5,4,2,3,7,3,5 } y n=3, después de
elimina_valor(Q,3) debe quedar
Q = {1,5,4,2,7,5}.
Sugerencia: usar una estructura auxiliar lista o cola.
Restricciones: el algoritmo debe tener un tiempo de ejecución
O(n), donde n es el número de elementos en la cola original.
[Tomado en Exámen Final 08-JUL-2004]
keywords: cola
bool es_biyectiva (map <int,int> &A)
que retorna true si la misma representa una función biyectiva,
esto es, si la correspondencia A describe una relación
uno a uno. Por ejemplo, supongamos el conjunto
X = (0,1,2,3,4,5) y consideremos las correspondencias
A1 = { (0,2), (1,5), (2,0), (3,3), (4,4), (5,1) } y
A2 = { (0,2), (1,1), (2,0), (3,3), (4,3), (5,1) }.
En el primer caso, cada elemento (de 0 a 5) tiene preimagen,
por lo que es_biyectiva (A1) debe retornar true.
En cambio, en el segundo caso, los elementos 4 y 5 no tienen
preimagen, por lo que es_biyectiva (A2) debe retornar
false.
keywords: correspondencia
bool es_permutacion(map<int,int> &M) que retorna
true si M es una permutacion y false si no lo es.
[Tomado en Primer Parcial 27-SET-2007].
keywords: correspondencia
vector<set<int>> G y un vertice de
partida x se desea determinar la estructuras de capas
de vecinos de G alrededor de x definida de la
siguiente forma: la capa 0 es {x}, la capa 1 son los
vecinos de x. A partir de alli la capa n>=2 esta
formada por los vecinos de los nodos de la capa n-1
(es decir la adyacencia de la capa) pero que no estan
en las capas anteriores (en realidad basta con verificar
que no esten en las capas n-1 ni #n-2#).
[Tomado en tercer parcial 22-NOV-2007].
keywords: conjunto
n conjuntos A_0, A_1, ... A_{n-1} determinar si
alguno de ellos (digamos A_j ) incluye a todos los otros.
Es decir A_j\subset A_k para todo k. En ese caso,
retornar el indice j, si no retornar -1.
int includes_all(vector< set<int> > &setv);
[Tomado en tercer parcial 22-NOV-2007].
keywords: conjunto
bool incluido(set<int> &A, set<int> &B); que retorna verdadero
si y solo si A esta incluido en B.
[Tomado en el 3er parcial 23/6/2005].
keywords: conjunto
M y asumiendo que es
invertible o biunivoca (esto es, todos
los valores del contradominio son distintos), la
correspondencia `inversa' N es aquella
tal que, si y=M[x], entonces x=N[y]. Por
ejemplo, si M={(0,1),(1,2),(2,0)}, entonces la
inversa es N={(1,0),(2,1,(0,2))}. Consigna:
Escribir una función
bool inverse(map<int,int> &M,map<int,int> &N)
tal que, si M es invertible,
entonces retorna true y N es su inversa. En caso
contrario retorna falso y N es la correspondencia
`vacia' (sin asignaciones)
[Tomado en el 1er parcial del 20/4/2006].
keywords: lista, correspondencia
bool is_mapped_set(set<int> &A,set<int> &B,int (*mapfun)(int));
que retorna verdadero si el conjunto B contiene los elementos
de A, mapeados via la funcion mapfun.
[Tomado en recuperatorio 29-NOV-2007].
keywords: conjunto
L de enteros escribir una función
bool es_constante (list <int> &L)
que retorna true solo si todos sus elementos son iguales.
Hacerlo con (i) sólo operaciones del TAD lista y (ii)
mediante una correspondencia.
Escriba un procedimiento void imprime (map <int,int> &M);
para imprimir una correspondencia.
keywords: lista, correspondencia
void map_pre_post(tree<int> &T,list<int> &L, int (*fpre)(int),int (*fpost)(int))
que lista los valores nodales del árbol ordenado orientado
T en una mezcla de orden previo y posterior, donde en orden
previo se listan los valores nodales aplicandoles fpre() y en
orden posterior los fpost().
Por ejemplo, si T=(1 3 (5 6 7 8)), f(x)=x y g(x)=x1000+,
entonces map_pre_post(T,L,f,g) debe dar
L=(1,3,1003,5,6,1006,7,1007,8,1008,1005,1001).
[Tomado en el recup 30/6/2005].
keywords: arbol orientado, lista
M tal que el
conjunto de sus valores es igual al conjunto
de sus claves, encontrar el índice
nilpotente, de la misma, es decir el número de
veces n que hay que componerla consigo misma
hasta llegar a la identidad, es decir M^n = I.
Consigna: Escribir una función
int nilpot(map<int,int> &M); que dada una correspondencia
M retorna el mínimo entero n tal que M^n=I.
[Tomado en el 1er parcial 21/4/2005].
keywords: correspondencia
bool ordnodo(tree<int> &A); que verifica si cada secuencia de
hermanos del subárbol del nodo n (perteneciente
al árbol ordenado orientado A están ordenadas
entre sí, de izquierda a derecha. Por ejemplo, para
el árbol (3 5 (6 1 3) (7 4 5)) debería
retornar true, mientras que para
(3 9 (6 1 3) (7 4 2)) debería retornar false, ya que
las secuencias de hermanos (9 6 7) y (4 2)
NO están ordenados. Se sugiere el siguiente algoritmo:
para un dado nodo retornar false si: 1) sus hijos no
estan ordenados o 2) algunos de sus hijos contiene en su
subárbol una secuencia de hermanos no ordenada.
(recursividad). Caso contrario retorna verdadero.
[Tomado en el final del 28/7/2005].
keywords: arbol orientado
m, n tal que m es hijo de n,
entonces el valor de m es mayor o igual al de n.
Consigna: Escribir un predicado
bool es_parcialmente_ordenado(tree<int> &T,bool (*comp)(int,int),
que verifica si el árbol ordenado
orientado T es parcialmente ordenado con respecto a la
función de comparación comp().
[Tomado en el examen final 7/7/2005].
keywords: arbol orientado
list< set<int> > L, escribir una función predicado
bool proper_subset(list< set<int> > &L), que determina si los
conjuntos de la lista L son subconjuntos propios en forma
consecutiva. Es decir, si L = (A_0, A_1, ...., A_{n-1}),
determinar si A_j es subconjunto propio de A_{j1}+,
para j=0,...,n-2.
[Tomado en el examen final 7/7/2005].
keywords: conjunto