Estrutura de dados

Prévia do material em texto

AV1 de Estrutura de Dados 	Data: 2 / 10 / 2012
�
Q1- 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 é: (1 pt)
(A) Matriz			(D) Vetor
(B) Função			(E) Registro
(C) Variável			(F) N. D. A.
Q2- Considere duas listas, a primeira ordenada, linear, sequencial. A segunda desordenada, circular, alocada dinamicamente. Considerando as operações básicas de operações em lista, qual a única teria a mesma estratégia nas duas implementações: (1 pt)
(A) Inclusão			(D) Alteração
(B) Busca			(E) Exclusão
(C) Listagem		(F) N. D. A.
Q3 - Descreva um algoritmo que receba duas listas ordenadas e junta as duas numa terceira lista também ordenada. Considere as duas listas com elementos não repetidos entre si. (2 pt)
bool junta (int a[], int ta, int b[], int tb, int c[], int tc){
 int i=0, j=0, k=0;
 if (ta + tb > tc ) return false;
 while (i < ta && j < tb)
 if (a[i] < b[j]){
 c[k] = a[i];
 k++; i++;
 } else {
 c[k] = b[j];
 k++; j++;
 }
 }
 while (i < ta){
 c[k] = a[i];
 k++; i++;
 }
 while (j < tb){
 c[k] = b[j];
 k++; j++;
 }
 return true;
}
Q4 - Considere o código da função stat: 
double stat (double v[], int tam, int op){
 double r = v[0];
 int i;
 for (i = 1; i < tam; i++){
 if (op == 1)
 if (v[i] > r) r = v[i];
 if (op == 2)
 if (v[i] < r) r = v[i];
 if ((op == 3) || (op == 4))
 r = r + v[i];
 }
 if (op == 3) r = r / tam;
 return r;
}
Agora, sabendo que a mesma é versátil quanto a sua funcionalidade, EXPLIQUE com um chinês o que ela retornaria para x, se recebesse a seguinte chamada de função: (2 pt)
x = stat ([2,4,6,8,10,0,1], 7, 4);
A função retornaria o valor 31, pois com o parâmetro op valendo 4 a mesma realiza a soma dos elementos.
Q5 - Ainda considerando a função stat da questão anterior, diga o que ela retornaria em função do 3º parâmetro op ter o valor: (0,20 cada - 1 pt)
op == 1 : O maior de todos (10)
op == 2 : O menor de todos (0)
op == 3 : A media da lista (4,4)
op == 4 : A soma dos elementos (31)
op == 5 : O primeiro element (2)
Q6 - Sabendo que tenho uma lista seqüencial desordenada de números reais que permite a inclusão de elementos repetidos, faça o algoritmo de uma função para contar as ocorrências de um elemento. Utilize o protótipo: (2 pt)
int busca (double v[ ], int tam, double elem)
Onde: v é o vetor com a lista desordenada, elem é o elemento a ser procurado e tam é a quantidade de elementos armazenados na lista.
int busca (double v[ ], int tam, double elem){
 int i, qtd = 0;
 for (i = 0; i < tam; i++){
 if (v[i] == elem) qtd++;
 }
 return qtd;
}
Q7 - Leia atentamente as afirmações abaixo, e diga se elas são verdadeiras ou falsas e justificando sua resposta. (2 pt) 
A) Numa lista seqüencial ordenada não é possível utilizar a busca seqüencial.
Falso. O fato de estar ordenada não impede o uso da busca sequencial.
B) Numa lista ordenada a busca binária sempre será mais eficaz que a busca seqüencial.
Falso. Se o elemento estiver nas primeiras posições, a busca sequencial será mais eficiente.
Q8 - Cite e justifique uma vantagem e uma desvantagem das listas lineares seqüenciais desordenadas e das listas lineares seqüenciais ordenadas. (2 pt)
Desordenadas: Vantagem – Inclusão e remoção rápidas. Desvantagem – Busca lenta.
Ordenadas: Vantagem – Busca rápida. Desvantagem – Inclusão e remoção lentas.
Q9 - Crie uma struct que represente as anotações sobre uma partida esportiva de um esporte de sua preferência. A mesma deve ter no mínimo 3 atributos. Depois faça uma função que realiza a leitura de uma struct do tipo criado por você. (2 pt)
struct partida{
 char time1[40];
 char time2[40];
 char data[10];
};
partida lePartida (){
 struct partida p;
 cout << “Time 1:”;
 cin >> p.time1;
 cout << “Time 2:”;
 cin >> p.time2;
 cout << “Data do jogo:”;
 cin >> p.data;
 return p;
}
Programa extra que junta pilha e fila:
#include <iostream>
#include <cstdlib>
#define MAX 200 // tamanho máximo para a área de armazenamento
// Programa que junta Pilha e Fila
using namespace std;
struct pilha {
 int a[MAX];
 int topo;
 int tamanho;
};
struct fila {
 int a[MAX];
 int ini;
 int fim;
 int tam;
};
void iniciaPilha (struct pilha *p){
 p->topo = -1;
 p->tamanho = MAX - 1;
}
bool pilhaVazia (struct pilha *p){
 if (p->topo == -1) return true;
 else return false;
}
bool pilhaCheia (struct pilha *p){
 if (p->topo == p-> tamanho) return true;
 else return false;
}
bool push (struct pilha *p, int n){
 if (pilhaCheia(p)){ return false; }
 else {
 p->topo++;
 p->a[p->topo] = n;
 return true;
 }
}
bool pop (struct pilha *p, int *r){
 if (pilhaVazia(p)){ return false; }
 else {
 *r = p->a[p->topo];
 p->topo--;
 return true;
 }
}
void exibePilha (struct pilha *p){
 int n; struct pilha t;
 iniciaPilha(&t);
 // Inverte a pilha para a pilha temporária t
 while (!pilhaVazia(p)){ pop(p,&n); push(&t,n); }
 cout << "\n\n";
 while (!pilhaVazia(&t)){
 pop(&t,&n);
 cout << n << " ";
 push(p,n);
 } // Inverte a pilha temporária t de volta para p exibindo na tela
}
void iniciaFila (struct fila *f){
 f->ini = 0;
 f->fim = 0;
 f->tam = 0;
}
bool filaVazia (struct fila *f){
 if (f->tam == 0) return true;
 else return false;
}
bool filaCheia (struct fila *f){
 if (f->tam == MAX) return true;
 else return false;
}
bool enfileira (struct fila *f, int n){
 if (filaCheia(f)){ return false; }
 else {
 f->a[f->fim % MAX] = n;
 f->fim++;
 f->tam++;
 return true;
 }
}
bool desinfileira (struct fila *f, int *r){
 if (filaVazia(f)){ return false; }
 else {
 *r = f->a[f->ini % MAX];
 f->ini++;
 f->tam--;
 return true;
 }
}
void exibeFila (struct fila *f){
 int i,n;
 for (i=0; i< f->tam; i++){
 desinfileira(f,&n);
 cout << n << " ";
 enfileira(f,n);
 }cout << "\n\n";
}
void invertePilha (struct pilha *p){
 int n; struct fila f;
 iniciaFila(&f);
 while (!pilhaVazia(p)){
 pop(p,&n);
 enfileira(&f,n);
 }
 while (!filaVazia(&f)){
 desinfileira(&f,&n);
 push(p,n);
 }
}
void inverteFila (struct fila *f){
 int n; struct pilha p;
 iniciaPilha(&p);
 while (!filaVazia(f)){
 desinfileira(f,&n);
 push(&p,n);
 }
 while (!pilhaVazia(&p)){
 pop(&p,&n);
 enfileira(f,n);
 }
}
int main(int argc, char* argv[]){
 struct pilha p;
 struct fila f;
 int x, op;
 iniciaPilha(&p);
 iniciaFila(&f);
 do {
 cout << "\n1 - Testa vazia";
 cout << "\n2 - Testa cheia";
 cout << "\n3 - Empilha";
 cout << "\n4 - Desempilha";
 cout << "\n5 - Exibir pilha";
 cout << "\n6 - Testa vazia";cout << "\n7 - Testa cheia";
 cout << "\n8 - Enfileira";
 cout << "\n9 - Desenfileira";
 cout << "\n10- Exibir fila";
 cout << "\n11- Inverter Pilha";
 cout << "\n12- Inverter Fila";
 cout << "\n13 - Sair";
 cout << "\nDigite sua opcao: ";
 cin >> op;
 switch (op){
 case 1: if (pilhaVazia(&p)){
 cout << "Sim\n\n";
 } else {
 cout << "Nao\n\n";
 }break;
 case 2: if (pilhaCheia(&p)){
 cout << "Sim\n\n";
 } else {
 cout << "Nao\n\n";
 }break;
 case 3: cout << "Digite um numero pra empilhar: ";
 cin >> x;
 if (push(&p,x)){
 cout << "Ok\n\n";
 } else {
 cout << "Erro\n\n";
 }break;
 case 4: if (pop(&p,&x)){
 cout << "Desempilhado = " << x <<"\n\n";
 } else {
 cout << "Erro\n\n";
 }break;
 case 5: exibePilha(&p); break;
 case 6: if (filaVazia(&f)){
 cout << "Sim\n\n";
 }else{
 cout << "Nao\n\n";
 }break;
 case 7: if (filaCheia(&f)){
 cout << "Sim\n\n";
 }else{
 cout << "Nao\n\n";
 }break;
 case 8: cout << "Digite um numero pra enfileirar: ";
 cin >> x;
 if (enfileira(&f,x)){
 cout << "Ok\n\n";
 }else{
 cout << "Erro\n\n";
 }break;
 case 9: if (desinfileira(&f,&x)){
 cout << "Desenfileirado = " << x <<"\n\n";
 }else{
 cout << "Erro\n\n";
 }break;
 case 10: exibeFila(&f); break;
 case 11: invertePilha(&p); break;
 case 12: inverteFila(&f); break;
 case 13: break;
 default: cout << "Opcao invalida . . .\n\n";
 }
 } while (op != 13);
 return 0;
}