Baixe o app para aproveitar ainda mais
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
Compartilhar