Tvc1-ED-12-3-GABARITO

Prévia do material em texto

UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
1º TVC de Estrutura de Dados – 14/01/2013 
ALUNO (A) _________________________GABARITO________________________________Turma:_____ 
ATENÇÃO: Sempre que necessário, apresentar as definições das estruturas de dados. 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
1) Conceituar e dar um exemplo de: 
a) Domínio de dados. 
b) Tipo de dados. (15) 
 
Uma solução poderia ser: 
 
1.a. Domínio de dados é um conjunto determinado de objetos. 
Ex.: Domínio de dados inteiros: é o conjunto dos números inteiros ou {0, ±1, ±2, ...}. 
 (5) 
1.b. Tipos de dados são dois conjuntos: um domínio de dados e um conjunto de operações 
aplicáveis diretamente sobre os objetos do domínio. (5) 
Ex.: Tipo de dados inteiro: 
Domínio: domínio dos inteiros. 
Conjunto de operações: operadores aritméticos: +, -, *, /, div e mod 
operadores relacionais: <, ≤, =, ≥, > e ≠ (5) 
 
Obs.: No exemplo de tipo de dados, o aluno que acertar o domínio e pelo menos 4 
operações, ganha os 5 pontos. 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
2) Preencher a tabela com as frequências de cada comando numerado no algoritmo BubbleSort, considerando o 
vetor A abaixo e os valores de N especificados na própria tabela. Não precisa calcular a frequência dos 
comandos 4, 5 e 6 para N = N. Determinar a ordem de grandeza de crescimento de tempo (O(?)) do 
algoritmo. (20) 
 void BubbleSort(int A[] int N){ 
 int i, j, aux; 
(1) for(j = 0; j < N - 1; j++) 
(2) for(i = 0; i < N-1; i++){ 
(3) if(A[i] > A[i+1]){ 
(4) aux = A[i]; 
(5) A[i] = A[i+1]; 
(6) A[i+1] = aux; 
 } //fim do if 
 }//fim for O(N²) 
 } //BubbleSort 
 
 0 1 2 3 . . . N - 1 
A = 15 4 7 26 . . . 19 
Comando N = 1 N = 2 N = 3 N = N 
1 1 2 3 N 
2 0 2 6 (N-1)*N 
3 0 1 4 (N-1)*(N-1) 
4 0 1 2 ------ 
5 0 1 2 ------ 
6 0 1 2 ------ 
Total 1 10 19 2N²-2N+1 
 
 
Obs.: Cada coluna vale (4) pontos e a ordem de grandeza também. 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
3) Definir um domínio estruturado para a seguinte matriz: (15) 
 
 
 
 
 
 
Uma solução poderia ser: 
 
typedef float Matriz[3][2]; (5) 
Matriz m; (5) 
m[0][0] = 7; 
m[0][1] = -5; 
m[1][0] = 8; 
m[1][1] = 0; 
m[2][0] = -3; 
m[2][1] = 6; (5) 
 
 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
4)Na solução de um problema científico, tornou-se necessário trabalhar com diversas matrizes quadradas n x n 
de elementos reais. Sabendo que, em todas essas matrizes, n é ímpar e são nulos todos os elementos situados 
fora das diagonais (principal e secundária) e fora da linha central e da coluna central, pede-se: 
a) Definir uma representação linear para a matriz descrita anteriormente. (10) 
7 -5 
8 0 
-3 6 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
b) Desenvolver um TAD (Tipo Abstrato de Dados) que utiliza a representação linear do item 4.a. 
Considerar que o usuário do PA (Programa Abstrato) fornecerá o valor de n, viabilizando a alocação 
dinâmica da representação linear e permitindo a verificação de validade dos índices da matriz quando 
necessário. 
 Obs.: o TAD deverá conter somente as operações padrões para um objeto matriz, isto é, construtor, 
destrutor, consulta, atribuição e validação dos índices da matriz. (5) (25)Considerando a representação natural da matriz M(1000 x 1000) de elementos reais abaixo, pede-se: 
c) Desenvolver o construtor e a operação de consulta do MI (Módulo de Implementação) do TAD do item 
4.b. (10) 
 
Uma solução poderia ser: 
 
a) Representação linear V da matriz M: 
 
