gabaritos_prova

gabarito_prova_manha.cpp

Prova Manhã.
1. 3 Pontos
2. 3.5 Pontos
3. 3.5 Pontos
4. 2 Pontos.

1.
    Hash.
        Memória: Maior uso de memória por alocar toda a tabela de espaço.
        Busca: tempo linear e constante, O(1), acesso direto por causa do hash.
        Inserção e remoção:
            tempo linear(1), por causa do hash e da estrutura
            de marçação e saltos.
        Organização interna: um vetor de elementos alocados estaticamente.
        Percorrimento:
            como não existe ordenação, o percorrimento se faz na estrutura
            do vetor.
        Ordenação: não existe critério de ordenação na inserção ou armazenamento.

    Tree
        Memória:
            Menor uso de espaço por alocar dinâmicamente o espaço de cada nó.
        Busca:
            logaritmico, pois necessita "descer na árvore" a procura do nó.
        Inserção:
            mais lento que no hash.
        Organização interna:
            Nós encadeados alocados dinâmicamente.
        Percorrimento:
            Existem vários tipos de percorrimento possíveis.
        Ordenação:
            ordenação explicita intrínseca dos elementos. É possível percorrer
            os elementos em ordem. Os elementos precisam de um critério de ordenação.

2. Inserção em hash
    Pontos importantes:
    1. calcular o hash a partir de "key" 0.5
    2. fazer busca por uma posição válida CIRCULARMENTE
    3. inserir 1.0 p
    4. resultar corretamente true ou false.

3.
    Procurar se existe o nó cujo falor foi passado.
    Dado o nó faça:
    Se não filhos remover e atualizar o pai com null.
    Se tiver apenas 1 filho, remover e atualizar pai com o filho.
    Se 2 filhos, buscar o descendente mais a direita do filho
        da esquerda
    Salvar o valor do filho
    Remover esse filho utilizando a recursão
    Substituir o valor do nó pelo valor do descendente removido.

4. Soma

    int soma(Node * node){
        if(node.filhos.size() == 0)//ponto de parada
            return node.value;
        int total = node.value;
        for(auto filho : node.filhos)
            total += soma(filho);//chamada recursiva
        return total;
    }

gabarito_prova_tarde.cpp

Prova Tarde
1. 3 Pontos
2. 3.5 Pontos
3. 3.5 Pontos
4. 2 Pontos.

1.
    Hash.
        Memória: Maior uso de memória por alocar toda a tabela de espaço.
        Busca: tempo linear e constante, O(1), acesso direto por causa do hash.
        Inserção e remoção:
            tempo linear(1), por causa do hash e da estrutura
            de marçação e saltos.
        Organização interna: um vetor de elementos alocados estaticamente.
        Percorrimento:
            como não existe ordenação, o percorrimento se faz na estrutura
            do vetor.
        Ordenação: não existe critério de ordenação na inserção ou armazenamento.

    Tree
        Memória:
            Menor uso de espaço por alocar dinâmicamente o espaço de cada nó.
        Busca:
            logaritmico, pois necessita "descer na árvore" a procura do nó.
        Inserção:
            mais lento que no hash.
        Organização interna:
            Nós encadeados alocados dinâmicamente.
        Percorrimento:
            Existem vários tipos de percorrimento possíveis.
        Ordenação:
            ordenação explicita intrínseca dos elementos. É possível percorrer
            os elementos em ordem. Os elementos precisam de um critério de ordenação.

2. Inserção em hash Pseudocódigo com realocação.
    1. Dada a chave, calcula o hash.
    2. Inicia uma busca a partir da posição do hash circularmente no vetor
      procurando(ou pelo valor ou por uma posição fazia)
    3. Se for encontrado o valor retorne false.
    4. Se for encontrada uma posição vazia verifique se alocação menor que 60%.
    5. Se houver espaço, insira e retorne true.
    5. Se não houver espaço, crie uma nova tabela com o dobro do tamanho.
    6. Insira todos os elementos na nova tabela.
    7. Atualize as variáveis de tamanho e tamanho máximo.
    8. Retorne true.

3. Inserção na bstree. (existem várias formas de implementar, essa é a mais fácil)
    void _insert(Node ** elo, int value){
        Node * node = *elo;
        if(node == nullptr){
            *elo = new Node(value);
            return true;
        }
        if(node.value < value)
            return _insert(&node.left); //chamada recursiva
        if(node.value > value)
            return _insert(&node.right); //chamada recursiva
        return false; //se nao é menor nem maior, só pode ser igual.
    }

    bool insert(int value){
        return _insert(&root, value);
    }

4. Mínimo na n-tree
    Pontos importantes: Caso base
    Chamada recursiva percorrendo o vetor.
    Tratamento do mínimo.

    int minimo(Node * node){
        if(filhos.size() == 0) //caso base
            return 0;
        int _min = node.value;
        for(auto filho : filhos)
            if(minimo(filho) < _min) //chamada recursiva
                _min = filho.value;
        return min;
    }