EstruturaDeDados_Semana5 2017

Prévia do material em texto

12/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2639/quizzes/8326/take 1/4
2 ptsPergunta 1
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 == NULL ) return(no);
 if (no-> chave < raiz->chave)
 raiz->esq = adiciona(raiz-> esq , no);
 else
 raiz->dir = adiciona(raiz-> dir , no);
 /*ignoro se o nó tiver chave igual*/
 return(raiz);
}
2 ptsPergunta 2
12/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2639/quizzes/8326/take 2/4
45(27()87(75(60()76(78(77()79())))100()))
45(27()79(75(60()76(78(77())))100(87())))
27(87(75(60(45())76(78(77()79())))100()))
45(27()87(60(76(75()78(77()79())))100()))
45(27()79(60(76(75()78(77())))100(87())))
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 alternativas a seguir mostra a
impressão da árvore após a remoção do elemento 90.
12/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2639/quizzes/8326/take 3/4
2 ptsPergunta 3
3(1(0()2())4(7(5(6())8(9()))))
6(4(3(0(1(2())))5())8(7()9()))
6(1(0()3(2()5(4())))7(8(9())))
6(3(2(1(0()))5(4()))8(7()9()))
6(3(2(0(1()))5(4()))9(7(8())))
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"?
2 ptsPergunta 4
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.
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.
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.
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.
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.
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:
2 ptsPergunta 5
 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:
12/09/2019 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/2639/quizzes/8326/take 4/4
Nenhum dado novo para salvar. Última verificação às 15:08 
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.
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.
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.
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.
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.
Enviar teste