Temos um conjunto de inteiros C
armazenado numa lista simplesmente ligada. Queremos saber se a condição
seguinte é verificada ou não:
R-
Soma (x, y, z, M)
x, y, z - elementos
Se x + y + z < M
l - lista
Entao devolve V
M - constante
Senao devolve F
Soma1 (x, y, l, M)
Se evaz ( l )
Entao devolve V
Senao se soma (x, y, cabeça ( l ), M)
Entao devolve soma1 (x, y, cauda ( l ), M)
Senao devolve F
Soma2 (x, l, M)
Se evaz ( l )
Entao devolve V
Senao se soma1 (x, cabeça ( l ), l, M)
Entao devolve soma2 (x, cauda ( l ), M)
Senao devolve F
Soma3 (x, l, M)
Se evaz ( l )
Entao devolve V
Senao se soma2 (cabeça ( l ), l, M)
Entao devolve soma3 (cauda ( l ), M)
Senao devolve F
Ex. 2 (5 valores)
a) Criar uma árvore Red-Black com as
seguintes inserções :
50, 70, 30,
45, 60, 42, 41, depois eliminar o 45.
Inserir ( 50 ) Inserir ( 70 ) Inserir (30)
· A raiz não pode ser vermelha
Inserir ( 45 )
· 2 nós vermelhos não podem 
·
O nº de nós pretos tem de ser igual em todos
os caminhos possiveis
ser seguidos
Inserir ( 60 )
Inserir
( 42 )
·
2 nós vermelhos não podem
·
O nº de nós pretos tem de ser iguais
ser
seguidos
em
todos os caminho possiveis
Inserir ( 41 )
Eliminar (45)
· O nº de nós pretos tem de ser igual em todos
os caminhos possiveis
b) Fazer o Splay de 41
Ex. 3 (2 valores)
a) Dar um exemplo onde o Quicksort não
é tão quick.
R – O quicksort não é tão quick quando a lista
está quase ordenada ou quando já está toda ordenada.
b) Dar um exemplo onde a ordenação por bolha é muito mais rápida do que qualquer outra ordenação por comparação .
R – A ordenação por bolha é muito mais rápida que todas as outras ordenações por comparação quando a lista está quase ordenada ou quando já está toda ordenada.
Ex. 4 (6 valores)
O objectivo
deste exercicio é isolar os centros de bombagem que podem mandar e receber petróleo
entre eles numa rede de oleoduto.
A rede está
formada de N centros de bombagem interligados entre eles com tubos. Cada centro
pode mandar o petróleo numa direcção dada para um outro centro de bombagem
mas pode receber de mais dum centro.
a)
Propor uma estrutura de dados para armazenar a rede.
R - Grafos com arcos direccionais.
b) Propor um exemplo para 8 centros de bombagem.
c) Propor e executar um algoritmo que irá
isolar os centros que podem mandar e receber entre eles.
G :
GT : ( Grafo transposto - trocam-se a orientação dos arcos )
GRUPO FORTEMENTE CONEXO
(os seus elementos conseguem dar e receber petróleo entre si)
Ex. 5 (3 valores)
Temos uma árvore binária de inteiros sem ordem. Queremos ordenar a árvore para optimizar as operações de procura. Escrever as subrotinas necessárias para transformar uma árvore sem ordem numa com ordem ou para criar uma árvore ordenada a partir duma outra sem ordem.
R –
Função Ordenar (arv ad) à
arvore
Começar
/* Função que
percorre uma árvore desordenada
/*
em Pós-Ordem e vai inserindo os elementos
se ñevaz (ad);
/* ordenadamente noutra ávore através da função
então
/* inserir_ord
{
ordenar (fe(ad), ao)
ordenar (fd(ad), ao)
inserir_ord (nó(a))
}
Fim
Função Inserir_ord (elemento x, arvore a) à Arvore
/* Função para inserir um elemento
Começar
/* numa arvore
ordenada
se
evaz (a);
então devolve consa (x, NULL, NULL );
senão se (x < nó(a))
então devolve consa (nó(a),
inserir (x,fe(a)), fd(a));
senão devolve consa (nó(a),
fe(a), inserir (x,fd(a)));
Fim