Questões de Revisão - Análise de Algoritmos de Ordenação e Busca - Gabarito
14 pág.

Questões de Revisão - Análise de Algoritmos de Ordenação e Busca - Gabarito


DisciplinaAnálise de Algoritmos191 materiais713 seguidores
Pré-visualização3 páginas
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Questões de Revisão
Análise de Algoritmos de Ordenação e Busca
1. Julgue os itens a seguir, acerca de algoritmos para ordenação.
I. O algoritmo de ordenação por inserção tem complexidade O(nlgn).
II. Um algoritmo de ordenação é dito estável caso ele não altere a posição relativa de
elementos de mesmo valor.
III. No algoritmo quicksort, a escolha do elemento pivô influencia o desempenho do
algoritmo.
IV. O bubblesort e o algoritmo de ordenação por inserção fazem, em média, o mesmo
número de comparações.
Estão corretos apenas os itens
a) I e II b) I e III c) II e IV d) I, III e IV e) II, III e IV
2. Considere o algoritmo que implementa o seguinte processo: uma coleção desordenada de
elementos é dividida em duas metades e cada metade é utilizada como argumento para a
reaplicação recursiva do procedimento. Os resultados das duas reaplicações são, então,
combinados pela intercalação dos elementos de ambas, resultando em uma coleção
ordenada. Qual é a complexidade desse algoritmo?
a) O(n2) b) O(n2n) c) O(2n) d) O(lgnlgn) e) O(nlgn)
3. Um algoritmo de ordenação é estável se a ordem relativa dos itens com chaves iguais
mantém-se inalterada após a ordenação. Quais dos seguintes algoritmos de ordenação são
estáveis?
I. BubbleSort (ordenação por bolha)
II. InsertionSort (ordenação por inserção)
III. HeapSort
IV. QuickSort
a) Somente II
b) Somente I e II
c) Somente I, II e III
d) Somente II, III e IV
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
e) Somente I, III e IV
4. Como o procedimento, a seguir, deve ser completado para que ele seja capaz de ordenar um
vetor de n elementos (n \u2264 100) em ordem crescente.
a) a[j] := x; j := j - 1; a[j] := x;
b) a[i] := x; j := j + 1; a[i] := x;
c) a[0] := x; j := j - 1; a[j+1] := x;
d) a[i] := x; j := j - 1; a[j+1] := x;
e) a[0] := x; j := j + 1; a[j] := x;
5. Realizou-se uma brincadeira com n crianças, que receberam uma bexiga (balão) vazia cada
uma, para então encherem até onde achassem que não estouraria. A brincadeira consistia,
então, em determinar uma estratégia que estabelecesse a ordem na qual os balões atingiriam
o teto do salão. Considerando a quantidade de ar em cada bexiga e assumindo que seja
possível determinar qual bexiga estava mais cheia de ar, quando comparadas duas a duas,
quantas comparações, no máximo, seriam necessárias para soltar todos os balões,
escolhendo de cada vez o balão precisamente mais cheio de ar?
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
a) lgn b) n2lgn c) 2n d) n2 e) 5n + 2
6. Considere o problema de ordenação onde os vetores a serem ordenados, de tamanho n > 0,
possuem \u230an/2\ufffd valores iguais a um número real x e \ufffdn/2\u2309 valores iguais a um outro número
real y. Considere que os números reais x e y são conhecidos e fixos, porém estão
distribuídos aleatoriamente no vetor a ser ordenado. Neste caso, é correto afirmar:
a) Podemos ordenar estes vetores a um custo O(n)
b) No caso médio, o Quicksort será o algoritmo mais eficiente para este problema, com um
custo O(nlgn)
c) O algoritmo de ordenação por inserção sempre opera no melhor caso com um custo O(n)
d) O limite inferior para esta classe de problema é \u2126(n2)
e) O limite inferior para esta classe de problema é \u2126(nlgn)
7. Com relação aos métodos de ordenação, relacione o algoritmo à descrição correspondente.
I. Inserção
II. Seleção
III. Quicksort
IV. Shellsort
V. Mergesort
A. Encontra o menor elemento e o troca com a primeira posição, depois o segundo menor com a
segunda posição e assim sucessivamente (n-1 vezes).
B. As comparações e trocas são feitas baseadas em uma distância determinada (por exemplo:
distância 4, onde o primeiro seria comparado com o quinto elemento, o segundo com o sexto, e
assim sucessivamente), depois a distância é reduzida. Este processo se repete até que a distância
seja 1 e as últimas comparações e trocas sejam efetuadas.
C. A partir do segundo elemento, este deve ser colocado na sua posição correspondente (entre os
elementos já analisados, como ao se organizarem as cartas de baralho na mão do jogador). Repete-
se o procedimento até o último elemento.
D. Escolhe-se um ponto de referência (pivô) e separam-se os elementos em 2 partes: à esquerda,
ficam os elementos menores que o pivô, e à direita, os maiores. Repete-se este processo para os
grupos de elementos formados (esquerda e direita) até que todos os elementos estejam ordenados.
V. Divide-se o grupo de elementos ao meio, repete-se a divisão para cada um dos subgrupos, até que
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
cada subgrupo tenha apenas 1 elemento. Nesse ponto, faz-se o reagrupamento dos subgrupos
comparando os elementos e trocando, se necessário, para que eles fiquem ordenados. Repete-se este
procedimento até restar um só grupo de elementos.
Indique a alternativa que contém a associação correta.
a) I-A, II-D, III-B, IV-C, V-E
b) I-B, II-A, III-C, IV-E, V-D
c) I-B, II-A, III-E, IV-D, V-C
d) I-C, II-A, III-D, IV-B, V-E
e) I-D, II-E, III-B, IV-A, V-C
8. Sobre o comportamento assintótico do algoritmo de ordenação mergesort, indique a
alternativa que apresenta, corretamente, sua complexidade.
a) O(lgn) b) O(nlgn) c) O(n2) d) O(n3) e) O(2n)
9. Sobre a escolha adequada para um algoritmo de ordenação, considere as afirmativas a
seguir. 
I. Quando os cenários de pior caso for a preocupação, o algoritmo ideal é o Heap Sort
II. Quando o vetor apresenta a maioria dos elementos ordenados, o algoritmo ideal é o
Insertion Sort
III. Quando o interesse for um bom resultado para o médio caso, o algoritmo ideal é o Quick
Sort
IV. Quando o interesse é o melhor caso e o pior caso de mesma complexidade, o algoritmo
ideal é o Bubble Sort.
Assinale a alternativa correta.
a) Somente as afirmativas I e II são corretas
b) Somente as afirmativas I e IV são corretas
c) Somente as afirmativas III e IV são corretas
d) Somente as afirmativas I, II e III são corretas
e) Somente as afirmativas II, III e IV são corretas.
10. Quais destes algoritmos de ordenação têm a classe de complexidade assintótica, no pior
caso, em O(nlgn)?
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
a) QuickSort, MergeSort, e HeapSort
b) QuickSort e SelectionSort
c) MergeSort e HeapSort
d) QuickSort e BubbleSort
e) QuickSort, MergeSort e SelectionSort
11. Professor Mac Sperto propôs o seguinte algoritmo de ordenação, chamado de SuperMerge,
similar ao merge sort: divida o vetor em 4 partes do mesmo tamanho (ao invés de 2, como é
feito no merge sort). Ordene recursivamente cada uma das partes e depois intercale-as por
um procedimento semelhante ao procedimento de intercalação do merge sort. Qual das
alternativas é verdadeira?
a. Super Merge não está correto. Não é possível ordenar quebrando o vetor em 4 partes
b. Super Merge está correto, mas consome tempo O(merge sort)
c. Super Merge está correto, mas consome tempo maior que O(merge sort)
d. Super Merge está correto, mas consome tempo menor que O(merge sort)
e. Super Merge está correto, mas consome tempo O((merge sort)/2)
12. No processo de pesquisa binária em um vetor ordenado, os números máximos de
comparações necessárias para se determinar se um elemento faz parte de vetores com
tamanhos 50, 1.000 e 300 são, respectivamente
a) 5, 100 e 30 b) 6, 10 e 9 c) 8, 31 e 18 d) 10, 100 e 30 e) 25, 500 e 150
13. Um programador propôs um algoritmo não-recursivo para o percurso em pré-ordem de uma
árvore binária com as seguintes características.
Sebastião
Sebastião fez um comentário
Não entendi na 20, pq vc diz q a afirmação 1 é falsa. Se o vetor está ordenado de forma crescente, então é só pedir pra retornar o valor da posição n-i. EX: VETOR [2,6,8,9,15,16,18,20,30]. Qual o quinto maior valor? têm 9 posições, então POS = 9 - 5. Na posição 4 se encontra o quinto maior valor; Como o vetor inicia em 0, então é o valor 15. Isso feito em tempo Constante.... Veja mais
0 aprovações
Carregar mais