Considere o seguinte vetor de inteiros:

V = {8, 3, 7, 4, 9, 2}.

Suponha que o algoritmo Quicksort seja aplicado a esse vetor utilizando a seguinte estratégia:

1. o pivô é sempre o primeiro elemento do subvetor;
2. a partição organiza os elementos de forma que valores menores que o pivô fiquem à esquerda e valores maiores fiquem à direita.

Após a primeira operação de partição, qual será a posição final do pivô no vetor? Considere o algoritmo de partição de Lomuto, onde o pivô é o primeiro elemento e, ao final da partição, o pivô é posicionado entre os elementos menores e maiores.

Analise o seguinte programa escrito em linguagem C conforme o padrão ANSI C, no qual arrays multidimensionais são armazenados em memória de forma contígua em ordem de linhas (row-major order):

Qual valor será impresso pelo programa?

Analise o vetor ordenado:

[3, 8, 12, 15, 19, 27, 31].

Aplicando busca binária para localizar o valor 19, quantas comparações serão realizadas até encontrar o elemento, considerando a estratégia padrão de busca binária que compara inicialmente com o elemento central? Considere a implementação clássica da busca binária que retorna o índice do elemento ou -1 se não encontrado. As comparações consideram apenas as verificações do elemento central.

Considere o algoritmo:

Qual é a complexidade assintótica?

Analise o pseudocódigo abaixo:

algoritmo "Repeticao"
var
   i, j, resultado : inteiro
inicio
   resultado <- 0
   para i de 1 ate 3 faca
      para j de 1 ate i faca
         resultado <- resultado + 1
      fimpara
   fimpara
   escreva(resultado)
fimalgoritmo

Qual é o valor final da variável resultado?

Para que a Busca Binária seja aplicada com sucesso em um vetor, qual pré-requisito é obrigatório e qual é a sua complexidade de tempo no pior caso?

Em ambientes Microsoft Windows, a variável de ambiente ____________ aponta para o diretório em que o JDK (Java Development Kit) ou o Java Runtime Environment (JRE) está instalado no computador.

Assinale a alternativa que preenche corretamente a lacuna do trecho acima.

Analise a função recursiva abaixo escrita em pseudocódigo:

função calcular(n: inteiro): inteiro
inicio
    se (n <= 1) entao
        retorne 1
    senao
        retorne n * calcular(n - 2)
    fimse
fimfunção

Qual é o valor retornado pela chamada calcular(6)?

Sobre análise de complexidade e algoritmos de ordenação, analise as assertivas a seguir:

I. A notação O (big-O) define um limite superior assintótico: f(n) = O(g(n)) se, e somente se, existem constantes c > 0 e n₀ ≥ 1 tais que 0 ≤ f(n) ≤ c·g(n) para todo n ≥ n₀.

II. O Merge Sort apresenta complexidade Θ(n log n) no pior, no melhor e no caso médio, mantendo esse desempenho independentemente da distribuição de entrada.

III. O algoritmo Quick Sort com estratégia de pivô aleatório (randomized quicksort) possui complexidade Θ(n log n) no pior caso, eliminando completamente a possibilidade de comportamento quadrático.

IV. Se um algoritmo tem complexidade O(n²), então ele também tem complexidade O(n³), pois toda função limitada superiormente por c·n² também é limitada superiormente por c·n³ para n suficientemente grande.

Quais estão corretas?

Considere árvores B não vazias, com grau mínimo t ≥ 2. Para árvores B+, adote a convenção usual de sistemas de indexação: todas as chaves de dados permanecem nas folhas, enquanto os nodos (nós) internos armazenam apenas chaves separadoras; todas as folhas estão na mesma profundidade. Nesse contexto, analise as assertivas a seguir:

I. Em uma árvore B de grau mínimo t, todo nodo não raiz armazena entre t−1 e 2t−1 chaves; a raiz armazena entre 1 e 2t−1 chaves.

II. A altura de uma árvore B aumenta somente quando a raiz é dividida e diminui somente quando, após uma fusão, uma raiz interna fica sem chaves e é substituída por seu único filho.

III. Na inserção em uma árvore B+, a divisão de uma folha cheia remove da folha a chave separadora promovida ao pai, exatamente como ocorre na divisão de um nodo em uma árvore B convencional.

IV. A altura h de uma árvore B de grau mínimo t, com n chaves, satisfaz h ≤ log_t((n+1)/2). Para t=500 e n=10⁹, conclui-se que h ≤ 3; ou seja, o caminho da raiz até uma folha contém no máximo 4 nodos. Assumindo um nodo por página de disco e a raiz residente em memória principal, uma busca exige, no máximo, 3 acessos a disco.

Quais estão corretas?