2020 1_Algoritmos_Avançados_Lista_Exercícios

Prévia do material em texto

Algoritmos Avançados – Prof. Ronaldo Candido 
 
1 
 
Lista de exercícios – Revisão para AV2 
 
1. Assinale a opção correta : 
 
a) Todo trecho com passos elementares, que não dependem do tamanho da entrada, possui complexidade 
constante, ou seja, é O(n). 
b) A complexidade da busca sequencial é O(n) e a da busca binária é O(log n), o que confirma que a busca 
binária é mais eficiente do que a busca sequencial quando a lista está ordenada. 
c) A complexidade da soma dos elementos de um vetor com n elementos é O(n2). 
d) Considere três trechos de um mesmo programa com complexidades O(n), O(n2) e O(n3). A complexidade 
do programa completo é, no pior caso, O(n). 
e) Se tenho 2 algoritmos que resolvem um problema P, ambos com complexidade de tempo no pior caso 
O(n), então sempre posso afirmar que os dois algoritmos terão tempos de execução idênticos para 
entradas do mesmo tamanho. 
 
2. Relacione as duas colunas seguintes e marque a sequência correta: 
 
1) Complexidade de Espaço ( ) Cálculo da complexidade recursiva. 
2) Complexidade de Tempo ( ) Uso da Pilha de Execução. 
3) Expansão Telescópica ( ) Ocupação de memória. 
4) Recursão ( ) Custo de processamento. 
 
a) 2 - 1 - 4 - 3. 
b) 4 - 3 - 1 - 2. 
c) 3 - 1 - 2 - 4. 
d) 4 - 1 - 3 - 2. 
e) 3 - 4 - 1 - 2. 
 
3. Dada a assinatura da função abaixo, escreva o código de função recursiva que ache o maior elemento de 
um vetor de tamanho n. 
int maximo (int n, int v[ ]) ; 
 
 
 
 
 
 
 
 
4. Faça uma função recursiva que receba um vetor de inteiros com n elementos e dobre os valores de todos 
seus componentes. Considere : 
Protótipo da função : void dobrar(int v[ ], int i, int n); 
Chamada da função no main() : dobrar(v,0,n); 
sendo que o vetor v, i (índice de v) e n foram previamente definidos. 
 
 
 
 
 
 
 
 
5. Qual dos dois algoritmos de cálculo dos números da sequência de fibonacci é mais eficiente? Por que ? 
 
 
 Algoritmos Avançados – Prof. Ronaldo Candido 
 
2 
 
A) 
int fibonacci (int n) { 
 if (n == 1) { 
 return 0; } 
 else if (n == 2) { 
 return 1; } 
 else { 
 return fibonacci (n-1) + fibonacci (n-2); } 
} 
 
B) 
 int fibonacci(int n) 
 { 
 int i, fib1 = 1, fib2 = 1, soma; 
 for (i = 3; i <= n; i = i + 1) { 
 soma = fib1 + fib2; 
 fib1 = fib2; 
 fib2 = soma; 
 } 
 return fib2; 
 } 
 
6. Relacione a primeira coluna de algoritmos com a segunda coluna de complexidade para o pior caso. 
 
( ) Busca Binária 1 - O(n log n) 
( ) Busca Sequencial 2 - O(n) 
( ) Ordenação BubbleSort 3 - O(log n) 
( ) Ordenação MergeSort 4 - O(n2) 
 
Assinale a alternativa com a relação correta entre as colunas : 
 
a) 2 - 3 - 1 - 4 
b) 3 - 2 - 4 – 1 
c) 2 - 3 - 4 - 1 
d) 3 - 2 - 1 - 4 
e) 1 - 2 - 3 - 4 
 
7. Sejam T1(n) = 100n + 10, T2(n) = 10n2 + 2n e T3(n) = 0,5n3 + n2 +2 as questões que descrevem a 
complexidade de tempo dos algoritmos Alg1, Alg2 e Alg3, respectivamente, para entradas de tamanho 
n. A respeito da ordem de complexidade desses algoritmos, pode-se concluir que: 
 
a) as complexidade assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente em O(n), O(n2) e O(n2). 
b) as complexidade assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente em O(100), O(10) e O(0,5). 
c) as complexidade assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente em O(n), O(n2) e O(n3). 
d) Alg2 e Alg3 pertencem às mesmas classes de complexidade assintótica. 
e) Alg1 e Alg2 pertencem às mesmas classes de complexidades assintótica. 
 
8. São exemplos de algoritmos de ordenação, exceto: 
 
