Lista de Exercício AV1_Parte 1doc-convertido

Prévia do material em texto

Faculdade Estácio de Belém Disciplina: Algoritmos Avançados Professora: Larissa Luz Gomes Turma: 1001_manhã
Aluno(a): 	
Lista de Exercício_AV1 – Parte 1
1) Considere a função recursiva F a seguir, que em sua execução chama a função G 1 void F(int n) {
2	if(n > 0) {
3	for(int i = 0; i < n; i++) { 4		G(i);
5	}
6	F(n/2);
7	}
8 }
Com base nos conceitos de teoria da complexidade, avalie as afirmações a seguir.
I. A equação de recorrência que define a complexidade da função F é a mesma do algoritmo clássico de ordenação mergesort.
II. O número de chamadas recursivas da função F é Θ(log n)Θ(l og n).
III. O número de vezes que a função G da linha 4 é chamada é O(n log n)O(n log n). É correto o que se afirmar em:
a) I, apenas.
b) II, apenas.
c) I e III, apenas.
d) II e III, apenas.
e) I, II e III.
2) O que determina uma árvore AVL possuir valores -1, 0 e +1 em qualquer circunstância entre seus nós?
a) Nós folhas.
b) Fator de balanceamento.
c) Struct.
d) Ordenação.
e) Peso das arestas.
3) Suponha que T seja uma árvore AVL inicialmente vazia, e considere a inserção dos elementos 10, 20, 30, 5, 15, 2 em T, nesta ordem. Qual das sequências abaixo corresponde a um percurso de T em pré- ordem:
a) 10, 5, 2, 20, 15, 30
b) 20, 10, 5, 2, 15, 30
c) 2, 5, 10, 15, 20, 30
d) 30, 20, 15, 10, 5, 2
e) 15, 10, 5, 2, 20, 30
4) Analisando o algoritmo de rotação abaixo, qual é a rotação que ela faz em nó:
void rot_dir(NO p){ NO q, temp;
q = p->esq; temp = q->dir; q->dir= p;
p->esq= temp; p = q;
}
5) Assinale a opção correta. Sobre o Mergesort é correto afirmar que:
a) É uma ordenação por intercalação que no pior caso tem complexidade O(n2)
b) É uma ordenação por trocas que no pior caso tem complexidade O(nlog2 n)
c) É uma ordenação por intercalação que no pior caso tem complexidade O(nlog2 n)
d) Só pode ser implementado de forma recursiva.
e) Trabalha com um pivô para permitir a intercalação, sendo que este pivô é o elemento central da lista.
6) 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) pilha
b) árvore AVL
c) deque
d) lista duplamente encadeada
e) árvore binária
7) 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
8) Considere uma árvore binária cheia com 7 nós. É possível de se 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.
9) Analisando a Complexidade do Merge Sort. Consideramos " n "(número de dados a serem ordenados) uma potência de 2 e a seguinte equação de recorrência, T(n) é o tempo para uma entrada de tamanho n.
T(1)=1(caso base) T(n)=2T(n/2)+3(n-1)
Temos 2 chamadas recursivas como n/2 e um total de 3(n-1) intercalações por aproximação vamos considerar n intercalações. Sendo assim faz sentido escrever
T(n) = 2T(n/2) + n
Uma vez que podemos substituir n/2 na equação principal. 2T(n/2) = 2(2T(n/4) + n/2)
2T(n/2) = 4T(n/4) + n
Logo:
T(n) = 2T(n/2) + n
T(n) = 4T(n/4) + n + n T(n) = 4T(n/4) + 2n
Assim se continuarmos a análise da equação, chegaremos a conclusão que a complexidade de pior caso para o MergeSort é
a) O(n)
b) O(n^2) onde n^2 é n elevado a 2
c) O(1)
d) O(n lg n) , onde lg é log na base 2
e) O(log n)
10) Qual a finalidade da análise de um algoritmo?
a) Digitação de menos código e consequentemente, menos trabalho.
b) Melhorar o algoritmo e melhor desempenho do algoritmo.
c) Obter uma saída de dados independente da entrada de dados.
d) Poder ser expresso em qualquer linguagem de programação.
e) Uso exclusivo da recursão no algoritmo.
11) Do ponto de vista de projeção de algoritmos, quais são as questões mais importantes?
a) corretude, eficiência, robustez e reusabilidade
b) corretude, eficiência, robustez e recursividade
c) corretude, eficiência, robustez e versatilidade
d) corretude, independência, robustez e autenticidade
e) corretude, independência, robustez e recursividade
12) O algoritmo abaixo aborda qual algoritmo de ordenação ? void funcao(int X[], int inicio, int fim) {
int meio;
if (inicio < fim){
meio = (inicio + fim )/2; funcao(X, inicio, meio); funcao(X,meio+1, fim); intercala(X, inicion, fim, meio);
}
}
a) Merge Sort
b) Bubble Sort
c) Insert Sort
d) Quick Sort
e) Selection Sort