Questão FC266053
O seguinte pseudocódigo implementa a operação chamada de “remove caracteres” que recebe uma string (variável chamada “texto”) e um char (variável chamada “letra”). A cada ocorrênci
Algoritmos e Lógica de Programação
IDECAN · 2019
O seguinte pseudocódigo implementa a operação chamada de “remove caracteres” que recebe uma string (variável chamada “texto”) e um char (variável chamada “letra”). A cada ocorrência de “letra” na string “texto”, o caractere anterior é removido, assim como a própria “letra”. Veja um exemplo após a aplicação da operação “remove caracteres” na string “Aman#ha tem p#rova”, onde a variável letra tem valor ‘#’: “Amaha tem rova”. O pseudocódigo abaixo usa uma estrutura de dados (chamada de “EstruturaDados” no pseudocódigo abaixo), onde utilizamos as operações de remoção (removeED), inserção (adicionarED) e tamanho (tamanhoED) dessa estrutura de dados, onde a operação de remoção remove e retorna um elemento da estrutura de dados, a operação de inserção adiciona um elemento e a operação de tamanho retorna quantos elementos estão na estrutura de dados.
EstruturaDados ed;
Para (cada i = 0 até n - 1){ //n é a variável com o tamanho da
string texto
Se (texto[i] == letra) removeED(ed);
Senão adicionarED(ed, texto[i]);
}
i = tamanhoED(ed);
Criar uma nova variável string chamada de textoAlterado de
tamanho i;
Enquanto (i > 0){
i--;
textoAlterado[i] = removeED(ed);
}
Assinale a alternativa que indica qual deve ser a estrutura de dados utilizada no lugar de “EstruturaDados” para que o pseudocódigo acima, caso implementado em uma linguagem de programação, execute corretamente a operação “remove caracteres”.
- Fila.
- Heap.
- Pilha.
- Árvore AVL.
- Árvore Rubro Negra.
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
A estrutura correta é a Pilha. Ela opera em LIFO (Last In, First Out), ou seja, o último caractere inserido é o primeiro a ser removido — comportamento necessário para “apagar” o caractere imediatamente anterior quando aparece a ocorrência de letra.
No pseudocódigo, adicionarED equivale ao push e removeED ao pop; tamanhoED retorna a quantidade de elementos na pilha. Assim, ao percorrer a string, cada caractere normal é empilhado e, ao encontrar letra, executa-se um pop para retirar o anterior e descarta-se a própria letra.
Se a pilha estiver vazia e surgir letra, um pop não remove nada — isso preserva o comportamento correto sem causar erro.
No final, o código retira da pilha (pop) os caracteres para construir a string resultante em ordem correta, porque a pilha inverte a ordem de inserção conforme desejado.
Complexidade: operação linear \(O(n)\), pois cada caractere é empilhado ou provoca um desempilhamento constante.
Conteúdo do catálogo FC Concursos · Atualizado em