Considere o grafo abaixo e selecione todas as afirmações corretas.

Escolha todas respostas corretas para a seguinte questão:

Num grafo não orientado, o que é um caminho?

Escolha a resposta mais correta para a seguinte questão:

O que é um vértice (nó) num grafo?

Escolha a melhor opção para a fórmula de fecho da seguinte fórmula recorrente:

Considere o algoritmo recursivo mostrado na figura abaixo. Estabeleça a ordem de complexidade deste algoritmo no pior caso.

     Nota: Para realizar o cálculo do trabalho, pode considerar o número de acessos ao array a amarelo (mas não é obrigatório).

Escolha a melhor opção para a ordem de complexidade da seguinte fórmula recorrente:

Considere o algoritmo quick-select, que resolve o problema da k-seleção através da escolha aleatória do elemento pivot.

Na primeira invocação do algoritmo (i.e., com o array de tamanho ), qual é a probabilidade de se escolher um pivot no intervalo de posições no array?

Qual das opções abaixo representa uma fórmula recorrente possível para o cálculo da ordem de complexidade do algoritmo seguinte?

ALGORITMO Alg1( n )
   //Input: um inteiro positivo n 
   //Output: inteiro positivo Alg1( n )
   If n < 2 return 0
   Else return 2*Alg1(n/4)+n+2

Escolha a opção correta para a ordem de complexidade da seguinte fórmula recorrente:

Dada a seguinte fórmula recorrente:

Complete a seguinte frase com a opção mais correta:

"Para o cálculo da ordem de complexidade desta fórmula recorrente..."