Em estruturas de dados, listas podem ser implementadas por ...
Próximas questões
Com base no mesmo assunto
Ano: 2026
Banca:
COPEVE-UFAL
Órgão:
IFAL
Prova:
COPEVE-UFAL - 2026 - IFAL - Professor EBTT - Informática |
Q3953491
Algoritmos e Estrutura de Dados
Em estruturas de dados, listas podem ser implementadas por
meio de vetores ou por meio de listas encadeadas com
ponteiros. Cada forma de implementação apresenta
características próprias quanto ao acesso aos dados, ao uso de
memória e ao desempenho dos algoritmos associados.
Ainda sobre essas duas formas de implementação, dadas as afirmativas,
I. O algoritmo de busca binária tem o mesmo desempenho se implementado numa lista encadeada ou num vetor de posições, desde que os elementos estejam ordenados.
II. A lista encadeada evita desperdício de espaço em memória por superdimensionamento, uma vez que aloca memória por demanda de uso e não a priori.
III. Diferentemente da lista encadeada, numa lista com vetores, é possível acessar qualquer espaço da memória com o mesmo custo computacional.
verifica-se que está/ão correta/s
Ainda sobre essas duas formas de implementação, dadas as afirmativas,
I. O algoritmo de busca binária tem o mesmo desempenho se implementado numa lista encadeada ou num vetor de posições, desde que os elementos estejam ordenados.
II. A lista encadeada evita desperdício de espaço em memória por superdimensionamento, uma vez que aloca memória por demanda de uso e não a priori.
III. Diferentemente da lista encadeada, numa lista com vetores, é possível acessar qualquer espaço da memória com o mesmo custo computacional.
verifica-se que está/ão correta/s
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
Gabarito: D
Fundamento decisivo: O ponto decisivo era a diferença de acesso entre as estruturas: em vetor, o acesso por índice é direto; em lista encadeada, é preciso percorrer os nós. Por isso, a busca binária não tem o mesmo desempenho nas duas implementações, enquanto o vetor mantém custo uniforme por posição, o que sustenta a combinação II e III.
Tema central: vetor e lista encadeada
Análise das alternativas
A
Errada
Está errada porque depende de a I ser verdadeira. A I é falsa: elementos ordenados não bastam para igualar o desempenho da busca binária em vetor e lista encadeada, pois a operação exige acesso ao elemento médio, e esse acesso não é eficiente da mesma forma na lista encadeada.
B
Errada
Está errada porque considera apenas a II. Embora a II seja verdadeira pela alocação sob demanda da lista encadeada, a III também é verdadeira, já que o vetor permite acesso direto por índice com custo uniforme por posição, diferentemente da lista encadeada.
C
Errada
Está errada porque inclui a I. A III é verdadeira, mas a I não se sustenta: a ordenação dos elementos não elimina a diferença estrutural de acesso entre vetor e lista encadeada, e por isso a busca binária não mantém o mesmo desempenho nas duas implementações.
D
Certa
A alternativa D está correta porque a afirmativa II é sustentada pela regra de alocação dinâmica da lista encadeada: os nós são criados conforme a necessidade, o que evita o superdimensionamento prévio do bloco principal de armazenamento. A afirmativa III também está correta porque, em vetor, o acesso por índice lógico tem custo constante e uniforme por posição da estrutura, ao contrário da lista encadeada, em que é necessário caminhar pelos nós até chegar à posição desejada. Já a I é falsa, porque a busca binária depende de acesso eficiente ao elemento médio, condição compatível com vetor, mas sem o mesmo desempenho em lista encadeada.
E
Errada
Está errada porque afirma que as três estão corretas, mas a I é falsa. O erro está em tratar a ordenação como condição suficiente para igualar o desempenho da busca binária, ignorando que o vetor permite acesso direto ao índice e a lista encadeada exige percurso sequencial.
Pegadinha da questão
A confusão real foi supor que, estando os elementos ordenados, a busca binária teria o mesmo desempenho em qualquer estrutura; não tem, porque o desempenho depende também do modo de acesso ao elemento médio. Outra armadilha foi ler a III como se falasse de qualquer endereço físico de memória, quando o ponto correto é o acesso por posição da estrutura.
Dica para questões semelhantes
- Para julgar desempenho de algoritmos em estruturas de dados, não basta olhar a ordenação dos elementos; verifique como a estrutura acessa uma posição intermediária.
- Se a afirmação tratar de vetor, teste primeiro se ela depende de acesso direto por índice; isso costuma distinguir vetor de lista encadeada.
- Quando o item mencionar economia de memória em lista encadeada, confirme se está falando de evitar superdimensionamento prévio, e não de ausência total de desperdício.
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Conheça nossos planos