Revisão Estrutura de Dados

1. Coloque em ordem crescente as seguintes complexidades: 2n, n!, n5, n log n, log n e
n.
log n, n, n log n, 2n, n^5, n!
2. Comente sobre a relação entre tipo de acesso disponível (sequencial e aleatório) em
uma dada estrutura de dados e a possibilidade de aplicação dos algoritmos de busca
sequencial e binária.
A relação entre o tipo de acesso disponível em uma estrutura de dados e a possibilidade de
aplicação de algoritmos de busca é importante. O acesso sequencial é mais adequado para
algoritmos de busca sequencial, enquanto o acesso aleatório é necessário para a aplicação de
algoritmos de busca binária. A estrutura de dados que permite acesso aleatório é mais
adequada para aplicar a busca binária, pois essa busca requer comparações de elementos em
posições aleatórias da estrutura.
3. Qual o número máximo de comparações executadas por cada um dos algoritmos de
busca estudados (sequencial e binária)? E o minimo? Justifique ambas as respostas.
A quantidade máxima de comparações executadas pelo algoritmo de busca sequencial é igual
ao número de elementos na estrutura de dados, já que ele precisa verificar cada elemento, um a
um, até encontrar o item procurado ou descobrir que ele não está presente. O mínimo de
comparações é 1, se o elemento procurado for encontrado logo na primeira posição.
Já o algoritmo de busca binária, no pior caso, realiza o log2 de comparações, onde "n" é o
número de elementos na estrutura de dados. Isso ocorre porque a busca binária divide a
estrutura de dados a cada passo, excluindo metade dos elementos. O mínimo de comparações é
1, se o elemento procurado for encontrado na primeira posição.
Ambos os algoritmos são mais eficientes quando a estrutura de dados está ordenada. A busca
binária só pode ser

4. Explique por que o Mergesort possui a mesma complexidade para qualquer caso de
entrada e o que isso implica no seu tempo de execução. Em que casos (de aplica-
ção) essa propriedade pode ser uma vantagem em relação aos demais algoritmos de
ordenação?
O Mergesort tem complexidade O(n log n), independentemente do caso de entrada. Isso se
deve ao fato de que o algoritmo funciona dividindo o vetor de entrada ao meio recursivamente,
até que cada sub-vetor tenha apenas um elemento. Depois, os sub-vetores são juntados em
pares, ordenados, e continuam sendo unidos até que o vetor inteiro tenha sido ordenado.
Essa propriedade de complexidade constante pode ser uma vantagem em casos onde a entrada
é frequentemente desordenada ou aleatória. Isso ocorre porque o tempo de execução do
Mergesort é garantido para ser sempre O(n log n), independentemente da entrada, e não é
afetado por entradas que sejam já ordenadas ou quase ordenadas.
Além disso, o Mergesort é estável, o que significa que ele mantém a ordem original de
elementos iguais. Isso pode ser uma vantagem em aplicações onde a estabilidade é importante.
5. Qual a relação que existe entre o pivô do algoritmo Quicksort e o pior caso do algo-
ritmo? Explique.
O pivô escolhido para o algoritmo Quicksort tem uma relação direta com o pior caso do
algoritmo. No pior caso, o Quicksort pode se comportar como um algoritmo de ordenação
linear, se o pivô escolhido for sempre o menor ou o maior elemento do conjunto. Isso acontece
porque a cada iteração, apenas um dos subconjuntos é ordenado, o que leva a uma quantidade
muito grande de comparações e trocas, tornando o algoritmo muito ineficiente. Por outro lado,
se o pivô é escolhido de maneira aleatória ou como o elemento mediano, a probabilidade de
que o Quicksort tenha um comportamento mais próximo do ótimo é maior, tornando o
algoritmo mais eficiente.
6. Simule duas execuções de algoritmos de ordenação para o seguinte conjunto de nú-
meros:
6 5 3 1 8 7 2 4
Para a primeira simulação escolha entre os algoritmos: bolha, seleção e inserção. Para
a segunda, escolha entre: mergesort e quicksort.
Na primeira simulação, o algoritmo de bolha realiza o maior número de comparações entre
todos os três (bolha, seleção e inserção), enquanto que o algoritmo de inserção realiza o menor
número de comparações. Já na segunda simulação, o Quicksort pode ser consideravelmente
mais rápido que os outros algoritmos, realizando em média cerca de 2n log n comparações. No
entanto, o pior caso do quicksort é o caso em que o pivô escolhido para dividir o conjunto é o
menor ou o maior elemento, o que pode resultar em uma quantidade excessiva de
comparações.

7. O que é um algoritmo de ordenação estável? Explique e cite exemplos de algoritmos
desse tipo.
Um algoritmo de ordenação estável é um algoritmo que mantém a ordem relativa de elementos
iguais ao ordená-los. Isso significa que, se duas entradas têm o mesmo valor, o algoritmo
garantirá que a posição relativa dessas entradas não seja alterada após a ordenação.
Algoritmos de ordenação estáveis são úteis quando a ordem original dos elementos é
importante para a aplicação.
Exemplos de algoritmos de ordenação estáveis incluem:
● Ordenação por inserção
● Ordenação por intercalação (MergeSort)
● Ordenação por contagem
● Ordenação por seleção estável.
8. Explique o processo de remoção de nós de uma árvore binária de busca visto em sala.
Aponte quais são os casos possíveis e as soluções para cada um.
A remoção de nós de uma árvore binária de busca pode ser feita de três maneiras diferentes,
dependendo do tipo de nó que se deseja remover:
1. Nó sem filhos: Neste caso, a remoção é simples, pois basta apagar o ponteiro para o nó
na árvore.
2. Nó com um filho: Neste caso, o nó é substituído pelo seu filho, que passa a ocupar o
lugar dele na árvore.
3. Nó com dois filhos: Neste caso, o nó é substituído pelo menor nó da subárvore da
direita ou pelo maior nó da subárvore da esquerda. Isso mantém a propriedade de
árvore binária de busca, pois garante que todos os nós à esquerda são menores e todos
os nós à direita são maiores do que o nó substituto.
9. Em uma estrutura de árvore binária de busca, foram inseridos os elementos ‘h’, ‘a’,
‘b’, ‘c’, ‘i’, ‘j’, nesta sequência. O tamanho do caminho entre um nó qualquer da
árvore e a raiz é dado pelo número de arestas neste caminho. Qual o tamanho do
maior caminho na árvore, após a inserção dos dados acima?
O tamanho do maior caminho na árvore depois da inserção dos dados acima será 3. É possível
construir a seguinte árvore binária de busca:
h
/ \
a i
/ \ \
b c j
Neste caso, o caminho mais longo da raiz até a folha é do nó "b" até a raiz, que tem 3 arestas.10. Um nó completo de uma árvore binária é um nó com duas subárvores não-vazias.
Considere l o número de folhas de uma árvore binária. Mostre que o número de nós
completos é l − 1.
Cada folha adiciona um nó à árvore, e a raiz é o único nó que não é folha, portanto, o número de
nós completos é igual ao número de folhas menos 1.
11. Um grafo pode ser utilizado para mostrar relacionamentos entre pessoas. Por exemplo,
dada a seguinte lista de pessoas pertencentes ao mesmo clube (vértices) e suas relações
de amizades (arestas) abaixo:
Pessoas = {Jorge, Jaime, José, Francisco, Frederico, João, Suzana}
Amizades = {(Jorge, Jaime), (Francisco, Frederico), (Jorge, João),
(Jaime, Frederico), (Jaime, Francisco), (Jaime, Suzana),
(Suzana, Francisco)}
Determine:
a. todos os amigos de João;
b. todos os amigos de Suzana;
c. todos os amigos de Jaime;
d. O grau de cada vértice.
a. Os amigos de João são Jorge e Jaime (por meio da aresta (Jorge, João) e (Jaime, João)).
b. Os amigos de Suzana são Jaime e Francisco (por meio da aresta (Jaime, Suzana) e (Suzana,
Francisco)).
c. Os amigos de Jaime são Jorge, Frederico, Francisco e Suzana (por meio das arestas (Jorge,
Jaime), (Jaime, Frederico), (Jaime, Francisco) e (Jaime, Suzana)).
d. O grau de cada vértice pode ser definido como o número de arestas incidentes a ele. A seguir
está o grau de cada vértice:
● Jorge: 2
● Jaime: 4
● José: 0
● Francisco: 3
● Frederico: 2
● João: 1
● Suzana: 212. Simule a execução do algoritmo de Dijkstra para o grafo direcionado com as arestas
abaixo (o grafo contém 8 vértices), iniciando pelo vértice 1:
origem -> destino (peso)
0 -> 1 (5) 3 -> 6 (9)
0 -> 7 (8) 4 -> 7 (5)
0 -> 4 (9) 4 -> 5 (4)
1 -> 7 (4) 4 -> 6 (20)
1 -> 3 (15) 5 -> 2 (1)
1 -> 2 (12) 5 -> 6 (13)
2 -> 3 (3) 7 -> 5 (6)
2 -> 6 (11) 7 -> 2 (7)
● Inicialmente: vértices não visitados: [0, 1, 2, 3, 4, 5, 6, 7] distâncias: [0, inf, inf, inf, inf, inf,
inf, inf]
● Primeira iteração: vértice selecionado: 0 vértices não visitados: [1, 2, 3, 4, 5, 6, 7]
distâncias: [0, 5, inf, inf, 9, inf, 8, inf]
● Segunda iteração: vértice selecionado: 1 vértices não visitados: [2, 3, 4, 5, 6, 7]
distâncias: [0, 5, inf, 15, 9, inf, 4, inf]
● Terceira iteração: vértice selecionado: 7 vértices não visitados: [2, 3, 4, 5, 6] distâncias:
[0, 5, inf, 15, 9, inf, 11, 6]
● Quarta iteração: vértice selecionado: 4 vértices não visitados: [2, 3, 5, 6] distâncias: [0,
5, inf, 15, 9, 13, 11, 6]
● Quinta iteração: vértice selecionado: 5 vértices não visitados: [2, 3, 6] distâncias: [0, 5,
1, 15, 9, 13, 11, 6]
● Sexta iteração: vértice selecionado: 2 vértices não visitados: [3, 6] distâncias: [0, 5, 1,
15,
13. Para o mesmo grafo da questão anterior, determine:
a. Sua representação na forma de matriz de adjacências;
b. Sua representação na forma de lista de adjacências;
a. Representação na forma de matriz de adjacências:
O grafo pode ser representado por uma matriz de adjacências onde cada elemento (i, j) da
matriz indica a existência de uma aresta entre os vértices i e j. Se existir uma aresta, o peso
desta aresta é armazenado na posição (i, j), caso contrário, o elemento na posição (i, j) é infinito.
Exemplo:
0 5 inf inf 9 inf inf 8 inf inf 12 15 inf inf inf 4 inf inf inf 3 inf 1 inf inf inf inf inf inf inf inf inf inf inf
inf inf inf inf 4 20 inf inf inf inf inf inf inf 13 6 inf inf inf inf inf inf inf inf inf inf inf inf inf inf 9 inf
b. Representação na forma de lista de adjacências:
Nesta representação, para cada vértice, mantemos uma lista de pares (destino, peso) que
indicam os vértices adjacentes e seus respectivos pesos.Exemplo:
Vértice 0: [(1, 5), (7, 8), (4, 9)] Vértice 1: [(3, 15), (2, 12), (7, 4)] Vértice 2: [(3, 3), (6, 11)] Vértice 3:
[(6, 9)] Vértice 4: [(7, 5), (5, 4), (6, 20)] Vértice 5: [(2, 1), (6, 13)] Vértice 6: [] Vértice 7: [(5, 6), (2,
7)]
14. Qual a relação entre o somatório dos graus dos vértices de um grafo e o número de
arestas do grafo?
Na teoria dos grafos, a relação entre o somatório dos graus dos vértices de um grafo e o
número de arestas do grafo é dada pela seguinte equação:
Grau total = 2 * número de arestas
Isso significa que, se somarmos o grau de todos os vértices em um grafo, o resultado será o
dobro do número de arestas. Essa relação é verdadeira para grafos não direcionados, já que
cada aresta contribui com dois graus, um para cada vértice conectado. Em grafos direcionados,
a equação pode ser representada como:
Grau total = número de arestas direcionadas.
15. Um grafo que possui o número máximo de arestas é chamado de grafo cheio. Desenhe
os grafos cheios não-direcionados que contêm dois, três, quatro e cinco vértices.
Grafo cheio não-direcionado com 2 vértices:
1 — 2
Grafo cheio não-direcionado com 3 vértices:
1
/ \
2 - 3
Grafo cheio não-direcionado com 4 vértices:
1
/ \
2 - 3
|
4Grafo cheio não-direcionado com 5 vértices:
1
/ \
2 - 3
/ \ / \
4 5 6 7
16. Prove que um grafo não-direcionado com n vértices contém no máximo n(n−1)
2 arestas.
A prova é feita pela contagem de pares. Em um grafo não-direcionado, cada par de vértices
pode ter, no máximo, uma única aresta conectando-os. Isso porque cada aresta é contada duas
vezes, uma para cada extremidade. Com n vértices, há n(n-1)/2 pares possíveis. Logo, o número
máximo de arestas é n(n-1)/2.
17. Considere um grafo G não-direcionado, conexo e acíclico com n vértices. Quantas
arestas G possui?
Em um grafo não-direcionado conexo e acíclico (ou seja, um grafo simples e uma árvore), cada
vértice, exceto a raiz, tem exatamente um ancestral, ou seja, uma aresta que o liga a outro
vértice. Portanto, o número de arestas em uma árvore é igual a n-1.
18. Qual o problema resolvido pela estrutura de dados chama Tabela Hash? Quais são
seus pontos positivos e negativos?
A tabela hash é uma estrutura de dados que resolve o problema da pesquisa (ou inserção) de
elementos em um conjunto. Ela mapeia cada elemento a uma posição (índice) em uma tabela,
de tal forma que a busca de um elemento seja feita em tempo constante (O(1)) em média.
Pontos positivos:
1. Tempo de busca e inserção rápidos em média, O(1).
2. Não precisa de ordenação prévia dos elementos.
3. Pode ser implementada como uma estrutura de dados estática ou dinâmica.
Pontos negativos:
1. Colisões: quando dois elementos são mapeados para a mesma posição, ocorre uma
colisão que precisa ser resolvida por algum método (exemplo: encadeamento). Isso
pode resultar em tempos de busca e inserção mais longos.
2. Escolha da função de hash: a escolha da função de hash é importante para minimizar as
colisões e garantir a distribuição uniforme dos elementos na tabela.3. Espaço: a tabela hash pode requerer um espaço adicional para armazenar informações
adicionais como a resolução de colisões ou a informação de ocupação da tabelas