·
Ciência da Computação ·
Estrutura de Dados
Send your question to AI and receive an answer instantly
Preview text
CURSO DE CIÊNCIA DA COMPUTAÇÃO Estrutura de Dados II CC6M Profº Msc Gustavo N Rocha LISTA DE EXERCÍCIOS ÁRVORES ENTREGA ATÉ 12052024 VIA BLOG INDIVIDUAL VALOR 2 PONTOS 1 Utilizando os conceitos de grafos defina uma arvore 2 Escreva uma func ao que conta o numero de nos de uma arvore binaria 3 Escreva uma func ao que conta o numero de nos naofolha de uma arvore binaria 4 Escreva uma func ao que conta o numero de folhas de uma arvore binaria 5 Escreva uma func ao que calcula a altura de uma arvore binaria 6 Escreva uma func ao para buscar um numero impar em uma arvore binaria N AO orde nada 7 Escreva uma func ao para achar o MAIOR numero em uma arvore binaria N AO ordenada 8 Escreva uma func ao que exclui todos os nos de uma arvore binaria N AO ordenada com ID par 9 Escreva uma func ao que exclui todos os nos de uma arvore binaria de busca com ID par 10 Escreva uma func ao que retorna verdadeiro se uma arvore e binaria de busca e falso caso contrario 11 Escreva uma func ao que encontra o valor maximo em uma arvore de busca binaria 12 Escreva uma func ao que obtem o espelho de uma arvore ou seja troca a subarvore direita pela subarvore esquerda de todos os nos da arvore 13 Duas ABBs sao SIMILARES se possuem a mesma distribuic ao de nos independente dos valores nos mesmos Em uma definic ao mais formal duas ABBs sao SIMILARES se sao ambas vazia ou se suas subarvores esquerdas sao similares e suas subarvores direitas tambem sao similares Implemente a func ao que verifica se duas arvores sao similares 14 Duas ABBs sao IGUAIS se sao ambas vazias ou entao se armazenam valores iguais em suas raizes suas subarvores esquerdas sao iguais e suas subarvores direitas sao iguais Implemente a func ao que verifica se duas arvores sao simlares 1 15 Uma ABB e estritamente binaria se todos os nos da arvore tem 2 filhos Implemente uma func ao que verifica se uma ABB e estritamente binaria 16 Implemente uma func ao para testar se uma arvore binaria e uma ABB 17 Pense na implementac ao nao recursiva dos algoritmos de inserc ao remoc ao e busca em uma ABB 18 Dada uma ABB inicialmente vazia insira E DESENHE os seguintes elementos nessa ordem M F S D J P U A E H Q T W K 19 Dada uma ABB inicialmente vazia insira E DESENHE os seguintes elementos nessa ordem A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 20 Descreva a ordem de visita para um percurso em preordem emordem e posordem na arvore abaixo 21 Qual a diferenca de uma ABB para uma AVL 22 O que difere na implementac ao da func ao de busca de uma ABB e de uma AVL 23 Obtenha a equac ao que relaciona a altura de uma arvore binaria completa com o seu numero de vertices 24 Escreva func oes nao recursivas para realizar os 3 tipos de percurso na arvore binaria dica use uma pilha a preordem b emordem c posordem 25 Escreva uma func ao naorecursiva que retorne o menor valor de uma arvore binaria nao ordenada 26 Escreva uma func ao naorecursiva que retorne o menor valor de uma arvore binaria de busca 27 Escreva uma func ao naorecursiva que retorne o kesimo menor valor de uma arvore binaria de busca 28 Escreva uma func ao que retorne o elemento menor ou igual floor que um de referˆencia x em uma ABB 2 29 Escreva uma func ao naorecursiva que verifique a existˆencia de um valor X na arvore binaria 30 Escreva uma func ao naorecursiva que verifique a existˆencia de um valor negativo na arvore binaria 31 Escreva uma func ao naorecursiva que verifique se uma arvore binaria e tambem de busca 32 Mostre passo a passo a arvore binaria resultante das seguintes operac oes a Inserc ao de 7 8 3 4 2 1 6 5 b Mostre o percurso em preordem emordem e posordem c Remoc ao de 7 e 6 33 Escreva e implemente um algoritmo nao recursivo para obter a altura de uma ABB 34 Escreva e implemente um algoritmo que dada uma ABB construa uma outra arvore ABB aproximadamente completa Para isso obtenha todas as chaves e valores e insira na nova arvore sempre o elemento mediano das chaves ainda nao inseridas 35 Faca uma func ao que retorne a quantidade de folhas de uma arvore binaria de busca 36 Faca uma func ao que retorne a quantidade de nos de uma arvore binaria de busca que possuem apenas um filho 37 Faca uma func ao que dada uma arvore binaria de busca retorne a quantidade de nos que guardam numeros primos 38 Faca uma func ao que compare se duas arvores binarias de busca sao iguais 39 Faca uma func ao que retorna a lista de caminhos da raiz ate cada folha 40 Escreva uma func ao que faca o percurso em nıvel em uma arvore binaria O percurso em nıvel ou em largura em uma arvore e um percurso que visita em ordem crescente todos os nos de um nıvel antes de continuar a visita no nıvel seguinte Uma das formas de implementar e utilizar uma fila FIFO para guardar quais serao os proximos nodes a serem visitados 41 Considere a arvore rubronegra caida para a esquerda cujo percurso em nıvel em lar gura e 67 51 87 23 53 82 90 17 31 52 60 16 21 Liste as chaves em nos rubros em ordem crescente 42 Defina com suas palavras o que e uma arvore AVL e como ela funciona 43 Explique as vantagens e desvantagens de usar arvores binarias balanceadas 44 Desenhe a arvore AVL resultante da inserc ao dos seguintes nos 35 39 51 20 13 28 22 32 25 33 nesta ordem 45 Qual a diferenca de uma arvore binaria de busca para uma AVL 46 Uma arvore binaria de busca e estritamente binaria se todos os nos da arvore tem 2 fi lhos Implemente uma func ao que verifica se uma arvore binaria de busca e estritamente binaria 47 Escreva um programa para copiar uma arvore binaria 3 48 Faca um esquema grafico que represente a estrutura final de uma arvore AVL gerada pela inserc ao dos numeros 13 7 31 43 8 17 5 3 1 23 16 e 36 nesta ordem 49 Modifique a implementac ao da arvore de busca binaria para que ela lide corretamente com chaves duplicadas Isto e se uma chave ja esta na arvore a nova deversubstituir a antiga 50 Exiba as arvores binarias com alturas de 2 3 4 5 e 6 que contenham as sete chaves 1 4 5 10 16 17 e 21 Eemplo com altura de 2 10 4 17 1 5 16 21 51 Considere a arvore mostrada na figura abaixo e responda a Quais sao os nos folhas b Quais nos sao ancestrais de C c Quais sao os descendentes de C d Qual e a altura da arvore e Quais sao os nos com grau 1 e 2 f Quantos caminhos de comprimento trˆes existem 52 Crie uma arvore binaria de busca adicionando um a um e nesta ordem os seguintes numeros 5 6 3 8 7 4 1 e 2 53 Quantas arvores de busca binaria com nos 1 2 3 e 4 existem 54 Considere uma arvore de busca binaria tendo como nos os numeros de 1 ate 1000 Nos procuramos um no marcado com 363 Qual das seguintes sequˆencias nao podem ser os valores dos nodos visitados na busca por 363 a 2 252 401 398 330 344 397 363 b 924 220 911 244 898 258 362 363 c 925 202 911 240 912 245 363 d 2 399 387 219 266 382 381 278 363 e 935 278 347 621 299 392 358 363 4 55 Dˆe um pequeno exemplo de como adicionar um numero a uma arvore AVL causando uma arvore desbalanceada do tipo direita direita Rebalancear a arvore 56 Dˆe um pequeno exemplo de como adicionar um numero a uma arvore AVL causando uma arvore desbalanceada do tipo direitaesquerda Rebalancear a arvore 57 Dˆe um pequeno exemplo de remoc ao de um numero de um arvore AVL causando uma arvore desbalanceada do tipo direitadireita Rebalancear a arvore 58 Projete um algoritmo para determinar o menor numero em uma arvore AVL 59 Escreva uma func ao que receba um nıvel da arvore e imprima todos os nos nesse nıvel 60 Escreva a func ao que retorna o numero de nos que sao divisores da soma de seus filhos Leve em conta apenas os nos com dois filhos 61 Dada uma arvore binaria e dois nos dela desenvolva um algoritmo para achar o ancestral comum mais baixo dos dois nos dados O ancestral comum e um no que possua os outros dois nos em suas subarvores O ancestral comum mais baixo e o ancestral comum que tem a maior profundidade 62 Em uma arvore binaria faca um algoritmo para alterar o valor de cada no exceto no folha para a soma dos valores dos nos esquerda e direita 63 Remova da seguinte arvore AVL o no 8 e em seguida adicione um no com valor 9 64 Faca um algoritmo que crie uma lista ligada com os nos de uma arvore binaria em um percurso emordem 65 Faca um algoritmo para somar os nos presentes nos nıveis impares de uma arvore binaria 66 Implementar uma func ao naorecursiva para calcular o tamanho de uma arvore binaria 67 Implementar uma func ao naorecursiva para cada um dos percursos abaixo a emordem b posordem c preordem 68 Monte uma arvore capaz de armazenar uma struct contendo as seguintes informac oes nome do municıpio area total do municıpio em km2 e populac ao A arvore devera ter func oes para inserir pelo nome percorrer e listar Implemente tambem func oes para 5 a Contar o numero de municıpios percorrendo os nos cadastrados na arvore b Mostrar apenas os nomes dos municıpios com mais de X habitantes Por exemplo X pode ser 100000 pessoas c Mostrar a densidade demografica de cada cidade A densidade demografica e a relac ao entre a populac ao e a area d Mostrar o somatorio de area em km2 de todas as cidades juntas em relac ao ao territorio nacional em porcentagem e Mostrar as cidades em ordem alfabetica com todos os dados f Mostrar o nome da cidade com a maior populac ao 6
Send your question to AI and receive an answer instantly
Preview text
CURSO DE CIÊNCIA DA COMPUTAÇÃO Estrutura de Dados II CC6M Profº Msc Gustavo N Rocha LISTA DE EXERCÍCIOS ÁRVORES ENTREGA ATÉ 12052024 VIA BLOG INDIVIDUAL VALOR 2 PONTOS 1 Utilizando os conceitos de grafos defina uma arvore 2 Escreva uma func ao que conta o numero de nos de uma arvore binaria 3 Escreva uma func ao que conta o numero de nos naofolha de uma arvore binaria 4 Escreva uma func ao que conta o numero de folhas de uma arvore binaria 5 Escreva uma func ao que calcula a altura de uma arvore binaria 6 Escreva uma func ao para buscar um numero impar em uma arvore binaria N AO orde nada 7 Escreva uma func ao para achar o MAIOR numero em uma arvore binaria N AO ordenada 8 Escreva uma func ao que exclui todos os nos de uma arvore binaria N AO ordenada com ID par 9 Escreva uma func ao que exclui todos os nos de uma arvore binaria de busca com ID par 10 Escreva uma func ao que retorna verdadeiro se uma arvore e binaria de busca e falso caso contrario 11 Escreva uma func ao que encontra o valor maximo em uma arvore de busca binaria 12 Escreva uma func ao que obtem o espelho de uma arvore ou seja troca a subarvore direita pela subarvore esquerda de todos os nos da arvore 13 Duas ABBs sao SIMILARES se possuem a mesma distribuic ao de nos independente dos valores nos mesmos Em uma definic ao mais formal duas ABBs sao SIMILARES se sao ambas vazia ou se suas subarvores esquerdas sao similares e suas subarvores direitas tambem sao similares Implemente a func ao que verifica se duas arvores sao similares 14 Duas ABBs sao IGUAIS se sao ambas vazias ou entao se armazenam valores iguais em suas raizes suas subarvores esquerdas sao iguais e suas subarvores direitas sao iguais Implemente a func ao que verifica se duas arvores sao simlares 1 15 Uma ABB e estritamente binaria se todos os nos da arvore tem 2 filhos Implemente uma func ao que verifica se uma ABB e estritamente binaria 16 Implemente uma func ao para testar se uma arvore binaria e uma ABB 17 Pense na implementac ao nao recursiva dos algoritmos de inserc ao remoc ao e busca em uma ABB 18 Dada uma ABB inicialmente vazia insira E DESENHE os seguintes elementos nessa ordem M F S D J P U A E H Q T W K 19 Dada uma ABB inicialmente vazia insira E DESENHE os seguintes elementos nessa ordem A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 20 Descreva a ordem de visita para um percurso em preordem emordem e posordem na arvore abaixo 21 Qual a diferenca de uma ABB para uma AVL 22 O que difere na implementac ao da func ao de busca de uma ABB e de uma AVL 23 Obtenha a equac ao que relaciona a altura de uma arvore binaria completa com o seu numero de vertices 24 Escreva func oes nao recursivas para realizar os 3 tipos de percurso na arvore binaria dica use uma pilha a preordem b emordem c posordem 25 Escreva uma func ao naorecursiva que retorne o menor valor de uma arvore binaria nao ordenada 26 Escreva uma func ao naorecursiva que retorne o menor valor de uma arvore binaria de busca 27 Escreva uma func ao naorecursiva que retorne o kesimo menor valor de uma arvore binaria de busca 28 Escreva uma func ao que retorne o elemento menor ou igual floor que um de referˆencia x em uma ABB 2 29 Escreva uma func ao naorecursiva que verifique a existˆencia de um valor X na arvore binaria 30 Escreva uma func ao naorecursiva que verifique a existˆencia de um valor negativo na arvore binaria 31 Escreva uma func ao naorecursiva que verifique se uma arvore binaria e tambem de busca 32 Mostre passo a passo a arvore binaria resultante das seguintes operac oes a Inserc ao de 7 8 3 4 2 1 6 5 b Mostre o percurso em preordem emordem e posordem c Remoc ao de 7 e 6 33 Escreva e implemente um algoritmo nao recursivo para obter a altura de uma ABB 34 Escreva e implemente um algoritmo que dada uma ABB construa uma outra arvore ABB aproximadamente completa Para isso obtenha todas as chaves e valores e insira na nova arvore sempre o elemento mediano das chaves ainda nao inseridas 35 Faca uma func ao que retorne a quantidade de folhas de uma arvore binaria de busca 36 Faca uma func ao que retorne a quantidade de nos de uma arvore binaria de busca que possuem apenas um filho 37 Faca uma func ao que dada uma arvore binaria de busca retorne a quantidade de nos que guardam numeros primos 38 Faca uma func ao que compare se duas arvores binarias de busca sao iguais 39 Faca uma func ao que retorna a lista de caminhos da raiz ate cada folha 40 Escreva uma func ao que faca o percurso em nıvel em uma arvore binaria O percurso em nıvel ou em largura em uma arvore e um percurso que visita em ordem crescente todos os nos de um nıvel antes de continuar a visita no nıvel seguinte Uma das formas de implementar e utilizar uma fila FIFO para guardar quais serao os proximos nodes a serem visitados 41 Considere a arvore rubronegra caida para a esquerda cujo percurso em nıvel em lar gura e 67 51 87 23 53 82 90 17 31 52 60 16 21 Liste as chaves em nos rubros em ordem crescente 42 Defina com suas palavras o que e uma arvore AVL e como ela funciona 43 Explique as vantagens e desvantagens de usar arvores binarias balanceadas 44 Desenhe a arvore AVL resultante da inserc ao dos seguintes nos 35 39 51 20 13 28 22 32 25 33 nesta ordem 45 Qual a diferenca de uma arvore binaria de busca para uma AVL 46 Uma arvore binaria de busca e estritamente binaria se todos os nos da arvore tem 2 fi lhos Implemente uma func ao que verifica se uma arvore binaria de busca e estritamente binaria 47 Escreva um programa para copiar uma arvore binaria 3 48 Faca um esquema grafico que represente a estrutura final de uma arvore AVL gerada pela inserc ao dos numeros 13 7 31 43 8 17 5 3 1 23 16 e 36 nesta ordem 49 Modifique a implementac ao da arvore de busca binaria para que ela lide corretamente com chaves duplicadas Isto e se uma chave ja esta na arvore a nova deversubstituir a antiga 50 Exiba as arvores binarias com alturas de 2 3 4 5 e 6 que contenham as sete chaves 1 4 5 10 16 17 e 21 Eemplo com altura de 2 10 4 17 1 5 16 21 51 Considere a arvore mostrada na figura abaixo e responda a Quais sao os nos folhas b Quais nos sao ancestrais de C c Quais sao os descendentes de C d Qual e a altura da arvore e Quais sao os nos com grau 1 e 2 f Quantos caminhos de comprimento trˆes existem 52 Crie uma arvore binaria de busca adicionando um a um e nesta ordem os seguintes numeros 5 6 3 8 7 4 1 e 2 53 Quantas arvores de busca binaria com nos 1 2 3 e 4 existem 54 Considere uma arvore de busca binaria tendo como nos os numeros de 1 ate 1000 Nos procuramos um no marcado com 363 Qual das seguintes sequˆencias nao podem ser os valores dos nodos visitados na busca por 363 a 2 252 401 398 330 344 397 363 b 924 220 911 244 898 258 362 363 c 925 202 911 240 912 245 363 d 2 399 387 219 266 382 381 278 363 e 935 278 347 621 299 392 358 363 4 55 Dˆe um pequeno exemplo de como adicionar um numero a uma arvore AVL causando uma arvore desbalanceada do tipo direita direita Rebalancear a arvore 56 Dˆe um pequeno exemplo de como adicionar um numero a uma arvore AVL causando uma arvore desbalanceada do tipo direitaesquerda Rebalancear a arvore 57 Dˆe um pequeno exemplo de remoc ao de um numero de um arvore AVL causando uma arvore desbalanceada do tipo direitadireita Rebalancear a arvore 58 Projete um algoritmo para determinar o menor numero em uma arvore AVL 59 Escreva uma func ao que receba um nıvel da arvore e imprima todos os nos nesse nıvel 60 Escreva a func ao que retorna o numero de nos que sao divisores da soma de seus filhos Leve em conta apenas os nos com dois filhos 61 Dada uma arvore binaria e dois nos dela desenvolva um algoritmo para achar o ancestral comum mais baixo dos dois nos dados O ancestral comum e um no que possua os outros dois nos em suas subarvores O ancestral comum mais baixo e o ancestral comum que tem a maior profundidade 62 Em uma arvore binaria faca um algoritmo para alterar o valor de cada no exceto no folha para a soma dos valores dos nos esquerda e direita 63 Remova da seguinte arvore AVL o no 8 e em seguida adicione um no com valor 9 64 Faca um algoritmo que crie uma lista ligada com os nos de uma arvore binaria em um percurso emordem 65 Faca um algoritmo para somar os nos presentes nos nıveis impares de uma arvore binaria 66 Implementar uma func ao naorecursiva para calcular o tamanho de uma arvore binaria 67 Implementar uma func ao naorecursiva para cada um dos percursos abaixo a emordem b posordem c preordem 68 Monte uma arvore capaz de armazenar uma struct contendo as seguintes informac oes nome do municıpio area total do municıpio em km2 e populac ao A arvore devera ter func oes para inserir pelo nome percorrer e listar Implemente tambem func oes para 5 a Contar o numero de municıpios percorrendo os nos cadastrados na arvore b Mostrar apenas os nomes dos municıpios com mais de X habitantes Por exemplo X pode ser 100000 pessoas c Mostrar a densidade demografica de cada cidade A densidade demografica e a relac ao entre a populac ao e a area d Mostrar o somatorio de area em km2 de todas as cidades juntas em relac ao ao territorio nacional em porcentagem e Mostrar as cidades em ordem alfabetica com todos os dados f Mostrar o nome da cidade com a maior populac ao 6