a) Bubble Sort 
b) Select Sort 
c) Merge Sort 
d) Busca Sequencial 
e) Quick Sort 
 
 
 
 Algoritmos Avançados – Prof. Ronaldo Candido 
 
3 
 
9. Considere o seguinte algoritmo, expresso na forma de uma pseudolinguagem : 
 
Para i de 1 até n faça 
 Para j de 1 até n faça 
 Instrução 1 
 Instrução 2 
 ... 
 Instrução k 
 
 A complexidade desse algoritmo, no tocante ao seu tempo de execução é: 
 
a) O(1) 
b) O(2) 
c) O(n) 
d) O(2n) 
e) O(n2) 
 
10. Assinale a opção correta : 
 
O que faz a função eureka definida a seguir ? Para isso, considere tam o total de elementos no vetor v e 
na 1ª. chamada da função, inicio igual a zero. 
 
int eureka(int v[], int inicio, int tam, int x) { 
 if (inicio == tam) 
 return -1; 
 if (v[inicio] == x) 
 return inicio; 
 return eureka(v,inicio+1,tam,x); 
} 
 
a) Realiza uma busca sequencial em v. 
b) Retorna 0 se x for zero 
c) Não compila, pois não tem caso base. 
d) Realiza uma busca binária em v. 
e) Apenas percorre o vetor v e retorna -1 em alguns casos. 
 
11. Considere a seguinte árvore binária : 
 
 
 
Assinale a opção que mostra a sequência impressa de acordo com o método pré-ordem : 
 
a) 40, 80, 26, 90, 13, 43, 75, 34, 55, 1, 5, 17 
b) 34, 80, 40, 43, 13, 26, 90, 75, 55, 5, 1, 17 
c) 40, 90, 26, 13, 75, 43, 80, 1, 17, 5, 55, 34 
d) 34, 80, 40, 43, 13, 75, 34, 55, 1, 5, 17 
e) 40, 90, 26, 13, 75, 43, 34, 80, 40, 43, 13, 5 
 
 Algoritmos Avançados – Prof. Ronaldo Candido 
 
4 
 
12. Relacione as duas colunas seguintes e marque a sequência correta: 
 
1) Árvore AVL ( ) Resolução de problemas complexos de conexão entre elementos. 
2) Percurso In-Order ( ) Cria um balanceamento entre os nós das subárvores. 
3) Árvore Binária ( ) Visita nó à esquerda  raiz  nó à direita. 
4) Grafo ( ) Cada nó possui de 0 a 2 filhos. 
5) Nó ( ) Guarda a informação e os ponteiros para a estrutura de dados usada. 
 
a) 2 - 1 - 4 - 3 - 5. 
b) 4 - 3 - 5 - 1 - 2. 
c) 5 - 3 - 1 - 2 - 4. 
d) 4 - 1 - 2 - 3 - 5. 
e) 3 - 4 - 1 - 5 - 2. 
 
13. Considere uma árvore binária em que cada nó é modelado pela struct : 
 
struct notree { 
 int dado; 
 notree *dir, *esq; } ; 
 
a) Escreva uma função recursiva para somar todos os dados da árvore, que pode ser vazia. 
 
 
 
 
 
 
 
 
 
 
b) Escreva uma função recursiva para retornar o endereço do menor elemento da árvore. 
 
 
 
 
 
 
 
 
14. Quantos nós possuirá uma árvore binária cheia com 128 folhas? 
 
a) 1024 b) 512 c) 511 d) 256 e) 255 
 
15. Considere uma árvore binária cheia com 7 nós. É possível afirmar que esta árvore: 
 
a) tem altura igual a três. 
b) tem três níveis. 
c) não se trata de uma árvore AVL. 
d) é uma árvore degenerada. 
e) possui Fator de Balanceamento igual a 1 em algum dos seus nós. 
 
 
 
 
 Algoritmos Avançados – Prof. Ronaldo Candido 
 
5 
 
16. Cite pelo menos 3 conceitos básicos sobre Árvores: 
 
 
 
 
 
 
17. Considere uma árvore binária, o tipo tree e a função misterio dados abaixo : 
 
struct tree { 
 int dado; 
 tree *esq; 
 tree *dir; 
}; 
 
tree *misterio(tree *r) { 
 tree *aux; 
 if (r == NULL) 
 return NULL; 
 aux = new tree; 
 aux->dado = r->dado; 
 aux->esq = misterio(r->esq); 
 aux->dir = misterio(r->dir); 
 return aux; } 
 
O que faz a função misterio ? 
 
