UNIVERSIDADE FEDERAL DE MINAS GERAIS
INSTITUTO DE CIÊNCIAS EXATAS
DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO
ALGORITMOS E ESTRUTURAS DE DADOS II
Prof. Raquel O. Prates 20
de abril de 2006
1.
Exercícios do Livro Capítulo 1: 1, 3, 4, 5, 18a
2.
que
é um algoritmo ótimo?
3.
A série de Fibonacci é formada pela seguinte seqüência
de números:
0 1 1 2 3 5 8 13 21 ...
Isto
é, cada número da série é a soma dos dois números anteriores. E os dois
primeiros são 0 e 1.
Escreva
uma função que recebe como parâmetro o número de termos desejados e retorna o
valor do termo na série:
a)
iterativa
b)
recursiva
4.
Calcule a função
de complexidade e a ordem de complexidade do pior caso – O – para os seguintes algoritmos:
Procedure
p1 (n: integer);
var
i,
j, k: integer;
begin
for i:=1 to n do
for j:=1 to n do begin
C[i,j]:=0;
for
k:= 1 to n do
C[i,j]:=C[i,j] + A[i,k] *B[k,j]
end
end;
Procedure p2 (n: integer);
var
i,
j, x, y: integer;
begin
for i:=1 to n do begin
for j:= i to n do
x:= x
+ 1;
for j:= 1 to i do
y:=y+1;
end;
end;
5.
Exercícios Livro Capítulo
3: 1, 2, 9
6.
O procedimento abaixo tinha
Procedure
delete (x: elementtype; var
L: LIST);
var
p: position;
begin
p:=FIRST(L);
while p <>
END(L) do begin
if RETRIEVE (p,L) = x THEN
DELETE(p,L);
p:= NEXT(p,L);
end
end;
7.
Queremos armazenar uma lista em
um vetor A, cujas células consistem de 2 campos, dado para armazenar o elemento e posição (inteiro) para indicar a posição do elemento. Um inteiro ultimo indica que A[1] até A[ultimo] armazenam a lista., O tipo LISTA pode ser identificado por:
type
LISTA = record
ultimo:
integer;
elementos: array [1..MAX] of
record
dados:
TipoElemento;
posição: integer;
end;
end;
Escreva
um procedimento
RETIRE(p,L) para remover um
elemento a posição p. Inclua todas as verificações de erro.
8.
Exercícios Livro Capítulo
4: 2
9.
Dados os inteiros: 1, 7, 3, 2, 0, 5, 0 ,8 ordene-os usando
(a) método da bolha; (b) método da seleção; (c) método de inserção. Mostre os passos
usados para a ordenação.