asdv

Ingenier´ıa en Inform´
atica
Relaciones de Estructuras de Datos. Curso 2008/2009
TDA Lineales
J. Fdez-Valdivia

Departamento de Ciencias de la Computaci´
on e I.A. ETS Ingenier´ıa Inform´
atica
Universidad de Granada. 18071 Granada. Spain.
Email: jfv@decsai.ugr.es

http://decsai.ugr.es/˜jfv/ed1/REL/rel3.pdf
Resumen
En este documento se presenta relaci´
on de problemas sobre TDALineales que se propone para la
asignatura de estructura de datos de primer curso de Ingenier´ıa en Inform´
atica .

1.

TDA Lineales

Problema 1.1
Dise˜
nar funciones para trabajar con listas de enteros capaces de realizar las operaciones siguientes:
Invertir la lista.
Formar una lista que contenga los elementos comunes de otras dos.
Insertar un elemento despu´es del elemento i-´esimo.Ordenar los elementos en orden creciente.
Calcular la media y la desviaci´
on t´ıpica de los elementos de la lista.
Mover un nodo j, n posiciones m´
as hacia adelante.
Problema 1.2 Dise˜
nar tres funciones que eliminen todas las apariciones de un elemento x en una lista,
una pila y una cola respectivamente.
Problema 1.3 Dise˜
nar una funci´
on swap que intercambie los contenidos de doslistas. Implementarlo
mediante una funci´
on independiente y como funci´
on miembro (o funci´
on amiga) de listas. ¿Qu´e eficiencia
tienen?
Problema 1.4 Un pal´ındromo es una cadena de caracteres que se lee igual hacia delante que hacia atr´
as
(pudi´endose modificar los espacios en blanco). Por ejemplo: D´abale arroz a la zorra el abad. Escribir un
programa para detectar si una cadena decaracteres es un pal´ındromo o no. (Nota: un mecanismo efectivo
de soluci´
on consiste en el uso simult´
aneo de una pila y una cola).
Problema 1.5 La notaci´
on infija es la manera habitual de representar las expresiones aritm´eticas, donde
el operador se coloca entre los operandos (p.e., “a + b”). Esta notaci´
on tiene el inconveniente de que
obliga a usar par´entesis para determinar elorden de realizaci´
on de las operaciones. Otro tipo de notaci´
on
es la postfija, en donde los operadores se colocan despu´es de los operandos, y no entre ellos (p.e., “a b
+” representa la suma de “a” y “b”). La notaci´
on postfija tiene la ventaja de que el orden en que se
deben realizar las operaciones est´
a completamente determinado por las posiciones de los operadores y losoperandos, y nunca es necesario el uso de par´entesis. Dise˜
nar programas para:
1

1. Evaluar el resultado de una expresi´
on aritm´etica escrita en notaci´
on postfija. Por simplicidad,
suponed que los operadores empleados s´
olo pueden ser “+, -, * y /”, y los n´
umeros son siempre
enteros.
2. Transformar una expresi´
on aritm´etica escrita en notaci´
on infija a notaci´
on postfija,con las mismas restricciones del apartado anterior, pero permitiendo la utilizaci´
on de variables en lugar de
constantes enteras.
Problema 1.6 Implementar el tipo de dato Pila utilizando como representaci´
on el tipo de dato abstracto
Lista.
Problema 1.7 Implementar el tipo de dato Cola utilizando como representaci´
on el tipo de dato abstracto
Lista.
Problema 1.8 Modifique laimplementaci´
on del tipo cola, de forma que use dos pilas para almacenar los
elementos que se insertan y eliminan. Las inserciones se realizan sobre la primera y los borrados sobre la
segunda. En caso de que la segunda no tenga elementos, se pasan los elementos de la primera. ¿Cu´
al es
la eficiencia de la operaci´
on pop?
Problema 1.9 Implementar el tipo de dato Cola con prioridad utilizando comorepresentaci´
on el tipo de
dato abstracto Lista.
Problema 1.10 Suponga una cola de valores enteros. Implemente una funci´
on que elimine todos los
elementos repetidos consecutivos (si hay una secuencia de elementos repetidos s´
olo se mantiene uno de
ellos).
Problema 1.11 Implementar una funci´
on, que recibe una lista de enteros L y un n´
umero entero n, y
modifica la lista eliminando...