MAC 710 - Estruturas de Dados - 1.a Prova - 13 de maio de 1997
Nome: ___________________________________________________________________ Nota: _______
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.
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.
(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).