Técnicas em Programação

Prévia do material em texto

UNIVERSIDADE FEDERAL DE RORAIMA 
UNIVERSIDADE ABERTA DE RORAIMA 
LICENCIATURA EM INFORMÁTICA 
ACADÊMICA: DENISE SHARON BACCHUS 
 
 
 
 
 
 
ATIVIDADE 05 
 
 
 
 
 
TÉCNICAS EM PROGRAMAÇÃO 
 
 
 
 
 
 
 
BOA VISTA 
2016.1 
 
COMPILADOR USADO GNU/GCC COMPILER. 
 
5ª Atividade 
1. (Valor: 1,0 pontos) Descreva a principal diferença entre a estrutura de dados 
árvore e as estruturas listas, pilhas e filas. 
As estruturas de dados listas, pilhas e filas comumente apontam para um elemento 
(o próximo). Encontram-se listas duplamente encadeadas, que cada elemento está ligado 
com o anterior e o próximo, contudo todas elas são lineares, formam uma sequência 
única. Agora as árvores não, pois cada elemento pode estar ligado em um ou mais 
elemento, formando assim uma sub-árvore, e cada uma destas pode formar outras, ou 
seja, há uma infinidade de caminhos e possibilidades para estruturas desse tipo. 
2. (Valor: 1,0 pontos) Descreva e caracterize uma árvore binária. 
A árvore binária possui uma estrutura de dados que se caracterizada por: Ou não 
tem elemento algum (árvore vazia). Ou tem um elemento distinto, denominado raiz, 
com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e 
sub-árvore direita. 
 Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau 
zero é denominado folha. Em uma árvore binária, por definição, cada nó poderá ter até 
duas folhas, sendo que ela se compara com a ABB (árvore binária de busca), apesar de 
não ter a propriedade da mesma ("na abb, existe uma regra na inserção"). 
A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a 
mesma profundidade é denominado nível da árvore. A maior profundidade de um nó é 
a altura da árvore. Uma árvore "estritamente binária" é uma árvore na qual todo nó tem 
zero ou duas folhas. 
 
3. (Valor: 1,0 pontos) O código que implementa o seguinte percurso em uma 
árvore: 
void 
arvore_impri
me(NO* n){ if 
(!arvore_vazia
(n)){ 
arvore_imprime(n-
>esquerda); 
printf("%d ", n-
>info); 
arvore_imprime(n-
>direita); 
} 
} 
Que tipo de percurso é executado pela função void arvore_imprime(NO* n)? 
 Em ordem. 
wB) Em pré-ordem. 
 C) Em pós-ordem. 
 D) Em ex-ordem. 
E) Ordenado pelo valor de info 
4. (Valor: 1,0 pontos) Preencha os campos em branco na função (int folhas (Arv* 
a)) escrita em C abaixo que retorna a quantidade de folhas de uma árvore binária. 
 int folhas1’ (Arv* a) 
 { 
 
 if (arv_vazia(a->esq) && arv_vazia(a->dir)) 
 return 1; 
 else if (!arv_vazia(a->esq) && arv_vazia(a->dir)) 
 return folhas(a->esq); 
 else if (arv_vazia(a->esq) && !arv_vazia(a->dir)) 
 return folhas(a->dir); 
 return folhas(a->esq) + folhas(a->dir); 
 } 
5. (Valor: 1,0 pontos) Considere uma árvore binária que representa expressões 
matemáticas, conforme figura abaixo. Por exemplo, as folhas da árvore 
armazenam operando e os nós internos operadores. Se avaliada a expressão (6 - 
3) * (4 + 1) + 5, esta expressão resulta no valor 20. 
 
Considere a existência do tipo abaixo usado para representar árvores binárias de 
expressões. 
struct arv { 
char op; //operador '+'. '-', '*' ou '/' 
int valor; //valor do operando 
struct arv *esq, *dir; 
}; 
typedef struct arv Arv; 
Onde o campo valor é usado apenas pelas folhas e o campo op pelos nós internos. 
Escreva funções que, dada à raiz de uma árvore binária de expressões (pode-se 
considerar que a árvore nunca será vazia): 
(A) Imprima a expressão em notação pós-fixada ou pós-ordem. Para exemplo 
acima, imprimiria: 6 3 - 4 1 + * 5 + . O protótipo da função deve ser: void 
imprime (Arv* a); 
void imprime(Arv* a) 
{ 
 /* supõe expressão não vazia */ 
 if ((a->esq == NULL) && (a->dir == NULL)) 
 printf(“%g”,a->valor); 
 else { 
 imprime(a->esq); 
 imprime(a->dir); 
 printf(“%c”,a->op); 
 } 
} 
(B) Retorne o valor correspondente à avaliação da expressão (para o exemplo 
acima, o retorno da função seria o resultado 20). O protótipo da função deve 
ser: int avalia (Arv* a); 
int avalia(Arv* a) 
{ 
 /* supõe expressão não vazia */ 
 if ((a->esq == NULL) && (a->dir == NULL)) 
 return a->valor; 
 else { 
 if(a->op == „+‟) return avalia(a->esq) + avalia(a->dir); 
 if(a->op == „-‟) return avalia(a->esq) - avalia(a->dir); 
 if(a->op == „*‟) return avalia(a->esq) * avalia(a->dir); 
 if(a->op == „/‟) return avalia(a->esq) / avalia(a->dir); 
 } 
}