Resumo AEDs 2

Prévia do material em texto

Ordenação 
 
Ordenação:​ Tarefa de colocar um conjunto de dados em uma determinada ordem. Permite acesso 
mais eficiente aos dados. 
 
Algoritmos de Ordenação​: É o algoritmo de colocar os elementos de uma dada sequência em ordem. 
Ordenação Básica 
Em geral a complexidade deste grupo é O(n^2). 
 
● BubbleSort ou “Ordenação por Bolha” 
● Comparar pares de elementos adjacentes e os troca de lugar se estiverem na ordem 
errada; 
● Esse processo se repete até que mais nenhuma troca seja necessária (elementos já 
ordenados) 
 
○ Performance 
■ Melhor Caso: O(n); 
■ Pior Caso: O(n^2); 
■ Não recomendado para grandes conjuntos de dados; 
 
● InsertionSort ou “Ordenação por Inserção 
○ Similar a ordenação de cartas de baralho com as mãos 
○ Pega-se uma carta de cada vez e a coloca em seu devido lugar, sempre deixando as 
cartas da mão em ordem. 
 
○ Performance: 
■ Melhor caso: o(n) 
■ Pior Caso: O(n^2) 
■ Eficiente para conjuntos pequenos de dados 
■ Estável: não altera a ordem de dados iguais 
■ Capaz de ordenar os dados a medida em que os recebe (tempo real) 
 
● SeletionSort ou Ordenação por Seleção 
○ A cada passo, procura o menor valor do array e o coloca na primeira posição do 
array; 
○ Descarta-se a primeira posição do array e repete-se o processo para a segunda 
posição do array; 
 
○ Performance: 
■ Melhor Caso: O(n^2) 
■ Pior Caso: O(n^2) 
■ Ineficiente para grandes conjuntos de dados 
■ Estável: não altera a ordem de dados iguais 
 
Ordenação Avançada 
● MergeSort ou Ordenação por Mistura 
○ Ideia básica: Dividir e Conquistar 
○ Divide, recursivamente, o conjunto de dados até que cada subconjunto 
possua 1 elemento 
○ Combina 2 subconjunto de forma a obter 1 conjunto maior e ordenado; 
○ Este processo se repete até que exista apenas 1 conjunto 
 
○ Performance : 
■ Melhor Caso: O(nlogN) 
■ Pior caso: O(nlogN) 
■ Desvantagem: recursivo e usa vetor auxiliar durante a ordenação 
 
