Exercícios de Estrutura de Dados em C

Prévia do material em texto

MC202 – Estrutura de Dados
Lista de exerc´ıcios 1
7 de agosto de 2013
To´picos:
• Vetores unidimensionais;
• Matrizes e vetores multidimensionais;
• Estruturas;
• Apontadores;
• Alocac¸a˜o dinaˆmica de memo´ria.
1 [1] Seja uma matriz tridimensional Al×m×n armazenada em um vetor b(l·m·n)×1 (bT e´ o vetor
transposto):
bT = [a111, a112, . . . , a11n, a121, a122, . . . , a12n, . . . , alm1, alm2, . . . , alm(n−1), almn] (1)
Escreva uma expressa˜o matema´tica que relaciona os elementos da matriz A com os elementos do
vetor b.
2 [1] Explique como armazenar de maneira eficiente duas matrizes sime´tricas An×n e Bn×n em uma
u´nica matriz retangular C. Escreva duas expresso˜es matema´ticas que relacionam os elementos da
matriz A e da matriz B com os elementos da matriz C.
3 [1] Uma matriz tridiagonal e´ uma matriz quadrada An×n onde ai,j = 0 se |i− j| > 1.
An×n =

x x 0 · · · · · · 0
x x x 0
...
0 x x x 0
... 0 x x x
. . .
0
. . .
. . .
. . . 0 0
. . . x x x 0
... 0 x x x
0 · · · · · · 0 x x

=⇒ b(3n−2)×1 =

a1,1
a1,2
a2,1
a2,2
a2,3
...
a(n−1),(n−2)
a(n−1),(n−1)
a(n−1),n
an,(n−1)
an,n

1
Considere a matriz tridiagonal A acima onde x representa um elemento inteiro possivelmente na˜o
nulo. Considere tambe´m que os poss´ıveis elementos na˜o nulos da matriz sa˜o armazenados, linha a
linha, em um vetor b. Descreva um algoritmo para obter o valor de um elemento gene´rico ai,j ∈ A,
dado o seguinte proto´tipo:
int acessaMatrizTridiagonal(int i, int j, int n, int b[]);
4 [1] Uma matriz de banda e´ uma generalizac¸a˜o de uma matriz tridiagonal, onde os elementos
na˜o nulos esta˜o confinados a 2k + 1 diagonais centradas na diagonal principal, para algum inteiro
k. Explicite em termos de k e n a quantidade de elementos na˜o nulos dessa matriz. Generalize o
algoritmo do exerc´ıcio [3] para uma matriz de banda utilizando o seguinte proto´tipo:
int acessaMatrizBanda(int i, int j, int k, int n, int b[]);
5 [3] No co´digo abaixo, qual sera´ o valor da varia´vel b apo´s a execuc¸a˜o da func¸a˜o DefineValor?
void DefineValor(int c, int *e){
c = 7;
*e = 11;
}
int main (){
int b = 1;
DefineValor(b, &b);
return 0;
}
6 [4] Escreva uma func¸a˜o em C que (i) recebe um vetor V (valor), seu tamanho n (valor) e dois
apontadores para inteiro min e max (refereˆncia), (ii) encontra os valores mı´nimo e ma´ximo em V e
(iii) retorna os enderec¸os desses valores em min e max .
7 [2, 12.2] Suponha que as seguintes declarac¸o˜es foram realizadas:
int v[] = {5, 15, 34, 54, 14, 2, 52, 72};\\
int *p = &v[1], *q = &v[5];
a. Qual o valor de *(p+3)?
b. Qual o valor de *(q-3)?
d. A expressa˜o p < q tem valor verdadeiro ou falso?
e. A expressa˜o *p < *q tem valor verdadeiro ou falso?
8 [2, 12.2] Qual o conteu´do do vetor v apo´s a execuc¸a˜o do seguinte trecho de co´digo?
#define N 10
int v[N] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int *p = &v[0], *q = &v[N-1], temp;
2
while (p < q) {
temp = *p;
*p++ = *q;
*q-- = temp;
}
9 [4] Escreva uma func¸a˜o em C para alocar um cubo de dimenso˜es n×m× r dinamicamente na
forma de vetor de apontadores.
10 [3] Nos itens abaixo voceˆ devera´ completar as func¸o˜es enunciadas de forma a construir uma
calculadora de polinoˆmios de grau um, com operac¸o˜es simples de soma, subtrac¸a˜o e multiplicac¸a˜o.
Para completar os exerc´ıcios, voceˆ devera´ utilizar os tipos de dado definidos abaixo.
typedef struct {
/* a + b*x */
int a, b;
} PolinomioGrauUm;
typedef struct {
/* a + b*x + c*x^2 */
PolinomioGrauUm *p;
int c;
} PolinomioGrauDois;
(i) Construa uma func¸a˜o que aloque dinamicamente um PolinomioGrauUm para os valores a e
b) fornecidos como paraˆmetro e o retorne. Tambe´m construa uma func¸a˜o que aloque dinami-
camente um PolinomioGrauDois para os valores a, b e c fornecidos como paraˆmetro e o
retorne.
PolinomioGrauUm *CriaPoliGrauUm(int a, int b);
PolinomioGrauDois *CriaPoliGrauDois(int a, int b, int c);
(ii) Construa duas func¸o˜es: uma que realize a soma de dois polinoˆmios de grau um e outra que
realize a soma entre um polinoˆmio de grau um e um escalar inteiro. O resultado da soma, em
ambas as func¸o˜es, deve ser alocado dinamicamente e retornado.
PolinomioGrauUm *SomaPoli(PolinomioGrauUm p, PolinomioGrauUm q);
PolinomioGrauUm *SomaEscalar(PolinomioGrauUm p, int e);
(iii) Idem ao anterior, mas implemente a operac¸a˜o de subtrac¸a˜o no lugar da soma.
PolinomioGrauUm *SubPoli(PolinomioGrauUm p, PolinomioGrauUm q);
PolinomioGrauUm *SubEscalar(PolinomioGrauUm p, int e);
(iv) Construa duas func¸o˜es: uma que realize a multiplicac¸a˜o entre um polinoˆmio de grau um e um
escalar inteiro e outra que realize multiplicac¸a˜o de dois polinoˆmios de grau um (gerando um
polinoˆmio de grau dois, que deve ser armazenado por uma varia´vel do tipo PolinomioGrauDois).
PolinomioGrauUm *MultEscalar(PolinomioGrauUm p, int e);
PolinomioGrauDois *MultPoli(PolinomioGrauUm p, PolinomioGrauUm q);
3
Refereˆncias
[1] Anamaria Gomide, 2013.
[2] Fabio Henrique Viduani Martinez. Algoritmos e programacao de computadores ii. Apostila,
2011.
[3] Lucas T. Teixeira, 2013.
[4] Guilherme Pimentel Telles, 2013.
4