Prova 2-2022 1

Prova 2 – Estruturas de Dados (INE5408) – 22mar2022 Ciˆencia da Computa¸c˜ao – Universidade Federal de Santa Catarina Estudante: ⇨ ξ = ξ = ( α + β + γ ) mod 4 β α γ ⇨ Defina em função dos últimos três dígitos de sua matrícula: x 1. (2,5pt) Uma matriz ´e dita esparsa se possui uma quantidade relativamente grande de valores iguais a zero. Para represent´a-la, optou-se pela utiliza¸c˜ao de listas cruzadas, conforme o exemplo e c´odigo a seguir: 0 1 Exemplo de matriz esparsa e listas cruzadas: H W W H L C 0 0 0 0 0 0 0 9 0 0 0 3 0 0 0 0 0 0 0 2 4 0 7 0 0 0 0 0 0 0 3 7 9 4 2 0 5 2 2 0 1 2 3 4 5 0 1 2 3 4 2 5 4 2 class Esparsa { public: Esparsa(float **matriz, int H_, int W_); ~Esparsa(); struct No { No(int x_, int y_, float v_); int x; // linha int y; // coluna float v; // valor No* inf; // pont. no' de baixo No* dir; // pont. no' à direita }; int H; // altura da matriz int W; // largura da matriz No **C; // vetor 'coluna' No **L; // vetor 'linha' }; float **matriz; Código das estruturas de dados: De posse de um objeto do tipo Esparsa, previamente constru´ıdo e referenciado por um ponteiro p, escreva uma fun¸c˜ao (c´odigo; ou pseudoc´odigo detalhado) que devolva (utilize apenas os atributos da classe acima): ˆ Para alunos com ξ = 0: – A quantidade de linhas com soma de valores maior do que a media da matriz esparsa. 2. A figura a seguir ´e uma AVL. Cada triˆangulo (A, B, C e D) representa uma sub´arvore completa (ou seja, com todos os n´ıveis preenchidos, de modo que qualquer inser¸c˜ao acarrete um acr´escimo de sua altura). Sabe-se ainda que as alturas das sub´arvores A, B, C e D s˜ao, respectivamente, h + 1, h, h e h + 1. Pede-se: y x D z C h + 1 h h h + 1 A B (a) (0,5pt) Calcule o fator de balanceamento (diferen¸ca entre alturas de suas duas sub´arvores) para os n´os x, y e z. (b) (1,5pt) Desenhe a AVL novamente, supondo que ocorra: ˆ Para alunos com ξ = 0 – Uma insercao na sub arvore B. 3. (2,5pt) Considerando a seguinte estrutura de n´o de ´Arvore-B, sendo M igual ao n´umero m´aximo de ponteiros para filhos (como exemplo, no desenho, M = 5): template <class T, int M> class BTreeNode { public: BTreeNode(); BTreeNode(const T&); private: bool leaf; // verdadeiro se folha int size; // nº chaves inseridas T keys[M-1]; // vetor de chaves BTreeNode *pointers[M]; }; De posse de um ponteiro para a raiz de uma ´Arvore-B, implemente um algoritmo (c´odigo; ou pseudoc´odigo deta- lhado) que calcule: ˆ Para alunos com ξ = 0: – A quantidade de nos folhas totalmente cheios. 4. Dado o algoritmo BuildMaxHeap() para a constru¸c˜ao de um heap de m´aximo, pede-se: // apresentar o conteúdo de A // troca (a) (1,0pt) O conte´udo do vetor A para cada valor de i na linha 3 de BuildMaxHeap(). (b) (1,0pt) O n´umero total de trocas (linha 9 de Max-Heapify()) para a finaliza¸c˜ao do m´etodo. (c) (1,0pt) Disserte sobre a complexidade de BuildMaxHeap(). Para responder aos itens (a) e (b), considere o seguinte vetor A de entrada: ˆ Para alunos com ξ = 0: A = [ 50, 20, 70, 15, 5, 10, 60, 30, 25, 80 ]