2º Simulado - AED III

20 Questes | Total Attempts: 268

SettingsSettingsSettings
Please wait...
2 Simulado - AED III

II - Simulado - AED IIIMatéria: Introdução à Complexidade de Algoritmos, Métodos de Pesquisa, Métodos de Ordenação.


Questions and Answers
  • 1. 
    Considere as seguintes afirmativas sobre o algoritmo de pesquisa bináriaI. a entrada deve estar ordenadaII. uma pesquisa com sucesso é feita em tempo logarítmico na médiaIII. uma pesquisa sem sucesso é feita em tempo logarítmico na médiaIV. o pior caso de qualquer busca é logarítmicoAs 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.

  • 2. 
    Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se oalgoritmo é quadrático, quanto tempo em segundos ele gastaria, aproximadamente, nomesmo computador, se a entrada tiver tamanho 100?
    • A. 

      10

    • B. 

      20

    • C. 

      40

    • D. 

      100

    • E. 

      500

  • 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 (II) InsertionSort (III) HeapSort(IV) QuickSort
    • A. 

      Somente (II).

    • B. 

      Somente (I) e (II).

    • C. 

      Somente (I), (II) e (III).

    • D. 

      Somente (II), (III) e (IV).

    • E. 

      Somente (I), (III) e (IV)

  • 4. 
    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 árvoree a raiz é dado pelo número de arestas neste caminho. Qual o tamanho do maiorcaminho na árvore, após a inserção dos dados acima?
    • A. 

      2

    • B. 

      6

    • C. 

      4

    • D. 

      5

    • E. 

      3

  • 5. 
    Considere a função Pot que calcula x elevado a n, para x real e n inteiro:Seja T(n) o tempo de execução da função Pot para as entradas x e n. A ordem deT(n)  é:
    • A. 

      T(n) = O(1)

    • B. 

      T(n) = O(log n)

    • C. 

      T(n) = O(n)

    • D. 

      T(n) = O(n log n)

    • E. 

      T(n) = O(n2)

  • 6. 
    Seja P o problema de ordenar, usando comparação, n  ≥ 1 elementos e C a classe dos algoritmos que resolvem P. O limitante inferior de C é:
    • A. 

      Ω(1)

    • B. 

      Ω(log n)

    • C. 

      Ω(n)

    • D. 

      Ω(n log n)

    • E. 

      Ω(n2)

  • 7. 
    Quais algoritmos de ordenação têm complexidade O(n log n) para o melhor caso,onde n é o número de elementos a ordenar.
    • A. 

      Insertion Sort e Quicksort

    • B. 

      Quicksort e Heapsort

    • C. 

      Bubble Sort e Insertion Sort

    • D. 

      Heapsort e Insertion Sort

    • E. 

      Quicksort e Bubble Sort

  • 8. 
    Como o procedimento abaixo deve ser completado para que ele seja capaz deordenar 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;

  • 9. 
    Observe as funções representadas no gráfico abaixoAssinale a afirmativa FALSA sobre o crescimento assintótico dessas funções
    • A. 

      F(n) = O(h(n)) e i(n) = Ω(g(n)).

    • B. 

      F(n) = Θ(h(n)) e i(n) = Ω(h(n)).

    • C. 

      G(n) = O(i(n)) e h(n) = Ω(g(n))

    • D. 

      G(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n)).

    • E. 

      H(n) = Ω(i(n)), logo, i(n) = O(h(n)).

  • 10. 
    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 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(log n) 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.

  • 11. 
    A função PASCAL-like abaixo deve implementar o algoritmo de busca binária num vetor de inteiros A, com N elementos, ordenado crescentemente, onde o argumento v é a chave de busca. Para que isso ocorra, o trecho pontilhado no corpo da função deve ser substituído por:
    • A. 

      (v=A[x]) or (e>d);

    • B. 

      (v=A[x]) and (e>d);

    • C. 

      (v=A[x]);

    • D. 

      (e>d);

    • E. 

      not ((v=A[x]) or (e>d));

  • 12. 
    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 crescente.

    • E. 

      Uma árvore rubro-negra.

  • 13. 
    Professor Mac Sperto propôs o seguinte algoritmo de ordenação, chamado de Super Merge, 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 abaixo é 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(mergesort)

    • C. 

      Super Merge está correto, mas consome tempo maior que O(mergesort)

    • D. 

      Super Merge está correto, mas consome tempo menor que O(mergesort)

    • E. 

      Nenhuma das afirmações acima está correta

  • 14. 
    Quais dos algoritmos de ordenação abaixo possuem tempo no pior caso e tempo médio de execução proporcional a O(n log n)
    • A. 

      Bubble sort e Quick sort

    • B. 

      Quick sort e Merge sort

    • C. 

      Merge sort e Bubble sort

    • D. 

      Heap sort e Selection sort

    • E. 

      Merge sort e Heap sort

  • 15. 
    Julgue os itens a seguir, acerca de algoritmos para ordenação.I - O algoritmo de ordenação por inserção tem complexidade O(n × log n).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  bubble-sort  e o algoritmo de ordenação por inserção fazem, em média, o mesmo número de comparações.
    • A. 

      I e II.

    • B. 

      I e III.

    • C. 

      II e IV.

    • D. 

      I, III e IV.

    • E. 

      II, III e IV.

  • 16. 
    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(n )

    • B. 

      O(n )

    • C. 

      O(2 )

    • D. 

      O(log n × log n)

    • E. 

      O(n × log n)

  • 17. 
    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, iguais a
    • 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.

  • 18. 
    Apresente o teste de mesa para o algoritmo acima, considerando a entrada 7,3,2,10,1
  • 19. 
    Dentre os algoritmos de ordenação citados abaixo, qual é o que executa mais rápido para uma grande variedade de entrada de dados?
    • A. 

      Bolha

    • B. 

      Shellsort

    • C. 

      Mergesort

    • D. 

      Quicksort

    • E. 

      Heapsort

  • 20. 
    • A. 

      Somente I e II

    • B. 

      Somente II, III e IV

    • C. 

      Somente III, IV e V

    • D. 

      Somente I, II e V

    • E. 

      Somente I, III e IV

Back to Top Back to top