Estruturas de Dados em Supermercado

Prévia do material em texto

Paulo Rech Wagner 1 Gabarito Prova P1 
 
 
PUCRS - FACULDADE DE INFORMÁTICA 
ENGENHARIA DE COMPUTAÇÃO 
Algoritmos e Estrutura de Dados II - Turma 590 
Prof. Paulo Rech Wagner 
PROVA P2 Data: 25/05/07 
 
 
 
Questão 1) 
A estrutura de dados utilizada para controlar as compras dos clientes em um 
supermercado foi implementada através de estruturas cruzadas (lista com lista, ABP com 
lista,...). Esta estrutura de dados deve ser totalmente dinâmica contendo os clientes e os 
produtos que cada um está comprando. Os clientes possuem os atributos nome (campo 
chave), cpf e uma referência para a lista dos produtos que está comprando. Cada produto 
possui os atributos nome e preço. Considerando que os dados já estão armazenados na 
estrutura de dados, faça: (3.0 pontos) 
a) defina a estrutura de dados a ser utilizada fazendo o seu desenho e indicando 
todas as classes utilizadas com seus respectivos atributos; 
b) um método, que recebe como parâmetro o nome de um cliente e retorne o produto 
mais barato que está comprando; 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Classes utilizadas: 
- Classe NodoLSE 
- Classe ListaLSE 
- Classe Cliente 
 inicio 
 literal nome , cpf 
lista dos clientes 
nome, cpf 
lista_prod 
nome preço 
lista dos produtos 
do cliente 
………… 
prim ult 
prim ult 
Objeto Produto 
Objeto Cliente 
Objeto ListaLSE 
Objeto ListaLSE 
Paulo Rech Wagner 2 Gabarito Prova P1 
 
 ListaLSE lista_prod 
 fim 
 
- Classe Produto 
 inicio 
 literal nome 
 real preco 
 fim 
 
- Classe ListaClientes subclasse de ListaLSE 
 inicio 
 ... 
 Produto produto_mais_barato(literal nome_cliente) 
 fim 
 
Algoritmo produto_mais_barato(literal nome_cliente) 
 inicio 
 ListaLSE lprod 
 NodoLSE nocli, noprod, mais_barato 
 Produto prod 
 
 nocli ← pesquisar(nome_cliente) 
 se ( nocli = nulo ) 
 então retorna nulo 
 senão inicio 
 mais_barato ← nulo 
 lprod ← nocli.get_info( ).get_lista_prod( ) 
 noprod ← lprod.get_primeiro( ) 
 enquanto ( noprod ≠ nulo ) faça 
 inicio 
 prod ← noprod.get_info( ) 
 se ( mais_barato = nulo ) 
 então mais_barato ← noprod 
 senão se ( prod.get_preco( ) < mais_barato.get_info( ).get_preco( ) ) 
 então mais_barato ← noprod 
 noprod ← noprod.get_prox( ) 
 fim 
 retorna mais_barato.get_info( ) 
 fim 
 fim 
 
Algoritmo Principal 
 inicio 
 ListaClientes listacli 
 NodoLSE nocli 
 literal nome 
 
 /* produto mais barato de um cliente */ 
 escreva (“informe o nome do cliente”) 
 leia (nome) 
 nocli ← listacli.pesquisar(nome) 
 se ( nocli = nulo ) 
 então escreva (“não existe este cliente”) 
 senão inicio 
 prod ← listacli.produto_mais_barato(nome) 
 se ( prod = nulo ) 
 então escreva (“este cliente não está comprando nada”) 
 senão escreva (“produto mais barato : “, prod.get_nome( )) 
 fim 
Paulo Rech Wagner 3 Gabarito Prova P1 
 
 
 
Questão 2) 
Os valores da seqüência abaixo devem ser incluídos em uma árvore binária de pesquisa 
(ABP). Sabe-se que o primeiro valor desta seqüência estará localizado na raiz da árvore. 
Mostre a representação gráfica da árvore após estas inclusões e liste seus elementos 
através das 3 formas de caminhamento, nomeando-as. (2.0 pontos) 
 
60 35 55 95 45 15 80 50 85 75 90 40 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Pré-fixado: 60 35 15 55 45 40 50 95 80 75 85 90 
Central: 15 35 40 45 50 55 60 75 80 85 90 95 
Pós-fixado: 15 40 50 45 55 35 75 90 85 80 95 60 
 
 
 
