Questão FC266060
A respeito das estruturas de dados e algoritmos amplamente utilizados na execução de operações de busca e indexação, analise as afirmativas abaixo e marque alternativa correta. I.
Algoritmos e Lógica de Programação
IDECAN · 2022
A respeito das estruturas de dados e algoritmos amplamente utilizados na execução de operações de busca e indexação, analise as afirmativas abaixo e marque alternativa correta.
I. Busca sequencial é a mais elementar de todas as buscas. Considerando a busca em uma estrutura de dados com informações ordenadas, a busca sequencial será sempre menos eficiente do que a busca binária, no pior caso. A busca binária se beneficia do fato da estrutura de dados estar ordenada, isso facilita sua estratégia de busca.
II. As funções hash são usadas para mapearmos grandes conteúdos de informações que, mesmo tendo tamanho variável, retornaram como resultado informações de pequeno porte e de tamanho fixo. Tratam-se de funções probabilísticas, ou seja, devem resultar sempre no mesmo valor toda vez que receberem um mesmo dado como entrada.
III. Árvores AVL possuem como uma de suas características o fato de serem balanceada. Isso significa que a altura sub árvore esquerda de qualquer nó tem a mesma altura da sua sub árvore direita.
- Apenas as afirmativas I e II estão corretas.
- Apenas a afirmativa I está correta.
- Apenas a afirmativa III está correta.
- Apenas as afirmativas II e III estão corretas.
- Todas as afirmativas estão corretas.
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
A afirmativa I está correta porque contrasta duas estratégias de busca em estruturas ordenadas.
Busca sequencial examina elementos um a um até encontrar o alvo ou chegar ao fim; no pior caso precisa percorrer todos os n elementos, com complexidade \(O(n)\).
Busca binária aproveita que os dados estão ordenados e elimina metade do espaço de busca a cada comparação: compara com o elemento do meio e decide em qual metade continuar, resultando em \(O(\log n)\) no pior caso.
Por isso, em uma coleção ordenada a busca binária é assintoticamente mais eficiente que a busca sequencial; vale notar que a busca binária exige acesso eficiente ao elemento do meio (ex.: vetores).
Conteúdo do catálogo FC Concursos · Atualizado em