Exercício de apoio - Semana 5 ESTRUTURAS DE DADOS - EID001

Prévia do material em texto

ESTRUTURAS DE DADOS
Árvores binárias e n-árias5
 
 
EXERCÍCIOS DE APOIO ( SEMANA 5 )
Apenas para praticar. Não vale nota.
Na videoaula 17, vimos a varredura infixa (subárvore esquerda – raiz – subárvore direita),
usada na contagem dos elementos da árvore. Também usamos, na leitura da árvore, a
varredura raiz – subárvore esquerda – subárvore direita, denominada prefixa. Uma outra
varredura bastante comum, mas que não foi citada, é a pós-fixa (subárvore esquerda –
subárvore direita – raiz).
 
Com relação ao código para árvores de busca binárias desenvolvido durante as aulas:
 
a) Escreva uma função para leitura da árvore na ordem infixa.
b) Escreva uma função para leitura da árvore na ordem pós-fixa.
 
 
Possíveis soluções:
a)
void infixa(PONT raiz) {
 if (raiz != NULL) {
 infixa(raiz->esq);
 printf(" %d",raiz->chave);
 infixa(raiz->dir);
 }
}
 
b)
void posfixa(PONT raiz) {
 if (raiz != NULL) {
 posfixa(raiz->esq);
 posfixa(raiz->dir);
 printf(" %d",raiz->chave);
 }
1.
}
 
 
Desenhe a árvore binária de pesquisa resultante da inserção sucessiva das chaves 40, 30,
50, 48, 12, 38, 60, 65, 62, 54, 35 em uma árvore inicialmente vazia.
 
 
 
 
2.
Desenhe as possíveis árvores resultantes da retirada do elemento de chave 50 da árvore da
questão anterior.
 
 
Substitui ou pelo nó mais à direita da subárvore da esquerda, ou pelo nó mais à esquerda da
subárvore da direita.
3.
ou
 
 
Como visto na videoaula 17, há inúmeras varreduras que podem ser feitas. Em que ordem
devemos percorrer a árvore para que, ao imprimirmos as chaves ao longo do caminho, estas
estejam em ordem decrescente? Apresente o código para tal.
 
4.
 
A ordem deve ser subárvore direita – raiz – subárvore esquerda:
 
void decrescente(PONT raiz) {
 if (raiz != NULL) {
 decrescente(raiz->dir);
 printf(" %d",raiz->chave);
 decrescente(raiz->esq);
 }
}
 
 
Dado o código para uma árvore n-ária apresentado na videoaula 19, escreva uma função
que conte o número de nós da árvore. A função deve seguir o modelo da varredura prefixa,
ou seja, contar a raiz, e então somar as contagens das subárvores de cada filho, da
esquerda para a direita. Ela também deve conter o seguinte cabeçalho:
 
int contaElementos(PONT raiz)
 
Segundo o qual ela recebe um ponteiro para a raiz da árvore, devolvendo o número de
elementos desta.
Uma possível solução é:
 
int contaElementos(PONT raiz) {
 int cont = 0;
 if (raiz) {//NULL conta como 0
 cont++;// contou a raiz
 PONT p = raiz->primFilho;
 // para cada filho, da esq para a dir, somo seus nós
 while (p) {
 cont += contaElementos(p);
 p = p->proxIrmao;
 }
 }
 return(cont);
}
 
5.
A figura a seguir apresenta uma árvore binária.
Uma função irá percorrê-la em ordem simétrica (inordem), inserindo seus nós em uma pilha
(implementada sobre uma lista encadeada) à medida que eles forem sendo visitados. A pilha
criada por essa função é:
6.
Considere a seguinte árvore de pesquisa binária:
Ao executarmos o procedimento de remoção do nó 11, na nova árvore binária de busca,
teremos, como filhos do nó 20, os nós:
14 e 21
7.
Dada a estrutura de uma árvore binária de busca, complete adequadamente a função teste,
de forma que receba a raiz de uma árvore binária de busca e imprima os valores de suas
chaves em ordem decrescente.
 
struct cel { 
 int chave; 
8.
 struct cel *pai; 
 struct cel *esq; 
 struct cel *dir; };
typedef struct cel no;
 
