Tvc1-ED-13-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 e Laboratório de Programação II – 18/12/2013 
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) 
 
Obs.: No exemplo de tipo de dados, o aluno que acertar o domínio e pelo menos 3 
operações, ganha os 5 pontos. 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
2) Preencher a tabela com as frequências de cada comando numerado no algoritmo SelectionSort, considerando 
o vetor A abaixo e os valores de N especificados na própria tabela. Determinar a ordem de grandeza de 
crescimento de tempo (O(?)) do algoritmo. (20) 
 void SelectionSort(int A[], int N){ 
 int i, j, menor, indiceMenor; 
(1) for(i = 0; i < (N-1); i++){ 
(2) menor = A[i]; 
 indiceMenor = i; 
(3) for(j = (i+1); j < N; j++) 
(4) if(A[j] < menor){ 
 menor = A[j]; 
 indiceMenor = j; 
 } // fim do if 
(5) A[indiceMenor] = A[i]; 
 A[i] = menor; 
 } // fim do for 
 } // fim do SelectionSort 
 
 0 1 2 3 . . . N - 1 
A = 17 5 9 33 . . . 13 
 
 
O(N2) 
Comando N = 1 N = 2 N = 3 N = N 
1 1 2 3 N 
2 0 1 2 N-1 
3 0 2 5 N*(N+1)/2-1 
4 0 1 3 N*(N-1)/2 
5 0 1 2 N-1 
Total 1 7 15 N2+3N-3 
 
Obs.: Cada coluna vale (4) pontos e a ordem de grandeza também. 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
3) Utilizar o TAD TListCont abaixo para desenvolver uma função de PA que leia 300 valores inteiros e crie 
uma lista contígua, atendendo as seguintes características: 
a) O primeiro valor lido será incluído como primeiro nó da lista. 
b) A partir do segundo valor lido: 
b.1) Ele será incluído no final da lista, se for maior do que o último nó da lista. 
b.2) Se ele não for maior que o último nó da lista, excluir o primeiro nó da lista. (20) 
 
class TListCont 
{ 
 private: 
 int m; // capacidade maxima de elementos do vetor 
 int ultimo; // indice do ultimo No da lista 
 int* X; // vetor que armazena a lista 
 public: 
 TListCont(int tam); // construtor 
 int Consulta(int k); // consulta No de indice k 
 int Consultault();// consulta ultimo No 
 void Atribui(int k, int val); // atribui val ao No de indice k 
 void Inserek(int k, int val); // insere antes do No de indice k 
 void Insereult(int val); // insere ultimo No 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 void Eliminak(int k); // elimina No de indice k 
 void Eliminault(); // elimina ultimo No 
 ~TListCont(); // destrutor 
}; 
 
Uma solução poderia ser: 
 
TListCont* CriaLista() 
{ 
 int val, i; 
 TListCont *Lista = new TListCont(300); (5) 
 cin>>val; 
 Lista->Insereult(val); (5) 
 for(i = 2; i <= 300; i++) 
 { 
 cin>>val; 
 if (val > Lista->Consultault()) 
 Lista->Insereult(val); (5) 
 else 
 Lista->Eliminak(0); 
 } 
 return Lista; (5) 
}; 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
4) Considerando uma lista simplesmente encadeada de valores reais conforme a figura abaixo, pede-se: 
 a) Desenvolver o TAD TListaSEncad. (10) 
 b) Desenvolver o operador do MI do TAD TListaSEncad que insere nó na lista. (5) 
 c) Desenvolver o operador do MI do TAD TListaSEncad que exclui nó da lista. (10) 
 
 
Uma solução poderia ser: 
 
4.a) TAD TListaSEncad: 
 
class TListaSEncad{ 
 private: 
 No *primeiro; // ponteiro para o primeiro No da lista 
 No *it; // ponteiro auxiliar para percorrer a lista (2) 
 public: 
 TListaSEncad(); // construtor 
 float Consulta(); // consulta No apontado por it 
 void Atribui(float val); // atribui val ao No apontado por it 
 bool Busca(float val); // verifica se existe No contend val (2) 
 void InserePri(float val); // insere No contendo val no inicio da lista 
 void EliminaPri(); // elimina o primeiro No da lista (2) 
 // operações para percorrer a lista 
 void Inicio(); // coloca o ponteiro it no início 
 void ProximoNo(); // avança o ponteiro it 
 bool FimDaLista(); // verifica se it está no final (= NULL) (2) 
 ~TListaSEncad(); // destrutor construtor + destrutor = (2) 
}; 
 
4.b) Operador do MI do TAD TListaSEncad que insere nó na lista: 
 
void ListaSEncad::InserePri(float val) (1) 
{ // insere No contendo val no início da lista 
 No *p = new No(); // cria No apontado por p 
 p->atribInfo(val); // preenche info com val 
 p->atribProx(primeiro); // prox recebe atual primeiro (3) 
 primeiro = p; // No apontado por p passa a ser o 1º (1) 
} 
 
4.c. Operador do MI do TAD TListaSEncad que exclui nó da lista: 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 
void ListaSEncad::EliminaPri() 
{ // elimina primeiro No 
 No *p; (2) 
 if(primeiro != NULL) // se lista não está vazia (2) 
 { 
 p = primeiro; // p aponta para o No a ser excluido 
 primeiro = p->consultaProx();// primeiro passa a apontar para o segundo 
 delete p; // exclui o 1º No (4) 
 } 
 else 
 Rotina_Erro(1); (2) 
} 
_______________________________________________________________________________________________________________________________________________________________________________________________________________________ 
5) Dados o TAD No e o TAD TListaDEncad correspondente a uma lista duplamente encadeada com descritor 
de valores reais, pede-se desenvolver os seguintes operadores do MI do TAD TListaDEncad: 
 a) InserePri. (10) 
 b) destrutor. (10) 
 
class No 
{ 
 private: 
 No *ant; //ponteiro No anterior 
 float info; // informação do No 
 No *prox; //ponteiro proximo No 
 public: 
 No(); 
 void atribAnt(No *p); 
 void atribInfo(float val); 
 void atribProx(No *p); 
 No *consultaAnt();float consultaInfo(); 
 No *consultaProx(); 
 ~No(); 
}; 
class TListaDEncad 
{ 
 private: 
 No *pri; // ponteiro para primeiro No da lista 
 int n; // número corrente de Nos da lista 
 No *ult; // ponteiro para o último No da lista 
 No *it; // ponteiro para percorrer a lista 
 public: 
 TListaDEncad(); // construtor 
 float Consulta(); 
 void Atribui(float val); 
 bool Busca(float val); 
 // insere No contendo val no início da lista 
 void InserePri(float val); 
 void EliminaPri();//elimina primeiro No da lista 
 // operações para percorrer a lista 
 void Inicio(); // coloca it no primeiro No 
 void ProximoNo(); // avança o ponteiro it 
 void NoAnterior(); // recua o ponteiro it 
 bool FimDaLista();//verifica se it está no final 
 ~TListaDEncad(); // destrutor 
}; 
 
Uma solução poderia ser: 
 
5.a) InserePri: 
 
void TListaDEncad::InserePri(float val) 
{ // insere No contendo val no início da lista 
 No *p = new No(); // cria No apontado por p (2) 
 p->atribInfo(val); // preenche info com val 
 p->atribProx(pri); // prox recebe atual pri 
 p->atribAnt(NULL); (2) 
 // atualiza o descritor 
 if(n == 0) 
 ult = p; (2) 
 else 
 pri->atribAnt(p); (2) 
 pri = p; 
 n++; (2) 
} 
 
5.b) destrutor: 
 
TListaDEncad::~TListaDEncad() 
{ 
 No *p = pri; (2) 
UNIVERSIDADE FEDERAL DE JUIZ DE FORA 
INSTITUTO DE CIÊNCIAS EXATAS 
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
 while(p != NULL) (2) 
 { 
 pri = p->consultaProx(); 
 delete p; 
 p = pri; (4) 
 } 
 n = 0; 
 ult = NULL; (2) 
}