Questão de Algoritmos e Estrutura de Dados — Algoritmos — IDCAP 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg225408
Banca
IDCAP
Órgão
Prefeitura de Ibirataia - BA
Ano
2024
Nível
Superior
Cargo
Analista de Sistemas
Considere as afirmativas abaixo sobre estruturas de dados homogêneas e heterogêneas, incluindo vetores e matrizes, registros, listas, filas, pilhas e árvores, métodos de busca e ordenação, e recursividade. Sobre o assunto, julgue as seguintes afirmações como verdadeiras (V) ou falsas (F):(__)A complexidade de tempo do algoritmo de ordenação Bubble Sort no pior caso é O(n²).(__)As listas ligadas permitem inserções e remoções eficientes em qualquer posição, mas ocupam mais memória devido ao armazenamento de ponteiros.(__)A recursividade é uma técnica de programação onde uma função faz chamadas a si mesma, podendo ser substituída por uma estrutura de repetição em qualquer situação.Assinale a alternativa cuja respectiva ordem de julgamento esteja correta:
AV − V − V.
BF − V − V.
CV − F − F.
DV − V − F.
Revelar gabarito e comentário▾
GabaritoD — V − V − F.
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”.
Algoritmos e Estruturas de Dados
Gabarito: D (V – V – F). A primeira afirmativa está correta: o Bubble Sort tem complexidade O(n²) no pior caso. A segunda está correta: listas ligadas permitem inserções/remoções eficientes em posições conhecidas e consomem mais memória pelos ponteiros. A terceira é falsa: nem toda recursão pode ser substituída por iteração de forma direta em qualquer situação (por exemplo, algoritmos que exigem retrocesso complexo).
Afirmativa
Julgamento
Justificativa
A complexidade de tempo do algoritmo de ordenação Bubble Sort no pior caso é O(n²).
V
O Bubble Sort, no pior caso, realiza aproximadamente n²/2 comparações e trocas, resultando em complexidade O(n²).
As listas ligadas permitem inserções e remoções eficientes em qualquer posição, mas ocupam mais memória devido ao armazenamento de ponteiros.
V
Inserções e remoções em posições conhecidas têm complexidade O(1), sem necessidade de deslocamento de elementos, porém cada nó armazena ponteiros adicionais.
A recursividade é uma técnica de programação onde uma função faz chamadas a si mesma, podendo ser substituída por uma estrutura de repetição em qualquer situação.
F
Embora toda recursão possa teoricamente ser convertida em iteração com pilha explícita, nem sempre a substituição é simples ou direta; o termo "em qualquer situação" torna a afirmação falsa.
Afirmativa 1 — ✅ Verdadeira
A complexidade de tempo do Bubble Sort no pior caso é O(n²). Isso é fato clássico de análise de algoritmos: o algoritmo percorre o vetor n vezes, comparando e trocando elementos adjacentes, resultando em aproximadamente n²/2 comparações.
Afirmativa 2 — ✅ Verdadeira
Listas ligadas (listas encadeadas) permitem inserir e remover elementos com complexidade O(1) quando já se tem referência ao nó anterior (para listas simplesmente encadeadas) ou ao próprio nó (para listas duplamente encadeadas). Não há necessidade de deslocar elementos como em arrays. Em contrapartida, cada nó armazena um ou mais ponteiros, aumentando o consumo de memória.
Afirmativa 3 — ❌ Falsa
A recursividade é uma técnica em que uma função chama a si mesma, mas a afirmação de que ela pode ser substituída por uma estrutura de repetição em qualquer situação é exagerada. Embora toda recursão teoricamente possa ser convertida em iteração com o uso de uma pilha explícita, nem sempre essa substituição é simples ou direta; há casos em que a versão iterativa é muito mais complexa ou pouco intuitiva. Portanto, o trecho "em qualquer situação" torna a afirmativa falsa.
Alternativa A — ❌ Incorreta
Sequência V – V – V. A terceira afirmativa é falsa, portanto a sequência não pode ser V V V. (Correto: V – V – F).
Alternativa B — ❌ Incorreta
Sequência F – V – V. A primeira afirmativa é verdadeira, não falsa. Logo, a sequência está errada.
Alternativa C — ❌ Incorreta
Sequência V – F – F. A segunda afirmativa é verdadeira, mas a alternativa marca F, e a terceira é falsa (marca F, mas deveria ser V – V – F).
Alternativa D — ✅ Correta ⟵ GABARITO
Sequência V – V – F. Exatamente o julgamento correto: verdadeiro (Bubble Sort O(n²)), verdadeiro (listas ligadas eficientes e com maior memória), falso (recursividade nem sempre substituível por iteração).
NÃO CAIA NESSA!
Em questões de complexidade, decore os casos clássicos: Bubble, Insertion e Selection Sort têm O(n²) no pior caso; Merge, Heap e Quick (médio) têm O(n log n). Para listas ligadas, lembre-se da troca "inserção/remoção eficiente vs. mais memória de ponteiros". Na recursão, o termo "qualquer situação" é um exagero típico de pegadinha.