void teste (no *r){
 if (r!=NULL){
 __________________;
 print("%d\t",_________);
 __________________;
 }
}
teste(r->esq), r->chave, teste(r->dir)
A função compara (ArvVar* a, ArvVar* b) verifica se duas árvores são iguais. Essa função
obedece ao seguinte protótipo:
 
struct arvvar {
 char info;
 struct arvvar *prim; /* ponteiro para eventual primeiro filho */
 struct arvvar *prox; /* ponteiro para eventual irmão */
 };
typedef struct arvvar ArvVar;
 
int compara (ArvVar* a, ArvVar* b)
{
 ArvVar* p;
 ArvVar* q;
 int n = 0;
 if (a == NULL && b == NULL)
 return 1;
 for (_________;___________;______________)
 {if (!igual(p,q))
 return 0;};
 return 1;
}
 
Complete a função compara adequadamente:
9.
p=a->prim, q=b->prim; p!=NULL && q!=NULL; p=p->prox, q=q->prox
Considere a estrutura de dados Trie definida a seguir:
 
#define TAMANHO_ALFABETO (27)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
struct trie {
 char tipo; // 'I' : inteiro 'P' : Palavra
 struct trie *filho [TAMANHO_ALFABETO];
}
typedef struct trie no;
 
no *criar_no(void){
 int i:
 no *novo = (no *) malloc(sizeof(no));
 if (novo != NULL){
 novo->tipo = 'I';
 for (i=0;i<TAMANHO_ALFABETO;i++)
 novo->filho[i]=NULL;
 }
 return novo;
}
 
void adciona_palavra (char *palavra, no *raiz){
 int nivel =0, indice;
 no *tmp = raiz; 
 for (nivel =0; nivel<strlen(palavra);nivel++){
 indice = CHAR_TO_INDEX(palavra[nivel]);
 if (tmp->filho[indice]==NULL)
 ________________________;
 ________________________;
 }
 tmp->tipo = 'P';
 
}
 
int busca_palavra (char *palavra, no *raiz)
10.
{
 int i, indice;
 no *tmp = raiz;
 for (i=0;i<strlen(palavra);i++){
 indice = CHAR_TO_INDEX(palavra[i]);
 if (tmp->filho[indice]!=NULL)
 ______________________;
 else
 break;
 }
 if (palavra[i]=='\0' && tmp->tipo =='P')
 return 1;
 else
 return 0;
}
 
Complete adequadamente a função adciona_palavra e busca_palavra:
tmp->filho[indice]=cria_no();tmp = tmp->filho[indice]; tmp = tmp->filho[indice]
Uma árvore binária de pesquisa tem a estrutura interna representada da forma a seguir. O
método "adiciona" foi implementado para inserir um novo nó em uma árvore de busca, cuja
raiz foi passada como parâmetro. Complete o método "adiciona" para que o mesmo tenha o
efeito desejado.
 
typedef int bool;
typedef int TIPOCHAVE;
 
typedef struct aux{
 TIPOCHAVE chave;
 struct aux *esq, *dir;
} NO;
 
typedef NO* PONT;
 
PONT adiciona(PONT raiz, PONT no) {
 if (raiz == [option1]) return(no);
 if (no->[option2] < raiz->chave)
 raiz->esq = adiciona(raiz->[option3], no);
11.
 
 
 else
 raiz->dir = adiciona(raiz->[option4], no);
 /*ignoro se o nó tiver chave igual*/
 return(raiz);
}
A sequência correta é: NULL - chave - esq - dir
Uma maneira conveniente de imprimir uma árvore é usando a ordem "raiz - subárvore
esquerda - subárvore direita", como implementado no código "exibirArvore" a seguir:
typedef int TIPOCHAVE;
 
typedef struct aux{
 TIPOCHAVE chave;
 struct aux *esq, *dir;
} NO;
 
typedef NO* PONT;
 
void exibirArvore(PONT raiz){
 if (raiz != NULL) {
 printf("%d",raiz->chave);
 printf("(");
 exibirArvore(raiz->esq);
 exibirArvore(raiz->dir);
 printf(")");
 }
}
 
