Exercícios de Estrutura de dados

Prévia do material em texto

Exercícios de Revisão
Passagem de parâmetros, escopo de variáveis, recursão, vetores, bubble sort
Analise o código abaixo e informe qual é a saída.
#include <iostream>
using namespace std;
int i = 10, j = 20;
void g (int i, int j, int k, int l){
 cout << i << " - " << j << " - " << k << " - " << l << endl;
}
void f (int *m, int *n, int p, int q) {
 int k, l;
 g (*m, *n, p, q);
 k = 5;
 l = 8;
 *m = 500;
 *n = 600;
 p = 800;
 q = 700;
 g (i, j, k, l);
 g (*m, *n, p, q);
}
int main()
{
 int i, j, k, l;
 i = 6;
 j = 7;
 k = 8;
 l = 9;
 g (i, j, k, l);
 {
 int j, k;
 i = 44;
 j = 45;
 k = 46;
 l = 47;
 g (i, j, k, l);
 f (&j, &k, i, l);
 }
 g (i, j, k, l);
 return 0;
}
2. A sequência de Fibonacci é definida por: 1, 1, 2, 3, 5, 8, 13, 21, ... Repare que os dois
primeiros termos são o número 1, e os demais são a soma dos dois termos predecessores.
Escreva um algoritmo iterativo que calcule e imprima o n-ésimo termo dessa sequência.
#include <iostream>
using namespace std;
unsigned long fibonacci(unsigned long number)
{
 if( ( number == 0) || (number == 1))
 return number;
 else
 return fibonacci(number - 1) + fibonacci(number - 2);
}
int main()
{
 int n;
 cout << "Digite um numero " << endl;
 cin >> n;
 n = n - 1;
 for(int j = 0; j <= n; j++)
 cout << "fibonacci( " << j + 1 << " ) = " << fibonacci(j + 1) << endl;
 return 0;
}
3. Faça a questão 2 usando recursividade.
#include <iostream>
using namespace std;
unsigned long fibonacci(int n){
 int g = 0;
 int l = 1;
 int k;
 for(k = 1; k <= n; k++){
 int t = g + l;
 g = l;
 l = t;
 }
 return l;
}
int main()
{
 int n, i;
 cout << "Digite um numero " << endl;
 cin >> n;
 //n = n - 1;
 for(int j = 0; j <= n; j++)
 {
 i = j;
 if((j == 1) || (j == 0))
 cout << "fibonacci( " << j + 1 << " ) = " << 1 << endl;
 else
 {
 cout << "fibonacci( " << j + 1 << " ) = " << fibonacci(i) << endl;}
 }
 return 0;
}
4. Uma empresa paga seu pessoal de vendas por comissão. Os vendedores recebem $200 por
semana mais 9% de suas vendas brutas por semana. Por exemplo, um vendedor que vende
$5.500 brutos em uma semana recebe $200 mais 9% de $5.500 ou um total de $695. Escreva
um programa (utilizando um array) que determine quanto o pessoal de vendas ganhou na
semana.
#include <iostream>
using namespace std;
int main()
{
 int n, vendas;
 cout << "Digite o numero de Empregados : ";
 cin >> n;
 int arr[n];
 for(int j = 0; j < n; j++)
 {
 cout << endl << "Digite o total de vendas do vendedor " << j + 1 << " : ";
 cin >> vendas;
 arr[j] = (vendas * 0.09) + 200;
 cout << endl << "Total do salario do venderdor " << j + 1 << " e " << arr[j] << endl;
 }
 return 0;
}
5. Construa um programa em C++ que declare um vetor de inteiros com 100 elemento. O
programa deve possuir uma função para inicializar o vetor, outra para efetuar a inversão dos
elementos do vetor e finalmente uma para impressão do vetor na saída padrão.
#include <iostream>
using namespace std;
void ler(int* vet)
{
 for(int j = 0; j < 6; j++)
 {
 cout << endl << "Digite um numero : ";
 cin >> vet[j];
 }
 for(int j = 0; j < 6; j++)
 {
 cout << " - " << vet[j] << " - ";
 }
}
void inverte(int* vetor)
{
int aux, i;
cout << endl;
for(int j = 0; j < 6; j++)
{
 i= 6 - j - 1;
 aux = vetor[j];
 vetor[j] = vetor[i];
 vetor[i] = aux;
cout << " - " << vetor[j] << " - ";
}
}
int main()
{
 int numeros[6];
 for(int j = 0; j < 1; j++)
 {
 ler(&numeros[j]);
 inverte(&numeros[j]);
 }
// inverte(6)
 return 0;
}
6. Construa um programa em C++ que receba através da linha de comando com a qual o
programa é executado, valores de i e j que correspondem ao número de linhas e de colunas
da matriz1 e da matriz2 (ambas matrizes de inteiros). O programa deve possuir uma função
para iniciar matrizes, outra para imprimir uma matriz na saída padrão e finalmente uma que
receba três matrizes e efetue a soma das duas primeiras colocando o resultado na terceira.
Através da utilização das funções existentes o programa deve inicializar as matrizes um e
dois, somá-las e imprimir a matriz resultante. OBS. A manipulação das matrizes deve ser
feita através de ponteiros.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class SomaMatriz{
public:
 SomaMatriz(int matrix[5][5],int i,int j)
 { }
 int linhas = 5, colunas = 5;
 void InicializarMatriz(int mat[5][5],int l, int c){
 cout<<"Digite os numeros da matriz: " << endl;
 for(int i=0;i<l;i++){
 for(int j=0;j<c;j++){
 cin>>mat[i][j];
 }
 }
 }
 void ExibirMatriz(int matrix[5][5],int l, int c)
 {
 cout<<"A Matriz eh : "<<endl;
 for(int i=0;i<l;i++){
 for(int j=0;j<c;j++){
 cout<<matrix[i][j]<<endl;
 }
 }
 }
 void SomarMatrizes(int matriz1[5][5],int matriz2[5][5],int matriz3[5][5]){
 for(int i=0;i<linhas;i++){
 for(int j=0;j<colunas;j++){
 matriz3[i][j]=matriz1[i][j]+matriz2[i][j];
 }
 }
 }
};
int main()
{
 int linhas, colunas;
 int matriz1[5][5],matriz2[5][5],matResult[5][5];
 cout<<"Digite a qtd de linhas: ";
 cin>>linhas;
 cout<<"Digite a qtd de colunas: ";
 cin>>colunas;
 SomaMatriz mat1(matriz1,linhas,colunas);
 SomaMatriz mat2(matriz2,linhas,colunas);
 SomaMatriz mat3(matResult,linhas,colunas);
 mat1.InicializarMatriz(matriz1,linhas,colunas);
 mat1.ExibirMatriz(matriz1,linhas,colunas);
 mat2.InicializarMatriz(matriz2,linhas,colunas);
 mat2.ExibirMatriz(matriz2,linhas,colunas);
 mat3.SomarMatrizes(matriz1,matriz2,matResult);
 mat3.ExibirMatriz(matResult,linhas,colunas);
 return 0;
}
7. Escreva um programa que classifica um array de 10 inteiros utilizando o método bubble
sort.
#include <iostream>
#include <vector>
using namespace std;
class ArrayBub
{
private:
 vector<int> v;
 int nEle;
 void troca(int um, int dois)
 {
 int temp = v[um];
 v[um] = v[dois];
 v[dois] = temp;
 }
public:
 ArrayBub(int tam) : nEle(0)
 {
 v.resize(tam);
 }
 void insert(int value)
 {
 v[nEle] = value;
 nEle++;
 }
 void display()
 {
 for(int j = 0; j < nEle; j++)
 cout << " - " << v[j] << " - ";
 cout << endl;
 }
 void bubbleSort()
 {
 int out, in;
 for (out = nEle - 1; out > 1; out--)
 for(in = 0; in < out; in++)
 if (v[in] > v[in + 1])
 troca(in, in + 1);
 }
};
int main()
{
 int max = 10, n;
 ArrayBub arr(max);
 for(int j = 0; j < 10; j++)
 {
 cout << "Digite um numero : ";
 cin >> n;
 arr.insert(n);
 cout << endl;
 }
 arr.display();
 cout << endl;
 arr.bubbleSort();
 arr.display();
 return 0;
}
8. Faça um programa que leia 20 números, cada um dos quais está entre 10 e 100, inclusive. À
medida que cada número é lido, valide-o e armazene-o no array somente se ele não for uma
duplicata de um número já lido. Depois de ler todos os valores, exiba somente os valores
únicos que o usuário inseriu. Previna-se para o 'pior caso' em que todos os 20 números são
diferentes. Utilize o menor array possível para resolveresse problema.
#include <iostream>
using namespace std;
int validar(int k)
{
 int n;
 cout << "Digite um numero : ";
 cin >> n;
 if(n >= 10 && n <= 100)
 return n;
 else
 cout << endl << "O numero digitado nao e valido !!!" << endl;
 validar(k);
}
int main()
{
 int array[20];
 for(int j = 0; j < 20; j++)
 {
 array[j] = validar(j);
 }
 for(int j = 0; j < 20; j++)
 cout << " - " << array[j] << " - ";
 return 0;
}
9. O que o seguinte programa faz?
#include <iostream>
using namespace std;
int whatIsThis(int b[], int size)
{
 if(size == 1)
 return b[0];
 else
 return b[size -1] + whatIsThis(b, size - 1);
}
int main()
{
 const int arraySize = 10;
 int a[arraySize] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 int result = whatIsThis(a, arraySize);
 cout << "Result is " << result << endl;
 return 0;
}
10. Uma pequena companhia aérea acabou de comprar um computador para seu novo sistema
automatizado de reservas. Você foi solicitado a programar o novo sistema. Você escreverá
um programa para atribuir assentos em cada vôo da companhia aérea (capacidade: 10
assentos).
Seu programa deve exibir o seguinte menu de alternativas – Por favor digite 1 para
“Primeira Classe” ou 2 para “Classe Econômica”. Se a pessoa digitar 1, seu programa deve
atribuir um assento na primeira classe (assentos 1-5). Se a pessoa digitar 2, seu programa
deve atribuir um assento na classe econômica (assentos 6-10). Seu programa deve imprimir
um bilhete de embarque indicando o número do assento da pessoa e se ela está na primeira
classe ou na Classe econômica do avião.
Utilize um array e inicialize-o com 0 para indicar que todos os assentos estão vazios. À
medida que cada assento é atribuído, configure os elementos correspondentes do array com
1 para indicar que o assento não está mais disponivel.
Quando a primeira classe estiver lotada, seu programa deve perguntar à pessoa se ela aceita
ficar na classe econômica (e vice-versa). Se ela aceitar, faça a atribuição apropriada de
assento. Caso contrário, imprima a mensagem “O próximo vôo saíra em 3 horas”.
#include <iostream>
#include<stdlib.h>
#include <stdio.h>
using namespace std;
void bilhete2(int b)
{
 if(b < 11)
 cout << "---------------------------------" << endl << "Voce esta na Classe Economica" << endl << "E sua Cadeira e a de numero : " << b + 1 << endl << "---------------------------------" << endl;
 else
 cout << "---------------------------------" << endl << "Voo Lotado" << endl << "---------------------------------" << endl;
}
void bilhete(int p)
{
 if(p < 5)
 cout << "---------------------------------" << endl << "Voce esta na Primeira Classe" << endl << "E sua Cadeira e a de numero : " << p + 1 << endl << "---------------------------------" << endl;
 else
 cout << "---------------------------------" << endl << "Voo Lotado" << endl << "---------------------------------" << endl;
}
int primeiraclasse(int bil)
{
 system("cls");
 if(bil >= 5)
 return 1;
 else
 {bilhete(bil);
 return 0;}
}
int economica(int bil2)
{
 system("cls");
 if(bil2 >= 10)
 return 2;
 else {
 bilhete2(bil2);
 return 0;
 }
}
int decisao(int c, int b1, int b2,int l, int opc)
{
 int voo, pergunt;
 cout << "Digite o tipo de voo :" << endl << "1 - Primeira Classe " << endl << "2 - Classe economica" << endl;
 cin >> voo;
 if(l == 0)
 {
 if(voo == 1)
 {
 opc = primeiraclasse(b1);
 if(opc == 1)
 decisao(c, b1, b2, 1, 1);
 else
 return 1;
 }
 else if(voo == 2)
 {
 opc = economica(b2);
 if(opc == 2)
 decisao(c, b1, b2,1,2);
 else
 return 2;
 }
 else
 {
 cout << "Digite um numero valido!!";
 decisao(c, b1, b2, l, opc);
 }
 }
 if(opc == 2)
 {
 cout << "O voo na Classe economica esta lotado" << endl;
 cout << "Aceita ir na Primeira classe ? Digite 1 caso Sim ou 2 caso Nao queira" << endl;
 cin >> pergunt;
 if(pergunt == 1)
 {
 primeiraclasse(b1);
 return 1;
 }
 else { if(pergunt == 2)
 economica(b2);
 return 2;
 }
 }
 else{ if(opc == 1)
 {
 cout << "O voo na Primeira Classe esta Lotado " << endl;
 cout << "Aceita ir na classe Economica? Digite 1 caso Sim ou 2 caso Nao queira" << endl;
 cin >> pergunt;
 if(pergunt == 2)
 {
 primeiraclasse(b1);
 return 1;
 }
 else { if(pergunt == 1)
 economica(b2);
 return 2;
 }
 }
}
}
int main()
{
 int a1 = 0, a2 = 5, b, voos[10], opcao = 0;
 for(int j = 0; j < 10; j++)
 {
 voos[j] = 0;
 }
 for(int j = 0; j < 10; j++)
 {
 b = decisao(j, a1, a2, 0, opcao);
 if(b == 1){
 if (a1 != 5)
 {
 voos[a1] = 1;
 a1 = a1 + 1;
 }
 }
 else {
 if (b == 2){
 if (a2 != 10)
 {
 voos[a2] = 1;
 a2 = a2 + 1;
 }
 }
}
 }
 return 0;
}
11. O que o seguinte programa faz?
#include <iostream>
using namespace std;
void somefuction(int [], int, int);
int main()
{
 const int arraysize = 10;
 int a[arraysize] = {1,2,3,4,5,6,7,8,9,10};
 cout << "Os valores no array sao: " << endl;
 somefuction(a, 0, arraysize);
 cout << endl;
 return 0;
}
void somefuction(int b[], int current, int size)
{
 if(current < size)
 {
 somefuction(b, current + 1, size);
 cout << b[current] << " ";
 }
}
12. Um palíndrome é uma string que é lida da mesma maneira, quer da esquerda para a direita,
quer da direita para a esquerda. Alguns exemplos de palíndrome são “radar”. Escreva uma
função recursiva testPalindrome que retorna true se a string armazenada no array for um
palíndromo e false caso contrário.
#include <iostream>
#include <string>
using namespace std;
bool TestaPalidrome(){
 string palavra;
 cout<<"Digite a palavra: "<<endl;
 cin>>palavra;
 for(int i=0, j ;i>=j;i++,j--){
 if(palavra[i]!= palavra[j]){
 return false;
 }
 return true;
 }
}
int main(){
 int n;
 for(int i=0;i<n;i++)
 {
 if(TestaPalidrome())
 cout<<"Eh Palindrome"<<endl;
 else
 cout<<"Nao Eh Palindrome"<<endl;
 }
 return 0;
}