Pular para o conteúdo

Atividades sobre algoritmos

14 materiais e 111 questões sobre algoritmos, com gabarito comentado.

Exemplos de questões sobre algoritmos

Montar prova com este tema

  1. Uma função de ordenação genérica recebe uma lista e uma segunda função, chamada chave, que diz qual informação de cada item deve ser comparada:

    função idade(p):
        devolva p.idade

    alunos ← [(Ana, 17), (Bia, 15), (Caio, 16)]
    escreva ordenar(alunos, chave = idade)

    A lista escrita e a vantagem desse tipo de função são

    1. [Ana, Bia, Caio]; a função ordenar sempre usa a ordem alfabética, e a chave serve só como comentário.
    2. [Bia, Caio, Ana]; mas é preciso escrever uma função ordenar diferente para cada tipo de dado.
    3. [15, 16, 17]; a função ordenar devolve apenas as idades, descartando os nomes dos alunos.
    4. [Bia, Caio, Ana]; a mesma função ordenar serve para qualquer critério, bastando trocar a função chave.
    5. [Ana, Caio, Bia]; a função ordenar coloca primeiro os mais velhos, qualquer que seja a chave informada.

  2. Para verificar se há nomes repetidos em uma lista de n nomes, um algoritmo compara cada nome com todos os que vêm depois dele:

    para i de 1 até n − 1 faça
        para j de i + 1 até n faça
            se nome[i] = nome[j] então
                escreva "há repetição"

    Para uma lista com 1 000 nomes, o número de comparações feitas e o comportamento do tempo de execução quando a lista dobra de tamanho são

    1. 1 000 comparações; o tempo dobra quando n dobra.
    2. 499 500 comparações; o tempo fica cerca de 4 vezes maior quando n dobra.
    3. 999 comparações; o tempo de execução fica cerca de 4 vezes maior quando n dobra.
    4. 1 000 000 de comparações; o tempo não se altera quando n dobra.
    5. 499 500 comparações; o tempo dobra quando n dobra.

  3. Um programa procura um nome em uma lista de 1.000 nomes em ordem alfabética usando a busca binária: compara o nome procurado com o do meio da lista e, conforme o resultado, descarta a metade em que ele não pode estar, repetindo o processo na metade restante.

    O número máximo de comparações necessárias para encontrar o nome (ou concluir que ele não está na lista) é:

    1. 10
    2. 50
    3. 100
    4. 500
    5. 1.000