Lista 1 EE

Prévia do material em texto

MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto
Departamento de Computação e Sistemas
Campus João Monlevade
Curso: Engenharia Elétrica
Disciplina: Algoritmos e Estruturas de Dados I - 2
o
semestre de 2013
Professor: Alexandre Magno de Sousa
Primeira Lista de Exercícios preparatória para a Primeira Prova - Data: 14/10/13
Obs: a lista deverá ser entregue no dia da prova (30 de outubro) e poderá ser feita em grupos
de até três pessoas. Será feita uma revisão do conteúdo para tirar dúvidas da lista no dia 28 de
outubro.
1. Um programa de uma indústria de automóveis armazena vários dados referentes aos carros
que fabrica. Desses dados, os principais são: marca do automóvel, modelo do automóvel, cor,
ano de fabricação e tipo do motor (por exemplo: 1.0, 1.6 ou 2.0). Diante das informações
apresentadas, crie uma estrutura para esses dados utilizando structs e typedef (recursos da
linguagem C). Depois de criar a estrutura, declare:
(a) um vetor que seja do tipo dessa estrutura e que armazene 100 (cem) automóveis.
(b) as linhas de instruções para realizar a leitura do campo referente ao modelo do auto-
móvel para todos os automóveis, ou seja, para os cem elementos do vetor.
(c) um ponteiro que seja do tipo dessa estrutura. Faça também alocação dinâmica de
memória para esse ponteiro em uma única célula de memória por meio do comando
calloc.
(d) a linha de instrução para realizar a leitura do campo tipo de motor por meio do ponteiro
declarado em (c) utilizando o operador seta.
2. Sabe-se que existem problemas relacionados ao uso de ponteiros, estes são classificados em
três, a saber: (1) ponteiros não inicializados; (2) ponteiros soltos; e, por fim, (3) células de
memórias perdidas. Diante disso, considere o trecho de código a seguir:
1. # include <stdio.h>
2. int main(){
3. float *alpha, *beta, *gama, delta;
4. beta =(float*) malloc(sizeof(float));
5. *beta = 7.987;
6. delta = 3.14;
7. beta = &delta;
8. *alpha = *beta;
9. return 0;
10. }
Responda o que se pede:
(a) Faça uma representação por meio de desenhos das atribuições e referências feitas com
os ponteiros do trecho de código apresentado anteriormente. Caso considere necessário,
identifique no desenho o número da linha de instrução do programa.
(b) Identifique os problemas com ponteiros existentes no trecho de código de acordo com
a classificação dada anteriormente no enunciado desta questão e argumente o porquê
do problema.
3. Utilizando aritmética de ponteiros, crie as seguintes funções:
(a) void StrLen(char *str): retorna o tamanho da string sem o barra zero.
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto
Departamento de Computação e Sistemas
Campus João Monlevade
(b) void StrCat(char *destino, char *origem): concatena a string origem na string destino.
(c) void StrCmp(char *str1, char *str2): retorna 1 se as duas strings forem iguais e 0 caso
contrário.
(d) void StrBlank(char *str): remove todos os espaços em branco da string str.
Crie programas que façam uso destas funções para verificar se elas estão funcionando corre-
tamente.
4. Sejam as seguintes estruturas:
typedef struct nomes{
char *nome;
char *sobrenome;
}TipoNome;
typedef struct data{
int dia;
int mes;
int ano;
}TipoData;
typedef struct documentos{
int cpf;
TipoData data_nascimento;
}TipoDocumentos;
typedef struct info_funcionais{
TipoNome nome;
TipoDocumentos doc;
float salario;
}TipoInfoFuncionais;
Dê o que se pede, escreva somente as instruções necessárias:
(a) Declare um ponteiro do tipo TipoInfoFuncionais e aloque três células de memória para
esse ponteiro.
(b) Leia o nome para o campo nome do ponteiro alocado em (a) para sua segunda célula
de memória, mas, antes de efetuar a leitura, não se esqueça de alocar memória para o
campo nome, pois ele também é um ponteiro.
(c) Faça a leitura do campo ano da data de nascimento do ponteiro alocado em (a).
(d) Por fim, libere a memória do ponteiro nome e depois libere a memória referenciada
pelo ponteiro declarado em (a).
5. Uma determinada loja necessita criar um sistema de cadastro e controle de estoque e neces-
sita armazenar os seguintes dados: descrição do produto, código do produto, quantidade,
preço unitário. Crie uma estrutura para estas informações. Faça um programa que armazene
cinco itens em um vetor, para isso, faça o que se pede:
(a) Faça uma função que receba um parâmetro do tipo da struct declarada, via referência,
e faça a leitura de cada informação.
Page 2
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto
Departamento de Computação e Sistemas
Campus João Monlevade
(b) Utilizando a função criada em (a) faça uma função que realiza o cadastro de itens no
vetor. Os itens deverão ser inseridos no vetor um de cada vez e sempre na última
posição disponível, caso o vetor esteja cheio, uma mensagem de que não é possível
cadastrar deverá ser informada.
(c) Crie uma função que receba como parâmetro o vetor de structs e calcule o valor total
de produtos em estoque.
(d) Desenvolva uma função que receba como parâmetro o vetor de structs e realize a im-
pressão de todos os dados cadastrados.
(e) Faça uma função que, dada a descrição de um produto, pesquise no vetor de structs se
o produto está cadastrado ou não.
(f) Crie uma função que receba o vetor de structs como parâmetro e coloque o vetor em
ordem decrescente de preço.
(g) Faça uma função que exclua um determinado produto pelo código do produto. Ao
excluir um produto do vetor, caso ele esteja cadastrado antes de algum outro produto,
os outros deverão ser rearranjados.
6. Crie uma função recursiva que recebe como parâmetro um número e seu expoente e calcule
a potência desse número a esse expoente.
7. Escreva uma função recursiva que retorne o comprimento de uma determinada string.
8. Faça uma função recursiva para somar os primeiros n termos da série:
1 +
1
2
− 1
3
+
1
4
− 1
5
...
9. Desenvolva uma função recursiva que converta uma cadeia de numerais (uma string que
contenha apenas digitos) em um inteiro. Por exemplo, a cadeia �1234� retornaria o número
1234. Dica: extrai-a os dígitos da direita para a esquerda, retirando primeiro a unidade,
depois a dezena, depois a centenas e assim por diante.
10. Encontre a função de complexidade do custo das atribuições dos seguintes trechos de código:
(a) for(k = 0; k < n - 2; k++)
for(i = k + 1; i <= n; i++){
x = vet[k][j];
vet[k][i] = vet[i][k];
vet[i][k] = x;
}
(b) i = 0;
while(i < n){
j = 0;
while(j <= n){
a[i][j] = b[i][j] + c[i][j];
j++;
}
i += 2;
}
(c) for(x = 0, j = 1; j <= n; j++)
for(i = 1; i <= j ; i++)
++x;
Page 3
MINISTÉRIO DA EDUCAÇÃO
Universidade Federal de Ouro Preto
Departamento de Computação e Sistemas
Campus João Monlevade
(d) void funcao(int *number){
int i, j, k;
for (i = 1; i < 4; i++)
for (j = i; j < n + 1; j++)
for (k = i; k < j + 1; k++)
*number = *number + i + j + k;
}
11. Qual das seguintes afirmações sobre o crescimento assintótico das funções não é verdadeira:
(a) 2n2 + 3n + 1 = O(n2).
(b) log n2 = O(log n).
(c) Se f(n) = O(g(n)) e g(n) = O(h(n)), então f(n) = O(h(n)).
(d) Se f(n) = O(g(n)), então g(n) = O(f(n))
(e) 2n+1 = O(2n).
(f) 22n = O(2n).
(g) f(n) = O(u(n)) e g(n) = O(v(n)) então f(n) + g(n) = O(u(n) + v(n))
(h) f(n) = O(u(n)) e g(n) = O(v(n)) então f(n)− g(n) = O(u(n)− v(n))
12. Sejam duas funções f(n) e g(n) que mapeiam números inteiros positivos em números reais
positivos. Com respeito às notações assintóticas de complexidade, avalie as afirmativas a
seguir.
A análise PERMITE CONCLUIR que
I. Diz-se que f(n) é O(g(n)) se existe uma constante real c > 0 e existe uma constanteinteira n0 ≥ 1 tal que f(n) ≤ c× g(n) para todo inteiro n ≥ n0.
II. Diz-se que f(n) é o(g(n)) se para toda constante real c > 0 existe uma constante inteira
n0 ≥ 1 tal que f(n) < c× g(n) para todo inteiro n ≥ n0.
III. Diz-se que f(n) é Ω(g(n)) se existe uma constante real c > 0 e existe uma constante
inteira n0 ≥ 1 tal que f(n) ≥ c× g(n) para todo inteiro n ≥ n0.
IV. Diz-se que f(n) é ω(g(n)) se para toda constante real c > 0 existe uma constante inteira
n0 ≥ 1 tal que f(n) > c× g(n) para todo inteiro n ≥ n0.
V. Diz-se que f(n) é Θ(g(n)) se, e somente se, f(n) é O(g(n)) e f(n) é Ω(g(n)).
(a) todas as afirmativas são falsas.
(b) todas as afirmativas são verdadeiras.
(c) apenas as afirmativas I e III são verdadeiras.
(d) apenas as afirmativas II e IV são verdadeiras.
(e) apenas a afirmativa V é falsa
Page 4