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).
Más abajo en esta página se listan los ejemplos por palabra clave.
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
M1 y M2 son inversas una
de la otra si tienen el mismo numero de asignaciones y
para cada par de asignacion x->y en M1 existe
el par y->x en M2. Escribir una funcion predicado
bool areinverse(map<int,int> &M1,map<int,int> &M2); que
determina si las correspondencias M1, M2 son una la
inversa de la otra o no.
[Tomado en Primer Parcial 17-SET-2009].
keywords: correspondencia, lista
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].
keywords: lista
map<int, list<bool> > M, verificar que para
todas las claves pares, la lista correspondiente tenga todos
sus elementos en true o bien que sea vacia. Si el map no
tiene elementos, la salida debe ser true.
[Tomado en primer parcial de lab 2011-09-17].
keywords: correspondencia, lista
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
void compacta(list<int> &L,stack<int> &S); que
toma un elemento entero n de S y, si es positivo,
saca n elementos de L y los reemplaza por su suma. Esto ocurre
con todos los elementos de S hasta que se acaben, o bien se acaben
los elementos de L.
[Tomado en el primer parcial del cursado 2010, 2010-09-14.]
keywords: lista, correspondencia
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
void concat_map(map<int,list<int> >& M, list<int>& L); tal que
reemplaza los elementos de L por su imagen en M. Si un
elemento de L no es clave de M entonces se asume que su imagen
es la lista vacía.
[Tomado en el primer parcial del cursado 2010, 2010-09-14.]
keywords: lista, correspondencia
map<int,set<int>> G encontrar los subconjuntos del
mismo list<set<int>> D que estan desconectados. Por ejemplo, si
G={1->{2},2->{1},3->{4},4->{3}},
entonces debe retornar D=({1,2},{3,4}).
La signatura de la funcion a implementar es
void connected(map<int,set<int>> &G, list<set<int>> &D);
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
cumsum.cpp pero ahora para AB.
El cumsum(v) de un vector v es la suma acumulada, es
decir en la posicion v[j] debe quedar la suma de los
elementos de v[0..j]. Para un arbol lo podemos extender
diciendo que en cada nodo del arbol queda la suma de los
valores de los nodos de su subarbol ANTES de la
operacion.
keywords: arbol binario
cumsum(v) de un vector v es la suma acumulada, es
decir en la posicion v[j] debe quedar la suma de los
elementos de v[0..j]. Para un arbol lo podemos extender
diciendo que en cada nodo del arbol queda la suma de los
valores de los nodos de su subarbol ANTES de la
operacion. Por ejemplo si T=(1 (2 (3 4 5 6)))) entonces
despues de cumsum(T) debe quedar T=(21 (2 (18 4 5 6)))).
La version hacia abajo corresponde a que en cada camino
n0,n1,...,nk queden los valores cumsum[*n0,*n1,...,*nk].
keywords: arbol orientado
void cutoff_map(map<int, list<int> > &M,int p,int q);
que elimina todas las claves que NO estan en el rango
[p,q). En las asignaciones que quedan tambien debe eliminar
los elementos de la lista que no estan en el rango. Si la lista queda
vacia entonces la asignacion debe ser eliminada.
[Tomado en el primer parcial del cursado 2010, 2010-09-14.]
keywords: lista, correspondencia
M y un elemento x0, podemos
generar una secuencia (x0,x1,x2,...) de la forma
x_{k1}=M(xk)+. La secuencia se detiene cuando uno de
los valores x_k generados no pertenece a las claves de
M. En ese caso la secuencia generada es finita. Por
otra parte, puede ocurrir que un elemento de la
secuencia se repita, es decir x_{km}=x_k+ con
m>0. Es obvio que, a partir de alli la secuencia se va
a repetir indefinidamente. Consigna: escribir una
Escribir una funcion
void cyclic(map<int,int> &M,list<int> &L);
que extrae en L todas aquellas
claves de M que generan una secuencia ciclica
infinita. Por ejemplo, si
M={(1,2),(2,5),(3,4),(4,6),(5,2)} entonces
cyclic(M,L) debe retornar L=(1,2,5).
[Tomado en 1er parcial 25-SEP-2008].
keywords: correspondencia, lista
m
escribir una funcion void decomp_int(int m, btree<int> &T);
que construye el arbol binario T de la siguiente forma:
1) Si m=0 da el arbol vacio
2) Si m=1 contiene un solo nodo con el valor 1.
3) Si m>1
3.a) En la raiz contiene m
3.b) En los hijos izquierdo y derecho contiene los valores
mr=m/2 y ml=m-mr.
3.c) Propaga recursivamente la decomposicion a los nodos.
Por ejemplo si m=5 entonces el arbol generado es
(5 (3 (2 1 1) 1) (2 1 1)).
[Tomado en el segundo parcial 2011-10-27].
keywords: arbol binario
T encontrar la maxima profundidad de
un nodo tal que satisface un predicado dado.
[Tomado en el 2do parcial del 2009-10-27].
keywords: arbol binario
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
S y una relacion de orden
bool comp(int x,int y) separar S, segun
sus clases de equivalencia en una lista list<set<int>> L.
Signatura:
void eqclass(set<int> &S, bool (*)(int x,int y),list<set<int>> &L)
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
void expand(list<int> &L,int m);
que transforma los elementos de una lista L de tal
forma que todos los elementos de L resulten ser menores o igual
que m, pero de tal forma que su suma se mantenga inalterada.
[Tomado en primer parcial 2011-09-15].
keywords: lista
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
void intersect_map(map< string,list<int> > &A,
map< string, list<int> > &B,map< string, list<int> > &C)
que a partir de los diccionarios A y B construye un
diccionario C de manera que las claves de C son la
interseccion de las claves de A y B y para cada clave k en
C la imagen C[k] es la interseccion de los valores en
A[k] y B[k].
[Tomado en Primer Parcial 17-SET-2009].
keywords: correspondencia, lista
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_balanced(btree<int> &T);
que determina si el arbol esta balanceado.
[Tomado en el segundo parcial 2011-10-27].
keywords: arbol binario
map<int, set<int> >G
y una lista de vertices list<int> L determinar si L es un
camino hamiltoniano en G.
[Tomado en tercer parcial 2011-11-24].
keywords: conjunto, grafo
bool is_indep(map<int, set<int> >&G,set<int>&S);
que determina si S es un conjunto
independiente de G. Se dice que S es un conjunto
independiente de G, si para cada par de vertices de S, NO existe una
arista que los une en G.
[Tomado en tercer parcial 2011-11-24].
keywords: conjunto, grafo
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
G, y un arbol T, decimos que T "expande" a
G si la raiz n de T es un vertice de G, y los caminos de
T permiten llegar desde n hasta cualquier otro nodo de G.
Escribir una funcion bool is_spng_tree(G,T) (por
"is-spanning-tree") que determina si T expande a G.
[Tomado en el 3er parcial del 2009-11-27].
keywords: conjunto, correspondencia
void lexico_stack(int n);
que genera todas las subsecuencias ordenadas de
la secuencia (1..n). Por ejemplo, si n=4 debe
generar (1), (12), (123), (124), (13),
(134), (14) (2), (23), (234) (24), (3), (34) y (4).
[Tomado en el 1er parcial del 21/4/2005].
keywords: pila
list2tree(tree<int> &T,list<int> &L);
que dada una lista L con el orden previo de T y el tamano
de sus subarboles reconstruye T. La forma de almacenar el
arbol en T es la siguiente: se almacena en orden previo 2
valores enteros por cada nodo, a saber el contenido del nodo y
el numero de hijos. Por ejemplo para el arbol
(6 4 8 (5 4 4) 7 9) se tenemos
L=(6 5 4 0 8 0 5 2 4 0 4 0 7 0 9 0).
Escribir tambien la funcion inversa tree2list(tree<int> &T,list<int> &L);
[Tomado en el 2do parcial de 2010, 2010-10-28]
Keywords: arbol orientado
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
map2list()
y list2map() de acuerdo a las siguientes especificaciones.
void map2list(map<int,int> &M,list<int> &keys,list<int> &vals);
dado un map M retorna las listas de claves y valores.
void list2map(list<int> &keys,list<int> &vals,map<int,int> &M);
dadas las listas de claves (k1,k2,k3...) y valores (v1,v2,v3...)
retorna el map M con las asignaciones correspondientes
{(k1,v1),(k2,v2),(k3,v3),...}. (Nota: Si hay
claves repetidas, solo debe quedar la asignacion
correspondiente a la ultima clave en la lista. Si hay menos
valores que claves, utilizar cero como valor. Si hay mas valores
que claves, ignorarlos).
[Tomado en Primer Parcial 17-SET-2009].
keywords: correspondencia, lista
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
A y B, que asocian
enteros con listas ordenada de enteros, escribir una
funcion
void merge_map(map<int,list<int>> &A, map<int,list<int>> &B, map<int,list<int>> &C) que
devuelve en C una correspondencia que asigna al
elemento x la fusion ordenada de las dos listas A[x]
y B[x]. Si x no es clave de A, entonces C[x]
debe ser B[x] y viceversa. Por ejemplo:
si M={(1,2),(2,5),(3,4),(4,6),(5,2)} entonces cyclic(M,L)
debe dejar L=(1,2,5).
[Tomado en 1er parcial 25-SEP-2008].
keywords: correspondencia, lista
void make_mirror(tree<int> &T); que
convierte in-place al arbol T en su espejo.
[Tomado en segundo parcial 2011-10-27].
keywords: arbol orientado
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
M y n, tales que n<M crear un
arbol binario completo (ABC) T tal que: 1) La suma de
las hojas es M, pero cada una de ellas es h<=n. 2) Se
satisface que para cada nodo n la suma de sus dos hijos
l y r es n=lr+. Ayuda: El arbol se puede construir
poniendo inicialmente M en la raiz, y dividiendo cada nodo
por 2 hasta obtener valores <=n.
keywords: arbol binario
M y n, tales que n<M crear un AOO
T tal que: 1) La suma de las hojas es M, pero cada
una de ellas es h<=n. 2) Se satisface que para cada
nodo p la suma de sus hijos es *p. 3) Cada nodo tiene
a lo sumo g hijos, con g>1 una constante dada.
Ayuda: El arbol se puede construir poniendo inicialmente
M en la raiz, y dividiendo el contenido *n de cada
nodo en g valores aprox iguales hasta obtener valores
<=n. [Tomado en el 2do parcial del 2009-10-27].
keywords: arbol orientado
cta_hojas : cuenta el número de hojas;
max_etiq_arbol : obtiene la máxima etiqueta de todo el árbol;
max_epar_arbol : obtiene la máxima etiqueta par del árbol;
max_etiq_hojas : obtiene la máxima etiqueta de solo las hojas;
sum_etiq_arbol : obtiene la suma de todas las etiquetas;
f_aplica : ejemplo simple de programación funcional
usando, una vez por vez, las funciones f_duplica y f_mitad
(ver en task1_bb.cpp las equivalentes para árbol binario).
Otras: es_camino, is_path, list_if
profundidad : calcula la profundidad de un nodo.
get_node_by_pre_index : busca un nodo dado su indice (en preorden).
keywords: arbol orientado
map<int, set<int> >G y una coloracion
map<int,string> C determinar si C es una coloracion valida, es
decir si dados dos vertices adyacentes x, y de G sus colores
son diferentes.
[Tomado en tercer parcial 2011-11-24].
keywords: conjunto, grafo
(git-repo-version aed-2.0.4-60-g3b07813)
(git-repo-date Sat Nov 26 11:41:05 2011 -0300)
(processed-date Sat Nov 26 11:41:22 2011 -0300)