Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — COMPERVE - UFRN 2017

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq245096
Banca
COMPERVE - UFRN
Órgão
UFRN
Ano
2017
Nível
Superior
Cargo
COMPERVE - - Engenheiro - Neuroengenharia
Uma sequência de números é um Tipo Abstrato de Dados (TAD) que representa um conjunto finito de valores ordenados, no qual um valor pode ocorrer em duplicidade. Considere as seguintes afirmações sobre a implementação de uma sequência de números utilizando arranjos e listas ligadas:I Arranjos permitem acesso a qualquer elemento da sequência com complexidade de tempo média constante.II Listas ligadas não permitem a inserção de um elemento no início da sequência com complexidade de tempo média constante.III Listas ligadas requerem que a sequência seja armazenada em uma faixa contínua de endereços de memóriaIV Arranjos não permitem a inserção de um elemento no meio da sequência com complexidade de tempo média constante.Estão corretas as afirmações
  1. AI e II.
  2. BII e III.
  3. CI e IV.
  4. DIII e IV.
Revelar gabarito e comentário

GabaritoC — I e IV.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Sequência: Arranjos vs Listas Ligadas

Gabarito: letra C — estão corretas apenas as afirmações I e IV. Arranjos (arrays) suportam acesso aleatório em tempo constante O(1), mas inserção no meio exige deslocamento de elementos (O(n)). Listas ligadas permitem inserção no início em O(1) e não requerem armazenamento contíguo.

Afirmação I — ✅ Correta

Arranjos armazenam elementos em posições consecutivas de memória, permitindo acesso direto pelo índice com complexidade O(1). Esse é um dos pontos fortes dos arrays.

Afirmação II — ❌ Incorreta

Em listas ligadas, a inserção de um novo nó no início da sequência pode ser feita em tempo constante O(1), bastando ajustar o ponteiro do novo nó para o antigo primeiro e atualizar a cabeça da lista. A afirmação diz o contrário, portanto errada.

Afirmação III — ❌ Incorreta

Listas ligadas são estruturas dinâmicas; cada nó é alocado separadamente e contém um ponteiro para o próximo. Elas não exigem que todos os nós estejam em uma faixa contínua de endereços — ao contrário, a própria característica é a alocação não contígua.

Afirmação IV — ✅ Correta

Inserir um elemento no meio de um arranjo exige deslocar todos os elementos seguintes uma posição para a direita (ou esquerda, dependendo da implementação), resultando em complexidade linear O(n) no pior caso. Logo, não é tempo constante.

Conclusão: corretas as afirmações I e IV, correspondendo à alternativa C (I e IV).

Link permanente: /questoes/qq245096