ENADE 2005

Prévia do material em texto

ENADE 2005
As questões a seguir são do ENADE de 2005 de Computação.
Questão 13
Julgue os itens a seguir, acerca de algoritmos para ordenação.
I) O algoritmo de ordenação por inserção tem complexidade O(n×logn)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.
Estão certos 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
Resolução
A afirmativa I está errada, pois o algoritmo de ordenação por inserção (insertion sort) tem complexidade O(n2) no pior caso e no caso médio e O(n) no melhor caso. As demais afirmações estão corretas. Portanto, a alternativa correta é a (E).
Questão 15
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)O(n2)
(B) O(n2n)O(n2n)
(C) O(2n)O(2n)
(D) O(logn×logn)O(log⁡n×log⁡n)
(E) O(n×logn)O(n×log⁡n)
Resolução
O enunciado basicamente descreve o algoritmo de ordenação por intercalação (merge sort), cuja complexidade é O(nlogn)O(nlog⁡n). Portanto, a alternativa correta é a (E).
Questão 43
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.
Resolução
A busca binária requer cerca de log2 n comparações para verificar se um elemento faz parte de um vetor de tamanho n:
log2 50 ≅ 5,6
log2 1000 ≅ 9,9
log2 300 ≅ 8,2
A alternativa que mais se aproxima desses resultados é a (B). Na prática, se você calcular o teto dos valores acima obterá os mesmos valores dessa alternativa (6, 10, 9).
É claro, na prova do ENADE não é permitido o uso de calculadoras. Nesse caso, você pode estimar o valor do logaritmo verificando o expoente das potências de 2 mais próximas de 50, 1.000 e 300, pois a base do logaritmo em questão é igual a 2:
32 < 50 < 64 ou 25 < 50 < 26
512 < 1000 < 1024 ou 29 < 1000 < 210
256 < 300 < 512 ou 28 < 300 < 29.
Analisando os expoentes, vemos que log2 50 está entre 5 e 6, log2 1000 está entre 9 e 10 e, finalmente, log2 300 está entre 8 e 9. Perceba que as estimativas estão de acordo com os resultados calculados anteriormente.
Por fim, concluímos que a alternativa (B) é a correta.
Questão 51
Imagem da questão 51 do ENADE 2005 de Computação
No famoso jogo da Torre de Hanoi, é dada uma torre com discos de raios diferentes, empilhados por tamanho decrescente em um dos três pinos dados, como ilustra a figura acima. O objetivo do jogo é transportar-se toda a torre para um dos outros pinos, de acordo com as seguintes regras: apenas um disco pode ser deslocado por vez, e, em todo instante, todos os discos precisam estar em um dos três pinos; além disso, em nenhum momento, um disco pode ser colocado sobre um disco de raio menor que o dele; é claro que o terceiro pino pode ser usado como local temporário para os discos.
Imaginando que se tenha uma situação em que a torre inicial tenha um conjunto de 5 discos, qual o número mínimo de movimentações de discos que deverão ser realizadas para se atingir o objetivo do jogo?
(A) 25
(B) 28
(C) 31
(D) 34
(E) 38
Resolução
O problema da Torre de Hanói é um clássico no estudo de algoritmos recursivos (assim como o fatorial e a sequência de Fibonacci). O número de movimentações para n discos é calculado utilizando a fórmula 2n-1. Para 5 discos, o número mínimo de movimentações será 25-1=31. Logo, a alternativa correta é a (C).