lista_exercicios.pdf - �rvores estrutura de dados

Prévia do material em texto

Lista de Exercícios
Estrutura de Dados 2
Prof. Guto Vannini
Observações
Todos os exercícios devem ser resolvidos utilizando linguagem C ou C++.
Árvores
1. Faça uma função para determinar se uma árvore é estritamente binária.
2. Faça uma função para determinar se uma árvore é binária completa.
3. Faça uma função para determinar se uma árvore é binária quase completa.
4. Faça uma função para determinar se uma árvore é binária AVL (considere os 
estados completa e quase completa).
5. Faça uma função para retornar a profundidade de uma árvore binária.
6. Faça as funções isleft(* nó) e isright(* nó) para verificar se um 
dado nó da árvore é o filho da esquerda ou da direita.
7. Faça a função brother(* nó) que retorna um ponteiro para o nó irmão de 
um dado nó da arvore.
8. Considere a seguinte situação: uma pessoa, de posse de um baralho, quer 
ordenar as cartas levando em consideração os naipes e os números. Dentro 
dessa forma de classificação a ordem dos naipes é  (ouro),  (espada),  
(copas) e  (paus), sendo o de ouro o menor e o de paus o maior. Para cada 
naipe, as cartas seguem a seguinte ordem: A 2 3 4 5 6 7 8 9 10 J Q K.
Faça um programa que ajude o usuário a ordenar as cartas. O programa 
deverá utilizar uma rotina de inserção em árvore binária de busca, onde cada 
carta retirada do maço (neste caso digitada pelo usuário) será incluída nesta 
árvore. Não pode haver cartas duplicadas inseridas na árvore. Após todas as 
cartas que o usuário desejar terem sido inseridas na árvore, elas devem ser 
mostradas em ordem na tela. Para a criação do programa, considere a 
seguinte estrutura abaixo:
struct carta
{
 short numero;
 short naipe;
 struct carta * esq, * dir;
};
DICA: para a inserção na árvore, primeiro deve ser levado em conta o naipe 
1
e em caso de empate do naipe, será considerado o número da carta.
Visto que a variável naipe é do tipo short, considere os seguintes valores 
para os naipes: 0 = ouro; 1 = espada; 2 = copas e 3 = paus. O mesmo deve 
ser feito com a variável numero, onde: A = 1, J = 11, Q = 12 e K = 13. Para 
apresentação em tela os valores devem ser trocados pelas letras/palavras 
correspondentes.
Ordenação
9. Modifique os programas de ordenação vistos em sala de aula para 
ordenarem um vetor de 1.000.000 de posições e marque o tempo de 
execução de cada programa para verificar qual é efetivamente mais rápido.
10.Modifique o programa de ordenação pelo método de seleção para a cada 
iteração encontrar o maior e o menor número, diminuindo assim o número de 
vezes. Inclua esse programa na comparação do primeiro exercício.
11.Modifique o programa de ordenação pelo método quick sort para quando a 
partição tiver 1 ou 2 elementos, resolver a ordem dos elementos sem chamar 
a função partição. Inclua esse programa na comparação do primeiro 
exercício.
Espalhamento
12.Faça um programa que permita controlar as notas de uma turma de alunos 
matriculados na faculdade. O programa deverá permitir ao usuário incluir, 
consultar, alterar e apagar dados (alunos e suas notas) da turma. Será 
utilizado um arquivo chamado alunos.txt para armazenar os dados da 
turma. Este arquivo deverá ser lido somente no início do programa, sendo ele 
guardado numa estrutura de memória (tabela de hash). Este arquivo também 
só será gravado ao final do programa, quando a estrutura de memória será 
salva automaticamente neste arquivo. Para a estrutura do arquivo considere 
código (inteiro longo), nome (string) e 4 notas bimestrais (float). Abaixo segue 
um exemplo desse arquivo:
030125406 ANDRE 8.0 8.5 7.0 9.0
031001222 BRUNO 4.0 5.0 6.5 7.0
032123789 ZEBEDEU 10.0 10.0 10.0 10.0
O único dado que não será permitida a alteração será o código do aluno, pois 
este deverá ser utilizado como chave para a tabela de hash.
Grafos
13.Modifique as funções join(a,b) e remove(a,b) para que o grafo não seja 
orientado.
2
14.Crie uma estrutura (struct) para matriz de adjacência do grafo de forma 
que seja possível associar um peso para o arco.
15.Com a estrutura do exercício anterior, crie as funções joinwt(a,b,x) e 
remvwt(a,b,x) onde x representa o peso do arco.
16.Crie a função existpath(a,b) que retorna um booleano indicando se há 
caminho entre os vértices a e b.
17.Crie a função ciclico() que retorna verdadeiro se o grafo for cíclico e falso 
caso contrário.
18.Faça a função orientado() que retorna verdadeiro (1) se o grafo contido 
na matriz de adjacência for orientado e falso (0) se não for orientado.
19.Faça uma função que receba como parâmetro um vértice do grafo e imprima 
o grau de saída, o grau de entrada e o grau total desse vértice. Não é 
necessário nenhum retorno por parte dessa função.
20.Escreva uma rotina que, dados dois vértices de um grafo (a,b) e um 
comprimento de caminho (x), calcule e retorne o número de caminhos de 
comprimento x existentes entre a e b.
21.Escreva uma rotina que, dados dois vértices de um grafo (a,b) retorne o 
número total de caminhos existente entre eles.
Arquivos
22.Criar um versão simplificada do utilitário diff do Unix. Este utilitário permitirá 
comparar dois arquivos texto, informando as linhas que tiveram modificação 
de um para outro. Esta versão simplificada deverá se chamar diffs 
(diffs.exe). Exemplo:
Suponha os seguintes arquivos:
Nome do arquivo: 1.txt 2.txt
Conteúdo do arquivo: a
b
d
e
f
a
b
c
d
e
A linha de comando para invocar o utilitário será como mostrado abaixo:
diffs 1.txt 2.txt
e o resultado deve ser o seguinte:
3
> c
< f
Onde:
> : significa a saída da linha do arquivo inicial (1.txt)
< : significa a entrada da linha no arquivo final (2.txt)
Observação: Sempre que duas linhas forem iguais nada deve ser informado, 
mesmo que elas estejam em posição numérica diferentes, como é o caso das 
linhas “d” e “e” do exemplo acima.
4