MAC 710 - Estruturas de Dados - 1.a Prova - 13 de maio de 1997
Nome: ___________________________________________________________________ Nota: _______

1. (2 pontos) Voce quer usar uma estrutura de dado para armazenar uma matriz A, de ordem .

   Suponha as seguintes operações que manipulam a matriz:

   (a) acessar o elemento A[i,j] dados i e j.

   (b) acessar todos os elementos não nulos de uma linha de A.

   (c) acessar todos os elementos não nulos de uma coluna de A.

   Que tipo de estrutura de dados e que tipo de alocação (sequencial ou ligada) voce usaria em cada caso seguinte:

   (a) a matriz é esparsa (e.g. contém no máximo 50 elementos não nulos)?

   (b) a matriz é densa (e.g. contém no mínimo 8000 elementos não nulos)?

   Não precisa escrever nenhum algoritmo, apenas dê uma descrição sucinta da estrutura de dado proposta.

2. (2.5 pontos) Considere o esquema de coleta de lixo usando contador de referências, onde cada nó contém os campos count, llink e rlink, onde count é um contador de referências ao nó, llink e rlink são ponteiros. Escreva a rotina Aterra-apontador(p), onde p é um apontador, que coloca nil no apontador p. Aterra-apontador deve fazer o que é necessário para atualizar o contador count e eventualmente devolver células inúteis para o espaço livre. Suponha existente uma rotina devolve(q) para devolver uma célula inútil apontada por q para o espaço livre. (Dica: Use recursividade. Em aula vimos um algoritmo que muda um ponteiro de um lugar a outro. Aqui temos um caso semelhante, so que muda para nil.)
3. (2.5 pontos) Considere a representação de um número inteiro positivo por uma lista linear ligada (um algarismo por elemento da lista), com um ponteiro por elemento.

   Dados dois números inteiros positivos i e j, deseja-se responder se são iguais, ou qual é o maior. Como voce armazenaria os números? Descreva sucintamente, sem escrever o algoritmo, o que tem que ser feito para dar a resposta.

4. (3 pontos) Considere alocação sequencial. Deseja-se implementar duas pilhas e uma fila de prioridade usando um ``heap'', tudo num mesmo espaço compartilhado de tamanho m.

   (a) Esboce o esquema de uso do espaço comum pelas três estruturas de dados.

   (b) Como voce detecta ``overflow'' quando se deseja inserir um elmento em cada uma das estruturas?

   (c) Escreva o algoritmo de inserção na pilha 1.

   (d) Escreva o algoritmo de inserção na pilha 2.

   (e) Escreva o(s) algoritmo(s) de tratamento de ``overflow'' (especifique que ``overflow'' voce está tratando: se na pilha 1, pilha 2 ou no heap).

 
• About this document ...