AAED - Lista de exercícios 5

Prévia do material em texto

Pós-Graduação em Ciência da Computação Universidade Federal de São Paulo - São José dos Campos
Exerćıcios sobre Pesquisa
AAED — Análise de Algoritmos e Estruturas de Dados
Prof. Jurandy G. Almeida Jr.
1o Semestre de 2020
Exerćıcios
1. Qual tipo abstrato de dados (TAD) é implementado pelos algoritmos de pesquisa? Defina as
operações básicas desse TAD. Quais as desvantagens de implementar esse TAD usando um
vetor ordenado? Em qual situação seria mais útil utilizar apenas um vetor simples? Justifique
a sua resposta.
2. Faça uma comparação entre todos os métodos de pesquisa estudados em aula com relação a
ordem de complexidade, levando em consideração o número de comparações.
3. Considere as técnicas de pesquisa sequencial e pesquisa binária. Descreva as vantagens e
desvantagens de cada uma dessas técnicas, indicando em que situações você usaria cada uma
delas. Dê a ordem de complexidade de melhor e pior caso de cada método, levando em
consideração o número de comparações.
4. Considere a árvore representada através de parênteses aninhados:
( A ( B ) ( C (D ( G ) ( H ) ) ( E ) (F ( I ) ) ) )
Responda as seguintes questões:
(a) Quantas subárvores contém?
(b) Quais os nós folha?
(c) Qual o grau de cada nó?
(d) Qual o grau da árvore?
(e) Liste os ancestrais dos nós B, G e I.
(f) Identifique as relações de parentesco entre os nós A, G e I.
(g) Liste os nós de quem C é ancestral próprio.
(h) Liste os nós de quem D é descendente próprio.
(i) Dê o ńıvel e a altura do nó F.
(j) Dê o ńıvel e a altura do nó A.
(k) Qual a altura da árvore?
5. Para montar uma árvore genealógica que contém todos os ancestrais consangúıneos de uma
pessoa, qual seria o grau da árvore?
6. Para montar uma árvore genealógica que contém todos os descendentes consangúıneos de uma
pessoa, qual seria o grau da árvore?
7. Dada a árvore:
——————————— 1
—————————– 2
——————— 7
——————— 8
—————————– 3
——————— 9
—————————– 4
——————— 10
————– 14
————– 15
————– 16
————– 17
—— 20
————– 18
————– 19
——————— 11
——————— 12
—————————– 5
——————— 13
—————————– 6
(a) Redesenhe-a na forma tradicional.
(b) Qual o grau da mesma? Explique.
(c) Qual a altura da árvore?
(d) Dê o ńıvel (altura) de cada nó.
(e) Dê o grau de cada nó.
8. O que é uma árvore binária balanceada?
9. Uma árvore binária cuja altura é igual ao número de nós pode possuir nós cheios ? Justifique.
10. Quantos elementos (nós), no mı́nimo e no máximo, pode ter uma árvore binária de altura 5?
11. Uma árvore binária completa e balanceada tem 31 nós até o seu ńıvel n. Sabe-se que ela tem
2n− 1 ńıveis. Quantos nós tem a árvore?
12. Sabendo que uma árvore binária tem altura 5 e está totalmente balanceada e completa,
quantos nós tem o ńıvel 3?
13. Uma árvore binária completa e balanceada com altura 5 tem quantos nós?
14. Sabendo que uma árvore binária está totalmente balanceada e completa e tem 1023 nos até
o seu nivel n, quantos nos tem o nivel n− 1?
15. Sugira uma estrutura de dados para representar uma árvore binária, armazenando um
conteúdo (inteiro) associado a uma chave (inteira).
16. Desenhe uma árvore estritamente binária com 7 nós para a qual os percursos em pré-ordem
e em-ordem produzem a mesma sequência de visitas.
17. Dados os percursos abaixo, reconstruir a árvore original:
pré-ordem: 1, 2, 3, 6, 8, 4, 9, 10, 12, 11, 5, 7, 13
em-ordem: 6, 3, 8, 2, 4, 9, 12, 10, 11, 1, 13, 7, 5
18. Diga, para cada uma das árvores binárias abaixo, se são balanceadas, perfeitamente balance-
adas ou nenhum dos casos ou ambos:
(a) (1 (2 (4) (5)) (3 (6) (7)))
(b) (A (B (D (F)) (E)) (C (G (H))))
19. Quais as propriedades de uma árvore binária de pesquisa?
20. Qual é a altura esperada na situação de pior caso e melhor caso para uma árvore binária de
pesquisa? Justifique a sua resposta.
21. Usando a estrutura de dados para árvore binária vista em aula, implemente as seguintes
operações:
(a) Contar o número de nós de uma árvore.
(b) Calcular a soma de todas as chaves de uma árvore.
(c) Verificar se uma árvore é estritamente binária, isto é, todos os nós não-folhas contém
exatamente 2 filhos.
22. O professor Amongus pensa que descobriu uma extraordinária propriedade de árvore binária
de pesquisa. Suponha que a busca por uma chave k em uma árvore binária de pesquisa
termine em uma folha. Considere três conjuntos: A contém os nós (chaves) à esquerda do
caminho da busca; B, as chaves no caminho da busca; e C, as chaves à direita do caminho da
busca. O professor Amongus afirma que quaisquer três chaves a ∈ A, b ∈ B e c ∈ C devem
satisfazer a < b < c. Apresente um pequeno exemplo que prove que ele está errado.
23. Suponha que tenhamos números entre 1 e 1000 em uma árvore binária de pesquisa e dese-
jamos fazer uma pesquisa (busca) pelo número 363. Qual(is) das seguintes sequências não
poderia(m) ser a sequência de nós examinados? Justifique.
(a) 2, 252, 401, 398, 330, 344, 397, 363.
(b) 924, 220, 911, 244, 898, 258, 362, 363.
(c) 925, 202, 911, 240, 912, 245, 363.
(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
(e) 935, 278, 347, 621, 299, 392, 358, 363.
24. Desenhe árvores binárias de pesquisa de alturas 2, 3, 4, 5 e 6 com o seguinte conjunto de
chaves {1, 4, 5, 10, 16, 17, 21}.
25. Desenhe uma árvore binária de pesquisa com a menor altura posśıvel com o seguinte conjunto
de chaves: {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43}.
26. Mostre passo a passo a árvore binária de pesquisa resultante das seguintes operações:
(a) Inserção das chaves 7, 8, 3, 4, 2, 1, 6, 5.
(b) Mostre o percurso em pré-ordem, em-ordem e pós-ordem.
(c) Remoção de 7 e 6.
27. Considere uma árvore binária de pesquisa, inicialmente vazia, a qual armazena caracteres.
Faça a inserção de todas as letras do seu nome completo na mesma sequência da escrita,
desprezando os espaços em branco. Considere, também, todas as letras maiúsculas, sem
acentuação e a ordenação da árvore de acordo com a ordem alfabética, onde a letra A é o
menor valor e a letra Z é o maior.
Exemplo: Dilma Vana Rousseff = DILMAVANAROUSSEFF; inserir a letra D, em seguida
a letra I, depois a letra L e assim por diante até a inserção da última letra que, no exemplo,
é a letra F.
Obs: Letras repetidas devem ser ignoradas.
Alfabeto: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z.
Em seguida, resolva:
(a) Qual é a altura da árvore?
(b) Dê o resultado de um percurso pós-fixado.
(c) Quem é o sucessor do nó de maior altura (caso existam dois ou mais, considere o menor
deles) na árvore?
(d) Quem é o predecessor do quarto nó inserido na árvore?
(e) Indique o resultado da retirada do nó raiz da árvore.
28. Uma árvore binária é zig-zag quando é vazia ou quando não possui nós cheios. Sem usar
recursividade, escreva uma função que recebe o endereço do nó raiz de uma árvore binária e
verifica se ela é zig-zag. Se a árvore dada for zig-zag, a função deverá retornar sua altura;
caso contrário, deverá retornar -1. Não utilize estruturas de dados auxiliares (pilhas, filas,
etc); apenas variáveis locais dos tipos ponteiro ou inteiro.
29. Quais as propriedades de uma árvore AVL?
30. Explique cada uma das rotações em árvore AVL e em que situação cada uma deve ser aplicada.
31. Qual é a altura esperada na situação de pior caso e melhor caso para uma árvore AVL?
Justifique a sua resposta.
32. Um certo professor Amongus afirma que a ordem pela qual um conjunto fixo de elementos é
inserido em uma árvore AVL não interessa – sempre resulta na mesma árvore. Apresente um
pequeno exemplo que prove que ele está errado.
33. Seja q um nó recém inserido em uma árvore AVL e p o seu ancestral mais próximo que se
tornou desbalanceado. Quais os posśıveis valores para o fator de balanceamento de p após a
inserção? Examinar o fator de balanceamento de p é suficiente para concluirse a inserção foi
à esquerda ou a direita de p? Justifique sua resposta.
34. Seja T uma árvore AVL. Considere a inserção de um nó q em T , que tornou T desbalanceada.
Seja p o nó desbalanceado mais próximo das folhas.
(a) Qual o valor exato de |hE(p)− hD(p)| ? Por que não pode ser nem mais nem menos?
(b) Supondo hD(p) > hE(p), então existe um filho direito u de p. Por que necessariamente
temos |hD(u)− hE(u)| = 1? Por que não pode ser 2? Por que não pode ser 0?
(c) De acordo com o item anterior, quando hD(p) > hE(p) existem dois subcasos a serem
considerados: hE(u) = hD(u) + 1 ou hD(u) = hE(u) + 1. Para cada um desses subcasos,
apresente a transformação que realiza o rebalanceamento de p.
(d) Por que o rebalanceamento de p (nó desbalanceado mais próximo das folhas) faz com
que toda a árvore fique balanceada?
35. Apresente duas maneiras distintas de inserir as chaves 10, 20, 30, 40 e 50 em uma árvore AVL
inicialmente vazia de modo que só ocorram exatamente 2 rotações duplas no mesmo sentido.
Justifique sua resposta, realizando as inserções.
36. Mostre passo a passo a árvore AVL formada pela inserção das chaves {99, 44, 71, 80, 74, 63, 59,
120, 98, 150} seguida da remoção das chaves {59, 63}. Redesenhe a árvore a cada operação e
indique a rotação feita, o nome da rotação e o nó desregulado, se houver. Caso necessário, na
remoção dê a preferência para a promoção da menor chave da subárvore à direita, ou seja, o
sucessor.
37. Mostre passo a passo a árvore AVL formada pela inserção das chaves {20, 30, 25, 84, 56, 12, 1, 69,
78} seguida da remoção das chaves {25, 20, 1, 30, 78, 56, 12, 84, 69}. Redesenhe a árvore a cada
passo e indique a rotação feita, o nome da rotação e o nó desregulado, se houver. Caso ne-
cessário, na remoção dê a preferência para a promoção da menor chave da subárvore à direita,
ou seja, o sucessor.
38. Quais as propriedades de uma árvore rubro-negra?
39. Liste as propriedades que podem ser violadas em uma operação de inserção em uma árvore
rubro-negra e explique como essas propriedades podem ser restauradas.
40. Liste as propriedades que podem ser violadas em uma operação de remoção em uma árvore
rubro-negra e explique como essas propriedades podem ser restauradas.
41. Qual é a altura esperada na situação de pior caso e melhor caso para uma árvore rubro-negra?
Justifique a sua resposta.
42. Mostre passo a passo a árvore rubro-negra formada pela inserção das chaves {99, 44, 71, 80, 74,
63, 59, 120, 98, 150} seguida da remoção das chaves {59, 63}. Redesenhe a árvore a cada
operação e indique o caso de desbalanceamento tratado e o nó desregulado, se hourver. Caso
necessário, na remoção dê a preferência para a promoção da menor chave da subárvore à
direita, ou seja, o sucessor.
43. Mostre passo a passo a árvore rubro-negra formada pela inserção das chaves {20, 30, 25, 84, 56,
12, 1, 69, 78} seguida da remoção das chaves {25, 20, 1, 30, 78, 56, 12, 84, 69}. Redesenhe a
árvore a cada passo e indique o caso de desbalanceamento tratado e o nó desregulado, se
houver. Caso necessário, na remoção dê a preferência para a promoção do sucessor.
44. Compare a árvore binária de pesquisa, a árvore AVL e a árvore rubro-negra, no que diz
respeito às operações de pesquisa, inserção e remoção.
45. Quais as caracteŕısticas de uma boa função de transformação de chaves?
46. Há um resultado matemático surpreendente chamado “paradoxo do aniversário” que afirma
que, se há mais de 23 pessoas em uma sala, há mais de 50% de chance de que duas pessoas
façam aniversário no mesmo dia. Explique porque este paradoxo é um exemplo do maior
problema da técnica de espalhamento (hashing).
47. Em que situações a tabela de hash deve ser utilizada? Descreva dois mecanismos diferentes
para resolver o problema de colisões de várias chaves em uma mesma posição da tabela. Quais
são as vantagens e desvantagens de cada mecanismo?
48. Se, no tratamento de colisões por encadeamento, as listas fossem mantidas de forma ordenada,
isso afetaria o tempo de inserção na tabela hash? Por quê? E o tempo de pesquisa seria
afetado de alguma forma?
49. Qual dos esquemas de tratamento de colisão (encadeamento ou endereçamento aberto) de
tabela hash consegue tolerar um fator de carga superior a 1 e qual não consegue? Justifique
sua resposta.
50. Substitua XXXXXXXXXXXX pelas 12 primeiras letras do seu nome, desprezando brancos e
letras repetidas. Desenhe o conteúdo da tabela hash resultante da inserção de registros com
as chaves XXXXXXXXXXXX, nesta ordem, em uma tabela inicialmente vazia de tamanho
7 (sete), usando listas encadeadas para resolver as colisões. Use a função de transformação
h(k) = k mod 7 para a k-ésima letra do alfabeto.
51. Substitua XXXXXXXXXXXX pelas 12 primeiras letras do seu nome, desprezando brancos e
letras repetidas. Desenhe o conteúdo da tabela hash resultante da inserção de registros com
as chaves XXXXXXXXXXXX, nesta ordem, em uma tabela inicialmente vazia de tamanho
13 (treze), usando endereçamento aberto e teste linear para resolver as colisões. Use a função
de transformação h(k) = k mod 7 para a k-ésima letra do alfabeto.
52. Considere uma tabela hash de tamanho 11 (onze), usando endereçamento aberto e teste
linear para resolver as colisões. Use a função de transformação h(k) = k mod 7. Mostre a
configuração da tabela após a inserção dos registros com as chaves: 4, 17, 13, 35, 25, 11, 2,
10, 32, 40, 3. Em seguida, mostre a configuração da tabela após a remoção dos registros com
as chaves: 25, 11.
53. Considere a inserção das chaves 10, 22, 31, 4, 15, 28, 17, 88 e 59 em uma tabela hash de
tamanho m = 11 usando o endereçamento aberto com a função de transformação h(k) =
k mod m. Ilustre o resultado da inserção dessas chaves utilizando as seguintes estratégias:
(a) Teste linear
(b) Teste quadrático com c1 = 1 e c2 = 3
54. Seja uma empresa que tem o seu número de clientes limitado ao máximo de 1000. Porém o
código do cliente (chave) é um número que começa com 4841200001 e vai em sequência até
4841201000. Como seria posśıvel utilizar um tabela hash, em vetores, para implementar tal
situação?
55. Descreva sucintamente o funcionamento de uma Trie binária. Qual é um de seus principais
problemas? Como a árvore Patricia resolve esse problema?
56. Que estrutura de dados para pesquisa digital você utilizaria em uma situação em que as
chaves são muito grandes? Porque?
57. Substitua XXXXXXXXXXXX pelas 12 primeiras letras do seu nome, desprezando brancos e
letras repetidas. Considere a representação em binário de cada letra com um número inteiro
k que indica a sua posição no alfabeto.
(a) Construa a Trie binária para armazenar as chaves XXXXXXXXXXXX.
(b) Construa a árvore Patricia para armazenar as chaves XXXXXXXXXXXX.
58. Considere as seguintes chaves: 5 (0101), 6 (0110), 1 (0001), 9(1001), 3(0011), 10 (1010),
4(0100), 7(0111). Insira estas chaves em uma Trie binária (Use a representação binária das
chaves), mostrando como fica a árvore após cada inserção. Insira estas chaves em uma árvore
Patricia, mostrando como fica a árvore após cada inserção.