Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FCC 2018
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
fc047613
Banca
FCC
Órgão
SABESP
Ano
2018
Cargo
Analista de Gestão - Sistemas
Considere as afirmativas, sabendo que N se refere ao número de elementos da estrutura de dados. É correto afirmar:
ANo pior caso do método de pesquisa sequencial são realizadas N comparações para se localizar um elemento e no melhor caso, quando o elemento não pertence ao vetor, é realizada 0 comparação.
BA quantidade de comparações que o método de pesquisa binária realiza é de ordem de complexidade logarítmica. No entanto, este método não pode ser aplicado quando o vetor está ordenado em ordem decrescente, mesmo se o código for readequado.
CUm software pode ter várias sub-rotinas ativas durante sua execução. Para fazer o seu controle é utilizada uma fila de execução. Nesta fila, quem invoca a sub-rotina insere nela o endereço de retorno. Quando termina sua execução, a sub-rotina invocada remove o endereço de retorno da fila, desviando a execução para aquele endereço.
DO método de seleção ou selection sort, conhecido como ordenação por flutuação, é um dos mais eficientes e simples. É baseado na estratégia de percorrer o vetor N vezes e, a cada passagem, ir fazendo o maior elemento flutuar para o final do vetor, onde o maior elemento da sequência deve estar.
EEm um Sistema Operacional monoprocessado, uma política de escalonamento por prioridade pode ser implementada utilizando um valor de prioridade para cada processo e para cada prioridade deve existir uma fila associada. Processos de mesma prioridade são escalonados de acordo com a política FIFO.
Revelar gabarito e comentário▾
GabaritoE — Em um Sistema Operacional monoprocessado, uma política de escalonamento por prioridade pode ser implementada utilizando um valor de prioridade para cada processo e para cada prioridade deve existir uma fila associada. Processos de mesma prioridade são escalonados de acordo com a política FIFO.
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: letra E. Apenas a alternativa E descreve corretamente a implementação de escalonamento por prioridade em sistemas monoprocessados, com filas FIFO por nível de prioridade. As demais contêm erros conceituais: em A, o melhor caso da busca sequencial exige ao menos 1 comparação (elemento presente na primeira posição); em B, a pesquisa binária pode ser adaptada para vetores decrescentes; em C, o controle de sub-rotinas utiliza uma pilha (LIFO), não uma fila; em D, a descrição corresponde ao bubble sort, não ao selection sort.
A banca testa conceitos clássicos de estrutura de dados e algoritmos, com foco em distinguir procedimentos semelhantes. É essencial dominar as definições e comportamentos de cada método.
Alternativa
Afirmação
Correção
Erro Conceitual
A
No pior caso da busca sequencial, N comparações; no melhor caso (elemento ausente), 0 comparações.
❌ Incorreta
Melhor caso é elemento na 1ª posição (1 comparação); elemento ausente exige N comparações (pior caso).
B
Busca binária tem complexidade O(log N); não pode ser aplicada em vetor decrescente, mesmo com adaptação.
❌ Incorreta
Pode ser adaptada para ordem decrescente ajustando a lógica de comparação.
C
Controle de sub-rotinas usa fila (FIFO); endereço de retorno é inserido na fila na chamada e removido no retorno.
❌ Incorreta
Usa pilha (LIFO), não fila.
D
Selection sort é conhecido como ordenação por flutuação; percorre o vetor N vezes, fazendo o maior elemento flutuar para o final.
❌ Incorreta
Descrição corresponde ao bubble sort, não ao selection sort.
E
Escalonamento por prioridade em sistema monoprocessado: fila FIFO por nível de prioridade.
✅ Correta
Descrição correta da implementação.
Alternativa A — ❌ Incorreta
Afirma que, no melhor caso, quando o elemento não pertence ao vetor, são realizadas 0 comparações. Na busca sequencial, mesmo para elemento ausente, é necessário percorrer todo o vetor até o fim, realizando N comparações (cada elemento é verificado uma vez). O melhor caso ocorre quando o elemento está na primeira posição, resultando em 1 comparação. Portanto, a afirmação está errada tanto no melhor caso (deveria ser 1, não 0) quanto ao confundir ausência com melhor caso.
Alternativa B — ❌ Incorreta
A pesquisa binária tem complexidade O(log N), o que está correto. Porém, a afirmação de que "não pode ser aplicada quando o vetor está ordenado em ordem decrescente, mesmo se o código for readequado" é falsa. A pesquisa binária exige que o vetor esteja ordenado (crescente ou decrescente), desde que a lógica de comparação seja ajustada para a ordem vigente. Portanto, é plenamente aplicável com pequena adaptação no código.
Alternativa C — ❌ Incorreta
Descreve o mecanismo de chamada de sub-rotinas utilizando uma fila (FIFO). Na realidade, sub-rotinas (funções, procedimentos) usam uma pilha (LIFO) — a call stack. O endereço de retorno é empilhado (push) na chamada e desempilhado (pop) no retorno, não inserido/removido de fila. A fila seria inadequada, pois a última sub-rotina chamada deve ser a primeira a retornar (LIFO).
Alternativa D — ❌ Incorreta
O selection sort não é conhecido como "ordenação por flutuação". O método descrito — percorrer o vetor N vezes fazendo o maior elemento "flutuar" para o final — corresponde ao bubble sort. No selection sort, a cada passagem seleciona-se o menor (ou maior) elemento e troca-se com o primeiro da parte não ordenada, sem movimento gradual de "flutuação". Além disso, o selection sort não é dos mais eficientes (complexidade O(N²) no pior caso, assim como o bubble sort).
Alternativa E — ✅ Correta ⟵ GABARITO
Em sistemas operacionais monoprocessados, o escalonamento por prioridade pode ser implementado com múltiplas filas, uma para cada nível de prioridade. Processos de mesma prioridade são tratados de forma FIFO (first-in, first-out), garantindo ordem de chegada. Essa é uma abordagem clássica, descrita em livros de sistemas operacionais.
NÃO CAIA NESSA!
A banca mistura conceitos intencionalmente: na C, troca pilha por fila; na D, troca selection sort por bubble sort. Fique atento às definições e palavras-chave como "flutuação" (bubble) e "seleção" (selection).