Estrutura de Dados I
1ª Lista de Exercícios
Considere a seguinte estrutura:
typedef struct lista{
int chave;
struct lista *prox;
}lista;
1. Escreva uma função que realiza a inserção ordenada de uma nova chave na lista.
2. Escreva uma função que remove o k-ésimo nó da lista encadeada.
3. Escreva uma função que remove um elemento com chave v da lista ordenada. Caso v não
pertença à lista, uma mensagem de erro deve ser exibida.
a) A primeira versão deve retornar o ponteiro para o primeiro elemento da lista.
b) A segunda versão deve ter como tipo de retorno void.
c) Explique o por quê da diferença na passagem de parâmetros entre as duas versões.
4. Escreva uma função que recebe duas listas ligadas ordenadas x = (x1 , ..., xn ) e y = (y1 , . . . ,
ym ) como parâmetros e retorna uma lista ordenada formada pelos elementos de x e y
intercalados. Seu algoritmo deve ter complexidade de tempo O(n).
5. Escreva uma função que concatena duas listas encadeadas.
6. Escreva uma fun ao
̧ que copie uma lista encadeada para um vetor e retorne-o para a função
que o chamou.
7. Escreva uma função que verifica se duas listas ligadas dadas são iguais.
8. Escreva uma função que recebe uma lista p e retorna a lista invertida.
9. Utilize a estrutura apresentada para implementar uma lista circular, escrevendo as seguintes
funções:
a) Inserção no início;
b) Inserção no final;
c) Inserção ordenada;
d) Remoção do primeiro elemento;
e) Remoção do último elemento;
f) Remoção do elemento com chave v.
Considere a seguinte estrutura:
typedef struct listadupla{
int chave;
struct listadupla *proximo;
struct listadupla *anterior;
}listadupla;
Refaça as questões 1 a 9 para a estrutura listadupla.
Refaça as questões 1 a 9 utilizando vetor para implementar a(s) lista(s).
Sobre pilhas e filas, responda:
1. O que é um tipo abstrato de dado?
2. Descreva as características de uma pilha.
3. Implemente a função de inserção em uma pilha, utilizando a estrutura lista.
4. Implemente a função de remoção em uma pilha, utilizando a estrutura lista.
5. Implemente uma função que imprima os elementos de uma pilha começando do topo.
6. Descreva as características de uma fila.
7. Implemnte a função de inserção em uma fila, utilizando a estrutura lista.
8. Implemente a função de remoção em uma fila, utilizando a estrutura lista.
9. Implemente uma função que imprima os elementos de uma fila.
10.Duas pilhas A e B podem compartilhar o mesmo vetor, como esquematizado na Figura. Faça
as declarações de constantes e tipos necessárias e escreva as seguintes funções:
a)
b)
c)
d)
e)
f)
g)
h)
cria pilhas, que inicia os valores de topoA e topoB;
verifica se a pilha A está vazia (vaziaA);
verifica se a pilha B está vazia (vaziaB);
verifica se as pilhas estão cheias;
empilha uma chave na pilha A;
empilha uma chave na pilha B;
desempilha A;
desempilha B.
Figura 1.
11.Implemente as funções de inserção e remoção em fila utilizando vetor.
12.Implemente uma fila utilizando lista circular estática.
13.Qual TAD é utilizado na implementação de uma busca em profundidade? Justifique.
14.Qual TAD é utilizado na implementação de uma busca em largura? Justifique.
15.Explique como é o processo de busca em profundidade.
16.Explique como é o processo de busca em largura.
17.Escreva um programa que lê uma lista de alunos (nome e nota) e forneça as seguintes
opções:
a) inserir um aluno; (ler nome e nota)
b) excluir um aluno;
c) calcular média da turma;
d) imprimir alunos acima da média;
e) ordenar a lista;
f) imprimir lista;
g) sair.
Na implementação da opção c, deve-se utilizar o algoritmo mergesort.