prova1-2017-Revisao

Prévia do material em texto

URI-Campus de Erechim Prova 1 de Algoritmos e E.D. III prof. Neilor 16/10/2015 Nome: _______________
1) Assinale a alternativa correta que corresponde respectivamente aos percursos prefixo, infixo e posfixo da árvore abaixo:
2 ) Circule a alternativa abaixo que representa a expressão (A-B/C+2/A) * (B*(3+C)/(2*A)) através de uma árvore. 
3) Assinale a alternativa que representa a árvore abaixo
4) Construa uma árvore binária de pesquisa (ABP) com o conjunto de números: {17, 27, 104 , 23, 9, 80, 143, 2, 12}. 
Insira-os na árvore por ordem de ocorrência.
5) Considerando uma árvore B de ordem 4 com tendência esquerda, mostre como a mesma ficaria após a inserção dos elementos:
16,1,17,8,34,12,14,18,20,60,22,13,6
K
C
N
J
O
I
A
B
F
G
D
M
 a) a,b,c,d,f,i,j,m,g,n,k,o - d,b,m,f,g,a,n,i,k,c,j,o - d,m,g,f,b,n,k,i,o,j,c,a 
 b) a,b,d,f,m,g,c,i,n,k,j,o - d,b,m,f,g,a,n,i,k,c,j,o - d,m,g,f,b,n,k,i,o,j,c,a 
 c) a,b,d,f,m,g,c,i,n,k,j,o - d,b,m,f,g,a,n,i,k,c,j,o - d,b,m,g,f,n,k,i,c,o,j,a 
 d) a,b,d,f,m,g,c,i,n,k,j,o - d,b,m,f,g,a,n,i,k,c,j,o - d,m,g,f,b,n,k,i,c,o,j,a 
 e) a,b,c,f,m,g,c,i,n,k,j,o - d,m,g,f,b,a,n,i,k,c,j,o - d,m,g,f,b,n,k,i,o,j,c,a
 f) a,b,c,d,f,i,j,m,g,n,k,o - d,m,g,f,b,n,k,i,o,j,c,a - d,m,g,f,n,k,i,o,j,b,c,a
 g) a,b,d,f,m,g,c,i,n,k,j,o - d,b,m,f,g,n,i,k,j,o,c,a - d,m,g,f,b,n,k,i,o,j,c,a 
 h) a,b,d,f,m,g,c,i,n,k,j,o - d,b,m,f,g,n,i,k,j,o,c,a - d,b,m,g,f,n,k,i,c,o,j,a 
 i) a,b,c,d,f,i,j,m,g,n,k,o - d,m,g,f,b,a,n,i,k,c,j,o - d,m,g,f,b,n,k,i,o,j,c,a 
 j) a,b,c,d,f,i,j,m,g,n,k,o - d,m,g,f,b,n,k,i,o,j,c,a - d,m,g,f,b,n,k,i,o,j,c,a 
 k) N.D.A
 
K
^
N
O-
*
/
+
G
D
M
a
+
2 3
/
*
-
/
c
a
b
*
+
2
*
/
c a
b
a
+
2
3
/
*
-
/
c
a
b
*
+
2
*
/
c a
b
a
+
2 3
/
*
-
/
c
a
b
+ 2
*
/
c
ab
*
a
+
2
3
/
*
-
/
c
a
b
+ 2
*
/
c
ab
*
e) N.D.Aa) b) c)
d)
a) D/M+G*(N-K^O) 
b) D/(M+G)*(N-K^O) 
c) (M+G)/D*(N-K)^O 
d) D/(M+G)*(N-K)^O 
e) D/M+G*(N-K)^O 
6) Considerando o arquivo de dados abaixo, apresente a árvore de indexação por código desse arquivo. (1.4 pontos)
 Obs.: Os registros foram inseridos nos índices na sequência em que foram gravados no arq. de dados.
 E# CÓD. NOME ... 
0 7 André ...
1 6 Marcos
2 4 Pedro ...
3 8 Juca ...
4 2 Paulo ...
5 1 Maria ...
6 9 Silvana ...
7 14 Márcia ...
8 3 Luciana ...
9 10 Ivanir ...
7) Considerando árvore de índice por nome apresentada abaixo, à direita, como seria o arquivo de dados que a originou? 
Preencha abaixo as posições físicas da árvore que estiverem faltando. 
 E# CÓD. NOME ...
0 ...
1
2 ...
3 ...
4 ...
5 ...
6 ...
7 ...
8 ...
9 ...
8) Com relação à exclusão de um nodo de uma árvore binária de pesquisa, implementada em laboratório:
Elimine a letra “C” e a letra “H” da árvore abaixo, apresentando-a no lado direito após a operação. 
 0 Elisa
 1 Caio 5 Gilda
 Ana 2 Delmar Fabiane 7 Valdo
 Beatriz Tiago
