AEDS I - 2ª Prova - UFMG 2015/1 - Rodolfo Resende

Prévia do material em texto

Universidade Federal de Minas Gerais 
Instituto de Ciências Exatas 
Departamento de Ciência da Computação 
Algoritmos e Estruturas de Dados I – 1° Semestre 2015 – 2ª Prova 
 
A folha de resposta deve conter na página 1: Q1 e Q2, na página 2: Q3 e Q4, na página 3: Q5 e Q6 e na 
página 4: Q7 e Q8. 
 
 
1. Mostre o que é impresso na execução do trecho de programa abaixo: 
 
int ii,jj; 
int a[4][5]={{1,1,1,1,1},{1,0,0,0,1},{1,0,0,0,1},{1,1,1,1,1}}; 
for(ii=0; ii<4; ii++){ 
for(jj=0; jj<5; jj++) 
 printf(“%c”,a[ii][jj]?’*’:’.’); 
printf(“\n”); 
} 
 
 
2. Faça um desenho, conforme as convenções de sala de aula, que mostra as estruturas em 
memória construídas a partir das sentenças abaixo. O desenho deve mostrar o que é (i) 
inicio, (ii) i, (iii) f e (iv) m e os demais elementos. 
 
struct E{int info; struct E *prox;}; 
struct E f={1,NULL}; struct E m={2,&f}; struct E i={0,&m}; 
struct E *inicio=&i; 
 
 
3. O trecho de programa C abaixo mostra uma possível implementação de um método de 
ordenação conhecido como “bolha”. Mostre o que é impresso por (imprime(x,N)) 
para a invocação bolha(ai,5) onde o arranjo ai é definido por int 
ai[]={50,20,10,40,30}; A invocação imprime(ai,5) escreve 50 20 10 40 
30. 
 
void bolha(int x[], int N){ 
 int ordenado; int temp; int ii; 
 do{ 
 ordenado=TRUE; 
 for(ii=0; ii<N; ii++) 
 if(x[ii]>x[ii+1]){ 
 temp=x[ii]; x[ii]=x[ii+1]; x[ii+1]=temp; 
 ordenado=FALSE; 
 } 
 Imprime(x,N); 
 }while(!ordenado); 
}; 
 
 
 
 
 
 
 
 
 
4. Considere a função r() e responda o que é impresso para a invocação mostrada abaixo. 
 
int r(int e[], int t[]){ 
 int uresp=0, dresp=0; 
 int ii,jj; 
 for(ii=0; ii<4; ii++) if(e[ii]==t[ii]) dresp++; 
 for(ii=0; ii<4; ii++) 
 for(jj=0; jj<4; jj++) 
 if(e[ii]==t[jj]) uresp++; 
 return dresp*10 + (uresp-dresp); 
} 
 
int esc[]={1,1,2,2}; 
int ten[]={1,2,1,2}; 
printf(“%d\n”,r(esc,ten)); 
 
 
5. Considere o trecho de programa abaixo. Explique porque a função valida() funciona 
corretamente e a função valida2() as vezes funciona e as vezes apresenta problemas. 
Sua explicação deve ter foco na comutatividade do operador &&. Considere LINHAS=8 
e COLS=13. 
 
int a[LINHAS][COLS]= 
 { {1,1,1,0,1,1,0,0,0,1,1,1,1}, 
 {1,0,1,1,1,0,1,1,1,1,0,0,1}, 
 {1,0,0,0,1,0,1,0,1,0,0,0,1}, 
 {1,1,1,0,1,1,1,0,1,0,0,0,1}, 
 {1,0,1,0,0,0,0,1,1,1,0,0,1}, 
 {1,0,0,1,1,1,1,1,0,1,1,1,1}, 
 {0,0,0,0,0,0,0,0,0,0,0,0,1}, 
 {1,1,1,1,1,1,1,1,1,1,1,1,1} }; 
int valida(int lin, int col){ 
 return lin>=0&&lin<LINHAS&&col>=0&&col<COLS&&a[lin][col]==1; 
} 
int valida2(int lin, int col){ 
 return a[lin][col]==1&&lin>=0&&lin<LINHAS&&col>=0&&col<COLS; 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
6. A função abaixo utiliza o arranjo a definido na questão anterior de forma global. Mostre 
como fica o arranjo a após a invocação temCaminhoPor(0,0). Considere 
TENTATIVA=3; CAMINHO=4; 
 
int temCaminhoPor(int lin, int col){ 
 int chegou=FALSE; 
 if(valida(lin, col)){ 
 a[lin][col]=TENTATIVA; 
 if(lin==LINHAS-1&&col==0) 
 chegou=TRUE; 
 else{ 
 chegou=temCaminhoPor(lin+1, col); 
 if(!chegou) chegou=temCaminhoPor(lin,col+1); 
 if(!chegou) chegou=temCaminhoPor(lin-1,col); 
 if(!chegou) chegou=temCaminhoPor(lin,col-1); 
 } 
 if(chegou) a[lin][col]=CAMINHO; 
 } 
 return chegou; 
} 
 
 
7. Considere que a função f1() chama a função f2() e que f2() chama a função f3(). 
Considere que f3() pode lançar uma exceção do tipo ERROtipoX. Mostre um trecho 
de código da função f2() onde (i) é verificado se houve o lançamento de exceção do 
tipo ERROtipoX por parte de f3(), caso positivo deve ser executada a sentença 
cout<<”sim lançou!”<<endl; caso negativo deve ser executada a sentença 
cout<<”não lançou!”<<endl; e (ii) se houve lançamento ele é “propagado”; Em 
outras palavras, f2() verifica e escreve se houve ou não o lançamento mas quem deverá 
tratar o lançamento é f1(). 
 
8. Considere um programa em C++ com o trecho abaixo precedendo a função main(). 
Mostre o que aparece na tela antes, durante e após terem sido instanciadas na função 
main() duas variáveis do tipo B(B v1,v2;). 
 
int m(int i){cout<<i<<endl; return i;} 
class A{ public: static int a2,a3; int h; A(){h=m(1);}}; 
int A::a2=m(2); 
int A::a3=m(3); 
class B:public A{public: static int b1, b2; int g; B(){g=m(4);}}; 
int B::b1=m(5); 
int B::b2=m(6);