● QuickSort ou Ordenação por Troca de Partições 
○ Ideia básica: Dividir e Conquistar 
○ Um elemento é escolhido como pivô 
○ Particionar: Os dados são rearranjados (valores menores do que o pivô são 
colocados antes dele e os maiores, depois 
○ Recursivamente ordena as 2 partições 
○ 
○ Performance: 
■ Melhor Caso: O( n log n) 
■ Pior Caso (raro): O(n^2) 
■ Estável: não altera a ordem de dados iguais 
■ Desvantagem: Como escolher o pivô? 
 
● HeapSort ou Ordenação usando heap 
○ Heap: vetor que simula uma arvore binária completa (exceção do último 
nível) 
○ Todo elemento “pai” do vetor possui dois elementos como “filhos” 
○ Pai(i)-> filhos : (2*i +1) e (2*i+2) 
● RadixSort 
○ É estável; 
○ Ordena de acordo com o primeiro pedaço 
○ Ordena de acordo com o último elemento de cada elemento: 
 
 
 
 
 
 
Pesquisa Simples 
● Pesquisa Sequencial 
○ A partir do primeiro registro, pesquisa sequencialmente até encontrar a chave 
procurada, então para. 
○ Análise 
■ Pesquisa com Sucesso: 
● Melhor Caso: O(1); 
● Pior caso: O(n); 
■ Sem Sucesso: 
● O(n+1) 
● Pesquisa Binária 
○ A cada iteração do algoritmo o tamanho da tabela é dividido no meio; 
 
● Árvores de Pesquisa 
○ Árvores Binárias de Pesquisa sem Balanceamento 
○ Árvores Binárias de Pesquisa com Balanceamento 
 
● Pesquisa Digital 
○ Trie , Patricia 
● Transformação de Chave (Hashing) 
○ Listas Encadeadas, Endereçamento Aberto, Hashing Perfeito 
 
Como recuperar a informação a partir de uma grande quantidade de informação? 
A informação é dividida em registros, cada registro possui uma chave a ser usada na 
pesquisa. 
● A escolha do método de pesquisa depende : 
○ Quantidade de dados envolvidos ; 
○ Frequência de inserção e remoção; 
 
Pesquisa Digital 
 
● Representação das chaves como uma sequência de caracteres ou dígitos: 
○ Representação de um número em binário; 
○ Representação de uma string; 
● Vantagens: 
○ Chaves grande e de tamanhos diferentes 
● Pesquisa digital vs. Radixsort 
○ Pesquisa digital : Árvore binária de pesquisa; 
○ Radixsort: Métodos de ordenação 
● Trie: 
○ Bit diferenciador; 
○ O formato das tries não depende da ordem em que as chaves são inseridas, 
e sim da estrutura das chaves através da distribuição de seus bits 
○ O maior comprimento possível é o tamanho da maior palavra possível; 
○ Desvatagens: 
■ Uma grande desvantagem é a formação de caminhos de uma só 
direção para chaves com um grande número de bits em comum 
● Patricia: 
 
 
Árvore 
● São um tipo especial de grafo; 
● Qualquer par de vértices está conectado a apenas uma aresta; 
● Graxo conexo (existe exatamente um caminho entre quaisquer dois de seus vértices) e 
acíclico (não possui ciclos); 
● Como são um tipo especial de “grafo” , elas são definidas como um conjunto não vazio de 
vértices (ou nós) e arestas que satisfazem com requisitos 
● Vértices 
● É cada uma das entidades representadas na árvore (depende da natureza do problema) 
● Aresta 
● É a conexão entre dois vértices 
● Aplicações 
○ Árvores são adequadas para representar estruturas hierárquicas não lineares; 
● Exemplos 
○ Relações de descendência (pai, filho, etc) 
○ Diagrama hierárquico de uma organização 
○ Campeonatos de modalidades desportivas; 
○ Taxonomia; 
○ Em computação 
■ Estruturas de diretórios (pastas) 
■ Busca de dados armazenados no computador; 
■ Representação de espaço de solução (ex.: jogo xadrex); 
■ Modelagem de algoritmos 
 
● Formas de Representação: 
○ Grafos (mais comum); 
○ Diagrama de Venn (conjunto aninhados) 
 
● Propriedades 
○ “pai”: é o antecessor imediato de um vértice; 
○ Filho: é o sucessor imediato de um vértice; 
○ Raiz: é o vértice que não possui “pai”; 
○ Nós terminais ou folhas: qualquer vértice que não possui filhos; 
○ nós não-terminais ou internos: Qualquer vértice que possui pelo menos 1 filho; 
 
● Caminho de uma árvore 
○ É uma sequência de vértices de modo que existe sempre uma aresta ligando o 
vértice anterior com o seguinte; 
○ Existe exatamente um caminho entre a raiz e cada um dos nós da árvore; 
 
● Sub-árvore 
○ Dado um determinado vértice, cada “filho” seu é a raiz de uma nova “sub-árvore”; 
○ De fato, qualquer vértice é a raiz de uma sub-árvore consistindo dele e dos nós 
abaixo dele; 
 
● Grau de um vértice 
○ É número de subárvores do vértice 
 
● Altura da árvore 
○ Também chamado de “Profundidade” 
○ É o comprimento do caminho mais longo da “raiz” até uma das suas folhas; 
 
● Níveis 
○ Numa árvore, os vértices são classificados em “níveis”; 
○ O nível é o número de nós no caminho entre o vértice e a raiz; 
 
 
 
 
Árvore Binária 
 
- É um tipo especial de árvore; 
- Cada vértice pode possuir duas “sub-árvores”: sub-árvore esquerda e sub-árvore direita; 
- O grau de cada vértice (número de filhos) pode ser 0, 1 ou 2 
 
Árvore Estritamente Binária 
- Cada nó (vértice) possui 0 ou 2 sub-árvores 
- Nenhum nó tem filho único; 
- Nós internos (não folhas) sempre têm 2 filhos; 
 
Árvore Binária Completa 
- É estritamente binária e todos os seus nós-filhos estão no mesmo nível; 
- O número de nós de uma árvore binária completa é 2^h -1, onde h é a altura da árvore; 
 
Árvore Binária Quase Completa 
- A diferença de altura entre as sub-árvores de qualquer nó é no máximo 1. 
- Se a altura da árvore é “D”, cada nó folha está no nível “D” ou “D-1”] 
 
 
Implementação: 
 
