MAC 2166 - Introdução à Computação para Engenharia
ESCOLA POLITÉCNICA - PRIMEIRO SEMESTRE DE 2001
Simulado para a terceira Prova

Nome:


Assinatura:


N $^{\mbox{\scriptsize\b{o}}}$ USP: Turma:


Professor:

Instruções:

1. Não destaque as folhas deste caderno.
2. Preencha o cabeçalho acima.
3. A prova pode ser feita a lápis. Cuidado com a legibilidade.
4. A prova consta de $3$ questões. Verifique antes de começar a prova se o seu caderno de questões está completo.
5. Não é permitido o uso de folhas avulsas para rascunho.
6. Não é permitido a consulta a livros, apontamentos ou colegas.
7. Não é permitido o uso de calculadoras.
8. Não é necessário apagar rascunhos no caderno de questões.
9. Qualquer questão pode ser resolvida em qualquer página. Se a resposta não está na página correspondente ao enunciado da questão, indique claramente em qual página se encontra a resposta.

DURAÇÃO DA PROVA: 2,5 horas

Questão	Valor	Nota
1	3.5
2	3.5
3	3.0
Total	10.0

1. (valor 3.5 pontos)
   Dizemos que uma matriz $A$ com dimensões $n \times n$ é a matriz inversa de uma matriz $B$ também $n \times n$, se o produto das matrizes for igual à matriz identidade.

   Faça um programa que leia um inteiro $n$, matrizes quadradas $A$ e $B$, de dimensões $n \times n$ e verifica se $B$ é a inversa de $A$. Suponha que $0 < n \leq 100$.

2. (valor 3.5 pontos)
   Faça uma função de protótipo

   
     void empurra (int vet[MAX], int n, int i);
   

   que recebe um vetor vet com n elementos e desloca de uma posição para frente todos os elementos do vetor a partir da posição i. Considere $0 \leq$ i $<$ n.

   Exemplo: Considere o vetor abaixo com $n=11$,

   12

   3

   -4

   7

   1

   13

   0

   8

   19

   11

   17

   Ao executar-se a função empurra com $i = 3$, teremos:

   12

   3

   -4

   7

   7

   1

   13

   0

   8

   19

   11

   17

   Note que o elemento na posição $3$, após a execução da função aparece duplicado no vetor.

3. (valor 3.0)
   Faça um programa que leia um inteiro $n > 0$ e uma seqüência com $n$ números inteiros e a ordena utilizando o método de ordenação por inserção descrito a seguir. Você deve usar a função da questão anterior, e não precisa reescrevê-la nesta questão.

   Em cada iteração $k$ do método o vetor $v$ estará ordenado nas posições anteriores a $k$ (ou seja, $v[0] \le v[1] \le \dots \le v[k-1]$). A idéia é determinar em que posição $i$ o elemento $v[k]$ deverá ser inserido nesta parte ordenada, empurrar os elementos $v[i], v[i+1], \dots v[k-1]$ de uma posição usando a função da questão anterior, abrindo espaço para o elemento que estava em $v[k]$ e finalmente colocá-lo na posição $i$ do vetor.

   Exemplo: Considere o vetor abaixo com $n=7$,

   12

   3

   -4

   7

   1

   13

   3

   Na iteração $k=0$ o elemento 12 fica na posição $v[0]$:

   12	3	-4	7	1	13	3

   Na iteração $k=1$ o $12$ é empurrado e o $3$ inserido na posição $v[0]$:

   3	12	-4	7	1	13	3

   Para $k=2$:

   -4	3	12	7	1	13	3

   Para $k=3$:

   -4	3	7	12	1	13	3

   Para $k=4$:

   -4	1	3	7	12	13	3

   Para $k=5$:

   -4	1	3	7	12	13	3

   E, finalmente para $k=6$:

   -4	1	3	3	7	12	13