Exercício de Algoritmos de Avançados

Prévia do material em texto

Ciência da Computação 
 
Questão 1 
Analise as sentenças abaixo sobre recursividade. 
• Um programa recursivo é um programa que chama a si mesmo. 
• Uma função recursiva é definida em termos dela mesma. 
• A recursividade pode ser classificada como direta ou indireta. 
• Para cada chamada de uma função recursiva os parâmetros e as variáveis 
locais são empilhados na pilha de execução. 
• A recursividade é a única alternativa para a implementação do algoritmo 
Merge Sort. 
Assinale a alternativa que contém a sequência correta. 
 
 
V,V,V,V,V 
 
V,V,V,V,F 
 
V,F,V,V,F 
 
F,V,V,V,F 
 
F,V,F,F,V 
 
Questão 2 
Qual das linhas abaixo completa o algoritmo de particionamento do QuickSort ? 
PARTICIONAR(A, inicio, fim) 
1 x <-- A[fim] 
2 i <-- inicio - 1 
3 for j <-- inicio to fim-1 
4 if A[j]<= x 
5 i <-- i + 1 
6 {SENTENCA} 
7 trocar A[i + 1] <-> A[fim] 
8 return i + 1 
 
 
6 {SENTENCA} = trocar A[j] <- A[inicio]. 
 
6 {SENTENCA} = trocar A[i+1] <- A[fim]. 
 
6 {SENTENCA} = trocar A[fim] <- A[j-1]. 
 
6 {SENTENCA} = trocar A[i] <- A[j]. 
 
6 {SENTENCA} = trocar A[j] <- A[fim]. 
 
 
Questão 3 
Assinale a opção correta. Sobre o Mergesort é correto afirmar que : 
 
 
É uma ordenação por intercalação que no pior caso tem complexidade 
O(nlog2 n). 
 
É uma ordenação por trocas que no pior caso tem complexidade O(log2 n). 
 
Trabalha com um pivô para separar os dados que depois serão intercalados. 
 
Trabalha dividindo a lista apenas uma vez. 
 
Só pode ser implementado de forma recursiva, pois usa a técnica de divisão 
e conquista. 
 
 
Questão 4 
Qual dos algoritmos abaixo expressa apropriadamente a multiplicação de dois 
números de forma recursiva ? 
 
 
function multiplica(a,b){ if(b==1){ return 0; }else{ return a + 
multiplica(a,b-1) } }. 
 
 function multiplica(a,b){ if(b==1){ return a; }else{ return a + 
multiplica(b,a-1) } }. 
 
function multiplica(a,b){ if(b==1){ return a; }else{ return a + 
multiplica(a,b-1) } }. 
 
 function multiplica(a,b){ if(a==1){ return a; }else{ return a + 
multiplica(a,b-1) } }. 
 
function multiplica(a,b){ if(b==1){ return a; }else{ return b + 
multiplica(a,b-1) } }. 
 
 
Questão 5 
Assinale a opção correta. O que faz a função G definida a seguir ? 
int G (int n) { 
 if (n == 0) 
 return(1); 
 return(n * G(n-1)); 
} 
 
Multiplica os inteiros de n até 0, inclusive. 
 
Calcula o fatorial de um inteiro n passado como parâmetro. 
 
Não executa corretamente, pois não tem caso base. 
 
Irá retornar 9 se passado o valor n igual a 3, pois calculará 3 * 3 * 3. 
 
Multiplica os inteiros de 0 até n-1, inclusive.