E
H13C
A IF
GB
9) Com base nessas informações e supondo que a raiz de uma árvore binária com n nós seja passada ao procedimento preordem(), 
julgue os itens seguintes. 
I O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso.
II O algoritmo só funcionará corretamente se o procedimento pop()for projetado de forma a retornar λ caso a pilha esteja vazia.
III Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser implementadas com custo constante.
IV A complexidade do pior caso para o procedimento preordem() é O(n).
Assinale a opção correta.
(A) Apenas os itens I, II e III estão certos.
(B) Apenas os itens II, III e IV estão certos.
(C) Apenas um item está certo.
(D) Apenas os itens I e IV estão certos.
(E) Todos os itens estão certos.
10) POSCOMP Dadas as seguintes características para uma Arvore B de ordem n: (página é o mesmo que nodo)
(I) Toda página contém no máximo 2n itens (chaves).
(II) Toda página, exceto a página raiz, contém no mínimo (n-1)/2 itens.
(III) Toda página ou e uma página folha, ou tem m + 1 descendentes, onde m e o número de chaves.
(IV) Todas as páginas folhas aparecem no mesmo nível.
Qual das seguintes opções e verdadeira:
(a) As características (I), (II), (III) e (IV) são falsas.
(b) As características (I) e (IV) são verdadeiras.
(c) As características (II), (III) e (IV) são verdadeiras.
(d) As características (I), (II), (III) e (IV) são verdadeiras.
(e) As características (II), (III) e (IV) são falsas
11) POSCOMP Dadas as seguintes características para uma Arvore B de ordem n: (página é o mesmo que nodo)
35. Em uma estrutura de arvore binaria de busca, foram inseridos os elementos \h",\a",\b", \c",\i",\j", nesta sequencia. O tamanho do 
caminho entre um no qualquer da árvore e a raiz e dado pelo número de arestas neste caminho. Qual o tamanho do maior caminho na 
arvore, apos a inserção dos dados acima?
(a) 6 (b) 4 (c) 5 (d) 3 (e) 2
12) POSCOMP Arvores binarias podem ser usadas para guardar e recuperar informações com número de operações proporcional à 
altura da arvore. Quais das seguintes figuras representam árvores binárias de altura balanceada ou do tipo AVL (Adelson-Velski e 
Landis). Teorema “Em uma árvore AVL, as alturas das duas sub-árvores a partir de cada nó difere no máximo em uma unidade” 
(a) Somente (I) e (IV) são arvores binarias AVL.
(b) Somente (I) e arvore binaria AVL.
(c) Somente (I), (II) e (III) são arvores binarias AVL.
(d) Somente (II) e (III) são arvores binarias AVL.
(e) Todas (I), (II), (III) e (IV) são arvores binarias AVL.
13) Árvore binária é uma estrutura de dados adequada à representação de hierarquia, sendo usada frequentemente em ordenação e 
pesquisa. Para a busca em um vetor ordenado, pode-se utilizar o algoritmo de busca binária, o qual não exige a implementação de uma 
árvore binária. 
( ) Certo
( ) Errado
14)
Analise as afirmativas. 
I. A árvore é uma estrutura linear que permite representar uma relação de hierarquia. Ela possui um nó raiz e subárvores não vazias. 
II. Na árvore binária o percurso permite a obtenção da sequência linear de seus nós. Na árvore binária de busca, um dos percursos 
permite que os nós sejam obtidos de forma ordenada. 
III. O processo de balanceamento (estático ou dinâmico) otimiza a busca em árvores binárias, minimizando sua altura. 
IV. Uma árvore-B não pode ser usada para armazenamento de dados em disco, pois necessita de um número maior de nós (maior 
altura) quando comparada a uma árvore binária. 
Está correto o que se afirma em
a) I, II, III e IV.
b) II e III, apenas.
c) I e II, apenas.
d) III e IV, apenas.
e) II, apenas.
15)
As operações de busca em uma árvore binária não a alteram, enquanto operações de inserção e remoção de nós 
provocam mudanças sistemáticas na árvore.
( ) Certo
( ) Errado
16)
Considerando-se como ponto de partida a raiz de uma árvore balanceada qualquer, o número de descendentes da esquerda e de 
descendentes da direita é igual.
( ) Certo
( ) Errado
17)
O tipo de dados árvore representa organizações hierárquicas entre dados.
( ) Certo
( ) Errado
18)
Qual Figura representa uma árvore AVL?
19)
A figura a seguir representa uma árvore
Uma função irá percorrê-la em ordem simétrica, inserindo seus nós em uma pilha (implementada sobre uma lista 
encadeada) à medida que eles forem sendo visitados. A pilha criada por essa função é
20) Construa na direita a rotina retira, com base na rotina *insere, que está abaixo
struct nodo *insere ( nodo *tree, TIPO informacao ) {
 if ( tree == NULL )
 tree = new nodo (informacao);
 else if ( informacao < tree->informacao)
 tree->esquerda = insere(tree->esquerda, informacao);
 else if ( informacao > tree->informacao )
 tree->direita = insere(tree->direita, informacao);
 return tree;
}