Questões de Concurso Comentadas sobre algoritmos de ordenação em algoritmos e estrutura de dados

Estruturas como Bubble Sort e Quicksort têm como finalidade:

A ordenação é uma operação comum em muitas aplicações. Muitos algoritmos foram desenvolvidos para executá-la. Sobre alguns desses algoritmos, é correto afirmar:

O indicador “Despesas com Educação” também foi medido em diversos municípios do estado do Rio Grande do Sul e as seguintes atividades deverão ser realizadas com base nestes dados:

I. Unir aos dados ordenados dos anos de 2008 a 2012, os dados já ordenados dos anos de 2000 a 2011, criando um único novo vetor ordenado.

II. Construir uma estrutura de dados que permita inserir o indicador de 2012 relativo às “Despesas com Educação” e os nomes de todos os municípios do Estado. A estrutura deve permitir realizar uma consulta eficiente pelo nome do município para obter o valor do indicador e também mostrar os nomes dos municípios em ordem alfabética junto com seu indicador.

Para as tarefas I e II, optou-se, de forma correta e mais adequada, por utilizar

Para realizar a ordenação de um vetor de inteiros contendo n números, foi utilizado um algoritmo de ordenação baseado na estratégia de dividir para conquistar e na divisão e ordenação recursiva das partes do vetor, obtendo um tempo de execução O(n log n). Qual das opções abaixo contém o algoritmo de ordenação descrito?

Assinale a alternativa que apresenta o método de ordenação cuja característica é a comparação do elemento atual com o próximo elemento do conjunto, realizando uma troca entre eles, caso o elemento atual tenha um valor maior que o de seu sucessor.

Em relação aos algoritmos de ordenação, avalie se são verdadeiras (V) ou falsas (F) as afirmativas a seguir:
I O algoritmo quicksort é muito eficiente quando temos uma quantidade pequena de elementos a ordenar. II O algoritmo shell utiliza intensamente a inserção direta. III No algoritmo bubble sort o número de variáveis envolvidas é pequeno.
As afirmativas I, II e III são, respectivamente:

Considerando os algoritmos de ordenação por comparação, o limite inferior para o pior caso desses algoritmos é

Para o método de ordenação Quicksort, a ordem de complexidade do pior caso e do caso médio, respectivamente, é

Na tabela a seguir, considerando os métodos de ordenação, que visam a colocar uma lista em ordem para facilitar a busca de informações nela contidas, associe os métodos à sua respectiva descrição. 

Método de Ordenação

(1) Bubble Sort 

(2) Insert Sort 

(3) Select Sort

(4) Shellsort

(5) Mergesort 

(6) Quicksort 

(7) Heapsort

  Descrição

(  ) Neste método, a lista é subdividida em h-listas, as quais são ordenadas com um método de ordenação qualquer. Esse procedimento é repetido para valores decrescentes de h, sendo que o último valor de h tem que ser 1.

(  ) Neste método, são usados, inicialmente, os elementos da lista que são inseridos em um heap binário crescente. Em seguida, são feitas sucessivas remoções do menor elemento do heap, colocando os elementos removidos do heap de volta na lista. 

(  ) Neste método, a lista é dividida em duas metades. Essas metades são ordenadas recursivamente e depois são intercaladas. Para tanto, faz-se uso das variáveis i e j para percorrer a metade esquerda e a metade direita, respectivamente. Em cada iteração, compara-se o elemento na posição i com o elemento na posição j. O menor deles é copiado para um vetor auxiliar. Esse procedimento é repetido até que uma das duas metades tenha sido totalmente copiada para o vetor auxiliar.

(  ) Neste método, os elementos da lista são movidos para as posições adequadas de forma contínua. Se um elemento está inicialmente numa posição i e, para que a lista fique ordenada, ele deve ocupar a posição j, então ele terá que passar por todas as posições entre i e j. Em cada iteração do método, percorre-se a lista a partir de seu início, comparando cada elemento com seu sucessor, trocando-os de posição se houver necessidade.

(  ) Neste método, a lista é dividida em parte esquerda e parte direita, sendo que os elementos da parte esquerda são todos menores do que os elementos da parte direita. Em seguida, as duas partes são ordenadas recursivamente.

(  ) Neste método, considera-se que a lista está dividida em parte esquerda, já ordenada, e parte direita, em possível desordem. Além disso, os elementos da parte esquerda são todos menores ou iguais aos elementos da parte direita. Cada iteração consiste em escolher o menor elemento da parte direita (pivô) e trocá-lo com o primeiro elemento da parte direita. Com isso, a parte esquerda aumenta, pois passa a incluir o pivô, e a parte direita diminui.

(  ) Neste método, considera-se que a lista está dividida em parte esquerda, já ordenada, e parte direita, em possível desordem. Inicialmente, a parte esquerda contém apenas o primeiro elemento da lista. Cada iteração consiste em colocar o primeiro elemento da parte direita (pivô) na posição adequada da parte esquerda, de modo que a parte esquerda continue ordenada.

Tabela: métodos de ordenação

Fonte: Próprio autor

A sequência correta desta associação é 

Acerca dos algoritmos de ordenação, assinale a afirmativa verdadeira.

O algoritmo quicksort é um método de ordenação comumente utilizado e que adota a estratégia de divisão e conquista. Qual a complexidade de tempo de pior caso do algoritmo?

Os métodos de ordenação são empregados para rearranjar um conjunto de objetos em uma ordem específica. Considere as seguintes proposições sobre esses métodos:

I. Um método de ordenação é dito estável se a ordem relativa dos itens com chaves iguais mantém-se inalterada pelo processo de ordenação.

II. A estabilidade de um método de ordenação é importante quando o conjunto de dados já está parcialmente ordenado.

III. Na ordenação interna, o número de registros a serem ordenados é pequeno o bastante para que todo o processo se desenvolva na memória interna (principal).

IV. Na ordenação externa, o número de registros a ser ordenado é maior do que o número que cabe na memória interna.

Assinale a alternativa CORRETA:

Analise as proposições abaixo sobre algoritmos e estrutura de dados:

I. Os métodos de ordenação por inserção e bolha possuem complexidade O(n² ) em relação ao número de comparações.

II. Embora O(n² ), o método de ordenação por inserção possui complexidade Ω(n) em relação ao número de comparações.

III. O método de ordenação por inserção, assim como o Quicksort, é estável.

IV. O método de ordenação Quicksort tem complexidade O(n² ) em seu pior caso.

Assinale a alternativa CORRETA:

O método de ordenação Bolha foi usado para ordenar uma tabela em ordem crescente contendo os números [10, 8, 7, 0], serão feitas:

O algoritmo Heapsort, quando usado para ordenar uma coleção n elementos distintos, possui, respectivamente, complexidade de melhor caso e de pior caso iguais a

Assinale a alternativa que contém apenas algoritmos de ordenação de ordem quadrática.

Um algoritmo de ordenação é executado através dos seguintes passos: (I) escolha de um elemento da lista, denominado pivô; (II) rearranjo da lista, de forma que todos os elementos anteriores ao pivô sejam menores do que ele e que todos os elementos posteriores ao pivô sejam maiores do que ele; e, também, de modo que o pivô, ao fim do processo, esteja em sua posição final, havendo duas sublistas não ordenadas; (III) ordenação recursiva das sublistas dos elementos menores e dos elementos maiores. Que algoritmo é esse?

Para ordenar um vetor com N elementos, o método de ordenação Seleção (Selection Sort) faz o seguinte número de comparações: