tag:blogger.com,1999:blog-75295730601203546152024-03-14T05:19:29.467-03:00Sistemas de InformaçãoPostado por Katiúcia, Limberg, Otoniel e William.Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-7529573060120354615.post-64599069554149725212011-10-26T21:29:00.003-02:002011-11-30T17:24:50.564-02:00QUESTIONÁRIO 08 - QUICKSORT<span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">1)<span style="font-family: "Times New Roman";"> </span></b>Por que o método quicksort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?</span><br />
<span style="color: #cccccc;">Resposta: O método Quicksort tem esse nome por ser um método <span style="font-family: Calibri;">que é mais rápido ordenar dois vetores com n/2 elementos cada um, do que um com n elementos (conceito dividir para conquistar). Além da versão recursiva, existe também a versão iterativa do <span style="font-family: Times New Roman;">Quicksort.</span></span></span><br />
<span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">2) </b>A ordenação pelo método quicksort é um dos mais simples. Qual a principal característica do método ou como ele funciona? </span><br />
<span style="color: #cccccc;">Resposta: O primeiro passo é escolher o pivô. Uma vez escolhido o pivô, os elementos do vetor são movimentados de forma que o subvetor à esquerda do pivô contenha somente os elementos cujo valor é menor que o valor do pivô e o subvetor da direita contenha valores maiores que o valor do pivô. O procedimento é repetido até que o vetor esteja ordenado.</span><span style="color: #bf9000;"><br />
</span><br />
<span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">3) </b>Qual é a classificação do método quicksort? Qual o seu grau de complexidade?</span><br />
<span style="color: #cccccc;">Resposta: O método quicksort é um método recursivo. Existem dois tipos de complexidade: Complexidade de Tempo e Complexidade de Espaço.</span><br />
<span style="color: #cccccc;">Complexidade de Tempo θ(n lg<sub><span style="font-size: x-small;">2</span></sub> n) no melhor caso e θ(n) no caso médio e θ(n<sup><span style="font-size: x-small;">2</span></sup>) no pior caso;</span><br />
<span style="color: #cccccc;">Complexidade de espaço: θ(lg<sub><span style="font-size: x-small;">2</span></sub> n) no melhor caso e no caso médio e θ(lg<sub><span style="font-size: x-small;">2</span></sub> n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n<sup><span style="font-size: x-small;">2</span></sup>) no pior caso.</span><span style="color: #bf9000;"><br />
</span><br />
<span style="color: #bf9000;"><b>4) </b>Dê exemplo de aplicação do método quicksort, com as comparações, trocas e iterações.</span><br />
<span style="color: #cccccc;">a) Pivô é escolhido no meio do vetor. O elemento é colocado numa variável auxiliar trab; </span><br />
<span style="color: #cccccc;">b) São iniciados dois ponteiros i e j; </span><br />
<span style="color: #cccccc;">c) O vetor é percorrido a partir da esquerda até que se encontre um V[i] ≥ trab (i é incrementado no processo); </span><br />
<span style="color: #cccccc;">d) O vetor é percorrido a partir da direita até que se encontre um V[j] ≤ trab (j é decrementado no processo); </span><br />
<span style="color: #cccccc;">e) Os valores V[i] e V[j] são trocados; i é incrementado de 1 e j é decrementado de 1; </span><br />
<span style="color: #cccccc;">f) O processo é repetido até que i e j se cruzem em algum ponto do vetor; </span><br />
<span style="color: #cccccc;">g) Quando são obtidos os dois segmentos do vetor por meio do processo de partição, realiza-se a ordenação de cada um deles de forma recursiva. </span><span style="color: #bf9000;"><br />
</span><br />
<span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">5) </b>Demonstre o código-fonte do método quicksort e comente o mesmo.<b style="mso-bidi-font-weight: normal;"></b></span><br />
<br />
<div align="left"><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMPdCvYnvTbS0NajwVhRA5mkA0I4CtP3c4XMNvPJoNWz2QJ26VyDTM2njcAWhfMeDI6MeFfCVFI5vQV634tvtvC-R8TrVLE9zx2nfqy0Bod9HSLcLL02xfuq1W-dlk83fKydDREWWNEdrq/s1600/COD.+QUICK.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiMPdCvYnvTbS0NajwVhRA5mkA0I4CtP3c4XMNvPJoNWz2QJ26VyDTM2njcAWhfMeDI6MeFfCVFI5vQV634tvtvC-R8TrVLE9zx2nfqy0Bod9HSLcLL02xfuq1W-dlk83fKydDREWWNEdrq/s320/COD.+QUICK.png" width="193" /></a></div> 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 ao pivô e outra parte direita maiores ou iguais. O vetor é percorrido a partir da direita até encontrar um V[j] ≤ V[i]. Os valores V[i] e V[j] são trocados, i é incrementado de 1 e j é decrementado de 1, o processo é repetido até que i e j se cruzem em algum ponto do vetor. Quando são obtidos os dois segmentos do vetor por meio do processo de partição, realiza-se a ordenação de cada um deles de forma recursiva. </div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com0tag:blogger.com,1999:blog-7529573060120354615.post-60733454748740222162011-10-22T16:00:00.013-02:002011-11-30T17:32:09.016-02:00QUESTIONÁRIO 07 - ORDENAÇÃO – MÉTODO MERGESORT<div class="MsoNormal" style="margin: 0cm 0cm 0pt; text-align: justify;"><span style="color: #bf9000;">1) Por que o método mergesort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?</span><br />
<span style="color: white;">Resposta: O mergesort ou ordenação por mistura (fusão), é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.</span><br />
<div class="MsoNormal" style="margin: 0cm 0cm 0pt; text-align: justify;"><br />
<span style="color: #bf9000;">2) A ordenação pelo método mergesort é um dos mais simples. Qual a principal característica do método ou como ele funciona? </span></div><div style="tab-stops: list 40.05pt; text-indent: -18.75pt;"> <span style="color: white;">Resposta: Complexidade de tempo. É (n log<sub>2 </sub>n). É possível implementar o mergesort utilizando somente um vetor auxiliar ao longo de toda a execução.</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt;"><br />
</div><div style="tab-stops: list 40.05pt; text-indent: -18.75pt;"> <span style="color: #bf9000;">3) Qual é a classificação do método mergesort? Qual o seu grau de complexidade?</span><br />
<span style="color: #bf9000;"> </span><span style="color: white;">Resposta: <span style="font-size: small;">O Mergesort é classificado como ordenação por partição, que parte do princípio de "dividir para conquistar". Este princípio é uma técnica que foi utilizada pela primeira vez por Anatolii Karatsuba em 1960 e consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente. </span></span><br />
<span style="color: white;"> Esta técnica realiza-se em três fases: </span><br />
<span style="color: white;"> <b><span style="font-family: Arial,Arial; font-size: small;"><span style="font-family: Arial,Arial; font-size: small;"> Divisão: </span></span><span style="font-size: small;">o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva. </span></b></span><br />
<b><span style="color: white;"> <b><span style="font-family: Arial,Arial; font-size: small;"><span style="font-family: Arial,Arial; font-size: small;">Conquista: </span></span><span style="font-size: small;">o resultado do problema é calculado quando o problema é pequeno o suficiente.</span></b></span></b><br />
<b><b><span style="color: white;"> <b><span style="font-family: Arial,Arial; font-size: small;"><span style="font-family: Arial,Arial; font-size: small;">Combinação: </span></span><span style="font-size: small;">os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, </span><i><span style="font-family: Arial,Arial; font-size: small;"><span style="font-family: Arial,Arial; font-size: small;">O</span></span></i><span style="font-size: small;">(</span><i><span style="font-family: Arial,Arial; font-size: small;"><span style="font-family: Arial,Arial; font-size: small;">nlogn</span></span></i><span style="font-size: small;">). Os dois representantes mais ilustres desta classe são o </span><i><span style="font-family: Arial,Arial; font-size: small;"><span style="font-family: Arial,Arial; font-size: small;">quicksort </span></span></i><span style="font-size: small;">e o </span><i><span style="font-family: Arial,Arial; font-size: small;"><span style="font-family: Arial,Arial; font-size: small;">mergesort</span></span></i><span style="font-size: small;">. </span></b></span></b></b><br />
<span style="color: #073763;"> </span></div><div style="tab-stops: list 40.05pt; text-indent: -18.75pt;"> <span style="color: #bf9000;">4) Dê exemplo de aplicação do método mergesort, com as comparações, trocas e iterações.</span><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8zr9q78CjbQXdBV6VgbEtTTBfUpuPXtVli2bcclPKsLLs-prAUwzIqBoBwJbgh4M-3dnBLSGbtloRB9RV62lrbv8ifmhuWNWNYL3Ka2yPlM-WEJwcSSwjiGJoxQF6pqYrXalJthyLtnJ1/s1600/Ex.+MergeSort.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi8zr9q78CjbQXdBV6VgbEtTTBfUpuPXtVli2bcclPKsLLs-prAUwzIqBoBwJbgh4M-3dnBLSGbtloRB9RV62lrbv8ifmhuWNWNYL3Ka2yPlM-WEJwcSSwjiGJoxQF6pqYrXalJthyLtnJ1/s1600/Ex.+MergeSort.png" /></a></div><span style="color: #bf9000;"> </span></div><div style="tab-stops: list 40.05pt; text-indent: -18.75pt;"><br />
</div><div style="tab-stops: list 40.05pt; text-indent: -18.75pt;"><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"> <span style="color: #bf9000;"> 5) Demonstre o código-fonte do método mergesort e comente o mesmo.</span></div></div><div style="tab-stops: list 40.05pt; text-indent: -18.75pt;"><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"> </div></div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3t5dT3c2ARZQwM6l8y0IxBrbEqLU41gh5FO1a4tPiFcGZtnBB547RIg28aWzsFaccjsH-Y3vPSiFUvFO8dgHlpIx11qVhsY1T19S6faBkwlLdYsDIRvg_OvpBUd8IJQ7ewRDCosRD0Ehy/s1600/Imagem1.png" imageanchor="1" style="cssfloat: left; margin-left: 1em; margin-right: 1em;"><img border="0" height="231" rda="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh3t5dT3c2ARZQwM6l8y0IxBrbEqLU41gh5FO1a4tPiFcGZtnBB547RIg28aWzsFaccjsH-Y3vPSiFUvFO8dgHlpIx11qVhsY1T19S6faBkwlLdYsDIRvg_OvpBUd8IJQ7ewRDCosRD0Ehy/s400/Imagem1.png" width="400" /></a></div><div class="separator" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none; clear: both; text-align: center;">Clique na figura para visualizar</div></div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com0tag:blogger.com,1999:blog-7529573060120354615.post-49532213570845470322011-10-05T21:52:00.005-03:002011-10-25T22:40:39.698-02:00QUESTIONÁRIO 06 - INSERÇÃO E MÉTODO SHELL<div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-bidi-font-size: 12.0pt;"><span style="mso-list: Ignore;">1)<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; line-height: normal;"> </span></span></span></b><span style="mso-bidi-font-size: 12.0pt;">Por que o método shell têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?</span></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="mso-bidi-font-size: 12.0pt;"><span style="color: #cccccc;">Resposta: O Método Shell leva o nome do seu inventor Donald L. Shell, formado em Ciência da Computação e teve seu PH.D. em matemática após a publicação <span class="hps" closure_uid_8e4e8a="181" td="null">do</span> <span class="hps" closure_uid_8e4e8a="182" td="null">algoritmo de ordenação</span> <span class="hps" closure_uid_8e4e8a="183" td="null">shell. A versão que existe é a versão 1.2 e em relação ao nome, ela também pode ser conhecida como concha, pois lembra o formato de uma concha. </span></span></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-bidi-font-size: 12.0pt;"><span style="mso-list: Ignore;">2)<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; line-height: normal;"> </span></span></span></b><span style="mso-bidi-font-size: 12.0pt;">A ordenação pelo método shell é um dos mais simples. Qual a principal característica do método ou como ele funciona? </span></span><br />
<span style="color: #cccccc;">Resposta: A principal característica do método shell é que ele trabalha com 2 vetores: Vetor Ordenado e Vetor Desordenado. Com o funcionamento e evolução do método shell, o vetor desordenado vai diminuindo seus elementos, enquanto o vetor ordenado vai aumentando seus elementos, ou seja, os elementos que estavam desordenados vai se ordenando até que o vetor ordenado fique com todos os elementos completo e o vetor desordenado não haja mais nenhum elemento, ou seja, se torna um vetor vazio (null).</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-bidi-font-size: 12.0pt;"><span style="mso-list: Ignore;">3)<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; line-height: normal;"> </span></span></span></b><span style="mso-bidi-font-size: 12.0pt;">Qual é a classificação do método shell? Qual o seu grau de complexidade?</span></span><br />
<span style="color: #cccccc; mso-bidi-font-size: 12.0pt;">Resposta: O método shell é classificado como método de simples implementação e o seu grau de complexidade é quadrática.</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-bidi-font-size: 12.0pt;"><span style="mso-list: Ignore;">4)<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; line-height: normal;"> </span></span></span></b><span style="mso-bidi-font-size: 12.0pt;">Dê exemplo de aplicação do método shell, com as comparações, trocas e iterações.</span></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 18pt; text-align: justify;"><div class="MsoNormal" style="margin: 0cm 0cm 0pt; text-align: justify;"><span style="color: red;"><span style="color: #cccccc;">Resposta: O primeiro elemento está no vetor ordenado e os demais no vetor desordenado; </span></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt; text-align: justify;"><span style="color: red;"><span style="color: #cccccc;">Retira-se o primeiro elemento do vetor desordenado, colocando-o no vetor ordenado. Nesse processo, são realizadas as comparações necessárias para inserí-lo na sua posição correta; </span></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt; text-align: justify;"><span style="color: red;"><span style="color: #cccccc;">Repete-se o processo até que todos os elementos do vetor desordenado tenham passado para o vetor ordenado. </span></span></div><br />
</div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-bidi-font-size: 12.0pt;"><span style="mso-list: Ignore;">5)<span style="font-family: "Times New Roman"; font-style: normal; font-variant: normal; font-weight: normal; line-height: normal;"> </span></span></span></b><span style="mso-bidi-font-size: 12.0pt;">Demonstre o código-fonte do método shell e comente o mesmo.<b style="mso-bidi-font-weight: normal;"></b></span></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt;"><br />
</div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com0tag:blogger.com,1999:blog-7529573060120354615.post-67454289366319299422011-09-28T21:43:00.006-03:002011-11-30T17:41:21.705-02:00QUESTIONÁRIO 05 - ORDENAÇÃO E MÉTODO BOLHA<div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; text-align: justify;"><br />
</div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">1)<span style="font-family: "Times New Roman";"> </span></b>Ordenar é um processo de rearranjar um conjunto de objetos em uma ordem </span><a href="http://www.blogger.com/" name="_GoBack"></a><span style="color: #bf9000;">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.</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 18pt; text-align: justify;"><span style="color: #bf9000;"><br />
</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">2)<span style="font-family: "Times New Roman";"> </span></b>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?<b style="mso-bidi-font-weight: normal;"></b></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; text-align: justify;"><span style="color: #bf9000;"><br />
</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">3)<span style="font-family: "Times New Roman";"> </span></b>A ordenação pelo método bolha é um dos mais simples. Qual a principal característica do método ou como ele funciona? </span><br />
<div style="text-align: justify;"><span style="color: #cccccc;">Resposta: O primeiro elemento é comparado com o segundo, se uma inversão for encontrada, a troca é feita. Em seguida, independente se houve ou não troca após a primeira comparação, o segundo elemento é comparado com o terceiro, e, caso uma inversão seja encontrada, a troca é feita. O processo continua até que o penúltimo elemento seja comparado com o último.</span></div></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">4)<span style="font-family: "Times New Roman";"> </span></b>Qual é a classificação do método bolha? Qual o seu grau de complexidade?<b style="mso-bidi-font-weight: normal;"></b></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 18pt; text-align: justify;"><span style="color: #bf9000;">Reposta: </span>N > N > log(N)<br />
E o seu grau de complexidade é pequeno , necessita de muita memória para opera-lo</div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;">5)<span style="font-family: "Times New Roman";"> </span></b>Dê exemplo de aplicação do método bolha, com as comparações, trocas e iterações.<b style="mso-bidi-font-weight: normal;"></b></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 18pt; text-align: justify;"><span style="color: #bf9000;"><span style="color: #f3f3f3;">Resposta: Bom um exemplo que pode ser dado é classificação numerica de forma cresente de uma derterminadaposta</span><span style="color: #f3f3f3;"></span><br style="color: #f3f3f3;" /><span style="color: #f3f3f3;">1 40 30 20 10 50</span><br style="color: #f3f3f3;" /><span style="color: #f3f3f3;">2 30 20 10 40 50</span><br style="color: #f3f3f3;" /><span style="color: #f3f3f3;">3 20 10 30 40 50</span><br style="color: #f3f3f3;" /><span style="color: #f3f3f3;">4 10 20 30 40 50</span><br style="color: #f3f3f3;" /><span style="color: #f3f3f3;">5 10 20 30 40 50 --> Todos os numeros Ordenados.</span><br />
</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 36.75pt; mso-list: l0 level1 lfo1; tab-stops: list 36.75pt; text-align: justify; text-indent: -18.75pt;"><br />
<span style="color: #bf9000;"><b>6)<span style="font-family: "Times New Roman";"> </span></b>Demonstre o código-fonte do método bolha e comente o mesmo.<b style="mso-bidi-font-weight: normal;"></b></span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt;">Resposta: #include <stdio.h> <br />
#include <stdlib.h><br />
<br />
void bubble(int a[],int n) <br />
{ <br />
<br />
int i,j,t; <br />
for(i=n-2;i>=0;i--) { <br />
for(j=0;j<=i;j++) { <br />
<br />
if(a[j]>a[j+1]) { <br />
t=a[j]; <br />
a[j]=a[j+1]; <br />
a[j+1]=t; <br />
} <br />
} <br />
<br />
} //Final do 1º FOR <br />
<br />
} //Final da Função <br />
<br />
int main() { <br />
<br />
int a[100],n,i; <br />
<br />
system("pause"); <br />
<br />
printf("\n\n Entre com o total de numeros a serem sorteados:\n\n "); <br />
scanf("%d",&n); <br />
<br />
for( i=0;i<=n-1;i++) { <br />
<br />
printf("\n\n Entre com o valor inteiro %d: ",i+1); <br />
scanf("%d",&a[i]); <br />
} </div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com0tag:blogger.com,1999:blog-7529573060120354615.post-46239999033655494592011-08-31T21:30:00.012-03:002011-10-25T22:53:39.809-02:00QUESTIONÁRIO 04 - ÁRVORES AVL (BALANCEADAS)<div class="MsoNormalCxSpFirst" style="line-height: normal; margin: auto auto 0pt; mso-add-space: auto;"><span style="color: #bf9000; font-size: 12pt;"><b>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. Para construirmos uma árvore balanceada ou AVL primeiramente precisamos utilizar o conceito de ABB. Portanto explique o conceito de árvore balanceada ou AVL? </b></span></div><div class="MsoNormalCxSpFirst" style="color: white; line-height: normal; margin: auto auto 0pt;"><span style="font-family: inherit;">Resposta: Uma árvore AVL é dita balanceada quando,<span id="goog_942917970"></span><span id="goog_942917971"></span> para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos. Para definir o balanceamento é utilizado um fator específico para nós. O Fator de Balanceamento (FB) é utilizado pela seguinte fórmula:</span></div><div class="O" style="color: white; line-height: normal; margin: auto auto 0pt; text-align: center;" v:shape="_x0000_s1026"><span style="font-family: Cambria;"><b><span style="font-family: inherit;">FB(nó) = altura(dir) - altura(esq) </span></b></span></div><div style="color: white;"><span style="font-family: Cambria;"></span></div><div style="color: white;"><span style="font-family: Cambria;"></span></div><div class="O" style="color: white; line-height: normal; margin: auto auto 0pt; text-align: left;" v:shape="_x0000_s1026"><span style="font-family: inherit;">O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.</span></div><div class="MsoNormalCxSpMiddle" style="line-height: normal; margin: auto auto 0pt; mso-add-space: auto;"><span style="color: #bf9000; font-size: 12pt;"><b>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.</b></span><br />
<div style="color: white;">Resposta: Primeiro, c é inserido como folha A, seguindo o algoritimo 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.</div></div><div class="MsoNormalCxSpMiddle" style="line-height: normal; margin: auto auto 0pt; mso-add-space: auto;"><br />
</div><div class="MsoNormalCxSpMiddle" style="line-height: normal; margin: auto auto 0pt; mso-add-space: auto;"><span style="color: #bf9000; font-size: 12pt;"><b>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.</b></span><br />
Resposta: Uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".<b><br />
</b></div><div class="MsoNormalCxSpMiddle" style="line-height: normal; margin: auto auto 0pt; mso-add-space: auto;"><span style="color: #bf9000; font-size: 12pt;"><b>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.</b></span><b></b><br />
<span style="font-family: "Times New Roman", "serif"; font-size: 12pt; line-height: 115%;">Resposta: A remoção deve ser dada por uma rotação em torno do nó a ser removido, a fim de torná-lo folha para que então possa ser removido. Em alguns casos, após a remoção são necessárias rotações para ajustar o fator de balanceamento.</span><br />
<br />
<br />
<ol type="1"><li class="MsoNormal" style="line-height: normal; mso-list: l0 level1 lfo1; mso-margin-bottom-alt: auto; mso-margin-top-alt: auto; tab-stops: list 36.0pt;"><span style="font-family: "Times New Roman", "serif"; font-size: 12pt;">Remover X da árvore AVL usando o mesmo algoritmo de remoção de um nó em uma árvore de busca binária. Recursivamente, empilhar cada nó que é visitado a partir do nó raiz até o nó X, incluindo-o;</span></li>
<li class="MsoNormal" style="line-height: normal; mso-list: l0 level1 lfo1; mso-margin-bottom-alt: auto; mso-margin-top-alt: auto; tab-stops: list 36.0pt;"><span style="font-family: "Times New Roman", "serif"; font-size: 12pt;">Verificar se a pilha está vazia </span></li>
<ul type="circle"><li class="MsoNormal" style="line-height: normal; mso-list: l0 level2 lfo1; mso-margin-bottom-alt: auto; mso-margin-top-alt: auto; tab-stops: list 72.0pt;"><span style="font-family: "Times New Roman", "serif"; font-size: 12pt;">Se sim, o algoritmo termina.</span></li>
<li class="MsoNormal" style="line-height: normal; mso-list: l0 level2 lfo1; mso-margin-bottom-alt: auto; mso-margin-top-alt: auto; tab-stops: list 72.0pt;"><span style="font-family: "Times New Roman", "serif"; font-size: 12pt;">Senão, vá para o passo (3).</span></li>
</ul><li class="MsoNormal" style="line-height: normal; mso-list: l0 level1 lfo1; mso-margin-bottom-alt: auto; mso-margin-top-alt: auto; tab-stops: list 36.0pt;"><span style="font-family: "Times New Roman", "serif"; font-size: 12pt;">Desempilhar um nó e verificar se a diferença de altura entre a sub-árvore da esquerda e da direita desse nó é maior que 1. </span></li>
<ul type="circle"><li class="MsoNormal" style="line-height: normal; mso-list: l0 level2 lfo1; mso-margin-bottom-alt: auto; mso-margin-top-alt: auto; tab-stops: list 72.0pt;"><span style="font-family: "Times New Roman", "serif"; font-size: 12pt;">Se sim, você precisará rotacionar os nós. Dependendo do tipo de rotação realizada, o algoritmo pode não terminar aqui. Se ele não terminar, vá para o passo (2).</span></li>
<li class="MsoNormal" style="line-height: normal;"><span style="font-family: "Times New Roman", "serif"; font-size: 12pt;">Senão, vá para o passo (2).</span><span style="font-family: "Calibri", "sans-serif"; font-size: 11pt; line-height: 115%;"> </span></li>
</ul></ol><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGjyH0kzRaH_cQ-xbqcIm4LDEUJzwkmxdJtVd-CmsZ__y0SyWyrdHyAvEfql69VznxbJxPwOJg2vEOvrq9i1eyUG4XmFZ48hz_YVBJFd1ZmfRo9k8_O3Gm-sEvKi7fe4-97xsSMjliyGnT/s1600/exmplo+1.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="139" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgGjyH0kzRaH_cQ-xbqcIm4LDEUJzwkmxdJtVd-CmsZ__y0SyWyrdHyAvEfql69VznxbJxPwOJg2vEOvrq9i1eyUG4XmFZ48hz_YVBJFd1ZmfRo9k8_O3Gm-sEvKi7fe4-97xsSMjliyGnT/s320/exmplo+1.JPG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi33V28-NaK7nQMmgb8po9Atmxc6J5MSnGckvms6TwxH0sw-sestT5WgFulevv-YU_ojSrPwoKYMAvbyQ6oKxs_6TRk3oL5F0ZQapGyCMMZNEtEHnPhWOIqWkBNwAYQGWwq7EJOj6J-PpFJ/s1600/exemplo+2.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="141" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi33V28-NaK7nQMmgb8po9Atmxc6J5MSnGckvms6TwxH0sw-sestT5WgFulevv-YU_ojSrPwoKYMAvbyQ6oKxs_6TRk3oL5F0ZQapGyCMMZNEtEHnPhWOIqWkBNwAYQGWwq7EJOj6J-PpFJ/s320/exemplo+2.JPG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgbjOES7FEi8I2srBwAFVHJjUKiJ9sesL71kbRl7rVv0W3aT7-DXkpQiOUROOApbOKBc9JmcbPnQCDFQnWS4tW230Und-IkOBc2Gx_KjlnAr0LMhDCGM7A3FbcypzTvvart0t0bIlW1V8JL/s1600/exemplo+3.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="99" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgbjOES7FEi8I2srBwAFVHJjUKiJ9sesL71kbRl7rVv0W3aT7-DXkpQiOUROOApbOKBc9JmcbPnQCDFQnWS4tW230Und-IkOBc2Gx_KjlnAr0LMhDCGM7A3FbcypzTvvart0t0bIlW1V8JL/s320/exemplo+3.JPG" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnxTmA8Pi2N2Z947lDUv3YeYm_NLlo-VGeZaGLSoC4ROp-_-Cq1QGrwjuU5JSpyHUIcPr9SrDszOBy2rsoCr73s8-rdp6Q6SZD839TrYCS-RZw19_dRBCpASFbJNgzo_SIRmHgJeKxAq3T/s1600/exemplo+4.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="99" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnxTmA8Pi2N2Z947lDUv3YeYm_NLlo-VGeZaGLSoC4ROp-_-Cq1QGrwjuU5JSpyHUIcPr9SrDszOBy2rsoCr73s8-rdp6Q6SZD839TrYCS-RZw19_dRBCpASFbJNgzo_SIRmHgJeKxAq3T/s320/exemplo+4.JPG" width="320" /> </a></div><div class="MsoNormal">Note que a operação de remoção pode ser realizada em tempo <b><i><span style="font-family: "Calibri", "sans-serif";">O(lg(n))</span></i></b>. Na remoção de um elemento em uma árvore AVL, pode haver a necessidade de realizar mais de duas rotações (o que não acontece na inserção), podendo se estender para uma rotação em cada nível (<b><i><span style="font-family: "Calibri", "sans-serif";">O(log(n))</span></i></b>) no pior caso. A figura a seguir mostra um exemplo deste caso:</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLWTotC88qRJk2h5dAkNaZAWK0abmITzEijTqN9sjSZ1ZxIfxiwXfSIyII56o935XASMLM5fzNJF8zaLw5a_jA3PnAk88ljxUR69-9A0KNFEGUT6SAUXYCjfinbKfo8oGveeS2Yygm5_o3/s1600/exemplo+5.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="146" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhLWTotC88qRJk2h5dAkNaZAWK0abmITzEijTqN9sjSZ1ZxIfxiwXfSIyII56o935XASMLM5fzNJF8zaLw5a_jA3PnAk88ljxUR69-9A0KNFEGUT6SAUXYCjfinbKfo8oGveeS2Yygm5_o3/s320/exemplo+5.JPG" width="320" /></a></div><div class="MsoNormal"><br />
</div></div><div class="MsoNormalCxSpMiddle" style="line-height: normal; margin: auto auto 0pt; mso-add-space: auto;"><span style="color: #bf9000; font-size: 12pt;"><b>5) Através dos conceitos discutidos, dê dois exemplos de inserção em árvores AVL e dois exemplos de remoção em árvores AVL.</b></span><br />
<div style="text-align: left;">Resposta: Exemplo de remoção: Exemplo 1 : Dada a árvore abaixo, retirando o 5 resulta uma arvore desbalanceada no nó 10(b). A partir daí, raciona-se como se estivéssemos inserindo: que nó inserido teria causado esse desequilíbrio? O 30. Aplicando os conhecimentos de inserção em arvore AVL, constata-se que uma rotação simples a esquerda resolve o problema. O resultado esta na AVL(C).</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh5_DPNu_i10i76X8b9ESrmSPpfK7wnSJQMxKsDkFSAX-jRDesnS5V8kYfQRvpvri73j7vgcs6-fV2O9Ljp4yer1TBdxPhW2qKXMzwyKYMaI_Dd7FdjrRwnZUT3kdMbfXSgP6s48Cz1lsU/s1600/exemplo+1+de+remo%25C3%25A7%25C3%25A3o.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="135" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgh5_DPNu_i10i76X8b9ESrmSPpfK7wnSJQMxKsDkFSAX-jRDesnS5V8kYfQRvpvri73j7vgcs6-fV2O9Ljp4yer1TBdxPhW2qKXMzwyKYMaI_Dd7FdjrRwnZUT3kdMbfXSgP6s48Cz1lsU/s320/exemplo+1+de+remo%25C3%25A7%25C3%25A3o.JPG" width="320" /> </a></div><div class="separator" style="clear: both; text-align: center;"></div><div class="MsoNormal">Exemplo 2: Retirando a folha 12 de (a), na figura abaixo, desbalanceia a raiz (b); supondo-se a inserção recente de 8, corrige-se o desequilíbrio mediante uma rotação dupla a esquerda (c).</div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgU25SQoAAx9MNBAzIs7Ep7zIREoY_7KUSbWnUJb7ay-8YOKS6fj2cgevfKTDlNx5giKaizr2Uglpy3YP7zYVy_8_gbvZkt6av567lchAdgMeH6Zr1PI_zW0fzfjfdIn3JZzI97DR3sRd9X/s1600/exemplo+2+de+remo%25C3%25A7%25C3%25A3o.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="135" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgU25SQoAAx9MNBAzIs7Ep7zIREoY_7KUSbWnUJb7ay-8YOKS6fj2cgevfKTDlNx5giKaizr2Uglpy3YP7zYVy_8_gbvZkt6av567lchAdgMeH6Zr1PI_zW0fzfjfdIn3JZzI97DR3sRd9X/s320/exemplo+2+de+remo%25C3%25A7%25C3%25A3o.JPG" width="320" /></a></div><div class="MsoNormal"><br />
Exemplo de inserção:</div>Exemplo 1: Inserção seqüencial ( Chaves de 1 a 7) em arvore AVL em destaque nós P e U dos exemplos que precisam de rotação ( e Y, filho que precisa “Trocar de Pai) em vermelho), nos retângulos arvore antes e após a rotação:<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwe9vnB4W3PcBSQT9s-F-WPK29qmLuqfD9yKq9YuMB_GIHkh0BlJ2nJX09VdlT_DN-szbDl9de_77oKaccOSAnM5hQuiu3g30VeOWSW1slfeQLfXWTwyVfvaqz1m3Wmv6rEn4OtxoMHBqz/s1600/exemplo+1+inser%25C3%25A7%25C3%25A3o.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="167" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjwe9vnB4W3PcBSQT9s-F-WPK29qmLuqfD9yKq9YuMB_GIHkh0BlJ2nJX09VdlT_DN-szbDl9de_77oKaccOSAnM5hQuiu3g30VeOWSW1slfeQLfXWTwyVfvaqz1m3Wmv6rEn4OtxoMHBqz/s400/exemplo+1+inser%25C3%25A7%25C3%25A3o.JPG" width="400" /></a></div><div class="MsoNormal"> </div><div class="MsoNormal"><br />
Exemplo 2:</div><div class="MsoNormal">Inserção das Chaves 80,40,60,50 e 45 (nessa seqüência ):</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhcbZcX-KhiCBhSFzRP2-msAipD-kFFiTnMK7qMMoV5o3KJD1MC3EkQR-3oUwOST-biEiNx8UN2CrSlhhC71rZpRoPtDPoovlKZcFLPdNXXS9N5oUhtdMB2m-aLY1m9BhdLMiRzNPAXLJqp/s1600/exemplo+2+de+inser%25C3%25A7%25C3%25A3o.JPG" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="285" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhcbZcX-KhiCBhSFzRP2-msAipD-kFFiTnMK7qMMoV5o3KJD1MC3EkQR-3oUwOST-biEiNx8UN2CrSlhhC71rZpRoPtDPoovlKZcFLPdNXXS9N5oUhtdMB2m-aLY1m9BhdLMiRzNPAXLJqp/s400/exemplo+2+de+inser%25C3%25A7%25C3%25A3o.JPG" width="400" /></a></div><div class="MsoNormal"><br />
</div></div><div class="MsoNormalCxSpMiddle" style="line-height: normal; margin: auto auto 0pt;"><br />
<div class="MsoNormal"><br />
</div></div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com0tag:blogger.com,1999:blog-7529573060120354615.post-9412208894606784202011-08-28T11:01:00.006-03:002011-10-25T22:52:07.733-02:00QUESTIONÁRIO 03 - ÁRVORE BINÁRIA DE BUSCA<div class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: left; text-indent: -18pt;"><div class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: left; text-indent: -18pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-fareast-font-family: "Times New Roman";"><span style="mso-list: Ignore;">1)<span style="font-family: "Times New Roman";"> </span></span></span></b><b style="mso-bidi-font-weight: normal;">Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.<span style="mso-spacerun: yes;"> </span>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,<span style="mso-spacerun: yes;"> </span>30, 40 e 13 numa árvore binária de busca. </b></span><br />
<span style="color: #cccccc;">Resposta: Primeiramente, ordenar os números em ordem crescente:</span><br />
<div style="text-align: center;"><span style="color: #cccccc;">10, 13, 15, 18, 20, 30, 40.</span></div><div style="text-align: left;"><span style="color: #cccccc;"> Após a ordenação dos números, identifica-se que a raiz será o número 18, pois se encontra no meio do intervalo de números acima;</span></div><div style="text-align: left;"><span style="color: #cccccc;"> Em seguida, colocar todos os números menores que 18 na subárvores da esquerda e maiores que 18 na subárvores da direita.</span></div><div style="text-align: left;"><span style="color: #cccccc;"> Veja como ficou inseridos os elementos na figura da árvore abaixo.</span></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaAWmNHcEEzpxl6eHqTHd2HZ6LP9x3CdNnlIgxzEuIcmDigtbKqI4c7QnA-_KL5mHdZ1Js7pdcRF1L9lELtwo0w50j45inrgVyciist7YodAQdLu8_PgbgtFt33zTweBokj4vtrKNWWL7O/s1600/Imagem1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="110" nba="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaAWmNHcEEzpxl6eHqTHd2HZ6LP9x3CdNnlIgxzEuIcmDigtbKqI4c7QnA-_KL5mHdZ1Js7pdcRF1L9lELtwo0w50j45inrgVyciist7YodAQdLu8_PgbgtFt33zTweBokj4vtrKNWWL7O/s320/Imagem1.png" width="320" /></a></div></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 18pt; text-align: left;"><br />
</div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: left; text-indent: -18pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-fareast-font-family: "Times New Roman";"><span style="mso-list: Ignore;">2)<span style="font-family: "Times New Roman";"> </span></span></span></b><b style="mso-bidi-font-weight: normal;">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?</b></span><br />
<span style="color: #cccccc;">Resposta: Inserção quando adciona-se um elemento na árvore na posição correta para que a propriedade fundamental seja mantida. Para inserirmos um valor x em uma árvore usamos sua estrutura recursiva, e a ordenação especifica na propriedade fundamental.</span><br />
<span style="color: #cccccc;">Remoçao quando se permite retirar um determinado elemento da árvore. Primeiro quando se deseja retirar um elemento da folha de árvore, basta retirar o elemento da árvore e atualizar o pai, pois seu filho não existe mais. Segundo passo quando o nó a ser retirado possui um único filho, para retirar esse elemento é necessário antes acertar o ponteiro do pai, pulando o nó, o único neto passa a ser o filho direto.</span><br />
<span style="color: #cccccc;">Construção as operações de inserção devem ser efetuadas conforme a ordem das chaves o 1º passo é inserir as chaves que ficaram mais proximas da raiz, se caso tivermos um conjunto de chaves deve se inserir o valor médio das chaves, inserindo as chaves inferior e as superiores a esse valor.</span></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt; text-align: left;"><br />
</div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: left; text-indent: -18pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-fareast-font-family: "Times New Roman";"><span style="mso-list: Ignore;">3)<span style="font-family: "Times New Roman";"> </span></span></span></b><b style="mso-bidi-font-weight: normal;">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,<span style="mso-spacerun: yes;"> </span>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.<span style="mso-spacerun: yes;"> </span>Portanto no conjunto de chaves K={1,2,3,4,5,6,7}.<span style="mso-spacerun: yes;"> </span>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}.</b></span><br />
<span style="color: #cccccc;">Resposta:<strong> </strong> <span style="font-family: "Bookman Old Style"; mso-ascii-font-family: "Bookman Old Style"; mso-hansi-font-family: "Bookman Old Style";">Se temos um conjunto de chaves {c1,. . . c} tal que c1 < ... < c, 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. </span></span><br />
<span style="font-family: "Bookman Old Style"; mso-ascii-font-family: "Bookman Old Style"; mso-hansi-font-family: "Bookman Old Style";"><span style="color: #cccccc;">Então, pela inserção <span style="font-family: Times New Roman;">K={2,4,6,8,10,12,14}, o número 8 é a raiz pois se encontra no meio desse intervalo de números. Veja na figura abaixo a inserção otimal do intervalo de números acima:</span></span></span><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgL_r0WlSqpaK4BJSjZYDYW_l3vINugGWOeD53ayIIe3pcbiEmSJZK5pnJGZGxJlTyOXbjtip-Da0XB5TojyYFQjV3VYx2oDauoZTfHagXeLPZGCFEkQK5mKJKw16GchY89LDvaWxliUKVv/s1600/Imagem2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" nba="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgL_r0WlSqpaK4BJSjZYDYW_l3vINugGWOeD53ayIIe3pcbiEmSJZK5pnJGZGxJlTyOXbjtip-Da0XB5TojyYFQjV3VYx2oDauoZTfHagXeLPZGCFEkQK5mKJKw16GchY89LDvaWxliUKVv/s1600/Imagem2.png" /></a></div></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt; text-align: left;"><br />
</div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: left; text-indent: -18pt;"><span style="color: #bf9000;"><b style="mso-bidi-font-weight: normal;"><span style="mso-fareast-font-family: "Times New Roman";"><span style="mso-list: Ignore;">4) </span></span></b><b style="mso-bidi-font-weight: normal;">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/<personname productid="em ordem. Explique" w:st="on">em ordem. Explique</personname> como funciona o procedimento para realizar cada percurso considerando as subárvores. Existe alguma diferença com relação às árvores binárias comuns?</b></span><br />
<div align="center" style="tab-stops: list 45.0pt; text-align: center; text-indent: -18pt;"><strong><span style="color: orange;">Percurso de uma árvore binária em <u>pré-fixado / pré-ordem</u></span></strong> </div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">Percorrer uma árvore binária em pré-ordem:</span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;"> 1.Visitar a raiz.</span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;"> 2. Percorrer a sua subárvore esquerda em pré-ordem.</span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;"> 3. Percorrer a sua subárvore direita em pré-ordem.</span></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjisD8WdSGV9MSM091xYnsP69gVXnDJtaLiu1B-xbRRGOtuu00wDF21RRgcKa1WNi0tU_lD7okXo1FhVt9f2DCUNFS2k1HPX41U3PwzuDjN3Um74aaLe1UzSAqB28dfU3KSIjQdu27z3zEX/s1600/Imagem3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" nba="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjisD8WdSGV9MSM091xYnsP69gVXnDJtaLiu1B-xbRRGOtuu00wDF21RRgcKa1WNi0tU_lD7okXo1FhVt9f2DCUNFS2k1HPX41U3PwzuDjN3Um74aaLe1UzSAqB28dfU3KSIjQdu27z3zEX/s1600/Imagem3.png" /></a></div><div align="left" class="separator" style="clear: both; text-align: center;"></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-align: justify; text-indent: -18pt;"><span style="font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;"><span style="color: #cccccc;">O percurso em pré-ordem segue os nós até chegar os mais “profundos”, em “ramos” de subárvores da esquerda para a direita. É conhecida usualmente pelo nome de percurso em</span> <span style="color: orange;">profundidade</span><span style="color: red;"> </span><span style="color: white;">(</span></span><span style="color: orange; font-family: NimbusSanL-ReguItal; mso-bidi-font-family: NimbusSanL-ReguItal;">depth-first</span><span style="color: white; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">).</span></div><div style="tab-stops: list 45.0pt; text-indent: -18pt;"><br />
</div><div align="center" style="tab-stops: list 45.0pt; text-align: center; text-indent: -18pt;"><strong><span style="color: orange; font-family: NimbusSanL-Regu;">Percurso de uma árvore binária em <u>pós-fixado / pós-ordem</u></span></strong><span style="font-family: NimbusSanL-Regu;"></span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><br />
</div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">Percorrer uma árvore binária em pós-ordem:</span><span style="font-family: NimbusSanL-Regu;"></span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">1. Percorrer a sua subárvore esquerda em pós-ordem.</span><span style="font-family: NimbusSanL-Regu;"></span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">2. Percorrer a sua subárvore direita em pós-ordem.</span><span style="font-family: NimbusSanL-Regu;"></span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">3. Visitar a raiz.</span><span style="font-family: NimbusSanL-Regu;"></span></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgskdrIG84DAO7dXpeOAiezadQXnwUbekXIGG8FtorZzBglShUbx88G7bKa28JfDQHvd29fD5cMcG1aqP2ljTQBlWdQahGeEuR1zD5NaJvO3oF5tLXEsulTUHmgJKgo0EXgofwPl7lb51Sm/s1600/Imagem4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" nba="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgskdrIG84DAO7dXpeOAiezadQXnwUbekXIGG8FtorZzBglShUbx88G7bKa28JfDQHvd29fD5cMcG1aqP2ljTQBlWdQahGeEuR1zD5NaJvO3oF5tLXEsulTUHmgJKgo0EXgofwPl7lb51Sm/s1600/Imagem4.png" /></a></div><div class="separator" style="margin: 0cm 0cm 0pt; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu;">Outro Exemplo:</span></div><div class="separator" style="margin: 0cm 0cm 0pt; tab-stops: list 45.0pt; text-indent: -18pt;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIAQwCwoyjFx3BYrSchHSBL9o9VJE8wmsDFlG6Nl1QpZtYQ_tA-qdVrK4T4PVrlB3Jc7KTjtfbqVr4c9og7D3cXZRpFkOalN_IVVq9MbobxBVIlcXT5QOjnrdpqD5IUHJF9tmXhmgAOJSM/s1600/Imagem5.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" nba="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjIAQwCwoyjFx3BYrSchHSBL9o9VJE8wmsDFlG6Nl1QpZtYQ_tA-qdVrK4T4PVrlB3Jc7KTjtfbqVr4c9og7D3cXZRpFkOalN_IVVq9MbobxBVIlcXT5QOjnrdpqD5IUHJF9tmXhmgAOJSM/s1600/Imagem5.png" /></a></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">A representação de uma expressão aritmética com o operador no final dos operando é conhecida pelo nome de notação reversa ou polonesa.</span><span style="font-family: NimbusSanL-Regu;"></span></div><div align="center" style="tab-stops: list 45.0pt; text-align: center; text-indent: -18pt;"><br />
</div><div align="center" style="tab-stops: list 45.0pt; text-align: center; text-indent: -18pt;"><strong><span style="color: orange; font-family: NimbusSanL-Regu;">Percurso de uma árvore binária em <u>in-ordem / em ordem</u></span></strong><span style="font-family: NimbusSanL-Regu;"></span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">Percorrer uma árvore binária em in-ordem:</span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">1. Percorrer a sua subárvore esquerda em in-ordem.</span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">2. Visitar a raiz.</span></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">3. Percorrer a sua subárvore direita em in-ordem.</span></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiG03IvLwwyvgXDViT0gYNDgv4uG2q_bM5LcKQn64EqfBGZ2kJceP9uNdV3ox5H_uxRu5Vo7xrOPzI4CSfsigHBQ86DVo6GzaQ4JzVMEodbmMDIiFCT4WNeugIU0ELYAw3e3bxmwr5V_MaS/s1600/Imagem6.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" nba="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiG03IvLwwyvgXDViT0gYNDgv4uG2q_bM5LcKQn64EqfBGZ2kJceP9uNdV3ox5H_uxRu5Vo7xrOPzI4CSfsigHBQ86DVo6GzaQ4JzVMEodbmMDIiFCT4WNeugIU0ELYAw3e3bxmwr5V_MaS/s1600/Imagem6.png" /></a></div><div style="mso-layout-grid-align: none; tab-stops: list 45.0pt; text-indent: -18pt;"><span style="color: #cccccc; font-family: NimbusSanL-Regu; mso-bidi-font-family: NimbusSanL-Regu;">A in-ordem visita a raiz entre as ações de percorrer as duas subárvores. É conhecida também pelo nome de ordem simétrica.</span></div><div style="mso-layout-grid-align: none;"><span style="color: #cccccc;"><br />
</span></div></div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: justify; text-indent: -18pt;"><br />
</div><div class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: center; text-indent: -18pt;"><br />
<div style="text-align: left;"></div></div></div><div align="left" class="MsoNormal" style="margin: 0cm 0cm 0pt 45pt; mso-list: l0 level1 lfo1; tab-stops: list 45.0pt; text-align: center; text-indent: -18pt;"></div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com1tag:blogger.com,1999:blog-7529573060120354615.post-79631180179734980912011-08-25T00:03:00.001-03:002011-10-25T22:46:42.169-02:00QUESTIONÁRIO 02 – ÁRVORES BINÁRIAS<div class="entry-content"><strong><span style="color: #bf9000;">1) Uma árvore é um conjunto de 1 ou mais nós, onde existe um nó especial chamado raiz e os demais nós formam conjuntos disjuntos onde cada conjunto é uma árvore (subárvore). O que caracterizaria então uma árvore Binária?</span></strong><br />
Resposta: Uma árvore binaria deve conter no máximo 2 filhos(nós), e nela possuem grau zero ou um.<br />
<br />
<strong><span style="color: #bf9000;">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?</span></strong><br />
Resposta: Sim, isso acontece através da Formula: 2n – 1 = Numero máximo de elementos de uma árvore binária.<br />
<br />
<strong><span style="color: #bf9000;">3) Nas árvores binárias podemos percorrer os elementos através de alguns percursos, quais são eles?</span></strong><br />
Resposta: IN-Ordem, PRÉ-Ordem, PÓS-Ordem.<br />
<br />
<strong><span style="color: #bf9000;">4) A definição do percurso EM-Ordem/IN-Ordem é: </span></strong><br />
Resposta: A raiz fica no meio das sub-arvores esquerda e direita.<br />
<br />
<strong><span style="color: #bf9000;">5) A definição do percurso PRÉ-Ordem/PRÉ-Fixado é:</span></strong><br />
Resposta: A raiz vem antes das sub-arvores esquerda e direita.<br />
<br />
<strong><span style="color: #bf9000;">6) A definição do percurso PÓS-Ordem/PÓS-Fixado é:</span></strong><br />
Resposta: A raiz vem depois das sub-arvores esquerda e direita.<br />
<br />
<strong><span style="color: #bf9000;">7) Existe outra maneira de percorrer uma árvore (não obrigatoriamente binária), conhecida como percurso por extensão ou largura. Explique esse processo.</span></strong><br />
<span style="font-size: small;">Resposta: Percurso por Extensão ou Largura: Os nós são visitados na ordem dos níveis da </span><span style="font-size: small;">árvore, isto é: </span><span style="font-size: small;">primeiramente são visitados os nós do nível </span><span style="font-size: small;">0, depois do nível 1, depois do nível 2 e</span><span style="font-size: small;">assim por diante; </span><span style="font-size: small;">os nós são visitados da esquerda para a </span><span style="font-size: small;">direita em cada um dos níveis.</span><br />
<div align="left"></div><div align="left"></div><table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIo0_tp86NAcbTc9KyykO0Bo85MYi8FiagCHAg_wFngzExfAem0tiy0SLVUJ1uecjYscAckZaOINw787amfyeXrXybJLwRt7H_WM84OEMnkwRMn_Y9A_mIiaixdTZmG3n1zvhDeZCGlkPY/s1600/Imagem1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="234" qaa="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhIo0_tp86NAcbTc9KyykO0Bo85MYi8FiagCHAg_wFngzExfAem0tiy0SLVUJ1uecjYscAckZaOINw787amfyeXrXybJLwRt7H_WM84OEMnkwRMn_Y9A_mIiaixdTZmG3n1zvhDeZCGlkPY/s320/Imagem1.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-family: NimbusSanL-Regu; font-size: large;"><span style="font-family: NimbusSanL-Regu; font-size: small;">Ordem de Processamento: A B E C F G D H</span></span></td></tr>
</tbody></table><br />
<div style="text-align: center;"><strong><u><span style="color: #bf9000;">Exercício do Slide</span></u></strong></div><div style="text-align: left;"><strong><span style="color: #bf9000;"><span style="font-family: "Franklin Gothic Book"; mso-ascii-font-family: "Franklin Gothic Book"; mso-hansi-font-family: "Franklin Gothic Book";">Faça o percurso em pré-ordem, in-ordem e pós-ordem da </span><span style="font-family: "Franklin Gothic Book"; font-size: 28pt; mso-ascii-font-family: "Franklin Gothic Book"; mso-hansi-font-family: "Franklin Gothic Book";"><span style="font-size: small;">seguinte árvore.</span> </span></span></strong></div><div style="text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnqnqTmX0RCeecQTnv90CbF0NlR6rPbKFj0sarJ0dj0bc6VWvzEOoxwv3MHrXW-yLrOk5XoGg7N4axulp0cFpS3Bywgo25Diq3Za47cMIUJ46abeCrxVuA6pjSS_rH_cvbfpMsDqe_5jV3/s1600/Imagem1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="241" qaa="true" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgnqnqTmX0RCeecQTnv90CbF0NlR6rPbKFj0sarJ0dj0bc6VWvzEOoxwv3MHrXW-yLrOk5XoGg7N4axulp0cFpS3Bywgo25Diq3Za47cMIUJ46abeCrxVuA6pjSS_rH_cvbfpMsDqe_5jV3/s320/Imagem1.png" width="320" /></a></div><div style="text-align: left;"><br />
</div><div style="mso-char-wrap: 1; mso-kinsoku-overflow: 1; mso-line-spacing: "100 50 0";"></div><div style="text-align: left;"><br />
<div class="O" v:shape="_x0000_s1026"><div style="mso-char-wrap: 1; mso-kinsoku-overflow: 1; text-align: justify;"><nobr><span style="font-family: "Franklin Gothic Book"; mso-ascii-font-family: "Franklin Gothic Book"; mso-hansi-font-family: "Franklin Gothic Book";"><span style="color: yellow;"><strong>PRÉ-ORDEM (RED) –</strong></span> A B D G C E H I F<span style="mso-spacerun: yes;"> </span></span></nobr></div><div style="mso-char-wrap: 1; mso-kinsoku-overflow: 1; text-align: justify;"><nobr><span style="font-family: "Franklin Gothic Book"; mso-ascii-font-family: "Franklin Gothic Book"; mso-hansi-font-family: "Franklin Gothic Book";"></span></nobr></div><div style="mso-char-wrap: 1; mso-kinsoku-overflow: 1; text-align: justify;"><nobr><span style="font-family: "Franklin Gothic Book"; mso-ascii-font-family: "Franklin Gothic Book"; mso-hansi-font-family: "Franklin Gothic Book";"><strong><span style="color: yellow;">IN/EM-ORDEM (ERD) –</span></strong> D G B A H E I C F </span></nobr></div><div style="mso-char-wrap: 1; mso-kinsoku-overflow: 1; text-align: justify;"><nobr><span style="font-family: "Franklin Gothic Book"; mso-ascii-font-family: "Franklin Gothic Book"; mso-hansi-font-family: "Franklin Gothic Book";"></span></nobr></div><div style="mso-char-wrap: 1; mso-kinsoku-overflow: 1; text-align: justify;"><nobr><span style="font-family: "Franklin Gothic Book"; mso-ascii-font-family: "Franklin Gothic Book"; mso-hansi-font-family: "Franklin Gothic Book";"><span style="color: yellow;"><strong>PÓS-ORDEM (EDR) –</strong></span> G D B H I E F C A </span></nobr></div><div style="mso-char-wrap: 1; mso-kinsoku-overflow: 1; mso-line-spacing: "100 50 0";"></div></div><br />
</div><div align="left"></div><div align="left"><br />
</div></div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com0tag:blogger.com,1999:blog-7529573060120354615.post-91557493041253929822011-08-24T23:51:00.001-03:002011-10-25T22:44:37.878-02:00QUESTIONÁRIO 01 – ÁRVORES, CONCEITOS GERAIS<div class="entry-content" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><strong><span style="color: #bf9000;">1) A estrutura de uma árvore é especializada em representar hierarquia. Defina e caracterize de forma completa o conceito da Estrutura Árvore.</span></strong></div><div class="entry-content" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">Uma árvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:</div><div class="entry-content" style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><ol><li>uma estrutura (uma árvore);</li>
<li>um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).</li>
<li>Não Existe árvores vazias, no minímo haverá um nó raiz(que não possui pai)</li>
</ol></div>Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são habitualmente chamados de <em>filhos</em> desses nós. Os nós sem filhos de uma árvore são chamados de folhas.<br />
<br />
<strong><span style="color: #bf9000;">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).</span></strong><br />
<strong><span style="color: yellow;">Hierarquia de classes:</span></strong> São as classes e subclasses, ou seja, uma classe subordinando a outra;<br />
<strong><span style="color: yellow;">Ordenação de Valores:</span></strong> São as Árvore ordenada na esquerda, na raiz, e na direita;<br />
<strong><span style="color: yellow;">Organogramas de empresas:</span> </strong>É a<strong> </strong> hierarquia entre os empregados de uma empresa.<br />
<br />
<strong><span style="color: #bf9000;">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.</span></strong><br />
Os conceitos básicos da estrutura árvore são:<br />
<div style="text-align: center;"><a href="http://kolw.blog.com/files/2011/08/1.jpg"><img alt="" class="size-thumbnail wp-image-9 aligncenter" height="170" src="http://kolw.blog.com/files/2011/08/1-e1313344216758-150x114.jpg" width="244" /></a></div><ul><li><span style="color: yellow;"><strong>Raiz</strong> –</span> é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8);</li>
<li><span style="color: yellow;"><strong>Nós</strong> –</span> são todos os itens guardados na árvore;</li>
<li><strong><span style="color: yellow;">Nós Filhos</span></strong> – são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3);</li>
<li><span style="color: yellow;"><strong>Nós Pais</strong> –</span> são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14);</li>
<li><span style="color: yellow;"><strong>Folhas ou nó terminal</strong> –</span> são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13);</li>
<li><strong><span style="color: yellow;">Nó Ascendente-</span></strong> Nó acima de um dado nó, em direção a raiz (No caso da figura acima, o nó 8 é ancestral do nó 3, 10 ,1, 6 …, 13);</li>
<li>Nó Descendente- Nó abaixo de um dado nó (No caso da figura acima, o nó 3 e 10 é ascendente de 8);</li>
<li><strong><span style="color: yellow;">Grau de um nó</span> </strong>é o número de nós filhos do mesmo. Obviamente um nó folha tem grau zero;</li>
<li><strong><span style="color: yellow;">Nível de um nó</span> </strong>é o número de nós existentes no caminho entre a raiz e o próprio nó;</li>
<li><strong><span style="color: yellow;">Altura de uma árvore</span> </strong>(também denominada <strong>profundidade</strong>) é a distância entre x e o seu descendente mais afastado. Mais precisamente, a altura de x é o número de passos do mais longo caminho que leva de x até uma folha somando um;</li>
<li><strong><span style="color: yellow;">caminho</span> </strong>da árvore é composto por uma seqüência de nós consecutivos (<em>n<sub><span style="font-size: xx-small;">1</span></sub>, n<sub><span style="font-size: xx-small;">2</span></sub>, …, n<sub><span style="font-size: xx-small;">k-1</span></sub>, n<sub><span style="font-size: xx-small;">k</span></sub></em>) tal que existe sempre a relação n<sub><span style="font-size: xx-small;">i</span></sub> é pai de <em>n<sub><span style="font-size: xx-small;">i+1;</span></sub></em></li>
<li><span style="color: yellow;"><strong>Floresta</strong>:</span> é um conjunto de zero ou mais árvores disjuntas, ou seja, se for eliminado o nó raiz da árvore, as sub-árvores que restarem chama-se de florestas.</li>
</ul><strong><span style="color: #bf9000;">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.</span></strong><br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://kolw.blog.com/files/2011/08/Apresentação1.jpg" style="margin-left: auto; margin-right: auto;"><img alt="" class="size-medium wp-image-10 " height="237" src="http://kolw.blog.com/files/2011/08/Apresentação1-e1313373347325.jpg" width="244" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Representação hierárquica</td></tr>
</tbody></table> <br />
<div class="mceTemp mceIEcenter"><div class="mceTemp mceIEcenter"> <br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://kolw.blog.com/files/2011/08/Apresentação11-e1313374303428.jpg" style="margin-left: auto; margin-right: auto;"><img alt="" class="size-medium wp-image-11" height="210" src="http://kolw.blog.com/files/2011/08/Apresentação11-e1313374303428-300x210.jpg" width="300" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Representação por conjuntos (diagrama de inclusão)</td></tr>
</tbody></table></div></div><div align="center"><br />
</div> <span style="color: yellow;"> <strong>Representação por expressão parentetizada (parênteses aninhados)</strong></span><br />
Cada conjunto de parênteses correspondentes contém um nodo e seus filhos.<br />
Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.<br />
<div align="center"><a href="http://kolw.blog.com/files/2011/08/Apresentação12.jpg"><img alt="" class="aligncenter size-medium wp-image-12" height="52" src="http://kolw.blog.com/files/2011/08/Apresentação12-e1313373958366-300x52.jpg" width="300" /></a></div> <strong><span style="color: yellow;">Representação por expressão não parentetizada </span></strong><br />
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.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="http://kolw.blog.com/files/2011/08/Apresentação13-e1313374537448.jpg" style="margin-left: 1em; margin-right: 1em;"><img alt="" class="aligncenter size-medium wp-image-13" height="43" src="http://kolw.blog.com/files/2011/08/Apresentação13-e1313374537448-300x43.jpg" width="300" /></a></div><div class="mceTemp mceIEcenter"></div><div align="center"><br />
</div>Katiúcia, Limberg, Otoniel e William.http://www.blogger.com/profile/15473700342947940240noreply@blogger.com0