Questões

Basicamente, existem dois métodos de pesquisa em um vetor de números, a Busca Linear e a Busca Binária. A Busca Binária é mais eficiente do que a Busca Linear, mas ela só funciona se o vetor estiver ordenado. Assinale a alternativa que indique a ordem de complexidade do pior caso da Busca Binária em um vetor de n números ordenados.

Considere o código de uma árvore implementado na linguagem Javascript, descrito a seguir:

class TreeNode {

        constructor(value) {

                this.value = value;

                this.children = [];

        }

        addChild(child) {

                this.children.push(child);

}

}

class Tree {

        constructor(value) {

                this.root = new TreeNode(value);

}

        compute(value) {

                if (!this.root) return null;

                const queue = [this.root];

                while (queue.length > 0) {

                        const current = queue.shift();

                        if (current.value === value) {

                        return current;

                        }

                        for (const child of current.children) {

                        queue.push(child);

                        }

                }

                return null;

        }

}

O método compute do código é conhecido pelo acrônimo em inglês:

Analise as sentenças relacionadas abaixo, retiradas da obra Projeto de algoritmos com implementações em Pascal e C, de Ziviani (1999), acerca de métodos de pesquisa em memória primária.

I - Método de pesquisa para registros ordenados que consiste em comparar a chave com o registro que está no meio da tabela, se a chave é menor, então o registro procurado está na primeira metade da tabela; se a chave é maior, então o registro procurado está na segunda metade da tabela. O processo é repetido até que a chave seja encontrada ou retorne pesquisa sem sucesso.

II - Neste método de pesquisa, podemos implementá-lo de duas maneiras: não-balanceada e balanceada. Ambas possuem nodos, todo nodo interno contém um registro e, para cada nodo, a seguinte propriedade é verdadeira: todos os registro com chaves menores estão à esquerda, e todos os registros com chaves maiores estão à direita.

III - O método de pesquisa mais simples que existe e funciona da seguinte forma: a partir do primeiro registro, pesquise sequencialmente até encontrar a chave procurada ou o fim do registro e, então, pare.

Tais sentenças se referem, respectivamente, aos métodos de pesquisa:

O analista Jon está ministrando um treinamento sobre algoritmos de busca e, durante a explicação sobre a busca binária em uma lista ordenada de n elementos, ele discute a eficiência desse algoritmo.

A complexidade de tempo correta que Jon deve apresentar para a busca binária é a de:

Em uma agência bancária, as filas de atendimento são ordenadas da esquerda para a direita, e o gerente dessa agência percebeu a presença equivocada de um idoso, com a senha 52, na fila de atendimento não preferencial. Visando a sanar o equívoco, o gerente resolveu que, na primeira oportunidade, faria uma busca no sistema para saber se a senha 52 ainda estava ativa, indicando a presença do idoso na fila de atendimento não preferencial. Em caso de resposta positiva, procuraria o cliente para trocar sua senha por outra de atendimento preferencial; se não, apenas registraria o fato para posterior discussão no grupo de qualidade de atendimento.

Considerando o uso de um algoritmo de busca sequencial otimizado, partindo da esquerda para a direita, e as sequências hipotéticas das senhas da fila de atendimento não preferencial e suas regras de ordenação, segundo as quais quem está à esquerda é atendido antes de quem está à direita, o menor número de comparações para o gerente conhecer o resultado de sua busca ocorre em