Treino Prova EDA

UCB - Universidade Católica de Brasília
Bacharelado em Ciência da Computação
Estrutura de Dados e Arquivos - Código 102011 Treino Prova 2

Questão 1
Construa a árvore balanceada AVL de inteiros, mostrando cada passo, para a seqüência: 6, 1, 5, 0.,2, 13, 33, 35,57,60, 58
Questão 2
Considerando a seguinte estrutura de nós para a árvore AVL do exercício anterior: typedef struct s_cel{ int val,alt; struct s_cel *esq,*dir;
} cel;
Mostre o resultado da execução da seguinte rotina caso seja passado como parâmetro a raiz da árvore construída na questão 1: int mostra(cel *esse) { int cont; if(esse==NULL) return 0; cont=esse->val; cont+=mostra(esse->esq); cont+=mostra(esse->dir); printf(“Subarvore em %d = %d\n“,esse->val,cont); return cont;
}
Questão 3
Escreva uma rotina que receba a raiz de uma árvore cujos nós têm a estrutura definida no exercício 2 e que calcule a altura de cada nó registrando o resultado no campo alt da estrutura.

//Calcula a altura de cada nó da ávore registrando o resultado
//no campo alt da estrutura. int altura( cel *r) { if (r == NULL) return -1; // altura de árvore vazia é -1 else { int he = altura( r->esq); int hd = altura( r->dir); if (hd > he) { r->alt = (hd + 1); return (hd + 1); } else { r->alt = (he + 1); return (he + 1); } }
}

Questão 4
Explique o conceito do espalhamento (hash) e em particular como lidar com as colisões.

As questões 5 e 6 se referem ao seguinte problema: os valores de uma matriz de inteiros foram indexados por uma árvore binária de busca. Cada nó da árvore se refere a um número que aparece na matriz. No nó o campo num representa o número da matriz e inicio indica o ínicio de uma lista encadeada. Nessa lista encadeada estão registrados as posições onde esse número