Árvore trie

Text Material Preview

Árvore trie 
O que e uma arvore Trie?
a) Uma estrutura de dados que armazena palavras, onde cada no representa um caractere.
b) Uma arvore binaria balanceada.
c) Uma lista encadeada que guarda palavras.
d) Um tipo de vetor usado para armazenar strings.
Resposta correta: a) Uma estrutura de dados que armazena palavras, onde cada no representa um
caractere.
Explicacao: A arvore Trie e uma estrutura de dados em arvore, onde cada no representa um
caractere de uma palavra e as palavras sao armazenadas de forma hierarquica.
Qual e a principal vantagem do uso da arvore Trie em relacao a outras estruturas como listas ou
vetores?
a) Uso de menos memoria.
b) Eficiencia na busca e insercao de palavras.
c) Facilidade de implementacao.
d) Nao permite a duplicacao de palavras.
Resposta correta: b) Eficiencia na busca e insercao de palavras.
Explicacao: A principal vantagem de uma Trie e que ela permite buscas e insercoes muito rapidas,
geralmente em tempo proporcional ao tamanho da palavra, ao contrario de outras estruturas que
podem exigir mais comparacoes.
Em uma arvore Trie, o que cada no geralmente representa?
a) Um numero inteiro.
b) Um caractere de uma palavra.
c) Uma palavra completa.
d) Um indice de uma lista.
Resposta correta: b) Um caractere de uma palavra.
Explicacao: Cada no de uma arvore Trie representa um unico caractere, e as palavras sao
armazenadas ao longo do caminho do no raiz ate um no folha, com cada nivel da arvore
representando uma letra da palavra.
Qual e a principal aplicacao da arvore Trie em sistemas de busca?
a) Armazenamento de dados numericos.
b) Ordenacao de palavras.
c) Busca eficiente de prefixos e palavras.
d) Armazenamento de listas de inteiros.
Resposta correta: c) Busca eficiente de prefixos e palavras.
Explicacao: Tries sao amplamente usadas em sistemas de busca para encontrar palavras ou
prefixos rapidamente, uma vez que cada no na arvore pode ser percorrido de forma eficiente para
verificar a existencia de uma palavra.
O que acontece quando inserimos uma palavra na arvore Trie?
a) A palavra e armazenada como um unico no.
b) A palavra e dividida e inserida nos nos correspondentes ao longo da arvore.
c) A palavra e transformada em um numero binario.
d) Nenhuma alteracao ocorre na arvore.
Resposta correta: b) A palavra e dividida e inserida nos nos correspondentes ao longo da arvore.
Explicacao: Ao inserir uma palavra em uma Trie, a palavra e dividida em seus caracteres e cada
caractere e armazenado em um no correspondente. Se os caracteres ja existirem, o caminho da
Trie e seguido, caso contrario, novos nos sao criados.
Qual e o tempo de busca de uma palavra em uma arvore Trie, em termos de seu comprimento?
a) O tempo de busca e proporcional ao logaritmo do numero de palavras armazenadas.
b) O tempo de busca e constante, independente do comprimento da palavra.
c) O tempo de busca e proporcional ao comprimento da palavra.
d) O tempo de busca depende do numero de nos na arvore.
Resposta correta: c) O tempo de busca e proporcional ao comprimento da palavra.
Explicacao: O tempo de busca em uma Trie e diretamente proporcional ao comprimento da palavra,
pois e necessario percorrer cada caractere da palavra, o que torna a busca muito eficiente em
comparacao a outras estruturas.
Qual e a principal desvantagem da arvore Trie?
a) Consome muita memoria, especialmente quando o conjunto de dados e grande.
b) As buscas sao mais lentas que em arvores binarias.
c) A insercao de palavras e dificil de realizar.
d) Nao e possivel armazenar palavras com caracteres especiais.
Resposta correta: a) Consome muita memoria, especialmente quando o conjunto de dados e
grande.
Explicacao: Embora a Trie seja eficiente em termos de busca, ela pode consumir muita memoria,
pois cada caractere de uma palavra precisa ser armazenado em um no separado. Isso pode ser
problematico quando lidamos com um grande numero de palavras.
O que e um no folha em uma arvore Trie?
a) O no que contem a palavra completa.
b) O no inicial de uma arvore Trie.
c) O no que armazena um prefixo, mas nao uma palavra completa.
d) O no que nao possui filhos.
Resposta correta: a) O no que contem a palavra completa.
Explicacao: O no folha em uma arvore Trie e aquele onde uma palavra termina. Ou seja, e o no que
representa o final de uma sequencia de caracteres que forma uma palavra completa.
Como a arvore Trie lida com palavras comuns em um grande conjunto de dados?
a) Cria multiplos nos para caracteres comuns.
b) Compartilha os nos comuns para palavras que tem os mesmos prefixos.
c) Armazena as palavras em um formato compactado.
d) Nao e possivel armazenar palavras comuns eficientemente.
Resposta correta: b) Compartilha os nos comuns para palavras que tem os mesmos prefixos.
Explicacao: A Trie e eficiente em termos de armazenamento, pois ela compartilha nos para prefixos
comuns entre palavras. Isso economiza memoria, ja que palavras que comecam com o mesmo
prefixo tem os mesmos nos iniciais.
Qual e o objetivo de realizar a "compressao" de uma arvore Trie?
a) Tornar a arvore mais rapida de buscar.
b) Reduzir a quantidade de memoria usada pela arvore.
c) Aumentar a altura da arvore para otimizar a insercao.
d) Transformar a arvore em uma lista.
Resposta correta: b) Reduzir a quantidade de memoria usada pela arvore.
Explicacao: A compressao de uma Trie visa reduzir a quantidade de memoria necessaria,
minimizando a criacao de nos redundantes. Em algumas versoes, os nos podem ser fundidos
quando tem apenas um filho, o que melhora a eficiencia no uso de memoria.
Em uma arvore Trie, como seria representada a palavra "cachorro"?
a) Cada caractere seria armazenado em um no separado, de 'c' a 'o', com uma sequencia de nos.
b) A palavra seria armazenada de forma compactada em um unico no.
c) Apenas as vogais seriam armazenadas.
d) A palavra "cachorro" nao pode ser armazenada em uma Trie.
Resposta correta: a) Cada caractere seria armazenado em um no separado, de 'c' a 'o', com uma
sequencia de nos.
Explicacao: A palavra "cachorro" seria armazenada como uma sequencia de nos representando
cada caractere. A arvore ficaria estruturada de modo que, ao percorrer os nos, a palavra completa
pudesse ser reconstruida.
Qual e o papel do no raiz em uma arvore Trie?
a) Armazenar a primeira letra de todas as palavras.
b) Nao armazena nada, apenas serve como ponto de partida.
c) Armazenar o comprimento de todas as palavras.
d) Guardar as palavras que ja foram inseridas.
Resposta correta: b) Nao armazena nada, apenas serve como ponto de partida.
Explicacao: O no raiz nao contem informacoes sobre palavras, ele apenas serve como ponto de
inicio da busca e insercao, apontando para os primeiros caracteres das palavras.
O que ocorre quando tentamos buscar uma palavra que nao esta presente na arvore Trie?
a) A busca retorna a palavra mais proxima.
b) A arvore e automaticamente reestruturada.
c) A busca retorna um valor nulo ou uma indicacao de falha.
d) A palavra e inserida automaticamente na arvore.
Resposta correta: c) A busca retorna um valor nulo ou uma indicacao de falha.
Explicacao: Quando uma palavra nao e encontrada, a busca retorna uma indicacao de falha, como
um valor nulo, ja que nao ha um caminho correspondente na arvore Trie para os caracteres dessa
palavra.
Quais sao as operacoes basicas realizadas em uma arvore Trie?
a) Insercao, busca e delecao de palavras.
b) Apenas insercao e busca de palavras.
c) Somente busca de palavras.
d) Insercao, busca, delecao e ordenacao.
Resposta correta: a) Insercao, busca e delecao de palavras.
Explicacao: As operacoes basicas de uma Trie incluem insercao de palavras, busca de palavras e
delecao de palavras, sendo essas as operacoes que garantem sua funcionalidade.
Em qual cenario uma arvore Trie pode ser mais vantajosa?
a) Quando se deseja realizar buscas rapidas por prefixos ou palavras completas.
b) Quando o numero de palavras e muito pequeno.
c) Quando a memoria e muito limitada.d) Quando as palavras a serem armazenadas sao numeros inteiros.
Resposta correta: a) Quando se deseja realizar buscas rapidas por prefixos ou palavras completas.
Explicacao: A Trie e ideal para cenarios onde e necessario realizar buscas rapidas por prefixos ou
palavras, pois sua estrutura permite buscas eficientes e rapidas, principalmente quando as palavras
possuem prefixos comuns.