Questão 3) 
Dado um banco de dados já construído e composto pelos seguintes campos: nome, cargo 
e salário. Sabendo que ele está organizado segundo uma árvore binária já construída, 
escreva um algoritmo que leia o nome de uma pessoa e verifique se ela está presente ou 
não na árvore binária. Caso ela esteja presente, escreva um método que calcule e 
informe a média salarial das pessoas que possuem o mesmo cargo do que ela (pessoa 
pesquisada) existentes neste banco de dados. (2.0 pontos) 
 
Classe Pessoa: literal nome, literal cargo, real salario 
 
/* versão 1 – utilizando dois métodos distintos: uma para contar e outro para somar */ 
Algoritmo Principal 
 inicio 
 Arv_Binaria ab 
 NodoAB no 
 literal nome, cargo 
 inteiro cont 
 real soma 
 
 escreva (“informe o nome de uma pessoa”) 
 leia (nome) 
 no ← ab.pesquisar(nome) 
 se ( no = nulo ) 
 então escreva (“esta pessoa não está na árvore”) 
35 
15 
95 
55 
85 
80 
60 
40 
45 75 
90 50 
Paulo Rech Wagner 4 Gabarito Prova P1 
 
 senão inicio 
 cargo ← no.get_info( ).get_cargo( ) 
 cont ← ab.conta_cargo(cargo) 
 soma ← ab.soma_salario(ab.get_raiz( ), cargo) 
 escreva (“media salarial das pessoas de mesmo cargo: ”, soma/cont) 
 fim 
 fim 
 
 
/* retorna a quantidade de pessoas do mesmo cargo. Chama o algoritmo recursivo */ 
Algoritmo conta_cargo (literal cargo) 
 inicio 
 retorna conta_cargo(raiz, cargo) 
 fim 
 
/* algoritmo recursivo que retorna a quantidade de pessoas do mesmo cargo */ 
Algoritmo conta_cargo (NodoAB no, literal cargo) 
 inicio 
 se ( no = nulo ) 
 então retorna 0 
 senão se ( no.get_info( ).get_cargo( ) = cargo ) 
 então retorna 1 + conta_cargo(no.get_esq( ),cargo) + 
 conta_cargo(no.get_dir( ),cargo) 
 senão retorna conta_cargo(no.get_esq( ),cargo) + 
 conta_cargo(no.get_dir( ),cargo) 
 fim 
 
/* retorna a soma salarial das pessoas do mesmo cargo */ 
Algoritmo soma_salario (NodoAB no, literal cargo) 
 inicio 
 se ( no = nulo ) 
 então retorna 0 
 senão se ( no.get_info( ).get_cargo( ) = cargo ) 
 então retorna no.get_info( ).get_salario( ) + 
 soma_salario(no.get_esq( ),cargo) + soma_salario(no.get_dir( ),cargo) 
 senão retorna soma_salario(no.get_esq( ),cargo) + 
 soma_salario(no.get_dir( ),cargo) 
 
 fim 
 
 
/* versão 2 – utilizando um único método para retornar a contagem e o somatório */ 
Algoritmo Principal 
 inicio 
 Arv_Binaria ab 
 NodoAB no 
 literal nome 
 real media 
 
 escreva (“informe o nome de uma pessoa”) 
 leia (nome) 
 no ← ab.pesquisar(nome) 
 se ( no = nulo ) 
 então escreva (“esta pessoa não está na árvore”) 
 senão inicio 
 media ← ab.media_salarial_cargo(no.get_info( ).get_cargo( )) 
 escreva (“media salarial das pessoas de mesmo cargo: ”, media)fim 
 fim 
 
Paulo Rech Wagner 5 Gabarito Prova P1 
 
/* objeto temporario utilizado para armazenar dois valores de retorno */ 
Classe objeto_temporario 
 inicio 
 inteiro cont 
 real soma 
 
 objeto_temporario ( ) : construtor 
 { cont ← 0; soma ← 0 } 
 inteiro get_cont ( ) : método que retorna o valor do contador 
 { retorna cont } 
 inc_cont ( ) : método que incrementa 1 no contador 
 { cont ← cont + 1 } 
 real get_soma ( ) : método que retorna o valor do acumulador 
 { retorna soma } 
 
 acum_soma (real val) : método que acumula o valor val no acumulador 
 { soma ← soma + val } 
 
 fim 
 
