Baixe o app para aproveitar ainda mais
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)
Compartilhar