Revisaoestrutura.docx

Prévia do material em texto

PXI			- Estrutura de Dados 					 - Professora : Jane 
Fixação para AV2 e AV3
Comentários :
AV2 : matéria toda. Há 8 questões, sendo 2 discursivas e as demais de múltipla escolha.
AV3 : matéria toda. Há 12 questões, sendo 2 discursivas e as demais de múltipla escolha.
 Cada questão discursiva vale 2 pontos e pode ser para implementar ou pode ser teórica. As demais questões podem valer 1,0 ponto ou 0,5 ponto cada uma.
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Exercícios
1)Complete :
a) Pilha é um tipo especial de lista em que as inserções ou remoções seguem o critério LIFO (Last In First Out). A operação de inserir em uma pilha chama-se empilhamento ou push em Inglês e a operação de remoção da pilha chama-se pop ou desempilhamento. NOTE : O último que entra na pilha é o primeiro que sai da mesma (LIFO).
b) Fila é um tipo especial de lista em que as inserções e remoções seguem o critério FIFO (First In First Out). Vimos duas implementações de fila sequencial : a fila simples e a fila circular. NOTE : O 1º. a entrar na fila será o 1º. a sair da mesma.
c) Uma lista sequencial qualquer ou uma pilha sequencial ou uma fila sequencial possuem duas situações críticas quando realizamos inserção e remoção. São elas :
>> ao inserir pode não haver espaço disponível na lista ou pilha ou fila, o que representa overflow ou underflow ? Overflow
>> ao remover pode não ter elemento para ser removido, o que representa overflow ou underflow ? Underflow
2) Faça o que se pede :
a) Imagine uma fila sequencial simples. Temos inicio inicializado com zero, fim inicializado com -1 e um vetor v com capacidade para 5 elementos. Após enfileirar nesta ordem, os valores 1, 3, 5, 7 e depois desenfileirar 2 valores, pergunta-se : qual o primeiro e último dados da fila simples ? Qual o valor de fim e o valor de inicio ao final das operações ? Desenvolvimento no quadro. Resposta final : O 1º. dado da fila é o 5 e o último dado da fila é o 7. O valor de início é 2 e o de fim é 3, após os enfileiramentos e desenfileiramentos.
b) Agora, considere uma fila sequencial circular com contador. Temos, além do vetor de dados, as variáveis inicio, fim e quantidade (fornece a quantidade de elementos). Inicialmente, temos que
 inicio = quantidade = 0;
 fim = -1;
Se tivermos um vetor com capacidade para 4 elementos e realizarmos a seguinte sequência de operações:
b.1) enfileirar os valores 10, 5, 7, 2
b.2) desenfileirar 2 valores
b.3) enfileirar o valor 8
Pergunta-se : Qual será o valor do inicio, do fim e da quantidade ? Que dados ainda permanecerão na fila ?
Desenvolvimento no quadro. Resposta final : Valor de inicio é 2, o de fim é 0 e a quantidade vale 3. Permanecerão na fila os valores 7, 2 e 8.
c) Ordenação...
c.1) Que métodos de ordenação foram estudados ? Ordenação por inserção, por seleção e o método da bolha (bubblesort).
c.2) Qual deles compara pares de chaves ... o 1o. com o 2o., depois o 2o. com o 3o. elemento, etc ... realizando trocas para ordenar ? Bubblesort ou método da bolha.
c.3) Que outros métodos de ordenação foram citados no curso ? Mergesort e o Quicksort. Quais deles é um método de ordenação por trocas assim como o bubblesort (bolha) ? Quicksort.
d) Explique, objetivamente, como funcionam as busca sequencial e binária.
Falado em aula.
e) Seja uma lista simplesmente encadeada não circular que implementa uma pilha de inteiros. Seja a struct que modela cada nó da lista assim definida : 
 struct no { int dado; 
 struct no *link; };
Sabe-se que struct é uma palavra reservada das linguagens C e C++ que permite definir um tipo de dados que é um agregado heterogêneo ou um registro. O termo registro é usualmente visto quando se trabalha com pseudocódigo.
Pergunta-se :
e.1) A função que implementa inserção no início da lista é a mesma que serve para empilhar em uma pilha dinâmica ? Sugestão : Veja a aula 9. Resposta : Sim
e.2) Escreva a função para imprimir apenas os dados pares de uma lista simplesmente encadeada não circular, considerando o tipo no acima. Protótipo : void imprimir(no *); 
Solução :
void imprimir(no *p)
{
	while (p != NULL) 	
 {
 if (p->dado % 2 == 0) 
		cout << " " << p->dado;
	 p = p->link; //fora do if
	}
}
 f) Que tipo de alocação de memória é realizada em uma lista encadeada ? E o armazenamento : é contíguo ou encadeado ? Alocação dinâmica e o armazenamento é encadeamento.
g) Considere uma fila dinâmica inicialmente vazia. Enfileiramos as letras M, U, L, U, A , nesta ordem. Depois, realizamos dois desenfileiramentos. Em seguida, enfileiramos C, H, E, I, A. Desenhe o lista encadeada que implementa a fila dinâmica mencionada. FEITO no quadro.
i) Sobre funções ...
 i.1) Uma função que não retorna nada tem o tipo de retorno void
 i.2) variáveis declaradas fora do escopo de qualquer função é uma variável global
i.3) os parâmetros passados para uma função são passados por valor ou por referência.
i.4) Escreva o protótipo de uma função de nome empilhar, que nada retorna e que deverá receber como parâmetros uma pilha p do tipo Pilha e valor, que é o elemento inteiro a ser empilhado. Sabe-se que Pilha é uma struct com os campos v (vetor de dados inteiros) e topo (tipo int).
 Solução : void empilhar (Pilha &p, int valor);
 Ou void empilhar (Pilha &, int );
j) Qual das listas encadeadas estudadas tem uma aplicação importante no estudo de sistemas operacionais ? 
As listas duplamente encadeadas (circulares) Que aplicação é esta ? O método Round Robin usado no sistema operacional UNIX é implementado usando lista duplamente encadeada (circular). 
3) Considere uma lista sequencial não ordenada de notas de alunos que é modelada pela seguinte struct :
 #define TAM 10
 struct Lista {
 int n;
 float notas[TAM];
 };
onde TAM é uma constante pré-definida como indicado acima.
Em cada item, escreva uma função para : 
a) inserir uma nota na lista L do tipo Lista. FEITO no quadro
b) imprimir todas as notas da lista L . FEITO no quadro
c) realizar uma busca sequencial em L . FEITO no quadro