Questões sobre Análise de Algorítimos

• A.

  calcula o fatorial de cada número lido e armazena em um vetor em ordem decrescente.

• B.

  está incorreto, pois qualquer vetor de inteiros em todas as linguagens de programação começam pela posição (índice) 1.

• C.

  está incorreto, pois se forem digitados para n os valores 3, 8, 1, 9 e 4, um laço infinito será gerado.

• D.

  classifica em ordem crescente os valores armazenados em um vetor.

• E.

  armazena 5 valores em um vetor e, em seguida, procura pelo maior valor armazenado.

Cláudia trabalha no Tribunal Regional do Trabalho da 15ªRegião e recebeu um arquivo com um texto de 4 milhões de palavras. Sua tarefa é armazenar as palavras do texto em uma estrutura de dados de forma que possa localizar rapidamente qualquer palavra no texto e, ainda obter todas as palavras em ordem alfabética, quando necessário. Cláudia, então, criou um programa e armazenou as palavras numa ABB − Árvore Binária de Busca de altura mínima, de forma que cada nó da árvore armazenasse uma palavra. O número máximo de comparações que serão necessárias para se localizar qualquer palavra na ABB e o tipo de percurso na árvore que permite a recuperação das palavras em ordem alfabética são, respectivamente:

• A. 4 milhões; pós-ordem.
• B. 22; em-ordem.
• C. 2 milhões; pré-ordem;
• D. 32; pós-ordem.
• E. 23; em-ordem.

O método ordena() acima classifica os elementos de v pelo algoritmo de ordenação

• A. por inserção, que faz Nlog₂N comparações, sendo N o número de elementos do vetor.
• B. bolha, que faz (N²-2N) /4 comparações, sendo N o número de elementos do vetor.
• C. por seleção, que faz (N²-N) /2 comparações, sendo N o número de elementos do vetor.
• D. por seleção, que faz N²log₂ (N) comparações, sendo N o número de elementos do vetor.
• E. por inserção, que faz (N²-N) /2 comparações, sendo N o número de elementos do vetor.

O distância Hamming é um algoritmo bastante simples e utilizado para detecção de erros em transmissões de palavras. Considere os valores das seguintes palavras: A=0101 e B=1101. A distância hamming entre estas palavras, expressa em valor binário é igual a

• A.

  0100.

• B.

  0011.

• C.

  0001.

• D.

  0010.

• A.

  a relação de dominação assintótica expressa pela notação O permite comparar funções de complexidade. Por exemplo, um programa O(f4) é sempre melhor que um O(f3).

• B.

  o comportamento assintótico de uma função f (n) é o limite do comportamento do custo quando n aproxima-se de 2ⁿ.

• C.

  f1, no gráfico, corresponde à função n log₂n.

• D.

  f2, no gráfico, corresponde à função log₂n.

• E.

  f3 e f4, embora sejam exponenciais, apresentam desempenho superior a 2ⁿ.

O Quicksort é um dos métodos de ordenação mais eficientes disponíveis e a técnica de busca por espalhamento ou hashing é muito utilizada em diversas aplicações. Em relação a estes métodos é correto afirmar:

• A.

  O método Quicksort é, essencialmente, uma aplicação do princípio “dividir para conquistar”. Para a ordenação, inicialmente o vetor é dividido em uma sublista da direita e uma da esquerda, de modo que todo elemento da sublista da esquerda seja menor que o da direita. Em seguida, ordenam-se, pelo mesmo processo, as duas sublistas de forma recursiva.

• B.

  Para o cálculo da complexidade do Quicksort, leva-se em consideração o número de vezes que n (número de elementos do vetor) pode ser dividido por 10 que é O(log₁₀n), e em cada partição são feitas O(n) comparações.

• C.

  No Quicksort, o pivô é responsável pelo número de partições em que o vetor é dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, o Quicksort não funciona quando há elementos repetidos.

• D.

  Espalhamento ou hashing é o processo de transformação de uma chave em um endereço. O tempo gasto com buscas em uma tabela de espalhamento depende do tamanho da tabela, e aí reside sua grande vantagem: devem sempre ser usadas tabelas pequenas.

• E.

  O índice gerado pela função hash é chamado endereço efetivo e o endereço verdadeiro do registro é chamado endereço primário. Quando duas ou mais chaves possuem o mesmo endereço efetivo, dizemos que houve dispersão, e essas chaves são chamadas de homônimas.

Considere o número em base 2 (binário):

1111101

Este número, convertido para a base 10, representa o valor decimal 125.

Já o número binário 1111101.110, convertido para a base 10, representa o valor

• A.

  125.6

• B.

  125.75

• C.

  126.0

• D.

  126.5

• E.

  125.25

• A.

  R1=0, R2=1, R3=1

• B.

  R1=1, R2=1, R3=0

• C.

  R1=1, R2=0, R3=0

• D.

  R1=0, R2=0, R3=1

• E.

  R1=0, R2=0, R3=0

Analise as seguintes afirmativas sobre métodos de ordenação.

I. Quicksort divide um conjunto de itens em conjuntos menores, que são ordenados de forma independe, e depois os resultados são combinados para produzir a solução de ordenação do conjunto maior.

II. Seleção é um método que consiste em selecionar o menor item de um vetor e substituí-lo pelo item que estiver na primeira posição. Essas duas operações são repetidas com os itens restantes até o último elemento.

III. Shellsort é uma extensão do algoritmo de ordenação por Inserção, contornando o problema que ocorre quando o menor item de um vetor está na posição mais à direita.

Assinale a alternativa CORRETA:

• A.

  A afirmativa III está errada e as afirmativas I, II estão corretas.

• B.

  A afirmativa II está errada e as afirmativas I, III estão corretas.

• C.

  A afirmativa I está errada e as afirmativas II, III estão corretas.

• D.

  As afirmativas I, II e III estão corretas.

• A.

  0 1 2 2 3 4

• B.

  1 3 2 2 3 1

• C.

  3 1 2 2 1 3

• D.

  0 4 1 3 2 2 3 1 4 0

• E.

  4 0 3 1 2 2 1 3 0 4