Tvc1-ED-14-1-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 e Laboratório de Programação II – 30/04/2014 
ALUNO (A) _________________________GABARITO___________________________________________ 
Turma de Estrutura de Dados:_____ Turma de Laboratório de Programação II: _____ 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
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) 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
2) a) Conceituar frequência de um comando. (5) 
b) Conceituar ordem de grandeza de crescimento de tempo (complexidade) de um algoritmo (5) 
c) Considerando o algoritmo abaixo, conhecido como BubbleSort, que tem como objetivo colocar os N 
elementos inteiros de um vetor A em ordem crescente, pede-se calcular a frequência do comando 
if(A[i] > A[i+1]) , bem como a ordem de grandeza do algoritmo. (10) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Uma solução poderia ser: 
 
2.a. Frequência de um comando: é o número de vezes que o comando é executado. (5) 
 
2.b. Ordem de grandeza de crescimento de tempo (complexidade) de um algoritmo: é a 
maior frequência encontrada num programa. (5) 
 
2.c. Frequência do comando if(A[i] > A[i+1]): (5) 
 Isoladamente o comando tem frequência: f = 1. 
 Mas, como ele pertence ao domínio de duas estruturas de repetição (for) embutidas, 
sua frequência será: 
 
Por pertencer ao domínio simples das duas estruturas de repetição (for) embutidas, 
ele é o comando de maior frequência do algoritmo. Assim, eliminando as constantes 
e os termos de menor grau de sua frequência, chega-se à complexidade do algoritmo, 
isto é: O(N2) (5) 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
3) Utilizar o TAD TMatTriang abaixo para desenvolver duas funções de PA com os seguintes objetivos: 
a) Ler 55 valores reais e criar uma matriz triangular inferior A(10x10), sabendo que os valores lidos 
devem preencher o triângulo inferior de A, percorrendo-o de cima para baixo e da esquerda para a 
direita, isto é, o primeiro valor lido é do elemento A[0, 0], o segundo é A[1, 0], o terceiro é 
A[1, 1], o quarto é A[2, 0]e assim por diante. 
b) Retornar o valor do menor elemento da matriz A. (20) 
 void BubbleSort(int A[] int N){ 
 int i, j, aux; 
 for(j = 0; j < N - 1; j++) 
 for(i = 0; i < N-1; i++){ 
 if(A[i] > A[i+1]){ 
 aux = A[i]; 
 A[i] = A[i+1]; 
 A[i+1] = aux; 
 } //fim do if 
 }//fim do for 
 } //BubbleSort 
 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 
class TMatTriang 
{ 
 int n; // ordem da matriz triangular 
 float *vet; // representação linear da matriz triangular 
 bool Verifica(int i, int j); 
 public: 
 TMatTriang(int ordemMatriz); 
 float Consulta(int i, int j); 
 void Atribui(int i, int j, float valor); 
 ~TMatTriang(); 
}; 
 
Uma solução poderia ser: 
 
3.a. 
TMatTriang* CriaLista() 
{ 
 int i, j; 
 float val; 
 TMatTriang *A = new TMatTriang(10); 
 for(i = 0; i < 10; i++) 
 for(j = 0; j <= i; j++) (5) 
 { 
 cin>>val; 
 A-> Atribui(i, j, val) 
 } 
 return A; (5) 
}; 
 
3.b. 
float Menor(TMatTriang *A) 
{ 
 int i, j; 
 float min = 0.0; 
 for(i = 0; i < 10; i++) (5) 
 for(j = 0; j <= i; j++) 
 { 
 if(A->Consulta(i, j) < min); 
 min = A->Consulta(i, j) 
 } 
 return min; (5) 
}; 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
4) Considerando uma matriz quadrada n x n de elementos reais, onde são nulos todos os elementos situados 
fora da diagonal secundária e das duas paralelas vizinhas a ela, pede-se: 
a) Definir uma representação linear para a matriz descrita anteriormente. (10) 
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 atribuição do MI (Módulo de Implementação) do TAD do item 
4.b. (10) 
 
