Questões de Concurso sobre Métodos de ordenação

Seja um array de inteiros de 32 bits com 10.000 elementos, gerados e posicionados aleatoriamente nesse array.

Nessas condições, qual algoritmo irá ordenar esse array com um consumo de tempo, em seu caso médio, proporcional ao consumo de tempo do pior caso do Quick sort?

Bárbara implementa um algoritmo de ordenação estável cuja complexidade temporal média O_T pertence a O(n.logn) e cuja complexidade espacial O_E pertence a O(n), sendo n o tamanho do vetor a ser ordenado.

O algoritmo implementado é o:

Para ordenar um vetor de 10 elementos usando-se a ordenação por seleção, a quantidade de comparações necessárias é igual a

O quicksort é um dos algoritmos mais famosos de ordenação, o qual, por sua vez, é um tema bastante estudado na informática. Mas, qual a vantagem do quicksort afinal?

Assinale a alternativa que contém uma descrição correta sobre o algoritmo.

Neste algoritmo de ordenação a Ideia básica do algoritmo é:

- Compare o primeiro elemento com o segundo. Se estiverem desordenados, então efetue a troca de posição.

- Compare o segundo elemento com o terceiro e efetue a troca de posição, se necessário;

- Repita a operação anterior até que o penúltimo elemento seja comparado ao último. Ao final desta repetição, o elemento de maior valor estará em sua posição correta, a n-ésima posição do vetor;

- Continue a ordenação posicionando o segundo maior elemento, o terceiro,... até que todo o vetor esteja ordenado.

Este algoritmo é chamado de:

Sobre os algoritmos para ordenação de dados, é correto afirmar que o

Considere as seguintes definições relacionadas a algoritmos de ordenação e assinale a alternativa que identifica corretamente as três definições, considerando sua ordem.

1. O algoritmo consiste em percorrer o vetor de itens desordenados da esquerda para a direita, ordenando um item por vez. A cada passo, o item não ordenado é comparado aos itens à sua esquerda (os quais já estão ordenados) de modo a encontrar em qual posição ele deve ser colocado. Esses passos são repetidos para cada um dos itens não ordenados restantes. O algoritmo termina quando o último item do vetor é colocado na posição correta.

2. O algoritmo divide logicamente o vetor em duas partições: uma partição contendo itens ordenados, que é construída da esquerda para a direita na frente (esquerda) do vetor, e uma partição contendo itens restantes não ordenados que ocupam o resto do vetor. Inicialmente, a partição ordenada está vazia e a partição não ordenada é o próprio vetor de entrada. Em cada passo, o algoritmo encontra o menor item na partição não ordenada, trocando-o com o item não ordenado mais à esquerda da partição (colocando-o, portanto, em ordem). Então, o limite lógico entre as partições ordenada e não ordenada é incrementado em uma posição e os passos anteriores são repetidos. O algoritmo termina quando resta apenas um item a ser ordenado.

3. O algoritmo divide o problema em partes menores, resolvendo cada parte separadamente e juntando os resultados posteriormente. O vetor é dividido em duas partes iguais, sendo cada uma delas dividida em duas partes, e assim por diante, até restarem partes com um ou dois itens, cuja ordenação é trivial. Para juntar pares de partes ordenadas, os dois primeiros itens de cada parte são separados e o menor deles é selecionado e posicionado como primeiro elemento. Em seguida, os menores entre os restantes são comparados e posicionados e assim se prossegue até que todos os elementos tenham sido juntados. O procedimento é repetido até que todas as partes tenham sido tratadas.

Associe a coluna I à coluna II, em relação aos algoritmos de pesquisa e classificação.

COLUNA I

1. Pesquisa binária

2. Classificação por borbulhamento

3. Classificação por intercalação

COLUNA II

( ) O(n²)

( ) O(log n)

( ) O(n log n)

Assinale a alternativa que apresenta a sequência correta da coluna II.

