Prova de Estrutura de Dados II

Prévia do material em texto

Universidade Federal da Fronteira Sul
Cieˆncia da Computac¸a˜o
Estrutura de Dados II
Marcelo Cezar Pinto
Prova de Recuperac¸a˜o
Chapeco´, 12 de dezembro de 2014.
Respostas:
1. (2 pontos) Escreva uma func¸a˜o file2buffer com o proto´tipo indicado abaixo que
recebe:
• um ponteiro de arquivo f — considere que o arquivo esta´ aberto;
• um inteiro delta para ler o conteu´do do arquivo f a partir da posic¸a˜o atual
+delta;
• um vetor de caracteres b — o buffer — de tamanho size caracteres — na˜o
esquec¸a o espac¸o para o terminador ’\0’;
• um inteiro n que indica quantos caracteres ja´ esta˜o presentes no buffer b da
posic¸a˜o 0 a posic¸a˜o n-1.
A func¸a˜o deve devolver, se poss´ıvel, o buffer b totalmente preenchido a partir da
posic¸a˜o b[n] com o conteu´do do arquivo f a partir da posic¸a˜o atual deslocada em
delta bytes e devolver a quantidade de caracteres escritos no buffer de fato.
int file2buffer( FILE *f, int delta, char *b, unsigned int size, int n);
Soluc¸a˜o:
int file2buffer( FILE *f, int delta , char *b, unsigned int size ,
int n) {
int r = 0;
if ( size - n - 1 > 0 ) {
fseek(f, delta , SEEK_CUR);
r = fread(&b[n], 1, size -n-1, f);
b[n+r] = ’\0’;
if ( (r != size -n-1) && !feof(f) ) return 0;
return r;
}
return 0;
}
Universidade Federal da Fronteira Sul
Cieˆncia da Computac¸a˜o
Estrutura de Dados II
Marcelo Cezar Pinto
Prova de Recuperac¸a˜o
2. (2 pontos) Escreva uma func¸a˜o insertBST com o proto´tipo indicado abaixo que, se
o valor value passado como paraˆmetro na˜o esta´ na a´rvore bina´ria de busca com raiz
root, insere um novo no´ na a´rvore de forma que se value < root->v o no´ deve ficar
na suba´rvore esquerda da raiz e se value > root->v o no´ deve ficar na suba´rvore
direita da raiz; e assim recursivamente.
Entretanto, caso o valor value ja´ esteja na a´rvore, a func¸a˜o apenas aumenta em 1
sua quantidade no no´ cujo valor seja igual a value.
A func¸a˜o devolve 1 se um novo no´ foi criado, 0 se o no´ ja´ existia na a´rvore e -1 em
outras situac¸o˜es.
int insertBST( Tree **root, int value);
Use a seguinte estrutura de a´rvore:
typedef struct bstfreq {
int value, quantity;
struct bstfreq *p, *left, *right;
} Tree;
Soluc¸a˜o:
int insertBSTrec(Tree *n, int v);
Tree *newnodeBST( int v) {
Tree *n = NULL;
n = (Tree *) malloc( sizeof(Tree) );
if ( n != NULL ) {
n->value = v;
n->quantity = 1;
n->p = n->left = n->right = NULL;
}
return n;
}
int insertBST( Tree **root , int value) {
if ( *root == NULL ) {
*root = newnodeBST(value);
if ( *root == NULL ) return -1;
return 1;
}
return insertBSTrec (*root , value);
}
Universidade Federal da Fronteira Sul
Cieˆncia da Computac¸a˜o
Estrutura de Dados II
Marcelo Cezar Pinto
Prova de Recuperac¸a˜o
int insertBSTrec(Tree *n, int v) {
if ( v == n->value ) {
n->quantity ++;
return 0;
}
else if ( v < n->value ) {
if ( n->left != NULL ) return insertBSTrec(n->left , v);
n->left = newnodeBST(v);
if ( n->left == NULL ) return -1;
n->left ->p = n;
return 1;
}
else {
if ( n->right != NULL ) return insertBSTrec(n->right , v);
n->right = newnodeBST(v);
if ( n->right == NULL ) return -1;
n->right ->p = n;
return 1;
}
return -1;
}
/* Antes de usar a funcao insertBST , a *
* variavel root deve ser alocada assim: *
* Tree **root = NULL; *
* root = (Tree **) malloc(sizeof(Tree *)); *
* *root = NULL; */
3. (2 pontos) Considere um heap ma´ximo H e as seguintes operac¸o˜es poss´ıveis:
I x: insere o nu´mero x em H;
R: remove a raiz de H;
M: mostra o vetor que armazena H.
Para a sequeˆncia de operac¸o˜es a seguir escreva em um arquivo texto, para cada
operac¸a˜o M, o vetor que armazena o heap H no formato:
H 123 45 100 20 5 99 2 19
i 0 1 2 3 4 5 6 7
onde H[i] e´ o valor armazenado na posic¸a˜o i do vetor que repreesenta o heap.
Operac¸o˜es:
M
I 8
I 98
I 14
Universidade Federal da Fronteira Sul
Cieˆncia da Computac¸a˜o
Estrutura de Dados II
Marcelo Cezar Pinto
Prova de Recuperac¸a˜o
I 5
I 57
I 1
M
R
I 23
I 75
I 42
R
M
R
M
Soluc¸a˜o:
(heap vazio)
H
i
insere 8, 98, 14, 5, 57, 1;
H 98 57 14 5 8 1
i 0 1 2 3 4 5
remove 98; insere 23, 75, 42; remove 75;
H 57 42 23 8 1 14 5
i 0 1 2 3 4 5 6
remove 57;
H 42 8 23 5 1 14
i 0 1 2 3 4 5
4. (2 pontos) Considere uma tabela hash de tamanho m = 1000 e uma func¸a˜o hash
correspondente h(k) = bm(kA mod 1)c para A = (√5−1)/2. Escreva em um arquivo
texto os locais em que as chaves 61, 62, 63, 64 e 65 sera˜o mapeadas.
Respostas sem apresentar os ca´lculos recebem nota zero.
Soluc¸a˜o:
h(k) = piso( 1000*( 0,618033989*k mod 1 ) )
A funcao x mod 1 remove a parte inteira de x,
deixando apenas a parte fracionaria.
Universidade Federal da Fronteira Sul
Cieˆncia da Computac¸a˜o
Estrutura de Dados II
Marcelo Cezar Pinto
Prova de Recuperac¸a˜o
h(61) = piso( 1000*( 37,700073314 mod 1 ) )
h(61) = piso( 1000 * 0,700073314 )
h(61) = piso( 700,073314 )
h(61) = 700
h(62) = piso( 1000*( 38,318107302 mod 1 ) )
h(62) = piso( 1000 * 0,318107302 )
h(62) = piso( 318,107302 )
h(62) = 318
h(63) = piso( 1000*( 38,936141291 mod 1 ) )
h(63) = piso( 1000 * 0,936141291 )
h(63) = piso( 936,141291 )
h(63) = 936
h(64) = piso( 1000*( 39,55417528 mod 1 ) )
h(64) = piso( 1000 * 0,55417528 )
h(64) = piso( 554,17528 )
h(64) = 554
h(65) = piso( 1000*( 40,172209269 mod 1 ) )
h(65) = piso( 1000 * 0,172209269 )
h(65) = piso( 172,209269 )
h(65) = 172
5. (2 pontos) Calcule a ordem p dos no´s internos e a ordem pf dos no´s folha de uma
a´rvore B+ onde o tamanho de um bloco e´ 1024 bytes, ponteiros de dados ocupam 8
bytes, ponteiros de a´rvore ocupam 4 bytes e cada chave utiliza 12 bytes.
Escreva estes resultados em um arquivo texto juntamente com a altura da a´rvore
— lembre-se: a raiz esta´ na altura zero! — para armazenar 25 mil chaves distintas
quando os no´s esta˜o 75% cheios.
Respostas sem apresentar os ca´lculos recebem nota zero.
Soluc¸a˜o:
B = 1024
Pa = 4
Pd = 8
K = 12
Universidade Federal da Fronteira Sul
Cieˆncia da Computac¸a˜o
Estrutura de Dados II
Marcelo Cezar Pinto
Prova de Recuperac¸a˜o
Nos internos:
p*Pa + (p-1)*K <= B
4p + 12(p-1) <= 1024
16p <= 1024 + 12
p <= 1036/16 = 64,75
p = 64
Nos folha:
pf*(K + Pd) + Pa <= B
(12+8)pf + 4 <= 1024
20pf <= 1024 - 4
pf <= 1020/20 = 51
pf = 51
Nos internos a 75% de ocupacao:
0,75*p = 0,75*64 = 48 ponteiros ocupados por no
Nos folha a 75% de ocupacao:
0,75*pf = 0,75*51 = 38,25 ponteiros ocupados por no
25000 chaves ocupam 654 nos folha (25000/38,25 = 653,6).
Cada no interno aponta para 48 nos folha. No nivel imediatamente
acima das folhas, existem 14 nos internos (654/48 = 13,6).
O proximo nivel e a raiz pois os 14 nos internos ocupam
somente 1 no interno (14/48 = 0,3).
Assim, a arvore tem altura 2.