QUESTIONÁRIO 08 - ORDENAÇÃO E MÉTODO QUICKSORT

1 - Por que o método quicksort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?

R: O método quicksort tem esse nome por ser o método mais veloz e ordenando dois vetores com n/2 elementos cada um , do que um com n de elementos e além de versões recursiva, existe também a versão interativa do quicksort.


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

R:  É conhecida pela característica rápida de ordenar dois vetores com 2 elementos cada um , do que com N elemento.

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

R: Método recursivo de complexidade de ordem algoritima recursivo. O método é 0)n log n).

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

R: Para matrizes com muitos elementos este é o método de ordenação mais rápido. Neste tipo de ordenação o programa considera sua matriz uma lista de valores. Inicialmente é selecionado o valor que está posicionado no meio da lista que chamaremos de elemento central. Depois a matriz é dividida e ordenada em duas listas menores separando numa os elementos cujo valor é maior que o valor do elemento central e e na outra os elementos cujo valor é menor que o valor do elementro central. A partir daí o mesmo processo é feito com cada uma das listas recursivamente. Isso continua até que a matriz esteja toda ordenada.

Considere a matriz formada pelos valores inteiros: 6, 2, 1, 3, 4, 5, 8, 7 e 0. A figura abaixo mostra como poderíamos classificar esta matriz em ordem crescente usando o quick sort.

5 - Demonstre o código-fonte do método quicksort e comente o mesmo.

R:

A parte muito importante do algoritmo é a escolha de um pivô , o vetor estará particionado ao final em uma parte esquerda com chaves menores ou iguais . O vetor é percorrido a partir da direita até encontrar um V[i] < V[i] . Os valores V[i] e V[i] são trocados , i é incrementado de 1 e j é decrementado de 1 , o processo é repetido até que i e j se cruzem em um ponto do vetor . Quando são obitidos os dois segmentos do vetor por meio do processo de participação , realiza-se a ordenação de cada um deles de forma recursiva.

QUESTIONÁRIO 07 - ORDENAÇÃO E MÉTODO MERGESORT

1 - Por que o método mergesort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?

R: Merge significa mistura ou fusão, é um algoritmo de ordenação do tipo dividir para – conquistar.

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

R: A principal característica do método é criar uma sequência ordenada a partir de duas outras também ordenadas. Para isso, ele divide a sequência original em pares de dados, ordena-as; depois as agrupa em sequências de quatro elementos, e assim por diante, até ter toda a sequência dividida em apenas duas partes.

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

R: Método recursivo e sua ordem de complexidade do algoritmo recursivo deste método é O(n log n) .

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

R:

5 - Demonstre o código-fonte do método mergesort e comente o mesmo.

R:

QUESTIONÁRIO 06 - INSERÇÃO E MÉTODO SHELL

1 - Por que o método shell têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?

R: Tem esse nome,pois o  matemático  que elaborou  a ordenação,  possuía  o sobrenome Shell . Existe a versão 1.2 . É  conhecida também  por método concha .

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

R: A  principal característica   é  que  o método  trabalha  com 2 vetores ,  sendo um  ordenado  e outro  desordenado ,  onde  conforme a evolução  do método  , o vetor desordenado  diminui seus elementos  e  o vetor ordenado  aumenta  , até que  não haja  nenhum elemento  no vetor desordenado .

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

R: Classificação de incremento decrescente. Seu grau de complexidade é quadrático na pior das hipóteses O(n²).

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

R:Veja o seguinte vetor de números inteiros:

     V = [38, 22, 19, 16, 44, 29]

A cada passagem do ShellSort (método de inserção), o vetor vai sendo alterado e reorganizado da seguinte forma:

– Inicial:             V=[38, 22, 19, 16, 44, 29]

– Após i=2:         V=[22, 38, 19, 16, 44, 29]

– Após i=3:         V=[19, 22, 38, 16, 44, 29]

– Após i=4:         V=[16, 19, 22, 38, 44, 29]

– Após i=5:         V=[16, 19, 22, 38, 44, 29]

– Após i=6:         V=[16, 19, 22, 29, 38, 44]

5 - Demonstre o código-fonte do método shell e comente o mesmo.

R:

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).

QUESTIONÁRIO 02 – ÁRVORES BINÁRIAS

1 - Uma árvore é um conjunto de 1 ou mais nós, onde existe um nó especial chamado raíz e os demais nós formam conjuntos disjuntos onde cada conjunto é uma árvore (subárvore). O que caracterizaria então uma árvore Binária?

R: É uma estrutura na qual o número máximo de filhos permitido pelo nó é dois. Ou seja, pode ter zero ou no máximo dois filhos.