/* retorna a média salarial das pessoas do mesmo cargo. Chama o algoritmo recursivo */ 
Algoritmo media_salarial_cargo (literal cargo) 
 inicio 
 objeto_temporatio temp 
 
 temp ← novo objeto_temporario( ) 
 media_salarial_cargo(raiz, cargo, temp) 
 retorna temp.get_soma( )/temp.get_cont( ) 
 fim 
 
/* algoritmo recursivo que retorna a média salarial das pessoas do mesmo cargo */ 
Algoritmo media_salarial_cargo (NodoAB no, literal cargo, objeto_temporario temp) 
 inicio 
 se ( no ≠ nulo ) 
 então inicio 
 se ( no.get_info( ).get_cargo( ) = cargo ) 
 então inicio 
 temp.inc_cont( ) 
 temp.acum_soma(no.get_info( ).get_salario( )) 
 fim 
 media_mesmo_sexo(no.get_esq( ),cargo,temp) 
 media_mesmo_sexo(no.get_dir( ),cargo,temp) 
 fim 
 fim 
 
 
Questão 4) 
Escreva um algoritmo que leia (no algoritmo principal) um valor inteiro e verifique se ele 
está presente ou não em uma árvore binária de pesquisa (ABP) contendo valores inteiros. 
Caso ele esteja presente, escreva um método que retorna e escreva (no algoritmo 
principal) a quantidade de valores presentes na ABP que são maiores do que ele. Para 
exemplificar, indicar dois valores quaisquer da árvore da questão 2 com suas respectivas 
quantidades de valores maiores. (3.0 pontos) 
 
Exemplos: 
- valor 60 → quantidade de valores maiores: 5 
- valor 50 → quantidade de valores maiores: 7 
 
Paulo Rech Wagner 6 Gabarito Prova P1 
 
Algoritmo Principal 
 inicio 
 Arv_BinPesquisa abp 
 NodoAB no 
 inteiro valor, nelem 
 
 escreva (“informe um valor”) 
 leia (valor) 
 no ← abp.pesquisar(valor) 
 se (no = nulo ) 
 então escreva (“não está na ABP”) 
 senão inicio 
 nelem ← abp.maiores(valor) 
 escreva (“existem “, nelem, “valores maiores do que “, valor) 
 fim 
 fim 
 
/* versão 1 – algoritmo recursivo */ 
Algoritmo maiores (inteiro valor) 
 inicio 
 retorna maiores(raiz,valor) 
 fim 
 
Algoritmo maiores (NodoAB no, inteiro valor) 
 inicio 
 se (no = nulo) 
 então retorna 0 
 senão se (no.get_info( ).comparar(valor) = -1) 
 então retorna 1 + maiores(no.get_esq( ),valor) + maiores(no.get_dir( ),valor) 
 senão retorna maiores(no.get_esq( ),valor) + maiores(no.get_dir( ),valor) 
 fim 
 
 
/* versão 2 – algoritmo interativo – subir até a raiz a partir do no*/ 
Algoritmo maiores (inteiro valor) 
 inicio 
 NodoAB no, pai 
 inteiro cont 
 
 no ← pesquisar(valor) 
 cont ← tamanho(no.get_dir( )) 
 pai ← acha_pai(no) 
 enquanto (pai ≠ nulo) faça 
 inicio 
 se ( pai.get_info( ).comparar(valor) = -1) 
 então cont ← cont + 1 + tamanho(pai.get_dir( )) 
 pai ← acha_pai(pai) 
 fim 
 retorna cont 
 fim 
 
 
/* versão 3 – algoritmo interativo – descer até achar. Se no maior, contar direita */ 
Algoritmo maiores (inteiro valor) 
 inicio 
 NodoAB paux 
 inteiro cont 
 lógico achei 
 
 achei ← falso 
Paulo Rech Wagner 7 Gabarito Prova P1 
 
 cont ← 0 
 paux ← raiz 
 enquanto (não achei) faça 
 inicio 
 se (paux.get_info( ).comparar(valor) = 0) 
 então inicio 
 achei ← verdadeiro 
 cont ← cont + tamanho(paux.get_dir( )) 
 fim 
 senão se (paux.get_info( ).comparar(valor) = -1) 
 então inicio 
 cont ← cont + 1 + tamanho(paux.get_dir( )) 
 paux ← paux.get_esq( ) 
 fim 
 senão paux ← paux.get_dir( ) 
 retorna cont 
 fim