Uma solução poderia ser: 
 
4.a. Representação linear V da matriz M: 
 
1. Armazenar em V somente os elementos de M situados na diagonal secundária e nas duas 
paralelas vizinhas a ela, percorrendo cada uma delas da esquerda para a direita e 
alocando esses elementos em V de acordo com a seguinte sequência: 
1º. Elementos da paralela superior (i + j = (n – 2)). 
2º. Elementos da diagonal secundária (i + j = (n – 1)). 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
3º. Elementos da paralela inferior (i + j = n). 
 
 [I] 
 V = 
 
 (5) 
2. Dimensionamento de V: a diagonal secundária tem n elementos e cada uma de suas 
paralelas tem n-1 elementos, portanto: 
 V possui n + 2(n-1) elementos, isto é, 3n-2 elementos. 
 
3. Relacionamento entre os elementos de V e de M. 
 
 V[j], se i + j = (n – 2) 
 M[i,j] = V[(n-1) + j], se i + j = (n – 1) 
 V[(2*n-2) + j], se i + j = n 
 0.0, caso contrário (5) 
 
4.b. TAD MatInvert: 
class MatInvert 
{ 
 //domínio: 
 int n; //ordem da matriz 
 float *V; //representação linear da matriz 
 //operações 
 bool Valida(int linha, int coluna); 
 public: 
 MatInvert(int ordem); 
 float Consulta(int linha, int coluna); 
 void Atribui(int linha, int coluna, float Valor); 
 ~MatInvert(); 
}; (5) 
 
4.c. Construtor: 
MatInvert::MatInvert(int ordem) 
{ //inicializa as variáveis internas (n) e aloca 
 //memória para a representação linear da matriz 
 n = ordem; 
 V = new float[3*n-2]; 
}(3) 
 
Consulta: 
float MatInvert:: Atribui(int linha, int coluna, float Valor) 
{ 
 if(Valida(linha, coluna)){ 
 if(linha+coluna == (n-2)) 
 V[coluna] = Valor; 
 else if(linha+coluna == (n–1)) 
 V[(n-1) + coluna] = Valor; (3) 
 else if(linha+coluna == n) 
 V[(2*n-2) + coluna] = Valor; 
 else if(Valor != 0) 
 cout << "Valor invalido!" << endl; 
 } 
 else 
 cout << "Indice invalido!" << endl; 
} (4) 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
5) Dados o struct dupla, o TAD TVetEsparso, algumas operações do seu MI e um trecho de um PA, pede-se 
preencher uma representação do vetor tab, após a execução de cada um dos comandos numerados no PA. 
 
 (20) 
 