1. Armazenar em V somente os elementos de M situados nas duas diagonais, na linha 
central e na coluna central, alocando esses elementos em V de acordo com a seguinte 
sequência: 
1º. Elementos da diagonal principal (L = C). 
2º. Elementos da diagonal secundária (L + C = (n – 1)). 
3º. Elementos da linha central (L = (n – 1) / 2). 
2º. Elementos da coluna central (C = (n – 1) / 2). 
 
 [I] 
 V = 
 
 (5) 
2. Dimensionamento de V: as diagonais, a linha central e a coluna central tem n 
elementos cada uma, portanto: 
 V possui 4*n elementos. 
 
3. Relacionamento entre os elementos de V e de M. 
 
 V[L], se L = C 
 V[n + L], se L + C = (n – 1) 
 M[L,C] = V[2*n + C], se L = (n – 1) / 2 
 V[3*n + L], se C = (n – 1) / 2 
 0.0, caso contrário (5) 
 
b) TAD MatCient: 
 
class MatCient 
{ 
 //domínio: 
 int n; //ordem da matriz 
 float *V; //representação linear da matriz 
 //operações 
 bool Valida(int linha, int coluna); 
 public: 
 MatCient(int ordem); 
 float Consulta(int linha, int coluna); 
 void Atribui(int linha, int coluna, float Valor); 
 ~MatCient(); 
}; (5) 
 
c) Construtor: 
 
MatCient::MatCient(int ordem) 
{ //inicializa as variáveis internas (n) e aloca 
 //memória para a representação linear da matriz 
 n = ordem; 
 V = new float[4*n]; 
} (5) 
 
 
 
 
0 1 ... n-1 n n+1 ... 2n-1 2n 2n+1 ... 3n-1 3n ... 4n-1 
m0,0 m1,1 ... mn-1,n-1 m0,n-1 m1,n-2 ... mn-1,0 m(n-1)/2,0 m(n-1)/2,1 ... m(n-1)/2,n-1 m0,(n-1)/2 ... m n-1,(n-1)/2 
L = C L + C = (n – 1) L = (n – 1) / 2 C = (n – 1) / 2 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
Consulta: 
 
float MatCient::Consulta(int linha, int coluna) 
{ 
 if(Valida(linha, coluna)) 
 if(linha == coluna) 
 return V[linha]; 
 else 
 if((linha + coluna) == (n – 1)) 
 return V[n + linha]; 
 else 
 if(linha == ((n – 1) / 2)) 
 return V[2*n + coluna]; 
 else 
 if(coluna == ((n – 1) / 2)) 
 return V[3*n + linha]; 
 else 
 return 0.0; 
 else 
 { 
 cout << "Indice invalido!" << endl; 
 exit(1); 
 } 
} (5) 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
5) Considerando a necessidade de se trabalhar com cálculo vetorial em 3 dimensões, foi desenvolvido o TAD 
Vetor3D abaixo. 
 Desenvolver o construtor e as operações Copia, Normaliza e ProdutoEscalar do MI deste TAD. (25) 
class Vetor3D 
{ 
 private: 
 float x, y, z; 
 
 public: 
 Vetor3D(float xx, float yy, float zz); // inicializa os campos da classe 
 Vetor3D* Copia(); // cria e retorna uma cópia do vetor armazenado 
 void Normaliza(); // normalizao vetor armazenado (norma = raiz(x²+y²+z²)) 
 float ProdutoEscalar(Vetor3D *v2); // calcula e retorna o produto escalar do 
// vetor armazenado com um outro vetor passado 
// como parâmetro (prod = x1*x2+y1*y2+z1*z2) 
 ~Vetor3D(); 
}; 
 
 
Uma solução poderia ser: 
 
Vetor3D::Vetor3D(float xx, float yy, float zz) 
{ 
 x = xx; 
 y = yy; 
 z = zz; 
} (5) 
 
Vetor3D* Vetor3D::Copia() 
{ 
 Vetor3D *novo = new Vetor3D(x, y, z); 
 return novo; 
} (5) 
 
void Vetor3D::Normaliza() 
{ 
 float norma = sqrt(x*x + y*y + z*z); 
 x = x / norma; 
 y = y / norma; 
 z = z / norma; 
} (10) 
 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
float Vetor3D::ProdutoEscalar(Vetor3D *v2) 
{ 
 float prod = x*v2->x + y*v2->y + z*v2->z; 
 return prod; 
} (5)