Busca, ordenação e eficiência de algoritmos

Computação, 2ª série: Busca, ordenação e eficiência de algoritmos

1. Uma lista ordenada tem 1 000 nomes. Na busca binária, compara-se o nome procurado com o elemento do meio e descarta-se a metade em que ele não pode estar, repetindo o processo. No pior caso, o número de comparações necessárias é de cerca de:

   1. a500
   2. b1 000
   3. c10
   4. d100
   5. e32

2. Para que a busca binária funcione corretamente, é necessário que:

   1. aa lista tenha um número par de elementos
   2. ba lista esteja ordenada
   3. ca lista tenha menos de 100 elementos
   4. do elemento procurado esteja no meio da lista
   5. ea lista não tenha números negativos

3. No método da bolha (bubble sort), percorre-se a lista comparando pares vizinhos e trocando-os de lugar quando estão fora de ordem. Aplicando uma única passagem completa à lista [5, 1, 4, 2], em ordem crescente, obtém-se:

   1. a[1, 2, 4, 5]
   2. b[1, 5, 4, 2]
   3. c[4, 1, 2, 5]
   4. d[1, 4, 2, 5]
   5. e[5, 4, 2, 1]

4. Um programa usa dois laços aninhados que percorrem uma lista de n elementos, executando cerca de n² operações. Para n = 1 000, ele leva 2 segundos. Mantidas as condições, para n = 4 000 a estimativa de tempo é:

   1. a8 s
   2. b16 s
   3. c4 s
   4. d64 s
   5. e32 s

5. Um programa passou a guardar em uma tabela os resultados de cálculos já feitos, para não precisar refazê-los quando aparecem de novo (técnica chamada memoização). O efeito esperado é:

   1. areduzir o tempo, usando mais memória
   2. breduzir o tempo de execução e também a memória usada
   3. caumentar o tempo, economizando memória
   4. dnão alterar o tempo nem a memória
   5. eeliminar a necessidade de processador

6. Um aplicativo de celular verifica a localização do usuário a cada segundo, mesmo quando isso não é necessário. Além de ocupar o processador, esse comportamento afeta principalmente:

   1. aa resolução da câmera
   2. bo tamanho da tela
   3. co consumo de energia
   4. da velocidade do teclado
   5. ea capacidade do chip SIM

7. Em muitas linguagens de programação, é possível chamar ordenar(lista, criterio), em que criterio é uma outra função, escrita pelo programador, que diz qual de dois elementos vem primeiro. Esse recurso é um exemplo de:

   1. aum algoritmo recebendo outro como entrada
   2. bum laço infinito que nunca termina de executar
   3. cum vírus que altera outros programas
   4. duma técnica de compressão de dados
   5. eum algoritmo que não tem entrada

8. Um compilador é um programa que:

   1. aconecta o computador à internet
   2. bapaga arquivos duplicados do disco
   3. cprotege o computador contra invasões
   4. dmede a velocidade do processador
   5. etraduz código-fonte em um programa executável

9. Uma escola quer escolher um aplicativo de estudos que funcione bem nos celulares antigos dos estudantes, que têm pouca memória disponível. A tabela mostra os resultados de testes com três aplicativos.

   Aplicativo	Tempo de resposta	Memória usada	Falhas a cada 1 000 usos
   A	1,2 s	300 MB	5
   B	0,8 s	900 MB	2
   C	1,5 s	120 MB	3

   Considerando a prioridade da escola, a escolha mais adequada é:

   1. aB, por ser o mais rápido e o de menos falhas
   2. bA, por ter valores intermediários em tudo
   3. cB, pois memória não influencia celulares antigos
   4. dC, que usa menos memória e tem poucas falhas
   5. eA, pois tem o maior número de falhas registradas

10. Qual destes itens é uma métrica objetiva para avaliar a qualidade de um software?

    1. aA cor do ícone do aplicativo
    2. bO número de letras do nome do programa
    3. cA quantidade de falhas a cada 1 000 usos
    4. dA opinião de uma única pessoa sobre o logotipo
    5. eO país em que a empresa tem sede

11. Dobrar o tamanho de uma lista ordenada aumenta em apenas cerca de uma comparação o pior caso da busca binária.

    (   ) Verdadeiro   (   ) Falso

12. a) Explique a diferença entre busca linear e busca binária, usando como exemplo a procura de um nome em uma lista de chamada.

    b) Em que situação a busca linear pode ser a melhor escolha? Justifique considerando os recursos envolvidos.

ProvaPiloto · provapiloto.com.br