-
Notifications
You must be signed in to change notification settings - Fork 2
/
P3
172 lines (155 loc) · 5.31 KB
/
P3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
1. [0,5] Analise as afirmações e indique a alternativa correta:
I. Toda árvore binária é também uma árvore de busca binária.
II. Toda árvore de busca binária é também uma árvore binária.
III. Numa árvore completa todas as folhas estão no mesmo nível.
(a) Apenas as afirmações I e II são verdadeiras.
(b) Apenas as afirmações I e III são verdadeiras.
(X) Apenas as afirmações II e III são verdadeiras.
(d) Nenhuma das anteriores.
2. [0,5] A respeito do programa a seguir, é correto afirmar que:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
struct node *left;
int item;
struct node *right;
} *Tree;
Tree tree(Tree left, int item, Tree right) {
Tree new = malloc(sizeof(struct node));
new->left = left;
new->item = item;
new->right = right;
return new;
}
void print(Tree T, int h) {
if( T==NULL ) return;
print(T->right, h+1);
printf("%*s%d\n", 3*h, "", T->item);
print(T->left, h+1);
}
int main(void) {
Tree A = tree(tree(tree(NULL,1,NULL),
2,
tree(NULL,3,NULL)),
4,
tree(tree(NULL,7,NULL),
5,
tree(NULL,6,NULL)));
print(A,0);
return 0;
}
(a) A árvore apontada por A é uma árvore de busca binária.
(x) A função print() percorre a árvore em ordem inversa.
(c) A função print() percorre a árvore em ordem direta.
(d) Ele não pode ser compilado e executado corretamente.
3. [0,5] Que composição da função tree(), definida na Questão 2,
cria a árvore binária ilustrada a seguir?
1
/
2
\
3
(a) tree(NULL,1,tree(NULL,2,tree(NULL,3,NULL))).
(X) tree(tree(NULL,2,tree(NULL,3,NULL)),1,NULL).
(c) tree(tree(NULL,2,NULL),1,tree(NULL,3,NULL)).
(d) Nenhuma das anteriores.
4. [0,5] Se T aponta o ponteiro que aponta a raiz de uma árvore binária não vazia, que instrução exibe o item da raiz dessa árvore?
(X) printf("%d",(*T)->item).
(b) printf("%d",*T->item).
(c) printf("%d",T->item).
(d) printf("%d",*T.item).
5. [0,5] Num percurso do tipo pré-ordem, em que ordem os nós da
árvore binária a seguir são visitados?
1
/ \
2 6
/ \ /
4 5 3
(a) 1, 2, 6, 4, 5, 6.
(b) 1, 6, 3, 2, 5, 4.
(X) 1, 2, 4, 5, 6, 3.
(d) Nenhuma das anteriores.
6. [0,5] Que sequência de inserções, em uma árvore inicialmente
vazia, resulta na criação da árvore de busca binária a seguir?
3
/ \
2 5
/ / \
0 4 8
\ /
1 7
/
6
(a) 3, 5, 4, 2, 8, 0, 6, 1, 7.
(b) 3, 2, 5, 4, 8, 1, 7, 0, 6.
(c) 3, 2, 0, 1, 5, 8, 4, 6, 7.
(X) 3, 5, 4, 2, 8, 0, 7, 1, 6.
7. [1,0] A função make(v,i,j) deve criar uma árvore binária balanceada com os itens do subvetor v[i..j]. Mostre como as lacunas nesta função, marcadas com ♥, ♦, ♣ e ♠, devem ser completadas para que o programa gere a saída dada na figura ao lado.
#include <stdio.h>
#include <stdlib.h>
… // tipos e funções definidos na Questão 2
Tree make(int v[], int i, int j) {
if( i>j ) return NULL;
int m = (i+j)/2;
return tree(make(v,♥,♦),v[m],make(v,♣,♠));
}
int main(void) {
int v[7] = {10,20,30,40,50,60,70};
Tree A = make(v,0,6);
print(A,0);
return 0;
}
♥ = i
♦ = m-1
♣ = m+1
♠ = j
8. [2,0] Usando o tipo Tree e a função tree(), definidos na Questão 2, crie a função recursiva mirror(T), que devolve uma cópia
espelhada da árvore binária cuja raiz é apontada pelo ponteiro T. Por exemplo, depois de completado corretamente com esta função e
demais definições necessárias, o programa a seguir deverá produzir a saída indicada na figura ao lado.
#include <stdio.h>
#include <stdlib.h>
…
int main(void) {
Tree A = tree(tree(tree(NULL,1,NULL),2,NULL),3,tree(NULL,4,NULL));
print(A,0);
puts("-------");
print(mirror(A),0);
return 0;
}
Tree mirror(Tree A){
if (A==NULL) return NULL;
return tree(mirror(A->right), A->item, mirror(A->left)) ;
}
9. [2,0] Usando o tipo Tree, definido na Questão 2, crie a função recursiva minimum(T), que devolve o item mínimo de uma árvore de
busca binária cuja raiz é apontada pelo ponteiro T. Por exemplo, depois de completado corretamente com esta função e demais
definições necessárias, o programa a seguir deverá produzir a saída indicada no comentário.
#include <stdio.h>
#include <stdlib.h>
…
int main(void) {
Tree A = tree(tree(tree(NULL,1,tree(NULL,2,NULL)),3,NULL),4,tree(NULL,5,tree(NULL,6,NULL)));
printf("Minimum item: %d\n",minimum(A)); // deve exibir Minimum item: 1
return 0;
}
int minimum(Tree A) {
if( A == NULL ) abort();
if( A->left == NULL ) return (A)->item;
return minimum(A->left);
}
10. [2,0] Usando o tipo Tree, definido na Questão 2, crie a função recursiva leaves(T), que exibe em ordem crescente apenas os itens
que são folhas na árvore de busca binária cuja raiz é apontada pelo ponteiro T. Por exemplo, depois de completado corretamente com
esta função e demais definições necessárias, o programa a seguir deverá produzir a saída indicada no comentário.
#include <stdio.h>
#include <stdlib.h>
…
int main(void) {
Tree A = tree(tree(tree(NULL,1,NULL),2,tree(NULL,3,NULL)),4,tree(NULL,5,tree(NULL,6,NULL)));
leaves(A); // deve exibir 1 3 6
return 0;
}
void leaves(Tree A) {
if( A==NULL ) return;
leaves(A->left);
if (A->left == NULL && A->right == NULL) printf("%d ",A->item);
leaves(A->right);
}