Algoritmos de ordenação são técnicas fundamentais na área da computação e são utilizados para organizar e ordenar coleções de dados, como listas ou arrays, de acordo com critérios específicos. Esses algoritmos têm uma ampla gama de aplicações em sistemas computacionais e são essenciais para a eficiência e eficácia de processos, nas mais diversas áreas do mundo do trabalho. Considere o algoritmo de ordenação ilustrado no pseudocódigo abaixo:

função sort(lista, esquerda, direita)

se esquerda < direita

pivo_index = particionar(lista, esquerda, direita)

sort(lista, esquerda, pivo _index - 1)

sort(lista, pivo_index + 1, direita)

função particionar(lista, esquerda, direita)

pivo = lista[direita] # escolhendo o pivo como último

elemento

i = esquerda - 1

para j de esquerda até direita -1

se lista[j] <= pivo

i=i+ 1

trocar(lista[i], lista[j])

trocar(lista[i + 1 ], lista[direita]) # colocando o pivo em sua

posição correta

retornar i + 1

# Inicializando o algoritmo com os índices apropriados

lista= [valores a serem ordenados]

sort(lista, 0, comprimento(lista)-1)

Qual das alternativas abaixo corresponde ao algoritmo em questão?

Observe o pseudocódigo abaixo demonstrado, o qual se trata de uma ordenação por inserção.

INSERTION-SORT(A)

1 for j = 2 to A • comprimento

2 __ chave =A [j]

3 __ // Inserir A [j] na sequência ordenada A [1 .. j -1].

4__ i = j - 1

5 __ while i > 0 e A [i] > chave

6 __ __ __ A [i + 1] = A [i]

7 __ __ __ i = i - 1

8 __ A [i + 1] = chave

Existem determinadas convenções que são praticadas em pseudocódigos, como é o caso do uso representativo de laços, em for e while. Versando somente acerca do segundo dos laços citados, é possível afirmar que ele começa em que linha, e contém qual(is) outra(s), respectivamente?

Julgue o item seguinte a respeito dos conceitos de algoritmo de ordenação.

O algoritmo merge sort ordena os elementos de um vetor percorrendo este diversas vezes e, a cada passagem, deslocando até o topo o maior elemento da sequência.

Sobre o algoritmo de ordenação Merge Sort, ou Ordenação por Mistura, é CORRETO afirmar que:

Algoritmos de ordenação são responsáveis por ordenar elementos de uma estrutura de dados de forma completa ou parcial. Sobre a complexidade dos algoritmos de ordenação, assinale, a seguir, o algoritmo de ordenação que, no pior caso, tem complexidade igual a O(n log n).

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?

São algoritmos de ordenação, EXCETO:

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?

Métodos de ordenação são algoritmos usados para organizar elementos de uma sequência em uma ordem específica. Qual método de ordenação tem complexidade de tempo médio O(n log n) e utiliza a técnica de dividir e conquistar?

Observe o pseudocódigo a seguir:

1.

2. _ var

3. ___ a, b : inteiro

4. ___ x : vetor[1..10] de inteiro

5.

6. _ procedimento questao( var a, b : inteiro )

7. _ var aux : inteiro

8. _ inicio

9. ___ aux <- a

10. ___ a <- b

11. ___ b <- aux

12. fimprocedimento

13.

14. inicio

15. aleatorio 0,100,3

16. para a de 1 ate 10 faca

17. _ leia(x[a])

18. fimpara

19.

20. para a de 1 ate 10 faca

21. _ para b de 1 ate 9 faca

22. ___ se x[b] > x[b+1] entao

23. ___ __ questao(x[b], x[b+1])

24. ___ fimse

25. _ fimpara

26. fimpara

27.

28. para a de 1 ate 10 faca

29. _ escreval(a:3," - ", x[a])

30. fimpara

31. fimalgoritmo

Trata-se do seguinte tipo de ordenação de dados:

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?

São exemplos de algoritmos de ordenação, EXCETO: