Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FADE - UFPE 2023
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq866891
Banca
FADE - UFPE
Órgão
UFPE
Ano
2023
Nível
Superior
Cargo
FADE - - Analista de Tecnologia da Informação - Área: Sistemas
Considere a implementação de uma fila (FIFO) de forma estática (array) com indexação circular, iniciando em 0 e finalizando no índice N-1, onde N é o tamanho do array. Seja Ins o índice da posição livre na qual a próxima inserção na fila deve ocorrer; seja Prim o índice do elemento mais antigo a permanecer na fila; e seja (A MOD B) o resto da divisão inteira de A por B. Com base nesses dados, analise as afirmações a seguir.1) Para inserção, caso a fila não esteja cheia, atribuímos o elemento ao array na posição Ins e, em seguida, atribuímos a Ins o valor de (Ins MOD N)+.2) Para deleção, caso a fila não esteja vazia, atribuímos a Prim o valor de ((Prim+1) MOD N).3) Se Prim=Ins, podemos concluir que a fila está vazia.4) Se Prim=((Ins+1) MOD N), podemos concluir que a fila está cheia.Estão corretas:
A1 e 2, apenas.
B3 e 4, apenas.
C1, 2 e 3, apenas.
D2, 3 e 4, apenas.
E1, 2, 3 e 4.
Revelar gabarito e comentário▾
GabaritoD — 2, 3 e 4, apenas.
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”.
Gabarito: D (2, 3 e 4 estão corretas). A implementação padrão de fila circular com array usa índices Ins (próxima inserção) e Prim (elemento mais antigo). Inicialmente Ins = Prim = 0. A condição de fila vazia é Prim == Ins, e a de fila cheia é (Ins+1) MOD N == Prim (um espaço reservado). A deleção incrementa Prim circularmente com (Prim+1) MOD N. A afirmação 1 está incorreta pois sua fórmula de atualização é inválida.
A questão testa o conhecimento do gerenciamento circular de filas estáticas. Vamos analisar cada afirmação:
Afirmação 1 — ❌ Incorreta
"Para inserção, caso a fila não esteja cheia, atribuímos o elemento ao array na posição Ins e, em seguida, atribuímos a Ins o valor de (Ins MOD N)+."
A fórmula apresentada (Ins MOD N)+ é incompleta ou errada. Na implementação correta, após inserir em Ins, o índice deve avançar circularmente: Ins = (Ins + 1) MOD N. O texto (Ins MOD N)+ não define uma operação válida (falta o incremento dentro do módulo). Mesmo que se interprete como (Ins MOD N) + 1, isso deixaria Ins fora do intervalo [0, N-1] quando Ins = N-1 (resultaria em N). Portanto, a afirmação está incorreta.
Afirmação 2 — ✅ Correta
"Para deleção, caso a fila não esteja vazia, atribuímos a Prim o valor de ((Prim+1) MOD N)."
Correto. Ao remover o elemento apontado por Prim, o índice do elemento mais antigo avança para a próxima posição circular, ou seja, Prim = (Prim + 1) % N. Essa é a operação padrão de dequeue em uma fila circular.
Afirmação 3 — ✅ Correta
"Se Prim=Ins, podemos concluir que a fila está vazia."
Correto. Na condição inicial (Prim = Ins = 0) e sempre que todos os elementos forem removidos, os dois índices se igualam, indicando fila vazia. Embora essa igualdade também ocorra quando a fila está cheia em algumas implementações que usam contador, a condição clássica (sem contador) adota Prim = Ins como vazia e (Ins+1) % N = Prim como cheia. A afirmação está de acordo com essa abordagem.
Afirmação 4 — ✅ Correta
"Se Prim=((Ins+1) MOD N), podemos concluir que a fila está cheia."
Correto. Para distinguir cheia de vazia sem contador, reserva-se uma posição do array. Assim, a fila está cheia quando o próximo índice de inserção (Ins+1) MOD N coincide com Prim (o elemento mais antigo). Essa é a condição universal de fila cheia em implementações circulares.
Conclusão: Estão corretas apenas as afirmações 2, 3 e 4, correspondendo à alternativa D.
Afirmação
Análise
Correta?
1) Ins = (Ins MOD N)+
Fórmula inválida/incompleta; o correto é Ins = (Ins + 1) MOD N
❌
2) Prim = ((Prim+1) MOD N)
Operação padrão de deleção em fila circular
✅
3) Prim == Ins → fila vazia
Condição clássica de fila vazia (sem contador)
✅
4) Prim == ((Ins+1) MOD N) → fila cheia
Condição clássica de fila cheia (um espaço reservado)
✅
Fila circular estática: Índices (Ins (próxima inserção), Prim (elemento mais antigo)); Condições (Vazia: Prim == Ins, Cheia: (Ins+1) % N == Prim); Operações (Inserir: Ins = (Ins+1) % N, Deletar: Prim = (Prim+1) % N)
NÃO CAIA NESSA!
A afirmação 1 usa uma sintaxe truncada (Ins MOD N)+ que parece uma tentativa de escrever (Ins+1) MOD N. Muitos candidatos podem assumir que se trata de um erro de digitação e considerá-la correta, mas a redação literal é inválida. A banca força o candidato a ler com atenção a expressão exata.
Gabarito: letra D — corretas as afirmativas 2, 3 e 4.