ALGORITMOS E COMPLEXIDADE QUIZ 2

Compare os algoritmos de busca sequencial (sequential search) e busca binária (binary search) em termos de complexidade de tempo, eficiência e aplicabilidade. Considere as seguintes afirmações e escolha a alternativa correta:

I) O tempo de execução da busca binária é menor do que o da busca sequencial na maioria dos casos.

II ) A busca sequencial é uma solução mais eficiente que a busca binária.

III) A busca sequencial é um algoritmo simples de implementar, mas não é muito eficiente, ou seja, o seu tempo de execução é alto

IV) No pior caso, a complexidade de tempo da busca sequencial é linear, enquanto a busca binária tem complexidade logarítmica.

• Apenas as afirmações I, III e IV são verdadeiras.

• Apenas as afirmações II e IV são verdadeiras.

• Apenas as afirmações I e II são verdadeiras.

• Apenas as afirmações I, II e III são verdadeiras.

O algoritmo é executado utilizando a seguinte fórmula recursiva: fn = fn-1 + fn-2. Considerando que f(0) = 0 e f(1) = 1, indique qual série está correta para f(5):

• 0, 1, 1, 2, 3, 5.

• 1, 2, 3, 5, 7, 11

• 1, 2, 3, 5, 8, 13

• 0, 2, 3, 8, 13, 21

Suponha que temos o seguinte array de inteiros:

int numeros[5] = {5, 1, 4, 2, 8};

Qual será a ordem do array números após a execução do método bubbleSort?

• {1, 2, 4, 5, 8}

• {5, 4, 2, 1, 8}

• {8, 5, 4, 2, 1}

• {1, 4, 2, 5, 8}

Dada a árvore ao lado, identifique o percurso em pós-ordem:

• D, E, B, F, G, C, A.

• D, B, E, A, F, G, C.

• A, B, D, E, F, C, G.

• A, B, C, D, E, F, G.

Considerando o grafo ponderado ao lado:

Utilizando o algoritmo do menor caminho, qual sequência de nós deverá ser percorrida partindo do ponto C para chegar ao ponto F?

• C, E, D, F

• C, E, F

• C, A, B, F

• C, E, D, B,F

Qual é o papel das sentinelas no algoritmo de ordenação Shell?

• As sentinelas são elementos que ocupam as primeiras posições de cada subvetor, indicando o início de cada subconjunto a ser ordenado.

• As sentinelas são elementos fictícios inseridos no meio do vetor para dividir o vetor em subvetores menores.

• As sentinelas são elementos que ocupam as últimas posições de cada subvetor, indicando o final de cada subconjunto a ser ordenado.

• As sentinelas são elementos que ocupam posições aleatórias no vetor, fornecendo informações adicionais ao algoritmo de ordenação Shell.

Qual é o papel do pivô no algoritmo de ordenação Quick Sort?

• O pivô é o primeiro elemento do vetor e é usado como referência para dividir o vetor em subvetores menores.

• pivô é escolhido aleatoriamente em cada iteração do algoritmo e determina a posição do próximo elemento a ser comparado.

• O pivô é um elemento fixo escolhido aleatoriamente no vetor e é usado como referência para dividir o vetor em subvetores menores.

• O pivô é um elemento central do vetor e é usado como referência para determinar a posição correta de todos os elementos menores e maiores.

O que são vetores em programação?

• Tipos de dados que armazenam apenas um valor

• Tipos de dados que agrupam várias variáveis num único tipo em sequência na memória

• Tipos de dados que armazenam apenas valores inteiros

• Tipos de dados que armazenam apenas valores de ponto flutuante

Um algoritmo tem tempo de execução dado por 1/2(n² + n). A complexidade desse algoritmo é:

• O(2n²)

• O(n²)

• O(n² + n)

• O(2n²) + O(n)

Usando a notação Big-O, a complexidade do Merge Sort é, no pior caso,

• O(n log n)

• O(n²)

• O(n log n)

• O(n^1.25)