Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-MS 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq508297
Banca
IF-MS
Órgão
IF-MS
Ano
2019
Nível
Médio
Cargo
Técnico em Tecnologia da Informação
Considere as seguintes afirmações sobre algoritmos e estruturas de dados:I. Filas são estruturas do tipo FIFO (First In First Out).II. A inserção no fim de uma lista duplamente encadeada e não ordenada é realizada em O(n).O tempo de execução do algoritmo quicksort no pior caso é O(n² ).Assinale a opção CORRETA:
AApenas a afirmação I é verdadeira.
BApenas a afirmação II é verdadeira.
CApenas a afirmação III é verdadeira.
DApenas as afirmações I e III são verdadeiras.
EAs afirmações I, II e III são verdadeiras.
Revelar gabarito e comentário▾
GabaritoD — Apenas as afirmações I e III são verdadeiras.
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”.
Análise das afirmações sobre algoritmos e estruturas de dados
Gabarito: letra D. Apenas as afirmações I e III são verdadeiras. Filas seguem o princípio FIFO (I), e o quicksort no pior caso tem complexidade O(n²) (III). A afirmação II está incorreta, pois a inserção no fim de uma lista duplamente encadeada, quando se mantém referência ao último elemento, é O(1), e não O(n).
Afirmação I — ✅ Correta
Filas são estruturas de dados que obedecem ao princípio FIFO (First In, First Out). O primeiro elemento inserido é o primeiro a ser removido. Conceito fundamental e universalmente aceito.
Afirmação II — ❌ Incorreta
Em uma lista duplamente encadeada não ordenada, a inserção no fim pode ser realizada em O(1) se a implementação mantiver um ponteiro para o último nó (tail). Mesmo sem tail, a operação seria O(n), mas o padrão em estruturas de dados é considerar que a lista possui referência para o fim, permitindo inserção em tempo constante. Portanto, afirmar que é O(n) é incorreto. A complexidade correta é O(1) para inserção no fim com tail.
Afirmação III — ✅ Correta
O algoritmo quicksort, no pior caso, tem complexidade de tempo O(n²). Isso ocorre quando o pivô escolhido é sempre o maior ou o menor elemento, resultando em partições extremamente desbalanceadas. Conforme a descrição do algoritmo:
O pior caso de particionamento ocorre quando o elemento pivô divide a lista de forma desbalanceada... o algoritmo terá tempo de execução igual a θ(n²).
Portanto, a afirmação está correta.
Conclusão: São verdadeiras apenas as afirmações I e III, correspondendo à alternativa D.