2 - Uma árvore binária tem por tanto uma subárvore da esquerda e outra subárvore da direita (mesmo que exista uma só ou nenhuma), existe alguma maneira de calcular o número máximo de elementos de uma árvore conhecendo sua altura?

R: Sim. 2n -1.

3 - Nas árvores binárias podemos percorrer os elementos através de alguns percursos, quais são eles?

R: Pré-ordem, In-ordem e Pós-ordem.

4 - A definição do percurso EM-Ordem/IN-Ordem é:

R: In-ordem percorre sua sub-arvore esquerda, visita a raiz e percorre a sua sub-arvore direita em in-ordem.

5 - A definição do percurso PRÉ-Ordem/PRÉ-Fixado é:

R: Pré-ordem visita a raiz, percorre sub-arvore esquerda e percorre sub-arvore direita.

6 - A definição do percurso PÓS-Ordem/PÓS-Fixado é:

R: Pós-ordem percorre sub-arvore esquerda, percorre sub-arvore direita e visita a raiz.

7 - Existe outra maneira de percorrer uma árvore (não obrigatoriamente binária), conhecida como percurso por extensão ou largura. Explique esse processo.

R: O percurso em largura é mais bem compreendido de forma não-recursiva. O percurso em largura de uma árvore visita os nós na ordem dos níveis da árvore. O percurso em largura primeiro visita todos os nós do nível 0, depois todos os nós do nível um, e daí por diante. Os nós são visitados da esquerda para a direita em cada um dos níveis.

8 –

R:

• Pré-ordem ->  A, B, D, G, C, E, H, I, F.
• In-ordem   ->  D, G, B, A, H, E, I, C, F.
• Pós-ordem ->  G, D, B, H, I, E, F, C, A.

QUESTIONÁRIO 01 – ÁRVORES, CONCEITOS GERAIS

1 - A estrutura de uma árvore é especializada em representar hierarquia. Defina e caracterize de forma completa o conceito da Estrutura Árvore.

R: A estrutura árvore representa uma das estruturas mais importantes da área da computação, principalmente em aplicações. Dentro da estrutura de árvores existe um relacionamento lógico entre os componentes da estrutura, isto é, existe uma hierarquia ou subordinação onde um subconjunto dos componentes é subordinado a outro. A estrutura de árvore é utilizada em casos onde os dados ou objetos a serem representados possuem relações hierárquicas entre si.

2 - O conceito da estrutura árvore é muito importante para as disciplinas de Sistema Operacional e Banco de Dados. Dê exemplos da aplicação prática da estrutura de dados árvore, explicando cada exemplo (pelo menos 3).

R:

• Organogramas de empresas – hierarquia entre os empregados
• Ordenação de Valores – Árvore ordenada. Ex. esquerda / raiz / direita
• Abstração de Composição – um objeto é composto por outros objetos

3 - Para compreender o conceito de árvore é necessário entender alguns conceitos básicos. Explique o conceito de raíz, nó filho, nó pai, nó terminal, nó ascendente, nó descendente, grau, altura, nível, profundidade, caminho e floresta.

R: Uma árvore é um conjunto finito A de zero ou mais nós, tais que:

• Caso o número de nós seja maior que zero, existe um nó denominado raiz da árvore, os demais nós formam m >= 0 conjuntos disjuntos S1, S2, ..., Sm, onde cada um destes conjuntos é uma árvore (Si são denominadas sub-árvores).
• Número de nós zero: árvore vazia.
• Cada nó da árvore é a raiz de uma subárvore. 
• Grau de um Nó é o número de subárvores de um nó. Nó de grau zero é denominado nó folha ou nó terminal. 
• Nível de um Nó raiz possui nível zero. Demais nós: é o comprimento do caminho que vai da raiz até o nó.
• Altura de uma Árvore é o maior nível de uma árvore (mais alto).
• Floresta conjunto de zero ou mais árvores disjuntas. Se o nó raiz de uma árvore for eliminado, as subárvores, que restarem serão chamadas de floresta.
• Nó Pai é o pai das raízes de suas subárvores e Nó Filho  possui um nó pai associado.     
• Nós Irmãos são os vários filhos de um nó pai.

4 - Existem diversas maneiras de representar a estrutura de uma árvore. Demonstre e conceitue a representação Hierárquica, Diagrama de Inclusão, Expressão parametrizada e Expressão não parametrizada.

R:

Diagrama de inclusão

Representação Hierárquica

Representação por expressão não parentetizada

Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e

em seguida por esses filhos, representados do mesmo modo.

A 2 B 2 D 0 E 0 C 1 F 0

Representação por expressão parentetizada (parênteses aninhados)

Cada conjunto de parênteses correspondentes contém um nodo e seus filhos. Se um

nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.

( A ( B ( D ( ) E ( ) ) ) ( C ( F ( ) ) ) ).