estárica (heap) 
 
- Uso de um array; 
- Usa 2 funções para retornar a posição dos filhos à esquerda e à direita de um pai 
FILHO_ESQ(PAI) = 2 * PAI +1; 
FILHO_DIR(PAI) = 2 * PAI + 2; 
 
Alocação Dinâmica ( lista encadeada) 
- Cada nó da árvore é tratado como um ponteiro alocado dinamicamente a medida que os 
dados são inseridos; 
 
Implementando uma ÁrvoreBinária ( Com alocação dinâmica - lista encadeada) 
- Para guardar primeiro nó da árvore utilizamos um “ponteiro para ponteiro) 
- Um ponteiro para ponteiro pode guardar o endereço de um ponteiro ; 
- Assim, fica fácil mudar quem é a “raiz” da árvore (se necessário); 
 
ArvoreBinaria.h : definir : 
- Os protótipos das funções; 
- O tipo de dado armazenado na árvore; 
- O ponteiro “árvore”; 
 
ArvoreBinaria.c : definir : 
- O tipo de dado árvore; 
- Implementar as suas funções; 
 
Informações básicas : 
 
● Está vazia? 
 
 Retornar com 0 ou 1 se a raiz está vazia: 
Função Vazia (ponteiro árvora raiz){ 
Se raiz == NULL retorna 1; 
Se raiz != NULL retorna 0; 
 
● Número de nós? 
Função NumerodeNos( ponteiro raiz){ 
Confere se existe; 
Confere se não está vazia; 
Chamar recursivamente a função: Lado esquerdo e lado direito; 
Retornar a Soma dos dois lados +1 
} 
 
● Altura da árvore? 
 Percorrer todos os nós , +/- como se faz para liberar ela . 
Função Altura( ponteiro raiz){ 
x = função Vazia; 
Se x == 0 retorna 0; 
se X == 1 continuar . Ver se o endereço que raiz aponta é NULL, se NULL retorna 0, se não 
continuar. 
FUnção recursiva: 
alt_esq == Função Altura (&((ponteiro raiz para lado esquerdo)); 
alt_dir == Função Altura (&(( ponteiro raiz lado direito)); 
 Olhar qual o máior 
retorna maior + 1 
} 
 
Percorrer Árvore Binária 
● Muitas operações em árvores binárias necessitam que se percorra todos os nós de suas 
sub-árvores, executando alguma ação ou tratamento em cada nó; 
● Cada nó é “visitado” uma única vez; 
● Isso gera uma sequência linear de nós, cuja ordem depende de como a árvora foi percorrida 
● Podemos percorrer a árvore de 3 formas ( essa são as mais importantes, existem outras) 
○ Pré-Ordem: 
■ Visita a raiz, o filho da esquerda e o filho da direita; 
○ Em-Ordem: 
■ Visita o filho da esquerda, a raiz e o filho da direita 
○ Pós-Ordem 
■ Visita o filho da esquerda, o filho da direita e a raiz 
 
Árvore Binária de Busca 
● É um tipo de árvore binária onde cada nó possui um valor (chave) associado a ele, e esse 
valor determina a posição do nó na árvora; 
● Não existem valores repetids; 
 
Posicionamento do valor 
● Para cada nó pai: 
○ Todo os valores da sub-árvora esquerda são menores do que o nó pai; 
○ Todos os valores da sub-árvore direita são maiores do que o nó pai; 
 
 
● A inserção e remoção de nós da árvore devem ser realizadas respeitando a propriedade da 
árvore; 
 
Aplicações 
● Busca binária; 
● Análise de expressões algébricas: prefica, infixa e pós fixa; 
 
Principais operações 
● Inserção 
○ Caso médio: O(log n); 
○ Pior caso: O(n); // Árvore não balanceada; 
 
● Remoção 
○ Caso médio: O(log n); 
○ Pior caso: O(n) // Árvore não balanceada; 
 
● Consulta: 
○ Caso Médio: O(log n); 
○ Pior Caso: O(n) // Árvore não balanceada 
 
Árvore Balanceada 
● É uma árvore binária onde as alturas das sub-árvores esquerda e direita de cada nó diferem 
de no máximo uma unidade; 
● Essa diferença é chamada de “fator de balanceamento” do nó; 
● A eficiência da busca em uma árvore binária depende do seu balanceamento; 
● Problema: 
○ Algoritmos de inserção e remoção não garantem que a árvore gerada a cada passo 
seja balanceada; 
○ Sequência de inserção em ordem de escada; 
 
● Custo da inserção, busca e remoção em uma árvore binária : 
○ Balanceada: O(log n); 
○ NÃO Balanceada: O(n); 
 
“n” corresponde ao número de nós na árvore; 
 
Solução para o problema de balanceamento? 
- Modificar as operações de inserção e remoção da árvore; 
- Exemplos de árvore balanceadas: 
- Árvore AVL; 
- Árvore 2-3-4; 
- Árvore Red-Black (também conhecida como vermelho-preto ou rubro-negra); 
 
 
Árvore AVL 
 
● É um tipo de árvore binária balanceada; 
● Permite rebalanceamento local 
○ Apenas a parte afetada pela inserção ou remoção é rebalanceada; 
○ Uso de rotação simples ou dupla nas etapas de rebalanceamento; 
● A árvore AVL busca manter-se como uma árvore binária quase completa 
○ Custo de qualquer algoritmo é máximo O( log n); 
● Fator de balanceamento ou fb 
○ Diferença nas alturas das sub-árvores esquerda e direita 
■ Se uma das sub-árvores não existir, sua altura será -1 
○ Em uma AVL, fb deve ser +1, 0, -1. 
■ Se fb<-1 ou fb>+1 a árvore deve ser balanceada; 
 
 
● Implementação 
○ É idêntica a da árvore binária; 
○ Para guardar o primeiro nó da árvore utilizamos um ponteiro para ponteiro; 
○ Um ponteiro para ponteiro pode guardar o endereço de um ponteiro; 
○ Assim, fica fácil mudar quem é a raiz da árvore (se necessário); 
 
ArvoreAVL.h : definir: 
- Os protótipos das funções; 
- O tipo de dado armazenado na árvore; 
- O ponteiro árvore; 
 
ArvoreAVL.c: definir: 
- O tipo de dado árvore; 
- Implementar as suas funções; 
 
Com exceção da inserção e da remoção as demais funções da árvore AVL são idênticas a da Árvore 
Binária 
 
● Tipos de rotação 
○ Operações básicas para balanceamento da AVL 
○ Dois tipos de rotações simples e dupla 
■ Simples 
● O nó desbalanceado e seu filho estão no mesmo sentido da 
inclinação; 
■ Dupla 
● O nó está desbalanceado e seu filho está inclinado no sentido 
inverso ao pai 
● Equivale a duas rotações simples 
 
 
 
○ Existem 2 rotações simples e 2 duplas 
■ Rotação à direita e à esquerda 
 
● Rotação RR ou rotação simples à esquerda 
○ O nó “C” é inserido na subárvore direita da sub-árvore direita de “A” 
○ O nó intermediário B deve ser escolhido para ser a raiz da árvore resultante; 
● Rotação LL ou rotação simples à direita 
○ O nó “C” é inserido na subárvore esquerda da sub-árvore esquerda de “A” 
○ O nó intermediário “B” deve ser escolhido para ser a raiz da árvore resultante; 
● Rotação RL ou Rotação dupla à esquerda 
○ O nó “C” é inserido na subárvore “esquerda” da sub-árvore direita de “A” 
○ O nó “C” deve ser escolhido para ser a raiz da árvore resultante; 
● Rotação LR ou Rotação dupla à direita 
○ O nó “C” é inserido na subárvore direita da sub-árvore esquerda de “A” 
○ O nó “C” deve ser escolhido para ser a raiz da árvore resultante; 
● Quando usar cada rotação? 
○ Considerar que o nó “C” foi inserido como filho do nó B, e que B é filho do nó A, se o 
fator de balanceamento for 
■ A= +2 e B=+1: Rotação LL; 
■ A= -2 e B= -1: Rotação RR; 
■ A=+2 e B= -1: Rotação LR; 
■ A= -2 e B= +1: Rotação RL 
As rotações LL e RR são simétricas entre si, assim como LR e RL 
 
Implementação de Rotação 
● As rotações são aplicadas no ancestral mais próximo do nó inserido cujo fator de 
balanceamento para a ser +2 ou -2; 
● Esse é o parâmetro das funções implementadas; 
● As rotações “simples” (LLe RR) atualizam as novas alturas das sub-árvores 
● As rotações “duplas” (LR e RL) podem ser implementadas com 2 rotações simples 
 
 
RotaçãoLL(ponteiro raiz){ 
Cria nó; 
Filho esquerda recebe nó direita; 
Filho direita recebe nó esquerdo; 
 
 
 
Fila de Prioridade 
● São um tipo especial de fila que generaliza a ideia de “ordenação”; 
● Os elementos inseridos na fila possuem um dado extra associado a eles: a sua 
prioridade; 
● É o valor associado a esta prioridade que determina a posição de um elemento na 
fila, assim como quem deve ser o primeiro a ser removido da fila, quando necessário. 
● Aplicações: 
○ Basicamente, qualquer problema em que seja preciso estabelecer uma 
prioridade de acesso aos elementos pode ser representado com uma fila de 
prioridade. 
● Exemplos: 
○ Processos em um processador; 
○ Uma fila de pacientes esperando transplante de fígado; 
○ Busca em grafos (algoritmo de Dijktra) 
○ Compressão de dados ; 
○ Sistemas operacionais ; 
○ Fila de pouso de aviões em um aeroporto. 
● Em uma Fila de Prioridade podemos realizar as seguintes operações básicas: 
○Criar fila; 
○ Inserir um elemento na fila com prioridade; 
○ Remover o elemento de maior prioridade ; 
○ Acesso ao elemento do início da fila; 
○ Destruir fila; 
○ Além de informações como tamanho, se a fila está cheia ou vazia; 
● Essas operações dependem da implementação 
○ Lista dinâmica encadeada; 
○ Array desordenado; 
○ Array ordenado; 
○ heap binária; 
● Qual implementação escolher? 
○ A implementação escolhida para uma fila de prioridade depende da sua 
aplicação; 
○ Algumas implementações são eficientes na operação de inserção, outras na 
de remoção; 
○ Há também implementações que são eficientes nas duas operações ; 
Implementação Inserção Remoção 
lista dinâmica 
encadeada 
o(N) O(1) 
array 
desordenado 
O(1) O(N) 
array ordenado O(N) O(1) 
heap binária O(logN) O(logN) 
 
● Implementação: 
○ Fila de prioridades Estática 
■ Sua implementação utiliza a mesma estrutura da Lista Sequencial Estática; 
■ Utiliza um array para armazenar os elementos; 
■ Desvantagens: 
● Necessitar que se defina o tamanho do array previamente; 
■ Vantagens: 
● O uso de um array permite que utilizemos a mesma estrutura da fila 
para duas implementações distintas: 
○ Array ordenado; 
○ Heap binário; 
● Para tanto, basta modificar as funções de : 
○ Inserção; 
○ Remoção; 
○ Consulta; 
● Heap: 
○ Permite simular uma árvore binária completa ou quase completa ( a exceção é o seu 
último nível); 
○ Cada posição do array passe a ser considerado o pai de duas outras posições, 
chamadas filhos; 
○ Posição “i” passa a ser pai das posições: 
■ 2*i+1 : filho esquerda; 
■ 2*i+2 : filho direita; 
○ Os elementos são dispostos na heap de forma que um pai tem sempre uma 
prioridade “maior ou igual” à prioridade de seus filhos; 
○ Custo: 
■ Inserção : O( log N); 
● Inserir o novo elemento na primeira posição vaga do array, ou seja, 
no final do array; 
● Levar o elemento inserido para a sua respectiva posição na heap de 
acordo com a sua prioridade; 
■ Remoção: O( log N); 
● Remover o elemento que está no topo da heap, ou seja, o início do 
array; 
● Levar o elemento que foi colocado no topo da heap para a sua 
respectiva posição de acordo com a sua prioridade; 
■ Em ambas precisamos verificar e corrigir violações de prioridades da heap; 
 
Tabela Hash 
 
● Muitos métodos de busca funcionam segundo o mesmo princípio: procurar a 
informação desejada com base na comparação de suas chaves, isto é, com base em 
algum valor que a compõe; 
● Problema: 
○ Algoritmos eficientes exigem que os elementos sejam armazenados de forma 
ordenada; 
○ Custo da ordenação no melhor caso: O( N log N); 
○ Custo de busca: O( log N); 
● Busca Ideal: 
○ Acessar direto ao elemento procurado, sem nenhuma etapa de comparação 
de chave: custo O(1) 
● Array: 
○ Estruturas que utilizam “Índices” para armazenar informações; 
○ Permite acessar uma determinada posição do array com custo O(1); 
○ Problema: 
■ Arrays não possuem nenhum mecanismo que permita calcular a 
posição onde uma informação está armazenada, de modo que a 
operação de busca em um array não é O(1); 
○ Solução: 
■ Usar uma tabela hash 
● Tabela Hash 
○ Também conhecida como tabelas de indexação ou de espalhamento; 
○ É uma generalização da ideia de “array” 
○ Utiliza uma função para espalhar os elementos que queremos armazenar na 
tabela; 
○ O espalhamento faz com que os elementos fiquem dispersos de forma não 
ordenada dentro do array que define a tabela; 
● Função de hashing: 
○ Função que espalha os elementos na tabela 
● Por que espalhar os elementos melhora a busca? 
○ Uma tabela hash permite a associação de “valores” a “chaves”; 
○ Chave: parte da informação que compõe o elemento a ser inserido ou 
buscado na tabela; 
○ Valor: é a posição (índice) onde o elemento se encontra no array que define 
a tabela; 
○ Assim, a partir de uma chave podemos acessar de forma rápida uma 
determinada posição do array; 
○ Na média, essa posição tem custo O(1) 
● Vantagens: 
○ Alta eficiência na operação de busca; 
○ Tempo de busca é praticamente independente do número de chaves 
armazenadas na tabela; 
○ Implementação simples; 
● Desvantagens: 
○ Alto custo para recuperar os elementos da tabela ordenados pela chave. 
Nesse caso, é preciso ordenar a tabela; 
○ Pior caso é O(N), sendo N o tamanho da tabela: alto número de colisões; 
● Aplicações 
○ Busca de elementos em base de dados; 
○ Criptografia; 
○ Implementação de tabela de símbolos dos compiladores; 
○ Armazenamento de senha de segurança; 
 
 
Árvore Vermelho e Preto 
 
● É um tipo de árvore balanceada; 
● Utilizada em esquema de coloração dos nós para manter o balanceamento da 
árvore 
● Nó da árvore possui um atributo de cor que pode ser vermelho ou preto; 
● Propriedades da árvore: 
○ Todo nó da árvore é vermelho ou preto; 
○ A raiz é sempre preta; 
○ Todo nó é vermelho, então os seus filhos são pretos ( ou seja, não existem 
nós vermelhos consecutivos) 
○ Para cada nó, todos os caminhos desse nó para os nós folhas descendentes 
contém o mesmo número de nós pretos; 
● Permite rebalanceamento local 
○ Apenas a parte afetada pela inserção ou remoção é rebalanceada; 
○ Uso de rotação e ajuste de cores na etapa de rebalanceamento; 
○ Essas operações corrigem as propriedades que foram violadas; 
● A árvore busca manter-se como uma árvore quase completa 
○ Custo de qualquer algoritmo é máximo O( log N); 
● AVL x Vermelho e Preto: 
○ Na teoria, possuem a mesma complexidade computacional (inserção, 
remoção e busca): O (log N); 
○ Na prática, a árvore AVL é mais rápida na operação de busca, e mais lenta 
nas operações de inserção e remoção; 
○ A árvore AVL é mais balanceada do que a Vermelho-Preto, o que acelera a 
operação de busca; 
○ Maior custo na operação de inserção e remoção: No pior caso uma operação 
de rotação pode exigir O( log N) rotações na Árvore AVL, mas apenas 3 
rotações na árvore Vermelho-Preto 
○ Se sua aplicação realiza de forma intensa a operação de busca, é melhor 
usar uma árvore AVL; 
○ Se a operação mais usada é a inserção ou remoção, use uma árvore 
Vermelho-Preto; 
○ Árvore Vermelho-Preto são de uso mais geral do que as árvores AVL. Isso 
faz com que elas sejam utilizadas em diversas aplicações e bibliotecas de 
linguagens de programação 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Questões Professor 
1. Ordene a sequˆencia 
10, 4, 7, 12, 19, 22, 8, 1, 13 
usando cada um dos algoritmos abaixo. Vocˆe deve reescrever a sequˆencia cada vez que 
uma troca ´e 
feita e dizer o n´umero de compara¸c˜oes e de trocas realizadas por cada algoritmo. 
• Bolha. 
• Inser¸c˜ao. 
• Sele¸c˜ao. 
• Mergesort. 
• Quicksort (utilizando sempre o primeiro elemento como pivˆo). 
2. Quais algoritmos de ordena¸c˜ao estudados podem ser considerados est´aveis? Para 
cada algoritmo n˜ao 
est´avel, construa uma sequˆencia que mostra que o algoritmo n˜ao ´e est´avel. 
3. Suponha que se deseja ordenar uma lista de elementos consistindo de 108 
elementos que foi constru´ıda 
a partir de uma lista ordenada adicionando-se 5 n´umeros arbitr´arios ao final. Qual o 
melhor algoritmo 
a se utilizar se desejamos ordenar esta sequˆencia? 
4. Considere o seguinte algoritmo em pseudo-c´odigo: 
• Ordena (Item vetor[ ], int inicio, int fim) 
– Se (fim > inicio) 
∗ Ordena (vetor, inicio, fim/2); 
– Quicksort(vetor, inicio, fim - sqrt(fim - inicio)); 
– Insertionsort(vetor, inicio, fim); 
Este algoritmo ordena a sequˆencia de n´umeros de entrada? Qual a complexidade deste 
algoritmo, 
assumindo que Quicksort ordena n elementos em tempo O(n log(n))? 
5. Dada uma sequˆencia de n´umeros inteiros, descreva um algoritmo para construir uma 
´arvore bin´aria de 
pesquisa a partir desta sequˆencia, de forma que a altura seja t˜ao pequenaquanto 
poss´ıvel. 
6. Considere que um programa precisa inserir n n´umeros inteiros em um vetor e realizar m 
consultas. 
Para cada uma das situa¸c˜oes a seguir, se vocˆe tivesse que escolher entre pesquisa 
sequencial e pesquisa 
bin´aria, diga qual seria sua escolha, justificando sua resposta. 
• N˜ao se conhece a ordem das opera¸c˜oes, mas m = n 
2 
. 
• N˜ao se conhece a ordem das opera¸c˜oes, mas n = m2 
. 
• Sabe-se que n = 100m e que, ap´os cada 100 inser¸c˜oes, uma pesquisa ´e feita. 
• Sabe-se que n = 1000m e que todas as pesquisas s˜ao feitas ao final. 
• Sabe-se que n = m e que todas as pesquisas s˜ao feitas ao final. 
• Sabe-se que 1000n = m e que todas as pesquisas s˜ao feitas ao final. 
 
7. Em uma ´arvore bin´aria de pesquisa com n n´os, qual o maior e menor n´umero 
ponteiros nulos que 
podem existir? 
 
8. Escreva um algoritmo recursivo que calcula, para cada n´o, a altura da sub´arvore 
enraizada naquele n´o. 
Vocˆe deve preencher, em cada n´o, um campo chamado “altura”. Aten¸c˜ao: no algoritmo, 
ao acessar 
um campo de n´o, certifique-se de que aquele n´o existe, isto ´e, n˜ao acesso tente acessar 
um campo de 
um n´o apontado por um ponteiro nulo. 
 
9. Insira a sequˆencia de n´umeros da quest˜ao 1 em uma ´arvore bin´aria de pesquisa. 
Desenhe a ´arvore final. 
 
10. Insira a sequˆencia de n´umeros da quest˜ao 1 em uma ´arvore AVL. Desenhe a ´arvore 
a cada inser¸c˜ao. 
 
11. Desenha a Trie e a ´arvore Patr´ıcia correspondentes ao seguinte conjunto de chaves: 
{casa, casco, corte, casaco, carro, contagem, criatura, contabilidade, contagem}. 
 
12. Escreva um algoritmo (em pseudo-c´odigo) para listar todas as chaves de uma Trie. 
 
13. Seja S um conjunto de n chaves, cada um de comprimento k a serem inseridas em um 
Trie. Qual o 
maior e o menor n´umero de n´os que a Trie pode ter em cada um dos casos a seguir. 
• Uma Trie bin´aria. 
• Uma Trie cujo tamanho do alfabeto ´e maior que n. 
 
14. Para cada afirma¸c˜ao abaixo, diga se ´e verdadeira ou falsa. Se for verdadeira, 
explique. Caso seja falsa 
dˆe um exemplo de situa¸c˜ao em que ´e falsa. 
• Para armazenar strings, ´arvores de pesquisa s˜ao melhores que tries. 
• Sejam T1 e T2 s˜ao duas ´arvores com alturas h1 e h2, respectivamente, ambas com n 
elementos. 
Se T1 ´e AVL e h1 > h2, ent˜ao T2 ´e AVL. 
• Com hashing sempre podemos efetuar opera¸c˜oes de pesquisa em tempo constante. 
 
15. Considere um hashing onde, em caso de colis˜ao, utiliza-se uma ´arvore balanceada, ao 
inv´es de uma 
lista encadeada. Discuta a eficiˆencia desta t´ecnica, mencionando vantagens, 
desvantagens em rela¸c˜ao 
`a vers˜ao com lista encadeada.