Baixe o app para aproveitar ainda mais
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).
Compartilhar