Elabore algoritmos para inclusão (empilhar) e exclusão (desempilhar) que permita implementar 2 pilhas em um único vetor. Os algoritmos devem solicitar a identificação de qual pilha (1 ou 2), e fazer a operação solicitada.
Qual a complexidade destes algoritmos?
Uma deque é uma lista na qual inclusões e exclusões podem ser efetuadas em qualquer das duas extremidades.
Elabore um algoritmo de inclusão para uma deque que deve obter o valor a ser inserido e a indicação da extremidade (esquerda ou direita) na qual a inclusão irá ocorrer, considerando a deque alocada sequencialmente (em vetor) e implementada como uma lista circular.
Considere uma lista não ordenada com alocação sequencial, em um vetor com 20 posições. Apresente um algoritmo que faça a inversão da ordem dos valores desta lista, utilizando para tal uma pilha com alocação encadeada. Definir a complexidade deste algoritmo.
Sejam duas listas ordenadas, encadeadas, com nó header. Elabore um algoritmo que intercale as duas listas, gerando uma terceira lista que inicialmente estará vazia, de forma que esta lista resultante seja também ordenada.
Considere uma lista linear ordenada, de números inteiros, alocada em um vetor (sequencial) de 15 posições, inicialmente vazia. Desenhe o vetor com a lista, após todas as inclusões em 1, após as exclusões em 2 e após todas as inclusões em 3, assumindo que as operações em 2 e em 3 acontecem com a lista gerada pelas operações do item anterior.
- Incluir – 10, 20, 25, 15, 5, 30;
- Excluir – 20, 10;
- Incluir – 12, 8, 18.
Uma deque é uma lista na qual inclusões e exclusões podem ser efetuadas em qualquer das duas extremidades. Os algoritmo de inclusão e exclusão devem receber a indicação da extremidade na qual a inclusão ou exclusão irá ocorrer. Na inclusão deve ser informado o elemento a ser inserido, e na exclusão este elemento deve ser devolvido.
Escreva os algoritmos de inclusão e exclusão para uma deque, alocada de forma encadeada. Qual a complexidade destes algoritmos?
Elabore um algoritmo que leia uma lista não ordenada com n elementos alocada sequencialmente em um vetor de m posições, e faça a inclusão de cada elemento lido em uma segunda lista, ordenada, alocada de forma encadeada, com header. Qual a complexidade deste algoritmo?
Desenhe a árvore binária de busca resultante da inclusão da seguinte sequência de valores: 45, 30, 15, 70, 60, 20, 40, 65, 100, 90, 35. Qual a altura desta árvore?
Para a árvore binária de busca obtida, apresente o resultado de percorrer a árvore em pré-ordem, em-ordem e pós-ordem.
Com os valores de chave apresentados, desenhe uma árvore binária de busca no formato zigue-zague.
Elabore os algoritmos de modo recursivo para o percurso em pré-ordem, ordem e pós-ordem de uma árvore binária.
Elabore os algoritmo não recursivos (iterativos) para o percurso em pré-ordem, ordem e pós-ordem de uma árvore binária. Como sugestão utilize uma ou mais pilhas.
Elabore um algoritmo para verificar se duas árvores biordenadas são ou não isomorfas.
Desenhe a árvore AVL resultante após cada uma das inclusões a seguir: 30, 50, 90, 10, 20, 40.
Apresente o algoritmo de rotação à esquerda numa árvore AVL.
Considere uma árvore Binária de Busca balanceada, similar à árvore AVL, na qual, para cada nó, a diferença da altura entre as sub-árvores esquerda e direita possa ser de até 2.
Elabore o algoritmo de inclusão para esta árvore, que atualize o balanceamento dos nós, e indique em que casos deve ser feito um roteamento e qual roteamento. Não é preciso apresentar os algoritmos de roteamento.
Construa um Heap com a lista de prioridades a seguir (desenhe a árvore e a lista resultantes):
- Inclusão - 18, 25, 41, 34, 14, 10, 52, 50, 48;
- Inclusão das prioridades 28 e 70;
- Exclusão da prioridade 41.
Elabore o algoritmo descer para um Heap de forma iterativa.