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

Prévia do material em texto

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 ≤ 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 ⌊n/2� valores iguais a um número real x e �n/2⌉ 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 é Ω(n2)
e) O limite inferior para esta classe de problema é Ω(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.• Cada nó da árvore binária é representado por um registro com três campos: chave, que
armazena seu identificador; esq e dir, ponteiros para os filhos esquerdo e direito,
respectivamente.
• O algoritmo deve ser invocado inicialmente tomando o ponteiro para o nó raiz da árvore
binária como argumento.
• O algoritmo utiliza push() e pop() como funções auxiliares de empilhamento e
desempilhamento de ponteiros para nós de árvore binária, respectivamente.
A seguir, está apresentado o algoritmo proposto, em que λ representa o ponteiro nulo.
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Com base nessas informações e supondo que a raiz de uma árvore binária com n nós seja passada ao
procedimento pré-ordem(), julgue os itens seguintes.
I. O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso.
II. O algoritmo só funcionará corretamente se o procedimento pop() for projetado de forma a
retornar λ caso a pilha esteja vazia.
III. Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser
implementadas com custo constante.
IV. A complexidade do pior caso para o procedimento pré-ordem() é O(n).
Indique a opção correta.
a) Apenas um item está certo. b) Apenas os itens I e IV estão certos.
c) Apenas os itens I, II e III estão certos. d) Apenas os itens II, III e IV estão certos.
e) Todos os itens estão certos.
14. Em relação à pesquisa sequencial e binária, assinale a alternativa correta.
a. A pesquisa binária percorre no pior caso lgn elementos
b. A pesquisa binária pode ser feita sobre qualquer distribuição dos elementos
c. A pesquisa sequencial exige que os elementos estejam completamente ordenados
d. A pesquisa sequencial percorre todos os elementos para encontrar a chave
15. Considere as seguintes afirmativas sobre o algoritmo de pesquisa binária:
I. a entrada deve estar ordenada
II. uma pesquisa com sucesso é feita em tempo logarítmico na média
III. uma pesquisa sem sucesso é feita em tempo logarítmico na média
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
IV. o pior caso de qualquer busca é logarítmico
As afirmativas corretas são:
a) Somente I e II b) Somente I, II e III c) Somente II e III 
d) Somente III e IV e) Todas as afirmativas estão corretas
16. Considere uma heap H com 24 elementos tendo seu maior elemento na raiz. Em quantos nós
de H pode estar o seu segundo menor elemento?
a. 18 b. 15 c. 14 d. 13 e. 12
17. Considere o algoritmo máximo (v, i, f) que devolve o índice de um elemento máximo de
{v[i], …, v[f]}:
Considerando n = f – i + 1, o número de comparações entre elementos de v numa execução de
máximo(v, i, f):
a. nlgn b. n/2 c. n – 1 d. lgn e. 2n
18. Em uma estrutura de árvore binária de busca, foram inseridos os elementos "h", "a", "b",
"c", "i", "j", nesta sequência. O tamanho do caminho entre um nó qualquer da árvore e a raiz
é dado pelo número de arestas neste caminho. Qual o tamanho do maior caminho na árvore,
após a inserção dos dados listados?
a. 2 b. 6 c. 4 d. 5 e. 3
19. Seja L = <r1, …, rn> uma lista qualquer de inteiros não necessariamente distintos. A esse
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
respeito, assinale a alternativa incorreta.
a. Existe um algoritmo determinístico ótimo de complexidade O(n) para selecionar o maior
elemento de L
b. Existe um algoritmo determinístico de complexidade O(nlgn) para selecionar, para 1 ≤ i
≤ n, o i-ésimo menor elemento de L
c. Se existe um algoritmo linear para selecionar o i-ésimo menor elemento de L, então,
usando esse algoritmo, é possível projetar um algoritmo linear para ordenar L em ordem
não crescente
d. Existe um algoritmo linear para determinar o terceiro maior elemento de L
e. Existe um algoritmo que, percorrendo uma única vez L, pode determinar o menor e o
maior elemento de L
20. Considere as seguintes sentenças:
I. Se um vetor A[1,n], n ≥ 2, de inteiros é ordenado em ordem não decrescente, então
encontrar o i-ésimo maior elemento, 1 ≤ i ≤ n, pode ser feito em tempo constante
II. Se um vetor A[1,n], n ≥ 2, de inteiros é ordenado em ordem não decrescente, o limite
inferior para o problema de encontrar o i-ésimo maior elemento, 1 ≤ i ≤ n, com um
algoritmo de comparação, é O(n) 
III. Se um vetor A[1,n], n ≥ 2, de inteiros é ordenado em ordem não decrescente, o limite
inferior para o problema de encontrar o i-ésimo maior elemento, 1 ≤ i ≤ n, com um
algoritmo de comparação, é O(lgn) 
IV. Se um vetor A[1,n], n ≥ 2, de inteiros é ordenado em ordem crescente, então encontrar o
(n – 1)-ésimo maior elemento, pode ser feito em tempo constante
V. Se um vetor A[1,n], n ≥ 2, de inteiros é ordenado em ordem crescente, então encontrar o i
-ésimo maior elemento, pode ser feito em tempo constante
A esse respeito, assinale a alternativa correta.
a) Apenas os itens II e IV são falsos b) Apenas os itens I, III e V são verdadeiros
c) Apenas os itens III, IV e V são verdadeiros d) Apenas os itens II e III são falsos
e) Apenas os itens II e V são verdadeiros
21. Deseja-se efetuar uma busca para localizar uma certa chave fixa x, em uma tabela contendo
n elementos. A busca considerada pode ser a linear ou binária. No primeiro caso pode-se
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
considerar que a tabela esteja ordenada ou não. No segundo caso a tabela está, de forma
óbvia, ordenada. Assinale a alternativa correta.
a. A busca binária sempre localiza x, efetuando menos comparações que a busca linear
b. A busca linear ordenada sempre localiza x, efetuando menos comparações que a não
ordenada
c. A busca linear não ordenada sempre localiza x, com menos comparações que a ordenada
d. A busca binária requer O(lgn) comparações, no máximo, para localizar x
e. A busca linear ordenada nunca requer mais do que n/2 comparações para localizar x.
22. Considere uma árvore binária de busca T com n nós e altura h. A altura de uma árvore é o
número máximo de nós de um caminho entre a raiz e as folhas. Analise as afirmativas:
I. h < 1 + lgn
II. Todo nó que pertence à subárvore esquerda de um nó x tem valor maior que o pai de x
III. Uma busca em ordem simétrica (em-ordem) em T produz uma ordenação crescente dos
elementos de T
Assinale a alternativa correta.
a) Apenas a afirmativa I está correta b) Apenas a afirmativa II está correta
c) Apenas a afirmativa III está correta d)Apenas as afirmativas I e II estão corretas
e) Apenas as afirmativas I e III estão corretas
23. Considere uma tabela de espalhamento (tabela hash) de comprimento m = 11, que usa
endereçamento aberto, a técnica de tentativa linear (linear probing) para resolver colisões e
com a função de dispersão (função hash), h(k) = k mod m, onde é a chave a ser inserida. 
Considere as seguintes operações sobre essa tabela:
Inserção das chaves 3, 14, 15, 92, 65, 35 (nesta ordem);
Remoção da chave 15; e
Inserção da chave 43.
Escolha a opção que representa esta tabela após estas operações:
a. 65 – ø – 35 – 14 – ø – 92 – 3 – ø – ø – ø – 43
b. 43 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 65
c. 65 – ø – 35 – X - 14 – 92 – 3 – ø – ø – ø – 43
d. 65 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 43
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
e. 43 – ø – 35 – 3 – 14 – X – 92 – ø – ø – ø – 65
24. Dado um conjunto C contendo n inteiros distintos, qual das seguintes estruturas de dados em
memória principal permite construir um algoritmo para encontrar o valor máximo de C em
tempo constante?
a. Um vetor não ordenado
b. Um vetor ordenado
c. Uma árvore binária de busca balanceada
d. Uma lista encadeada simples ordenada em ordem crescente25. Em relação à pesquisa sequencial e binária, assinale a alternativa correta.
a. A pesquisa binária em média percorre a metade dos elementos do vetor
b. A pesquisa binária percorre no pior caso lgn elementos
c. A pesquisa binária pode ser feita sobre qualquer distribuição dos elementos
d. A pesquisa sequencial exige que os elementos estejam completamente ordenados
e. A pesquisa sequencial percorre todos os elementos para encontrar a chave
26. Observe a árvore binária de busca, a seguir.
Assinale a alternativa que apresenta, corretamente, a sequência de inserção que gera tal árvore.
a) 30, 15, 40, 10, 20, 60, 80 b) 30, 15, 40, 10, 20, 80, 60 
c) 30, 15, 60, 10, 20, 40, 80 d) 30, 60, 20, 80, 15, 10, 40
e) 30, 60, 40, 10, 20, 15, 80
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
27. Sobre árvores binárias, considere as afirmativas a seguir.
I. Qualquer nó de uma árvore binária é raiz de, no máximo, outras duas subárvores
comumente denominadas subárvore direita e subárvore esquerda
II. Uma dada árvore binária A armazena números inteiros e nela foram inseridos 936 valores
não repetidos. Para determinar se um número x está entre os elementos dessa árvore, tal
número será comparado, no máximo, com 10 números contidos na árvore A
III. Uma dada árvore binária de busca A armazena números inteiros e nela foram inseridos
936 valores não repetidos. Para determinar se um número x está entre os elementos dessa
árvore, serão feitas, no máximo, 10 comparações. 
IV. Uma dada árvore binária de busca A armazena números inteiros e nela foram inseridos
936 valores não repetidos. Supondo que r seja o nó raiz da árvore A e que sua subárvore
esquerda contenha 460 elementos e sua subárvore direita possua 475 elementos. Para
determinar se um número x pertence a essa árvore, serão feitas, no máximo, 476
comparações.
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
28. Considere uma tabela de espalhamento (tabela hash) com 4 posições numeradas 0, 1, 2 e 3.
Se a sequência de quadrados perfeitos 1, 4, 9, …, i2, … for armazenada nessa tabela segundo
a função f(x) = x mod 4, como se dará a distribuição dos elementos pelas posições da tabela,
à medida que o número de entradas cresce?
a. Cada posição da tabela receberá aproximadamente o mesmo número de elementos
b. Três posições da tabela receberão, cada uma, aproximadamente um terço dos elementos
c. Uma única posição da tabela receberá todos os elementos, e as demais posições
permanecerão vazias
d. Todas as posições da tabela receberão elementos, mas as duas primeiras receberão, cada
uma, o dobro das outras
e. As duas primeiras posições da tabela receberão, cada uma, aproximadamente a metade
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
dos elementos, e as demais posições permanecerão vazias
29. Considere o algoritmo de busca sequencial de um elemento em um conjunto com n
elementos. A expressão que representa o tempo médio de execução desse algoritmo para
uma busca bem sucedida é
a. n2 b. n(n+1)/2 c. lgn d. (n+1)/2 e. nlgn
30. Considere n chaves armazenadas
I. de maneira arbitrária numa lista encadeada simples
II. de maneira arbitrária numa lista encadeada dupla
Considere também as mesmas chaves
III. armazenadas de maneira ordenada numa lista encadeada simples
IV. armazenadas de maneira ordenada numa lista encadeada dupla
Qual das alternativas preenche a seguinte tabela com a complexidade de busca no pior caso,
em cada uma das situações I, II, III e IV descritas?
a. b.
c. d.
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
Nome: ___________________________________________________
Nome: ___________________________________________________
Data: 02/09/2016
Respostas
Marque X na alternativa escolhida.
Questão Resposta
1 A B C D E
2 A B C D E
3 A B C D E
4 A B C D E
5 A B C D E
6 A B C D E
7 A B C D E
8 A B C D E
9 A B C D E
10 A B C D E
11 A B C D E
12 A B C D E
13 A B C D E
14 A B C D E
15 A B C D E
16 A B C D E
17 A B C D E
18 A B C D E
19 A B C D E
20 A B C D E
21 A B C D E
22 A B C D E
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Questão Resposta
23 A B C D E
24 A B C D E
25 A B C D E
26 A B C D E
27 A B C D E
28 A B C D E
29 A B C D E
30 A B C D E
	Questões de Revisão
	Questões de Revisão
	Respostas