0 1 ... n-2 n-1 n ... 2n-2 2n-1 2n ... 3n-3 
mn-2,0 mn-3,1 ... m0,n-2 mn-1,0 mn-2,1 ... m0,n-1 mn-1,1 mn-2,2 ... m1,n-1 
i + j = (n – 2) i + j = (n – 1) i + j = n 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
typedef struct 
{ 
 int ind; 
 float val; 
}dupla; 
void TVetEsparso::Remove(int k) 
{// remove a dupla de índice k 
 int t; 
 for(t = k; t < total-1; t++) 
 {// desloca duplas para esquerda 
 tab[t].ind = tab[t+1].ind; 
 tab[t].val = tab[t+1].val; 
 } 
 tab[total].ind = f1+1;//inclui folga 
 tab[total].val = 0.0; 
 total--; 
} 
class TVetEsparso 
{ 
 int c, f; 
 int max; // capacidade máxima do vetor 
 int total; // total de elementos 
 dupla *tab; // vetor de registros 
 int DetInd(int i); 
 void Remove(int k); 
 void Insere(int i, float valor); 
 public: 
 TVetEsparso(int cc, int ff, int naonulo); 
 float Consulta(int i); 
 void Atribui(int i, float valor); 
 ~TVetEsparso(); 
}; 
TVetEsparso::TVetEsparso(int cc,int ff,int n) 
{ 
 c = cc; 
 f = ff; 
 max = n + 4; // não nulos + folga 
 total = 0; 
 tab = new dupla[max]; 
 for(int i = 0; i < max; i++){ 
 tab[i].ind = f + 1; 
 tab[i].val = 0.0; 
 } 
} 
void TVetEsparso::Insere(int i, float 
valor) 
{ 
 if(total < max){ 
 int t = 0; 
 // inserir o índice na ordem correta 
 while(t < total && tab[t].ind < i) 
 t++; 
 for(int m = total; m > t; m--){ 
 //desloca para abrir espaço 
 tab[m].ind = tab[m-1].ind; 
 tab[m].val = tab[m-1].val; 
 } 
 // insere dupla na posição t 
 tab[t].ind = i; 
 tab[t].val = valor; 
 total++; 
 } 
 else 
 cout<<"Nao ha espaco!"<<endl; 
} 
int TVetEsparso::DetInd(int i) 
{ 
 if(i >= c && i <= f){ 
 int k = -1; 
 for(int t = 0; t < total; t++){ 
 if(tab[t].ind == i){ 
 k = t; 
 break; 
 } 
 } 
 return k; 
 } 
 else{ 
 cout<<"Indice invalido!"<<endl; 
 exit(1);} 
} 
void TVetEsparso::Atribui(int i, float val) 
{ 
 int k = DetInd(i); 
 if(k != -1) 
 { 
 if(valor == 0.0) // remove a dupla 
 Remove(k); 
 else 
 tab[k].val = valor; // atualiza o valor 
 } 
 else if(valor != 0.0) 
 Insere(i, valor); // insere nova dupla 
} 
int main() 
{ 
 .......... 
 TVetEsparso* esp; 
 esp = new TVetEsparso(-2,4,3); (1) 
 esp->Atribui(-2,7); (2) 
 esp->Atribui(0,5); (3) 
 esp->Atribui(4,3); (4) 
 esp->Atribui(1,-4); (5) 
 esp->Atribui(-1,8); (6) 
 esp->Atribui(0,0); (7) 
 esp->Atribui(3,9); (8) 
 esp->Atribui(-1,0); (9) 
 esp->Atribui(1,10); (10) 
 .......... 
} 
 
 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
Cada tabela (2) 
(1) 0 1 2 3 4 5 6 
tab = 
5 5 5 5 5 5 5 
0.0 0.0 0.0 0.0 0.0 0.0 0.0 
 
(3) 0 1 2 3 4 5 6 
tab = 
-2 0 5 5 5 5 5 
7 -5 0.0 0.0 0.0 0.0 0.0 
 
(5) 0 1 2 3 4 5 6 
tab = 
-2 0 1 4 5 5 5 
7 -5 -4 3 0.0 0.0 0.0 
 
(7) 0 1 2 3 4 5 6 
tab = 
-2 -1 1 4 5 5 5 
7 8 -4 3 0.0 0.0 0.0 
 
(9) 0 1 2 3 4 5 6 
tab = 
-2 1 3 4 5 5 5 
7 -4 9 3 0.0 0.0 0.0 
 
 
(2) 0 1 2 3 4 5 6 
tab = 
-2 5 5 5 5 5 5 
7 0.0 0.0 0.0 0.0 0.0 0.0 
(4) 0 1 2 3 4 5 6 
tab = 
-2 0 4 5 5 5 5 
7 -5 3 0.0 0.0 0.0 0.0 
(6) 0 1 2 3 4 5 6 
tab = 
-2 -1 0 1 4 5 5 
7 8 -5 -4 3 0.0 0.0 
(8) 0 1 2 3 4 5 6 
tab = 
-2 -1 1 3 4 5 5 
7 8 -4 9 3 0.0 0.0 
(10) 0 1 2 3 4 5 6 
tab = 
-2 1 3 4 5 5 5 
7 10 9 3 0.0 0.0 0.0