Uma dada árvore, quando impressa pela função "exibirArvore", devolve a seguinte string:
"45(27()90(75(60()76(87(78(77()79()))))100()))". Qual das alternativasa seguir mostra a
impressão da árvore após a remoção do elemento 90.
Resposta: 45(27()87(75(60()76(78(77()79())))100()))
12.
45(27()87(75(60()76(78(77()79())))100()))a.
45(27()79(75(60()76(78(77())))100(87())))b.
45(27()79(60(76(75()78(77())))100(87())))c.
45(27()87(60(76(75()78(77()79())))100()))d.
27(87(75(60(45())76(78(77()79())))100()))e.
 
 
Em uma árvore binária de busca inicialmente vazia, um total de 10 elementos distintos no
intervalo [0 .. 9] foram inseridos na seguinte ordem: "6, 8, 3, 5, 2, 7, 1, 4, 0, 9". Qual das
alternativas a seguir mostra a impressão da árvore na ordem "raiz - subárvore esquerda -
subárvore direita"?
Resposta: 6(3(2(1(0()))5(4()))8(7()9()))
13.
6(3(2(0(1()))5(4()))9(7(8())))a.
6(1(0()3(2()5(4())))7(8(9())))b.
6(4(3(0(1(2())))5())8(7()9()))c.
6(3(2(1(0()))5(4()))8(7()9()))d.
3(1(0()2())4(7(5(6())8(9()))))e.
Sobre uma estrutura de dados "árvore N-ária", em que cada nó pode ter até n filhos, assuma
que a implementação ocorreu sem nenhuma ordenação nos nós. Nesse contexto, é
correto afirmar que:
Resposta: A estrutura é uma generalização das árvores binárias, permitindo vários filhos por
nó, de modo a evitar a criação de árvores muito profundas. A busca por um dado nó pode
exigir o acesso a todos os outros nós.
14.
A estrutura é uma generalização das árvores binárias de pesquisa. Nesse caso, a
estrutura mantém a vantagem de ser possível alcançar qualquer nó de forma
eficiente com um mecanismo semelhante ao algoritmo de busca binária.
a.
A estrutura é uma generalização das árvores binárias, permitindo vários filhos por nó,
de modo a evitar a criação de árvores muito profundas. A busca por um dado nó
pode exigir o acesso a todos os outros nós.
b.
Percursos comuns em árvores binárias são de difícil implementação em árvores N-
árias. Por exemplo, a impressão da árvore na ordem "raiz - subárvore esquerda -
subárvore direita" exige acessar um mesmo nó repetidas vezes na implementação
de árvores N-árias.
c.
Como cada nó da árvore possui um número limitado de filhos, garante-se que o
conjunto total de nós da árvore é finito, o que permite a representação interna como
um arranjo de elementos contíguos na memória. 
d.
Na busca por um determinado nó a partir de uma chave de busca, compara-se a
chave sendo buscada com as chaves que estão em cada nó. Se a chave de busca
for menor, então a busca prossegue nos nós filhos. Caso contrário, a busca
prossegue nos nós irmãos.
e.
Uma estrutura de dados tries foi usada para armazenar um conjunto de palavras de modo a
tornar a busca eficiente. Nesse contexto, é correto afirmar que:
15.
Buscas, remoções e inserções ocorrem de maneira parecida com as
implementações em árvores binárias, exceto pelo fato de em tries usarmos cadeias
de caracteres ao invés de números inteiros.
a.
Supondo que o conjunto possui duzentas mil palavras, o algoritmo de busca por uma
palavra usando tries necessitará de um total de 18 comparações, aproximadamente.
b.
Usando tries, o número de comparações feitas pelo algoritmo que busca uma palavra
dentro do conjunto independe do tamanho do conjunto. O número de comparações
feitas dependerá apenas do tamanho da palavra buscada.
c.
Usando tries, o número de comparações feitas pelo algoritmo de inserção de uma
palavra dentro do conjunto depende do tamanho da palavra, enquanto que para o
algoritmo de busca o número de comparações depende do tamanho do conjunto.
d.
Usando tries, o número de comparações feitas pelo algoritmo de busca depende do
tamanho da palavra quando essa palavra realmente existe no conjunto. Entretanto,
se a palavra não existir no conjunto, o algoritmo percorrerá todos os nós da árvore.
e.
 
ESCONDER
GABARITO
Resposta: Usando tries, o número de comparações feitas pelo algoritmo que busca uma
palavra dentro do conjunto independe do tamanho do conjunto. O número de comparações
feitas dependerá apenas do tamanho da palavra buscada.