a) Inverte a árvore de entrada, gerando outra árvore. 
b) Divide a árvore gerando duas novas árvores 
c) Gera uma árvore binária que é a cópia da árvore de entrada. 
d) Intercala os dados da árvore, obtendo uma árvore resultante. 
e) Expande a árvore, com mais subárvores. 
 
18. Considere uma árvore binária de busca, o tipo tree e a função eureka, dados abaixo : 
 
struct tree { 
 int dado; 
 tree *esq; 
 tree *dir; }; 
 
 void eureka (tree *nc) { 
 if (nc != NULL) { 
 eureka(nc->dir); 
 cout << nc->dado << " " ; 
 eureka(nc->esq); 
 } 
} 
 
Pede-se : O que faz a função eureka ? 
 
a) imprimeos dados da árvore em ordem decrescente. 
b) Imprime os dados da árvore de acordo com o percurso pré-ordem. 
c) imprime os dados da árvore em ordem crescente. 
d) imprime os dados da árvore segundo o percurso pós-ordem. 
e) imprime os dados da árvore um nível por vez. 
 
 Algoritmos Avançados – Prof. Ronaldo Candido 
 
6 
 
 
19. Pergunta: O algoritmo de Dijkstra utiliza a técnica de relaxamento e produz ao final de sua execução, 
uma árvore de caminhos mais curtos entre um vértice origem s e todos os vértices que são alcançáveis a 
partir de s. Certo ou Errado ? R: _____________________. 
 
 
20. Considere a seguinte árvore binária : 
 
 
 
 Assinale a opção que mostra a sequência impressa de acordo com o método pós-ordem : 
 
a) 40 43 80 55 34 
b) 34 80 40 43 55 
c) 34 80 55 40 43 
d) 40 80 43 34 55 
e) 55 34 43 80 40 
 
 
21. Um grafo é uma estrutura de dados consistida em um conjunto de nós (ou vértices) e um conjunto de 
arcos (ou arestas). O grafo em que os arcos possuem um número ou peso associados a eles, é chamado 
de grafo : 
 
a) predecessor b) adjacente c) incidente d) ponderado e) orientado 
 
 
22. Na teoria dos grafos, dois nós ligados por um arco são chamados de nós : 
 
a) parciais b) conexos c) adjacentes d) acíclicos e) fortemente conexos. 
 
 
23. O que é correto afirmar sobre árvore binária de busca (ABB) ? Assinale a opção correta: 
 
a) Estando balanceada ou não, todas as suas operações terão complexidade, no pior caso, O(log n). 
b) Todos os elementos à direita da raiz são maiores que a raiz, todos os elementos à esquerda da raiz 
são menores que a raiz e não há elementos repetidos. O mesmo ocorre para as subárvores direita e 
esquerda. 
c) É sempre balanceada. 
d) É sempre completa. 
e) É sempre cheia. 
 
 
24. Assinale a opção em que é apresentado exemplo de estrutura de informação do tipo abstrata, 
balanceada, não linear e com relacionamento hierárquico : 
 
a) árvore AVL b) vetor c) grafo d) fila e) árvore binária 
 
 
 
 
 
 Algoritmos Avançados – Prof. Ronaldo Candido 
 
7 
 
25. Complete o código a seguir para realizar as operações indicadas : 
 
// inserir nó na árvore binária 
Arv* inserir(Arv* aux, int num) 
{ // Se árvore está vazia 
 if (aux == NULL) 
 { // criar novo nó e definir que não tem filhos 
 ________________________________ 
 ________________________________ 
 ________________________________ 
 ________________________________ 
 } // senão inserir à esquerda se menor 
 else if (num < aux->numero) 
 ________________________________ 
 else 
 // senão inserir à direita 
 _______________________________ 
 return aux ; 
 } 
 
 
26. Defina uma struct necessária para um nó poder armazenar : um nome, os filhos esquerdo e direito, e as 
alturas esquerda e direita de uma árvore AVL : 
 
 
 
 
 
 
 
 
27. Nos grafos, quando um caminho é percorrido sem repetir os vértices, nem retornando ao mesmo ponto 
de origem, ele é chamado : 
 
a) ciclo b) trajeto c) conexo d) adjacência e) caminho simples 
 
 
28. Nos grafos, uma das buscas que percorre os vértices criando um centro e biparticiona as arestas do grafo 
em arestas de árvore e arestas de cruzamento é a busca: 
 
a) em largura b) binária c) sequencial d) em profundidade e) desconexa 
 
 
Fim da lista de exercícios