Estruturas de Dados - COM160 - Semana 5 - Atividade Avaliativa

Prévia do material em texto

Supondo que temos uma estrutura de árvore binária de busca, como a mostrada a seguir, e queremos substituir e E com os números 5. A B E c D Indique a alternativa correta para fazer a substituição garantindo que a árvore seja binária de busca. = = Dada a árvore binária de busca a seguir, assinale a alternativa correta: 64 40 92 2 58 73 37 66 79 a. A altura do nó 40 é igual a 1. b. Dois nós possuem grau igual a 3. C. Apesar de ser uma árvore binária, não satisfaz as propriedades de árvore binária de busca. d. Exatamente três nós possuem graus iguais a zero. e. A profundidade do nó 73 é igual a 2.Uma árvore binária é uma árvore em que abaixo de cada nó existem no máximo duas subárvores. Sobre conceitos de árvore, analise as afirmativas a seguir. I. A altura de um nó equivale ao comprimento do caminho mais longo do nó até uma folha. II. A altura da árvore é a altura do nó raiz r. III. A profundidade de um nó é a distância percorrida da raiz até 0 nó. IV. Um nó folha é um nó de grau 1. Está correto 0 que se afirma em: a.l, III e IV, apenas. III e IV, apenas. C. I, e III, apenas. d. e IV, apenas. e. e III, apenas. Leia atentamente 0 que se afirma a seguir. Para realizar buscas, as árvores binárias são mais eficientes do que outras estruturas como filas e pilhas. Diante disso, assinale a alternativa que explique corretamente a afirmativa apresentada. a. A vantagem das árvores binárias está em sua aplicação, pois elas podem transformar qualquer linguagem em C + + Esse tipo de árvore alterna a linguagem que não é C + + para que 0 programa possa ser lido universalmente. b.A vantagem das árvores binárias está no seu eficiente tempo de busca quando a árvore está razoavelmente balanceada, 0 que equivale a dizer que as folhas em cada extremidade estão em igual profundidade. C. Quando utilizamos árvores binárias, conseguimos reutilizar comandos que se repetem uma única vez, fazendo com que códigos sejam realizados dez vezes mais rápido que sem a utilização dela. d.As árvores binárias podem ter 10 subárvores ligadas à raiz, por isso são mais eficientes que as demais, pois cada subárvore faz pesquisas em cada linha. Por isso, 0 código precisa ter somente 10 linhas, nem mais, nem menos. e. A vantagem das árvores binárias é a separação de dígitos que facilitam as buscas, pois se a separação é feita, ocorre uma busca mais otimizada e ágil, visto que 0 tempo de pesquisa do código total diminui. Em árvores binárias, podemos realizar dois procedimentos: processo de inserção, que é incluir um novo nó na lista, e processo de remoção, que é excluir um nó da árvore. No processo de remoção de se nó não tiver filhos, ele é simplesmente retirado; porém, se ele tiver um filho, então este ficará em seu lugar e nó será removido. Se nó tiver mais de um filho, é necessário fazer sua substituição pelo lógico antes de removê-lo. Uma observação é que 0 sucessor lógico é sempre O elemento mais à esquerda na subárvore da direita. Também há outra opção: se nó tiver mais de um filho, ele pode ser substituído por seu lógico antes de sua remoção. Nesse caso, predecessor lógico é sempre elemento mais à direita na subárvore da esquerda. Preencha as lacunas, escolhendo a alternativa correta. a. lista lineares; antecessor; sucessor. b. árvores binárias; antecessor; nó C. elementos; sucessor. d.lista lineares; e. árvores binárias; sucessor; antecessor.Em estrutura de dados, existem as árvores binárias, nas quais, quando um novo nó é inserido, deve-se verificar que, se seu valor for menor que 0 nó na posição atual, ele é inserido a esquerda; e se for maior que nó na posição atual, ele é inserido a direita. Podemos utilizar como exemplo uma árvore recém-criada, que tem em seu nó raiz número 35. Após a inserção de um novo valor, algoritmo deve conferir se número é menor do que 35; nesse caso, 0 novo número deve ser inserido no galho da esquerda, do contrário, número deve ser inserido no galho da direita. 25 20 30 15 24 35 33 40 Com relação à inserção do número 22 na árvore binária da figura, assinale a alternativa que corresponde à posição para inserção do novo valor. a. À direita do 24, filho do 24. b.À esquerda do 15, filho do 15. C. À direita do 15, filho do 15. esquerda do 33, filho do 33. e. À esquerda do 24, filho do 24. Nas opções de percorrer uma árvore em estrutura binária, existe um método chamado "pós-ordem", em que se inicia percurso pelos últimos nós da esquerda até chegar à raiz; em seguida, começa-se pelos últimos nós da direita e se encerra na raiz da árvore. 60 51 80 44 59 85 46 81 Com relação ao percurso em pós-ordem realizado na árvore da figura, assinale a alternativa que contém esse percurso. a. 46, 44, 59, 51, 81, 85, 80, 60. b. 60, 51, 44, 46, 59, 80, 85, 81. C. 46, 44, 59, 52, 81, 85, 80, 60. d. 81, 85, 80, 60, 51, 44, 46, 59. e. 60, 51, 44, 46, 59, 80, 85, 81.Nas opções para percorrer uma árvore em estrutura binária, pode-se iniciar pelo nó raiz, seguir pelos nós que estão à esquerda e, por fim, OS que estão à direita. Essa opção é denominada de "pré-ordem". 50 45 75 30 47 86 23 40 79 92 Com relação ao percurso em pré-ordem realizado na árvore da figura, assinale a alternativa que contém 0 percurso. a. 92, 86, 79, 75, 50, 45, 47, 30, 23, 40. b. 50, 75, 86, 92, 79, 45, 47, 30, 40, 23. C. 23, 30, 40, 45, 47, 50, 75, 86, 79, 92. d. 45, 47, 30, 23, 40, 50, 75, 86, 79, 92. e. 50, 45, 30, 23, 40, 47, 75, 86, 79, 92.