QUESTIONÁRIO 05 - ORDENAÇÃO E MÉTODO BOLHA

1- Ordenar é um processo de rearranjar um conjunto de objetos em uma ordem ascendente/crescente ou descendente/decrescente. Qual a importância da ordenação para qualquer processo e para informática? Dê exemplos práticos de utilização. Defina a complexidade dos métodos de ordenação e a sua classificação.

R:

• A ordenação é importante para localização de registros ou para exibição de dados (relatórios) ou outras operações que necessitem dos dados ordenados. Exemplos: impressão de relatórios, informações de dados em tela, relatórios analíticos, etc...
• A complexidade dos métodos de ordenação pode ser simples e sofisticados, quantas mais trocas ele faz mais complexo é o método, estão classificados em n²>n>logⁿ.

2 - Qual é a classificação dos métodos de ordenação? Qual a diferença entre eles? Quais são os métodos de ordenação mais utilizados ou principais?

R: Estão classificados em quadrática, normal e logarítmica. Os métodos mas utilizados são bolha, Shell, quick, merge.

3 - A ordenação pelo método bolha é um dos mais simples. Qual a principal característica do método ou como ele funciona?

R: A principal característica é a simplicidade e ele funciona basicamente trocando as posições entre dois elementos do array (vetor) de acordo com a ordem desejada, fazendo passadas ate termino da ordenação.

4 - Qual é a classificação do método bolha? Qual o seu grau de complexidade?

R: O BubbleSort é um método de simples implementação e sua ordem é de complexidade quadrática.

5 - Dê exemplo de aplicação do método bolha, com as comparações, trocas e iterações.

R:

6 - Demonstre o código-fonte do método bolha e comente o mesmo.

R:

 

QUESTIONÁRIO 04 - ÁRVORES AVL

01 - Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.  Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Para construirmos uma árvore balanceada ou AVL primeiramente precisamos utilizar o conceito de ABB. Portanto explique o conceito de árvore balanceada ou AVL?

R: A árvore AVL é balanceada quando a diferença da sub-árvores (direita e esquerda) for = < 1, e se seus filhos e netos tiverem diferenças maiores que 1 essa arvore não esta balanceada.  

2 - Sabendo que podemos inserir elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de inserção na árvore AVL e do seu algoritmo.

R: Seja c uma nova chave a inserir numa árvore AVL A. Primeiro, c é inserido como folha de A, seguindo o algoritmo do caso geral das ABBs.  Se depois da inserção a árvore permanece AVL, então nada mais temos a fazer.  Caso contrário, é necessário remanejar a árvore.

3 - Sabendo-se que os conceitos de rotação simples a direita/esquerda e de rotação dupla a direita/esquerda são essenciais na inserção de elementos na árvore avl. Explique os conceitos de rotação simples e rotação dupla.

R: Rotação simples é utilizada quando a apenas filhos alinhados Ex: 3 > 7  > 9 o valor 9 é a raiz principal, o 7 é filho do 9 e pai do 3, agora vamos balanceá-la, o 7 se torna a raiz principal, o 3 é filho esquerdo de 7 e o 9 é filho direito de 7.

4 - Sabendo que podemos retirar elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de remoção na árvore AVL e do seu algoritmo.

R: A remoção deve ser feita por uma rotação em torno do nó a ser removido e torná-lo folha para que então possa ser retirado. Em alguns casos, após ser retirado são necessárias rotações para ajustar o fator de balanceamento.

5 - Através dos conceitos discutidos, dê dois exemplos de inserção em árvores AVL e dois exemplos de remoção em árvores AVL.

R:

QUESTIONÁRIO 03 – ÁRVORES "ABB"

1 - Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.  Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Portanto explique como serão inseridos os elementos 10, 20, 15, 18,  30, 40 e 13 numa árvore binária de busca.

R: Insere o 10 como raiz, 20 a direita, o 15 a esquerda do 20, o 30 a direita do 20, 13 a esquerda do 15, 18 a direita do 15 e 40 a direita do 30.

2 - Sabendo que podemos inserir elementos numa árvore binária e que isso é uma operação básica das árvores, indique e explique quais são as operações básicas de uma árvore binária?

R: Inserção – é quando se insere novo item na arvore seguindo a regra esquerdo menor e direito maior e sempre nas extremidades (folhas).

     Exclusão – é quando se exclui um item existente, que pode não conter filhos, conter somente um filho ou conter dois filhos.

3 - Sabendo que as árvores binárias podem ser cheias e completas e que uma árvore otimal é uma árvore completa que a operação de inserção segue a regra de inserção por ordem das chaves. Como as inserções sempre ocorrem à nível de folha,  deve-se primeiro inserir as chaves que ficarão mais perto da raíz. Se temos um conjunto de chaves {c1,..,ci} tal que c1<...<ci, deve se inserir o valor médio das chaves, inserir o conjunto das chaves inferior a esse valor, e inserir o conjunto das chaves superior a esse valor.  Portanto no conjunto de chaves K={1,2,3,4,5,6,7}.  Uma ordem de inserção otimal seria o 4, 2, 6, 1, 7, 5 e 3. Explique como ficaria uma inserção otimal do conjunto K={2,4,6,8,10,12,14}.

R: Como raiz usaremos o nurmero 8 pois o mesmo é o numero médio (existem três algarismo tanto a esquerda quanto a direita), o numero 4 será o filho a esquerda e o 12 o filho a direita (pois os mesmo são números médios em relação a 2 e 6, e, 10 e 14, respectivamente). 2 será a esquerda de 4 e 6 a direita, 10 a esquerda de 12 e 14 a direita.

4 - Uma das operações mais úteis das ABB é a localização, outra característica desse tipo de árvore são os chamados percursos que mostram os elementos que a árvore contém e que são classificados em pré-fixado/pré-ordem, pós-fixado/pós-ordem e in-ordem/em ordem. Explique como funciona o procedimento para realizar cada percurso considerando as subárvores. Existe alguma diferença com relação às árvores binárias comuns?

R: Basicamente a diferença está na forma de inserção e busca dos elementos, enquanto as arvores binárias comuns insere elementos sem necessidade de verificar qual elemento é maior ou menor (dificultando a busca de elementos), a arvore de busca insere raiz-(menor) à esquerda e (maior) à direita (facilitando a busca dos elementos).