Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — UEM 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg617023
Banca
UEM
Órgão
UEM
Ano
2025
Nível
Superior
Cargo
Analista de Informática - Edital nº 175
Considere as seguintes afirmativas sobre estruturas de dados:I. Um arranjo é caracterizado por alocação contígua e acesso indexado em tempo constante.II. Uma lista com encadeamento simples permite a inserção e a remoção de itens em qualquer posição de forma eficiente.III. As formas mais comuns para tratamento de colisões em tabelas de dispersão são o encadeamento separado e o endereçamento aberto.IV. Os arranjos e as listas encadeadas são exemplos de estruturas de dados lineares, em que cada elemento tem, no máximo, um predecessor e um sucessor.Estão corretas
Aapenas as afirmativas I, II e IV.
Bapenas as afirmativas III e IV.
Capenas as afirmativas I e III.
Dapenas as afirmativas I, III e IV.
Eapenas as afirmativas II e IV.
Revelar gabarito e comentário▾
GabaritoD — apenas as afirmativas I, III 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”.
Estruturas de Dados: Arranjos, Listas e Tabelas de Dispersão
Gabarito: letra D. Estão corretas apenas as afirmativas I, III e IV. A afirmativa II é falsa porque, em uma lista com encadeamento simples, a inserção e a remoção em qualquer posição (que não seja a primeira) exige percorrer a lista até o ponto desejado, resultando em complexidade O(n) – portanto não é eficiente para posições arbitrárias.
Afirmativa
Status
Justificativa
I – Arranjo: alocação contígua e acesso indexado O(1)
Correta
Armazenamento em posições consecutivas de memória com acesso direto por índice em tempo constante.
II – Lista encadeada simples: inserção/remoção eficiente em qualquer posição
Incorreta
A eficiência O(1) só ocorre no início ou quando já se tem ponteiro para o nó; para posição arbitrária, é necessário percorrer a lista (O(n)).
III – Tratamento de colisões em tabelas hash: encadeamento separado e endereçamento aberto
Correta
São as duas técnicas clássicas: encadeamento separado (listas nas posições) e endereçamento aberto (sondagem linear, quadrática, duplo hash).
IV – Arranjos e listas encadeadas: estruturas lineares (máx. 1 predecessor e 1 sucessor)
Correta
Ambas mantêm relação de ordem sequencial; arrays por índices, listas por ponteiros.
Análise das afirmativas
✅ Afirmativa I – Correta
Um arranjo (array) armazena elementos em posições consecutivas de memória (alocação contígua) e permite acesso direto a qualquer posição por meio de um índice, com tempo constante O(1). É uma das propriedades fundamentais dos arrays.
❌ Afirmativa II – Incorreta
A afirmação é verdadeira apenas para operações no início da lista (ou quando se já tem um ponteiro para o nó). Para inserir ou remover em uma posição arbitrária, é necessário percorrer os nós até encontrar o local desejado, o que é O(n) no pior caso. Portanto, a expressão "em qualquer posição de forma eficiente" é uma generalização indevida.
NÃO CAIA NESSA!
O examinador explora a confusão entre a eficiência da lista encadeada para operações na extremidade (onde é O(1)) e a ineficiência para posições internas (O(n)). O aluno pode achar que a inserção/remoção é sempre rápida por não exigir deslocamento de elementos, mas esquece que é preciso encontrar a posição primeiro.
✅ Afirmativa III – Correta
As duas técnicas clássicas de tratamento de colisões em tabelas hash (tabelas de dispersão) são:
Encadeamento separado: cada posição da tabela contém uma lista encadeada com todos os elementos que colidiram.
Endereçamento aberto: quando ocorre colisão, busca-se outra posição livre na própria tabela (ex.: sondagem linear, quadrática, duplo hash).
Ambas são amplamente ensinadas e utilizadas.
✅ Afirmativa IV – Correta
Tanto arrays quanto listas encadeadas são estruturas lineares, onde cada elemento possui, no máximo, um predecessor e um sucessor (relação de ordem sequencial). Em arrays, a linearidade é implícita pelos índices; em listas, ela é explicitamente mantida por ponteiros.
PEGA ESSA DICA!
Ao julgar afirmações sobre eficiência de operações em listas encadeadas, lembre-se de que localizar o nó para inserir/remover é a etapa custosa (O(n)), a menos que você já tenha uma referência ao nó ou esteja operando no início.
Conclusão: Corretas I, III e IV → gabarito letra D.