EJERCICIOS DE EXÁMEN DE LA ASIGNATURA ALGORITMO Y ESTRUCTURA DE
DATOS C++
EJERCICIO 1. Se solicita crear una nueva clase template Pila llamada template<class T>
class stack_sll_t que contenga lo siguiente:
(a) Atributo privado de la clase para implementar una pila mediante una sll_t
(b) Método Push
(c) Método Pop
(d) Método Top
(e) Método Empty
EJERCICIO 2. Se tiene un programa principal que utiliza una pila stack P. Utilizando sólo
los métodos propios de una pila, desarrolla una función recursiva llamada
sumaElementos que reciba por parámetros una pila y sume los elementos de la misma
de forma recursiva.
int sumaElementos(stack_t<int>& p);
EJERCICIO 3. Implementar el procedimiento:
void sll_union(const sll_t<int>& A, const sll_t<int>& B, sll_t<int>& C);
que realiza la unión (tipo conjunto) de dos listas no ordenadas A y B con elementos no
repetidos, y devuelve el resultado en la lista C.
Por ejemplo, si A={2,1,4,3} y B={1,5,3,6}, el resultado sería C={6,3,5,1,4,2}.
EJERCICIO 4. El clásico algoritmo de conversión de un número n en base decimal (base
10) a otra base b, consiste en dividir n entre la base b sucesivamente mientras el
dividendo sea mayor o igual que b y, a continuación, se coge el último cociente hasta el
primer resto en orden inverso. Por ejemplo, si se convierte el número 100 en base 10 a
base 2.
Dado un número entero positivo n y una base entera b, se pide desarrollar un algoritmo
recursivo de conversión de dicho número entero a cualquier base b (con 1 < b < 10)
usando una cola (queue_t<T>) para guardar el número en dicha base, y cuya cabecera
debe ser:
void to_base(const unsigned n, const unsigned short b, queue_t<unsigned>&
q);
Usando el ejemplo anterior, si el valor del entero es 100, y la base es 2, el resultado
esperado por pantalla sería: 1100100. En caso de ser base 8, el resultado sería: 144.
NOTA: se valorará la eficiencia del algoritmo y el esquema recursivo implementado
(caso base y caso general).
EJERCICIO 1. Escribe una función en C++ con la siguiente cabecera:
vector_t<int> rotate(const vector_t<int>& v, const int r)
que devuelve un nuevo vector vector_t<int>, y que contiene los elementos del vector
original rotados r veces hacia la derecha. Por ejemplo, si v=[10,21,32,43,54,65,76,87,98],
el resultado esperado para la llamada a rotate(v, 5) sería [54,65,76,87,98,10,21,32,43].
EJERCICIO 2. Escribe una función en C++ con la siguiente cabecera:
bool es_palindroma(const vector_t<char>& cadena);
y verifique si la cadena de entrada es palíndroma. Un palíndromo es una palabra o frase
que se lee igual de izquierda a derecha y de derecha a izquierda, sin tener en cuenta los
espacios ni los caracteres especiales. La función debe utilizar una pila (stack_v_t<char>
o stack_l_t<char>) para realizar la verificación. Por ejemplo, el resultado esperado sería
true para la siguiente cadena de entrada:
['Y','O','H','A','G','O','Y','O','G','A','H','O','Y']
EJERCICIO 3. Dado un tamaño n, y un objeto de la clase vector_t<char> de longitud n, se
pide desarrollar un procedimiento recursivo en C++ con la siguiente cabecera:
void all_bin(vector_t<char>& binario, const int i = 0);
que genere por pantalla todas las cadenas de números binarios de longitud n. Por
ejemplo, si ejecutamos all_bin(binario) con un tamaño n igual a 4, el resultado debería
ser:
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110
1111
NOTA: El último parámetro es el índice que itera sobre la cadena de caracteres que, por
defecto, empieza en 0. En la evaluación de este ejercicio se tendrá muy en cuenta la
implementación del caso base y del caso general, y la eficiencia de los bucles (si fueran
necesarios).
EJERCICIO 4. Para la clase dll_t<int>, desarrollar el método especializado
template<> dll_node_t<int>* dll_t<int>::find(const int v);
que busca un valor dentro de la lista, devolviendo el puntero del nodo que lo contiene o
NULL si no lo encuentra.
EJERCICIO 5. Para la clase sll_t<T>, desarrollar el método especializado que elimina y
libera todos los elementos de posiciones pares de la lista, y cuya cabecera es:
