2014.03 - AV Estrutura de Dados

Prévia do material em texto

19/3/2014 BDQ Prova
file:///G:/Pessoal/Acad%EAmico/Est%E1cio%20de%20S%E1/2o%20Semestre/Estrutura%20de%20Dados/Provas/Prova%20AV_files/bdq_prova_resultado… 1/5
 
Avaliação: CCT0260_AV_ » ESTRUTURA DE DADOS
Tipo de Avaliação: AV
Aluno: N.A.
Professor: ALEXANDRE SOARES ALVES Turma: 9001/AA
Nota da Prova: 6,2 Nota de Partic.: 2 Data: 06/03/2014 16:32:59
 1a Questão (Ref.: 201304133913) Pontos: 0,0 / 0,5
As estruturas de dados em programação são muito utilizadas para tornar o acesso aos dados mais eficiente e
organizado. A estrutura de dados considerada mais simples e tem como característica apresentar apenas uma
dimensão é:
Registro
 Variável
Função
 Vetor
Matriz
 2a Questão (Ref.: 201304116897) Pontos: 0,5 / 0,5
Marque a opção que representa uma característica CORRETA a respeito da estrutura de dados pilha.
Não é possível criar uma pilha utilizando vetores.
O primeiro item inserido é o primeiro a ser retirado.
Os acessos aos itens ocorrem de forma aleatória.
 O último item inserido é o primeiro item a ser retirado.
O último item inserido é o último item a ser retirado.
 3a Questão (Ref.: 201304133390) Pontos: 0,5 / 0,5
O que acontece ao se inserir uma informação quando já usamos toda a área disponível do vetor (topo = fim)?
remoção
inclusão
ordenação
underflow
 overflow
 4a Questão (Ref.: 201304133581) Pontos: 0,0 / 0,5
Marque a afirmativa correta para a "Inserção em lista linear sequencial ordenada".
 Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos.
19/3/2014 BDQ Prova
file:///G:/Pessoal/Acad%EAmico/Est%E1cio%20de%20S%E1/2o%20Semestre/Estrutura%20de%20Dados/Provas/Prova%20AV_files/bdq_prova_resultado… 2/5
 Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos.
Consiste em fazer uma busca em um vetor já ordenado, dividindo o espaço de busca ao meio e
verificando se o dado está no meio ou, antes do meio ou depois do meio.
É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente.
 Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
Consiste em fazer uma busca em um vetor desordenado, dividindo o espaço de busca ao meio e
verificando se o dado está no meio ou, antes do meio ou depois do meio.
 5a Questão (Ref.: 201304133440) Pontos: 0,5 / 0,5
O armazenamento de dados na memória do computador é feito de forma ordenada, utilizando-se estruturas e
regras de operações. Das alternativas a seguir, assinale a correta:
A lista binária é uma forma não-linear de organização dos dados. Existe um nó denominado raiz da
árvore, que pode ter duas ou mais sub-árvores, que por sua vez também podem ter outras sub-árvores.
 Em uma lista linear com alocação duplamente encadeada os nós da estrutura ocupam espaços aleatórios
na memória e cada nó armazena além da sua informação os endereços do nó anterior e do próximo nó
da estrutura.
Em uma lista linear com alocação sequencial, os dados são heterogêneos e os nós da lista podem ter
tamanhos diferentes, mas exigem espaço em endereço contíguo de memória.
Existem várias formas de apresentação de listas lineares, como listas circulares e as matrizes, que são
formas exclusivas das listas de alocação encadeada.
Fila e Pilha são tipos especiais de listas lineares. Na Fila, o último que entra é o primeiro que sai,
enquanto na Pilha, o primeiro que entra é o primeiro que sai.
 6a Questão (Ref.: 201304133574) Pontos: 0,5 / 0,5
Qual a importância de se entender a "ordenação" de dados ?
A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se
conhecimento para manter outros problemas.
A ordenação é a base na qual, muitos programas são construídos. Entendendo a ordenação, tem-se
conhecimento para manter outros problemas.
A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se
conhecimento para manter outros problemas.
 A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se
conhecimento para resolver outros problemas.
A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se
conhecimento para resolver outros problemas.
 7a Questão (Ref.: 201304133927) Pontos: 1,0 / 1,0
