Questões de Concurso sobre Bubble sort (2 a 2)

Um professor está precisando ordenar os seus alunos pelas notas obtidas na última avaliação. Considerando que são muitos alunos distribuídos aleatoriamente e que a menor nota foi zero e a maior foi dez, qual o algoritmo de ordenação apropriado que o professor deve utilizar para essa tarefa?

Um algoritmo de ordenação é estável quando preserva a ordem relativa de elementos com chaves iguais. São exemplos de algoritmos de ordenação estáveis:

A Secretaria de Saúde de determinado município desenvolveu um sistema para organizar a fila de pacientes em uma unidade de pronto atendimento. O sistema precisa ordenar os registros com base na prioridade de atendimento (alta, média ou baixa) e, dentro de cada nível de prioridade, ordenar os pacientes de acordo com a data e hora de chegada. Durante os testes do sistema, a equipe de TI implementou diferentes algoritmos de ordenação, analisando suas características e desempenho.

Cada um desses algoritmos foi descrito pelos programadores da seguinte forma:

• Implementação 1: o algoritmo percorre repetidamente a lista, comparando e trocando elementos adjacentes até que toda a lista esteja ordenada.

• Implementação 2: a lista é dividida em duas metades recursivamente, e as metades ordenadas são combinadas para formar a lista final.

• Implementação 3: o algoritmo constrói a lista ordenada elemento por elemento, inserindo cada novo item na posição correta.

• Implementação 4: uma estrutura de heap é utilizada para armazenar os elementos, garantindo que o maior ou menor elemento seja extraído de forma eficiente.

Com base nas descrições anteriores, assinale a alternativa que relaciona corretamente as implementações aos algoritmos de ordenação.

Observe o código Python a seguir.

A partir do código apresentado, que implementa um algoritmo de ordenação, a função metodo_ordenacao que implementa o algoritmo é

Considere o seguinte código Python que implementa um método de ordenação:

def ordenar(lista):

n = len(lista)

for i in range(n):

trocado = False

for j in range(0, n - i - 1):

if lista[j] > lista[j + 1]:

lista[j], lista[j + 1] = lista[j + 1], lista[j]

trocado = True

if not trocado:

break

return lista

# Exemplo de uso

numeros = [64, 34, 25, 12, 22, 11, 90]

print(ordenar(numeros))

Qual método de ordenação é implementado no código acima?

vetor = [11, 4, 7, 2, 6]

n = tamanho(vetor)

para (i de 0 até (n ‑ 2)) faça

para (j de 0 até (n ‑ 2 ‑ i)) faça

se vetor[j] > vetor[j + 1] então

temp = vetor[j]

vetor[j] = vetor[j + 1]

vetor[j + 1] = temp

fim se

fim para

fim para

escreva(vetor)

Com base nesse algoritmo, desenvolvido em pseudocódigo, assinale a opção que apresenta corretamente o resultado de “escreva(vetor)”.

Em lógica de programação, um algoritmo é uma sequência finita de instruções bem definidas e não ambíguas, projetada para resolver um problema específico. Para que um algoritmo seja considerado correto e eficiente, ele deve processar dados de entrada e produzir uma saída desejada. No contexto de estruturas de dados, os algoritmos de ordenação são usados para organizar uma coleção de itens em uma ordem específica. Qual é a principal característica do algoritmo de ordenação conhecido como "Bubble Sort" (Ordenação por Bolha)?

O Bubble Sort é um algoritmo simples de ordenação que percorre repetidamente a lista, compara elementos adjacentes e os troca se estiverem na ordem errada. Esse processo é repetido até que a lista esteja ordenada. Considerando essas informações e o uso do algoritmo Bubble Sort, qual das seguintes afirmações é verdadeira?

A seguinte figura apresenta um algoritmo de ordenação da tabela L, de n elementos, segundo o seu campo chave. Assinale a alternativa que descreve o método de ordenação.

Existe a necessidade de ordenar dados em alguns contextos, demandando a aplicação de algoritmos de ordenação específicos, como o Bubble Sort, sobre o qual é válido afirmar que:

Um analista tem disponíveis quatro algoritmos de ordenação: inserção, mergesort, heapsort e bubblesort. Como o analista não tem conhecimento sobre o tamanho do conjunto de dados e as suas condições de ordenação inicial, resolve utilizar como critério de escolha a menor complexidade do pior caso.

