Qual abordagem permite verificar se uma string S é palíndroma em tempo linear e espaço constante? Cite o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual abordagem permite verificar se uma string S é palíndroma em tempo linear e espaço constante? Cite o algoritmo e a estrutura de dados usada.
- A) Dois ponteiros (índices) nas extremidades que convergem ao centro; algoritmo O(n) tempo e O(1) espaço.
- B) Usar um loop que inverte a string e a compara com a original.
- C) Verificar a string letra por letra sem um plano de convergência dos índices.
- D) Comparar apenas os primeiros e últimos caracteres, sem verificar o meio.
- E) Utilizar uma estrutura de pilha para armazenar os caracteres da string.
✅ Resposta correta: alternativa A
Resolução passo a passo
- Um palíndromo é uma string que se lê igual de trás para frente, por exemplo 'arara'. A questão pede uma verificação em tempo linear (proporcional ao tamanho n da string) e espaço constante (memória que não cresce com n).
- A ideia é comparar os caracteres das extremidades. Coloque um ponteiro (índice) no início e outro no fim. Se os caracteres forem iguais, avance o primeiro para a direita e recue o segundo para a esquerda. Repita até que os ponteiros se cruzem ou se encontrem no meio.
- Se algum par de caracteres for diferente, a string não é palíndroma e o algoritmo para. Caso contrário, ela é palíndroma.
- Cada caractere é visitado no máximo uma vez, então o tempo é O(n). Usam-se apenas dois índices, então o espaço é O(1). A estrutura usada são os próprios índices sobre o vetor de caracteres, sem cópias.
- A alternativa B está errada, pois inverter a string cria uma cópia de tamanho n, o que usa espaço O(n). A alternativa C está errada, pois comparar letra por letra sem convergir os índices não garante a verificação eficiente nem o espaço constante. A alternativa D está errada, pois sem verificar o meio, caracteres internos diferentes passariam despercebidos. A alternativa E está errada, pois uma pilha armazena os n caracteres, usando espaço O(n).
- O gabarito oficial A está correto.
💡 Dica: Considere a definição de palíndromo e a estrutura de dados adequada.
Alternativa por alternativa
Comparando pares de caracteres com dois índices evita estruturas auxiliares e visita cada caractere no máximo uma vez, usando espaço constante.
O aluno acredita que, por ser simples e correto comparar a string com sua inversa, o método atende às restrições. Ele ignora que inverter a string exige uma cópia de tamanho n, o que viola o espaço constante.
Por que engana: O aluno pode confundir a abordagem de dois ponteiros com a inversão da string, acreditando que ambas têm a mesma eficiência.
O aluno entende que qualquer comparação letra por letra resolve o problema. Ele não percebe que, sem um plano de convergência dos índices, não há garantia de eficiência linear nem de cobrir corretamente todos os pares de posições.
O aluno supõe que, se o primeiro e o último caractere coincidem, a string é palíndroma. Ele esquece que os caracteres internos também precisam ser comparados em pares simétricos.
O aluno associa a verificação de palíndromo à inversão via pilha (LIFO), sem notar que a pilha guarda todos os n caracteres. Assim, o espaço deixa de ser constante.
Raio-X da questão
palíndromos e algoritmos
avaliacao
estrutura de dados · análise de algoritmos
Revisar algoritmos que verificam palíndromos e suas complexidades.
O aluno pode confundir a abordagem de dois ponteiros com a inversão da string, acreditando que ambas têm a mesma eficiência.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Descreva como implementar um algoritmo que verifica se uma palavra é um palíndromo. Cite as etapas e a lógica que você…
- Projete um algoritmo em pseudocódigo que verifique se uma string (dado) é palíndroma, ignorando espaços e pontuação…
- Em pseudocódigo, qual é o caso base adequado para um algoritmo recursivo que verifica se uma lista L é palíndroma (mesma…
- Considere uma lista ligada não ordenada com n elementos. Qual estratégia que usa uma estrutura auxiliar permite remover…
- Dada uma lista de dados com repetições, qual método preservando a ordem dos primeiros aparecimentos tem complexidade…
- Para implementar em um algoritmo uma tabela de símbolos com busca rápida por chaves alfanuméricas (por exemplo nomes)…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog