Instituto de Computação - UNICAMP

MC202 - Estruturas de Dados

Segundo Semestre de 2005

Lista de Exercícios 2


Heap

  1. Defina heap. Dê um exemplo de um heap.
  2. Uma árvore binária completa pode ser armazenada de maneira eficiente em um vetor (os nós no vetor seguem a mesma ordem de um percurso em largura na árvore).
  3. Seja H um heap de máximo de tamanho n armazenado em um vetor. Em quais posições do vetor você pode encontrar:

  4. Descreva dois métodos para transformar um vetor em um heap. Simule seu métodos para a seguinte entrada: 12, 25, 13, 17, 19, 3, 14, 5, 11. Qual método é o melhor?
  5. Execute as operações indicadas no heap contendo os seguintes elementos (nesta ordem): 90, 80, 70, 50, 60, 68, 56, 45, 54, 55.
  6. Crie um algoritmo O(log n) para a operação Remove_Heap(A,i), que remove do heap A o elemento na posição i do vetor.
  7. Qual o número mínimo e máximo de elementos que podem ser armazenados em um heap de profundidade d?

    Árvore AVL

  8. Dada uma árvore binária T, proponha um algoritmo que determine se T é uma árvore AVL (lembrando-se das restrições de altura e de árvore de busca).
  9. Uma árvore AVL pode ter 2 folhas cujas profundidades (isto é, as respectivas distâncias até a raiz) difiram de mais do que 2? Por exemplo, uma folha teria profundidade 10 e outra teria 7.
  10. Desenhe a sequência de árvores que se obtém pela construção de uma árvore AVL pela inclusão das chaves a seguir, nesta ordem em uma árvore originalmente vazia: 170, 289, 110, 153, 128, 140, 303, 240, 264, 255.
  11. Nesta questão, você deverá executar duas inserções e duas remoções de chaves da árvore AVL mostrada baixo. Desenhe a árvore resultante da operação correspondente, seguindo estritamente os algoritmos explicados em classe.

    Árvore B

  12. Dada uma árvore B de ordem 512, diga:

  13. Dada a árvore B (com no máximo 4 chaves e 5 subárvores) mostrada abaixo, desenhe as árvores resultantes da aplicação das operações seguintes operações: inserção de 98, inserção de 28, remoção de 94 e remoção de 13.

  14. Mostrar as árvores B resultantes da remoção de A, B, Q e M, nesta ordem.

  15. Descreva como prover acesso seqüencial ordenado a um arquivo indexado por uma árvore B.

    Tabela de Espalhamento

  16. Na tabela de espalhamento representada na figura abaixo, a função de hashing é dada pelo resto da divisão do valor da chave pelo tamanho da tabela e a estratégia para resolução de colisões é linear.

    Posição Chave Estado
    0 - Livre
    1 6 Ocupado
    2 1 Ocupado
    3 - Livre
    4 - Removido

  17. Escreva um algoritmo para remover um valor X de uma hash table que usa uma função de espalhamento f e endereçamento aberto com reespalhamento linear para resolver colisões. Mostre que marcar a posição previamente ocupada por X como "livre" não resolve o problema. Como deve ser elaborado um algoritmo de busca para que funcione corretamente quando remoções são permitidas?

    Grafo

  18. Desenhe um grafo orientado e sua representação utilizando listas de adjacências e matrizes de adjacências. Comente quais são as vantagens e desvantagens de cada uma destas representações levando em consideração o espaço para armazenamento e a complexidade das seguintes operações: (i) verificar a existência de uma aresta; (ii) verificar quais são os nós adjacentes a um nó j e (iii) verificar quais nós apontam para um nó j. Para cada um destes itens, leve em consideração a existência de grafos densos (muitas arestas) e esparsos (poucas arestas).
  19. O professor Ricardo promoverá um jantar de confraternização para os n alunos deste curso. Todos os alunos deverão se sentar numa mesa redonda de n lugares. O problema do professor é o seguinte: verificar se é possível garantir que cada pessoa tenha um amigo ou amiga sentado de ambos os lados, sabendo-se as relações de amizade entre os alunos e sendo que estas não são necessariamente transitivas (isto é: se A é amigo de B e B é amigo de C isto não significa necessariamente que A é amigo de C). Formule o problema do professor Ricardo como um problema em grafos e diga claramente qual o problema que tem que ser resolvido usando a linguagem de grafos.