Considerando-se esse critério de menor complexidade do pior caso, quais seriam os dois algoritmos que o analista deve utilizar para fazer uma primeira seleção?

Medir a complexidade dos métodos de ordenação é fundamental para entender o desempenho desses algoritmos e poder fazer escolhas adequadas dependendo do contexto do problema. Qual método de ordenação o pior caso tem a mesma complexidade do método Quick Sort no pior caso?

Considere o seguinte fragmento de código, escrito na linguagem java, baseado em GEEKS FOR GEEKS (2022):

(GEEKS FOR GEEKS. Java Program for Bitonic Sort. Noida: Geeks for Geeks, 2022. Disponível em: https://www.geeksforgeeks.org/java-program-for-bitonic-sort/. Acesso em: 14 abr. 2024.)

Escolha a opção que indique o resultado obtido após a sua execução na última versão oficial do Java.

Relacione adequadamente as colunas a seguir sobre os métodos de ordenação à sua descrição correspondente.

1. Bubble Sort.

2. Merge Sort.

3. Quick Sort.

4. Selection Sort.

5. Insertion Sort.

( ) Divide a lista em sublistas menores; ordena essas sublistas e as mescla para obter a lista ordenada.

( ) Algoritmo de comparação que percorre repetidamente a lista; compara elementos adjacentes e troca-os se estiverem na ordem errada.

( ) Divide a lista em duas partes; ordena-as individualmente e combina-as para obter a lista ordenada.

( ) Algoritmo que seleciona iterativamente o elemento mínimo da lista e coloca-o na posição correta.

( ) Algoritmo de comparação que escolhe um elemento como pivô; divide a lista em dois subconjuntos e ordena-os recursivamente.

A sequência está correta em

Os algoritmos de ordenação desempenham um papel crucial em ciência da computação, permitindo organizar elementos de uma lista em uma ordem específica, como crescente ou decrescente. Um desses algoritmos funciona comparando repetidamente pares adjacentes de elementos e trocando-os se estiverem na ordem errada, até que toda a lista esteja ordenada. Sabendo disso, assinale a alternativa que apresenta CORRETAMENTE esse algoritmo de ordenação.

O analista José precisa escolher entre dois algoritmos, Abusca e Cbusca. José sabe que, sendo N o tamanho da entrada do algoritmo, Abusca requer 2^N + log₂(N) operações para ser executado. Já o Cbusca requer N⁴ + N operações para ser executado. José determinou, na notação O-grande, a complexidade de tempo no pior caso para cada algoritmo e, por fim, deve escolher o algoritmo que apresenta a menor ordem de complexidade no pior caso.

José deve escolher o algoritmo:

O Bubble Sort, também conhecido como método bolha, é um algoritmo utilizado para organizar uma sequência de números ou outros elementos em ordem crescente ou decrescente. A implementação percorre a sequência de itens ordenáveis e faz a troca, quando necessária. Nesse sentido, para ordenar, de modo crescente, o array {11, 5, 7, 3, 2, 1}, utilizando o método bolha, serão necessárias

Um programador quer ordenar a lista [5, 4, 3]. Qual alternativa representa todas as situações dessa lista até a sua completa ordenação utilizando o método Bubble Sort?

Analise as assertivas abaixo sobre notação big-O e complexidade de algoritmos, observando as afirmações sobre algoritmos de ordenamento:

I. O algoritmo quicksort tem uma complexidade no caso médio de Θ(nlog(n)).

II. O algoritmo mergesort tem uma complexidade no pior caso de O(n log(n)).

III. O algoritmo bubble sort tem uma complexidade no melhor caso de Ω(n).

IV. O algoritmo selection sort tem uma complexidade no melhor caso de Ω(n).

Quais estão corretas?

Analise as assertivas abaixo:

I. Uma pilha é um tipo abstrato de dados que, quando implementado, opera utilizando a estratégia LIFO (Last In First Out), enquanto uma fila opera utilizando a estratégia FIFO (First In First Out).

II. O algoritmo de Dijkstra resolve o problema de caminhos mínimos de fonte única em grafos dirigidos de forma gulosa.

III. Bubblesort é um algoritmo de ordenação que funciona permutando repetidamente elementos adjacentes que estão fora de ordem.

Quais estão corretas?