Questão de Algoritmos e Estrutura de Dados — Algoritmos — IV - UFG 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq444650
Banca
IV - UFG
Órgão
UFG
Ano
2019
Nível
Médio
Cargo
CS - - Técnico de Tecnologia da Informação
Seja uma lista linear L com n elementos (n>5), o primeiro elemento está na posição 1 (um), o segundo elemento está na posição 2 (dois), e assim por diante. As operações para L são:insere(L, elemento, k): inserir elemento em L, tal que elemento fique na posição k;remove(L, k): remover de L o elemento que está na posição k e retornar o elemento removido.Considere o pseudocódigo abaixo:para i = 1 até n, faça<instrução-X>fim-paraSe o propósito do pseudocódigo é inverter a ordem dos elementos da Lista L, então <instrução-X> pode ser:
Ainsere(F, remove(F, i), n–i)
Binsere(F, remove(F, i), n–i+1)
Cinsere(F, remove(F, i), 1)
Dinsere(F, remove(F, i), n)
Revelar gabarito e comentário▾
GabaritoC — insere(F, remove(F, i), 1)
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”.
Inversão de Lista Linear com Operações de Inserção e Remoção
Gabarito: letra C. A instrução insere(F, remove(F, i), 1) remove o elemento da posição i e o insere no início da lista. Percorrendo de i = 1 até n, ao final os elementos estarão na ordem inversa. A cada iteração, o elemento que estava na posição i (conforme a lista corrente) é movido para o início, e como i avança, o último elemento original acaba sendo inserido no início por último, gerando a inversão completa.
A banca testa a compreensão do comportamento das operações insere e remove durante a iteração, especialmente como os índices se deslocam após cada remoção.
1i=1: remove 1º, insere no início
2i=2: remove 2º, insere no início
3i=3: remove 3º, insere no início
4... até i=n
5Resultado: ordem inversa
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
insere(F, remove(F, i), n – i). Quando i = 1, remove o primeiro elemento e insere na posição n-1. Isso não produz a inversão; os deslocamentos impedem que a ordem final seja a inversa. Por exemplo, com lista [1,2,3]:
i=1: remove 1, insere na posição 2 (n-1=2) -> [2,1,3] (supondo inserção após remoção? Na verdade, após remover, a lista fica [2,3]; inserir na posição 2 coloca 1 no final: [2,3,1].
i=2: remove o elemento da posição 2 (que agora é 3) -> [2,1]; insere na posição 1? Se n-2=1? n=3, n-i=1: insere no início -> [3,2,1]. Isso parece funcionar nesse exemplo? Mas para n=4: [1,2,3,4] -> i=1: remove 1, insere pos3: [2,3,4,1]; i=2: remove pos2 (3), insere pos2: [2,4,1,3]? Não fica invertido. Portanto, a expressão não é geral.
Alternativa B — ❌ Incorreta
insere(F, remove(F, i), n – i + 1). Com n=3, i=1: remove primeiro, insere na posição 3 (final) -> [2,3,1]; i=2: remove pos2 (3), insere na posição 2 (n-i+1=2) -> [2,1,3]; i=3: remove pos3 (3), insere pos1? n-i+1=1 -> [3,2,1]. Parece funcionar para n=3? Mas testando n=4: i=1: remove 1, insere pos4 -> [2,3,4,1]; i=2: remove pos2 (3), insere pos3 -> [2,4,1,3]; i=3: remove pos3 (1), insere pos2 -> [2,1,4,3]; i=4: remove pos4 (3), insere pos1 -> [3,2,1,4]. Resultado [3,2,1,4] não invertido. Então não funciona em geral.
Alternativa C — ✅ Correta ⟵ GABARITO
insere(F, remove(F, i), 1). Remove o elemento da posição i e insere no início. A cada iteração, o elemento que está na posição i (na lista corrente) é movido para o primeiro lugar. Quando i=1, o elemento é removido e reinserido na mesma posição, não alterando a lista. A partir de i=2, os elementos vão sendo trazidos para o início na ordem inversa. Após todas as iterações, a lista fica invertida. Exemplo com [1,2,3,4]:
insere(F, remove(F, i), n). Remove da posição i e insere no final (posição n). Com n=3, [1,2,3]: i=1: remove 1, insere final -> [2,3,1]; i=2: remove pos2 (3), insere final -> [2,1,3]; i=3: remove pos3 (3), insere final -> [2,1,3]. Não inverte.
NÃO CAIA NESSA!
A banca explora a confusão entre inserir no início ou no final. O candidato pode pensar que remover do início e inserir no final (opção B) inverte, mas isso apenas rotaciona a lista. A chave é notar que inserir sempre no início desloca os elementos restantes para a direita, acumulando a ordem inversa.