Os métodos de ordenação são muito utilizados em estruturas de dados para facilitar a busca e a recuperação
posterior de itens de conjuntos ordenados. Existem vários métodos de ordenação, por este motivo, marque
corretamente a alternativa que apresenta o código do método de seleção.
int ordena(float v[], float valor, int n) {
 int ini = 0, fim = n-1, meio;
 while (ini >= fim){
 meio = ini/2;
 if (v[meio] == valor)
 return meio; 
 if (valor < v[meio])
 fim = meio -1;
 else
 ini = meio+1;
}
void ordena (int v[], int n){ 
 int i, j, aux; 
19/3/2014 BDQ Prova
file:///G:/Pessoal/Acad%EAmico/Est%E1cio%20de%20S%E1/2o%20Semestre/Estrutura%20de%20Dados/Provas/Prova%20AV_files/bdq_prova_resultado… 3/5
 int i, j, aux; 
 for (j = 1; j < n; j++) 
 for (i=j; i > 0 && v[i-1]> v[i]; i--){ 
 aux = v[i-1]; 
 v[i-1] = v[i]; 
 v[i] = aux; 
 } 
}
 void ordena(int v[], int n){ 
int i, j, menor, aux; 
for (j = 0; j < n-1; j++) { 
 for (i = j+1; i < n; i++) { 
 if (v[i] < v[j]) { 
 aux = v[j]; 
 v[j] = v[i]; 
 v[i] = aux; 
 } 
 } 
} 
}
int ordena(float v[], float valor, int n) { 
 int ini = 0, fim = n -1, meio; 
 while (ini <= fim){ 
 meio = (ini + fim)/2; 
 if (v[meio] == valor) 
 return meio; 
 if (valor < v[meio]) 
 fim = meio -1; 
 else 
 ini = meio+1; 
 } 
 return -1; 
}
int ordena(float v[], float valor, int n){
 for (int i = 0; i < n; i++)
 if (v[i] == valor)
 return i;
 return -1;
}
 8a Questão (Ref.: 201304136979) Pontos: 1,0 / 1,0
Existem vários algoritmos de busca em estruturas de dados, um destes realiza a busca em vetores, e requer
acesso aleatório aos elementos desta estrutura e parte do pressuposto de que os dados do vetor estejam
ordenados e utiliza a técnica de divisão e conquista comparando o elemento desejado com o elemento do meio
do vetor. Esta técnica ainda verifica se o elemento do meio do vetor for o desejado, a busca termina. Caso
contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior
do vetor. E se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. O
algoritmo que utiliza esta metodologia é:
Seleção
 Pesquisa binária
Pesquisa sequencial
Bolha
Inserção
 9a Questão (Ref.: 201304154856) Pontos: 0,7 / 1,5
Defina um tipo de dado (registro) capaz de armazenar as seguintes informações sobre um determinado cliente
de um banco: nome, CPF, RG, número da conta, data de abertura da conta, e saldo.
Com base neste tipo de dado, construa o trecho código em C++ que represente a leitura dos dados do cliente
feita pelo usuário.
19/3/2014 BDQ Prova
file:///G:/Pessoal/Acad%EAmico/Est%E1cio%20de%20S%E1/2o%20Semestre/Estrutura%20de%20Dados/Provas/Prova%20AV_files/bdq_prova_resultado… 4/5
Resposta: struct Data { int dia, mes, ano; } struct Cliente { char nome[40]; long long int cpf, rg, numero_conta;
Data data_abertura; float saldo; } void exibirDadosCliente(Cliente &clienteX) { cout<<"Nome Cliente: " <<
clienteX.nome << "\n"; cout<<"CPF:" << clienteX.cpf << "\n"; cout<<"RG:" << clienteX.rg << "\n";
cout<<"Numero Conta:" << clienteX.numero_conta << "\n"; cout<<"Data Abertura:" <<
clienteX.data_abertura.dia << "\"<< clienteX.data_abertura.mes << "\" << clienteX.data_abertura.ano <<
"\n"; cout<<"Saldo:"<<clienteX.saldo; }
Gabarito:
struct ClienteBanco{
 string nome;
 string cpf;
 int rg;
 int numConta;
 double saldo;
};
ClienteBanco cliente;
cin >> cliente.nome;
cin >> cliente.cpf;
cin >> cliente.rg;
cin >> cliente.saldo;
 10a Questão (Ref.: 201304154993) Pontos: 1,5 / 1,5
const int TAMMAX = 100;
struct TipoLista{
int qtde; // descritor que representa a quantidade de elementos na lista
int elemt[TAMMAX];
};
Fundamento no tipo de dado(registro) acima que representa uma implementação de uma lista linear sequencial.
Construa um procedimento para adicionar um dado no final da lista.
A lista e o dado serão passados por parâmetro. Usar o mecanismo de passagem por referência se for
necessário.
Resposta: void adicionarElemento(TipoLista &lista, int valor) { if (lista.qtde == TAMMAX) { cout<<"Lista cheia,
impossivel adicionar"; return; } lista.elemt[lista.qtde++] = valor; }
Gabarito:
void addFinalLista ( TipoLista &lista, int dado ){
if(lista.qtde == TAMMAX){cout << "Lista Cheia."; }
else{ lista.elemt[lista.qtde] = dado;
 lista.qtde++;
 cout << "Dado adicionado com sucesso.";
} }
Período de não visualização da prova: desde 26/02/2014 até 18/03/2014.
19/3/2014 BDQ Prova
file:///G:/Pessoal/Acad%EAmico/Est%E1cio%20de%20S%E1/2o%20Semestre/Estrutura%20de%20Dados/Provas/Prova%20AV_files/bdq_prova_resultado… 5/5
Período de não visualização da prova: desde 26/02/2014 até 18/03/2014.