AED-I-Lista-4

Prévia do material em texto

1
 
Algoritmos e Estruturas de Dados I IBm1014 
Departamento de Computação e Matemática 1º Semestre/2012 
Prof. Dr. José Augusto Baranauskas 4ª Lista de Exercícios 
 
1. Suponha que L é uma lista contendo caracteres x, y e z são variáveis do tipo caractere. Mostre o 
conteúdo da lista L em cada passo dos seguintes fragmentos de código bem como o valor das variáveis x, 
y e z: 
 
a) L.Insert(1,´a´); 
L.Insert(1,´b´); 
L.Insert(1,´c´); 
L.Delete(1,x); 
L.Delete(1,y); 
L.Delete(1,z); 
b) L.Insert(1,´a´); 
L.Insert(2,´b´); 
L.Insert(3,´c´); 
L.Delete(2,x); 
L.Delete(1,y); 
L.Insert(2,x); 
L.Insert(1,y); 
L.Delete(3,z); 
c) L.Insert(1,´a´); 
L.Insert(1,´b´); 
L.Clear(); 
L.Insert(2,´c´); 
L.Delete(1,x); 
L.Insert(2,´a´); 
L.Delete(1,y); 
L.Insert(2,´b´); 
L.Delete(1,z); 
d) L.Insert(1,´a´); 
L.Insert(2,´b´); 
L.Insert(3,´c´); 
while (! L.Empty()) 
 L.Delete(1,x); 
 
2. Reimplemente o ADT Lista considerando o uso de sentinelas, tanto para alocação contígua como 
dinâmica encadeada. 
 
3. Implemente pilhas e filas fazendo uso exclusivo dos métodos de listas. Comparece a complexidade dessa 
implementação com aquelas específicas para pilhas e filas vistas em aula. 
 
4. Obtenha uma representação mapeando uma pilha P e uma fila F em um único vetor V[1:n]. Escreva os 
métodos para inserir e remover elementos destes dois objetos de dados. Qual a complexidade de sua 
representação, no pior caso? 
 
5. Altere a representação anterior para um vetor V[0:n-1]. Qual a complexidade de sua representação, no 
pior caso? 
 
6. Uma fila de 2 pontas (deque) é uma lista linear em que inserções e eliminações podem ser feitas em 
qualquer extremidade. Obtenha uma representação mapeando uma fila de 2 pontas em um vetor. Escreva 
métodos para inserir e eliminar elementos de qualquer uma das extremidades da fila. 
 
7. Uma lista linear circular e mantida num vetor C[0:n-l] com H e T com as mesmas funções de head e tail 
em filas circulares. 
a) Obtenha uma fórmula em termos de H,T e n para o número de elementos na lista; 
b) Escreva um algoritmo para eliminar o k-ésimo elemento da lista; 
c) Escreva um algoritmo para inserir um elemento Y imediatamente após o k-ésimo elemento. 
 
8. Seja A=(a1,a2, ...,an) uma lista linear representada em um vetor V[1:n] usando o mapeamento: o i-ésimo 
elemento de A, ou seja ai, é armazenado em V[i]. Escreva um método para inverter a ordem dos 
elementos em V, isto é, o algoritmo deve transformar V tal que V[i] contenha o elemento n-i+l de A. O 
único espaço adicional disponível para seu algoritmo é aquele para variáveis simples. A entrada para seu 
algoritmo é V e n. 
 
9. Seja A=(a1,a2, ...,an) uma lista linear representada em um vetor V[0:n-1] usando o mapeamento: o i-
ésimo elemento de A, ou seja ai, é armazenado em V[i-1], escreva os métodos de manipulação de listas. 
 
10. Admitindo que uma lista encadeada possui um campo chave do tipo inteiro, escreva os seguintes 
métodos usando diretamente ponteiros: 
a) Sort, para ordenar a lista em ordem crescente dos valores das chaves; 
b) Reverse, para inverter a lista; 
c) Minimum, para encontrar o elemento de menor valor da lista; 
d) Maximum, para encontrar o elemento de maior valor da lista; 
e) Copy, para copiar todos os elementos da lista em uma outra lista. 
 2
 
11. Sejam as listas A=(al, ..., an) e B=(bl, ..., bm) representadas de forma encadeada. Elabore um algoritmo 
para intercalar A e B, ou seja, formar a lista C=(a1, b1, a2, b2, ...). As listas A e B devem permanecer 
inalteradas. 
 
12. Se A=(al, ..., an) e B=(bl, ..., bm) são listas ordenadas então A < B se ai = bi para 1 ≤ i < j e aj < bj ou ai=bi 
para 1 ≤ i ≤ n e n < m. Escreva um método que retorna -1, 0 ou +1 dependendo se A < B, A = B ou A > 
B, respectivamente. Assuma que e possível comparar átomos ai e bj. 
a) Assuma que as listas A e B estão implementadas em um vetor; 
b) Assuma que as listas A e B estão implementadas de forma encadeada. 
 
13. Dada uma lista circular encadeada: 
 
head
...
head
...
 
 
Implemente as operações de manipulação de listas lineares usando a implementação circular encadeada. 
 
14. Uma lista bidirecional ou duplamente encadeada é uma lista cujos elementos são ligados em ambos os 
lados, conforme a figura seguinte. Defina uma class em C++ para efetuar buscas, inserções e remoções 
de elementos em listas duplamente encadeadas. 
head tailhead tail
 
 
15. Escreva um método para concatenar duas listas duplamente encadeadas utilizando diretamente ponteiros. 
 
16. Para cada uma das seguintes listas {não ordenada simplesmente encadeada, ordenada simplesmente 
encadeada, não ordenada duplamente encadeada, ordenada duplamente encadeada}, indique o tempo 
assintótico no pior caso para cada uma das seguintes operações: Insert, Delete, Search, Minimum, 
Maximum. 
 
17. Sejam X={x1, x2, …, xn} e Y={y1, y2, …, ym} duas listas encadeadas ordenadas. Defina o método Merge 
que intercala as duas listas ordenadas em uma lista Z final também ordenada. O método deve fazer uso 
diretamente de ponteiros e apenas os métodos de status de listas ordenadas podem ser utilizados. 
 
18. Uma maneira de se representar um conjunto é pela lista de seus elementos. Supondo esta representação, 
defina os métodos para as operações usuais de conjunto: união, intersecção, diferença e pertinência. 
 
19. Polinômios podem ser representados por meio de listas encadeadas, nas quais cada nó contém o 
coeficiente e o expoente associado. Por exemplo, o polinômio P(x) = 3x14 + 2x8 +1 seria representado 
como: 
 
head
3 14 2 8 1 0
head
3 14 2 8 1 0
 
 
 3
enquanto o polinômio Q(x) = 8x14 – 3x10 + 10x6 apareceria como: 
 
head
8 14 -3 10 10 6
head
8 14 -3 10 10 6
 
 
Note que as listas possuem os nós em ordem decrescente do expoente. Defina as operações elementares de 
manipulação de polinômios utilizando listas encadeadas: criação, número de termos, etc; inserção e remoção 
de termos em um polinômio; dados dois polinômios A e B obter o polinômio soma C=A+B, o polinômio 
produto C=A*B. Os métodos devem deixar A e B sem alteração e criar C como uma nova lista encadeada. 
Demonstre que sendo n e m as quantidades de termos de A e B, respectivamente, a multiplicação pode ser 
efetuada em tempo O(nm2) ou O(mn2). Se A e B forem densos, demonstre que a multiplicação toma O(nm).