p2 mc102 2014

Prévia do material em texto

MC102 – Algoritmos e Programac¸a˜o de Computadores
1o semestre de 2014 – Turmas Coordenadas
2a Prova (24/06/2014)
Nome:
RA: Turma:
Questa˜o Valor Nota
1 3,0
2 3,0
3 3,0
4 3,0
Total 12,0
Instruc¸o˜es (LEIA!!!!!)
1. A durac¸a˜o da prova e´ de 100 minutos.
2. Na˜o e´ permitida consulta a qualquer material.
3. Somente sera˜o consideradas respostas nos espac¸os indicados.
4. Use o verso das folhas apenas como rascunho.
5. Celulares, tablets, pagers, calculadoras e demais dispositivos eletroˆnicos de comunicac¸a˜o ou
computac¸a˜o devem permanecer desligados durante toda a prova.
6. Nenhum aluno sera´ autorizado a deixar a sala de prova antes que tenham decor-
ridos 70 minutos desde o seu in´ıcio.
7. Todo aluno que deixar a sala de prova devera´ entrega´-la em definitivo.
8. Todos os co´digos devem ser escritos na linguagem de programac¸a˜o C.
9. Nos espac¸os reservados para as respostas, cada ce´lula do formula´rio quadriculado deve conter
uma letra do texto da resposta. Em adic¸a˜o, indentac¸a˜o deve ser utilizada para facilitar
a leitura de toda resposta que seja um programa ou trecho de programa em C. Questo˜es
cujas respostas na˜o estejam formatadas de acordo com esta regra perdera˜o 20% de seu valor
nominal.
10. Nas questo˜es que pedem como respostas programas em C a clareza do programa sera´ um
fator muito relevante para a avaliac¸a˜o.
11. BOA PROVA!
1. Considere o trecho de programa em C abaixo:
1 struct sA { int sc ; int ∗ s ; } ;
2 typedef struct sA∗ tipA ;
3
4 tipA criaA ( int sc ) {
5 tipA s ;
6 s = mal loc ( s izeof ( tipA ) ) ;
7 s−>sc = sc ;
8 s−>s = mal loc ( sc ∗ s izeof ( int ) ) ;
9 return s ;
10 }
11
12 tipA m i s t e r i o ( tipA x , tipA y ) {
13 tipA z ; int tc ;
14 int i , j ;
15 int i t ;
16
17 z = criaA ( ( (∗ x ) . sc )+(y−>sc ) ) ;
18 tc = 0 ;
19 for ( i=x−>sc −1; i >=0; i−−) { z−>s [ i ] = x−>s [ i ] ; t c++; }
20 for ( i =0; i<y−>sc ; i++) {
21 i t= 0 ;
22 for ( j =0; j<x−>sc ; j++) i f (y−>s [ i ] == z−>s [ j ] ) i t = 1 ;
23 i f ( ! i t ) { z−>s [ t c ] = y−>s [ i ] ; t c++; }
24 }
25 z−>sc = tc ;
26 return z ;
27 }
Inicialize os atributos das instaˆncias x e y de tipA com os d´ıgitos do seu RA e com os d´ıgitos da data
de ontem, respectivamente. Em seguida, invoque a func¸a˜o misterio com x e y como paraˆmetros.
Escreva em z o resultado retornado por misterio.
Preenchimento dos diagramas de x, y e z: A data deve ser escrita no formato DDMMAA (D
de dia, M de meˆs, A de Ano). Por exemplo, se o RA fosse 077432 e a data fosse 13/06/2013 os
inteiros a serem utilizados na inicializac¸a˜o de x e y seriam: 0,7,7,4,3,2 e 1,3,0,6,1,3, respectivamente.
Nesse caso, os campos sc dos diagramas de x e y teriam ambos sido inicializados com o valor 6,
porque o atributo sc indica o tamanho do vetor s.
A notac¸a˜o “s: ↓” significa que s e´ um apontador para o vetor de inteiros, desenhado imediatamente
abaixo da seta, cujas posic¸o˜es devem ser preenchidas da esquerda para a direita, de cima para
baixo.
x
sc: s: ↓
y
sc: s: ↓
z
sc: s: ↓
2. No laborato´rio 08, denominado “Killing the messenger”, um aluno de MC102 observou que a
biologia molecular era apenas pano de fundo para a especificac¸a˜o do seguinte problema: Dadas
duas cadeias de caracteres x e y, x ≤ y, verifique se o complemento reverso de x ocorre em y. O
co´digo do programa C escrito por esse aluno encontra-se logo abaixo. Infelizmente, esse co´digo
conte´m 2 erros. Escreva no espac¸o reservado para a resposta desta questa˜o a versa˜o correta do
co´digo fornecido. Na˜o e´ necessa´rio copiar o co´digo todo, basta indicar, utilizando o nu´mero da
linha de co´digo, onde e qual foi a correc¸a˜o realizada. Na˜o introduza novas linhas, se precisar inserir
co´digo, insira-o no ponto correto de uma linha ja´ existente, modificando-a como achar necessa´rio.
Por exemplo, se o erro fosse simplesmente a falta de um “;” na linha 10, voceˆ deveria escrever na
folha de resposta: 1 0 c h a r * c ; . Outro exemplo, se o erro fosse a falta de
iniciac¸a˜o de i, na linha 59, a correc¸a˜o seria indicada como:
5 9 i n t a c h o u = 0 ; i = - 1 ; .
1 #define MAXY 101
2 #define MAXX 26
3 void r ev e r s o (char ∗x , char∗ r ) ;
4 char∗ complemento ( char ∗x ) ;
5 int procura (char ∗c , char ∗x ) ;
6
7 int main ( ) {
8 int sx , sy , achou ;
9 char y [MAXY] , x [MAXX] , r [MAXX] ;
10 char ∗c ;
11
12 scan f ( ”%s ” , y ) ;
13 s can f ( ”%s ” , x ) ;
14
15 r eve r s o (x , r ) ;
16 c = complemento ( r ) ;
17 i f ( procura ( c , y ) )
18 p r i n t f ( ”%s oco r r e em %s .\n” , x , y ) ;
19 else
20 p r i n t f ( ”%s nao oco r r e em %s .\n” , x , y ) ;
21
22 return 0 ;
23 }
24
25 void r ev e r s o (char ∗x , char ∗ r ) {
26 char ch ; int n ;
27 i f ( (∗ x)== ’ \0 ’ ) { (∗ r)= ’ \0 ’ ;}
28 else {
29 r eve r s o (x , r ) ;
30 n=s t r l e n ( x ) ;
31 ∗( r+n−1)=∗x ;
32 ∗( r+n)= ’ \0 ’ ;
33 }
34 }
35
36 char∗ complemento ( char ∗x ) {
37 char ∗c ; int i ;
38 int sx = s t r l e n ( x ) ;
39 c = mal loc ( ( sx +1)∗ s izeof (char ) ) ;
40
41 for ( i = 0 ; i<sx ; i++) {
42 switch ( x [ i ] ) {
43 case ’C ’ : { c [ i ] = ’G’ ; break ; }
44 case ’G ’ : { c [ i ] = ’C ’ ; break ; }
45 case ’A ’ : { c [ i ] = ’U ’ ; break ; }
46 case ’U ’ : { c [ i ] = ’A ’ ; break ; }
47 }
48 }
49 c [ i ] = ’ \0 ’ ;
50
51 return c ;
52 }
53
54 int procura (char ∗c , char ∗x ) {
55 int i , j ; int sx , sc ;
56 sx = s t r l e n ( x ) ;
57 sc = s t r l e n ( c ) ;
58
59 int achou = 0 ;
60 for ( i = 0 ; ( ( i <(sx−sc ) ) && ( ! achou ) ) ; i++) {
61 achou = 1 ;
62 for ( j = 0 ; ( ( j<sc ) && ( achou ) ) ; j++) {
63 i f ( c [ i+j ] != x [ i ] ) achou = 0 ;
64 }
65 }
66 return achou ;
67 }
Espac¸o reservado para a resposta da Questa˜o 2.
3. Como vimos no Laborato´rio 10, um vetor pode ser utilizado para armazenar os elementos de
uma matriz. A seguir aparece a definic¸a˜o do tipo Matriz utilizado na programac¸a˜o da soluc¸a˜o para
o laborato´rio 10.
1 typedef struct matr i z {
2 int nc , n l ; /∗ nc : numero de colunas , n l : numero de l i n h a s ∗/
3 int n ; /∗ n : nc∗ n l ( tamanho da matr iz ) ∗/
4 int ∗v ; /∗ v : v e t o r de i n t e i r o s de tamanho de tamanho n ∗/
5 } Matriz ;
Suponha implementadas as func¸o˜es CriaMatriz, DestroiMatriz, ImprimeMatriz e CarregaMatriz,
como especificadas abaixo. Portanto, voceˆ na˜o precisa implementa´-las mas deve utiliza´-las na
soluc¸a˜o da questa˜o.
1 /∗ Aloca a memoria nece s sa r i a para a in s t anc iacao ∗/
2 /∗ de uma matrix de tamanho n l inhas por ncolunas ∗/
3 Matriz∗ CriaMatr iz ( int nl inhas , int ncolunas ) ;
4
5 /∗ Desaloca a memoria or i g ina lmente a locada para uma matr iz ∗/
6 /∗ retornando−a para o con t r o l e do s i s tema operac iona l ∗/
7 void Destro iMatr i z ( Matriz ∗m) ;
8
9 /∗ Imprime os e lementos da Matriz na sa ida padrao . ∗/
10 void ImprimeMatriz ( Matriz ∗m) ;
11
12 /∗ Carrega na matr iz os $n$ e lementos l i d o s da entrada padrao ∗/
13 void CarregaMatriz ( Matriz ∗m) ;
Implemente em C as func¸o˜es especificadas a seguir e um programa main que mostra como utilizar
a func¸a˜o TranspoeMatriz.
1 /∗ Retorna o ind i c e do ve to r em funcao da l i nha e coluna da matr iz ∗/
2 int IndiceDadoLinhaColuna ( Matriz ∗m, int l inha , int coluna ) ;
3
4 Matriz∗ TranspoeMatriz ( Matriz ∗m) ;
Espac¸o reservado para a resposta da Questa˜o 3.
Espac¸o reservado para a resposta da Questa˜o 3.
Espac¸o reservado para a resposta da Questa˜o 3.
4. Dado um inteiro n entre 0 e 999999999, escreva a func¸a˜o recursiva void imprimeEne(int n)
que imprime cada digito de n, separado por um espac¸o, na ordem em que aparece em n. Por
exemplo, se imprimeEne for chamada com 82134950 imprimira´ a cadeia “8 2 1 3 4 9 5 0 ”.