ENADE: Tendo como base a árvore acima, faça o que se pede nos itens a seguir

ENADE: Tendo como base a árvore acima, faça o que se pede nos itens a seguir

ENADE: Tendo como base a árvore acima, faça o que se pede nos itens a seguir.

a) Descreva uma ordem de visita dos nós para uma busca em profundidade a partir do nó de valor 41. (valor: 3,0 pontos) 

b) Considerando que o nó de valor 33 seja a raiz da árvore, descreva a ordem de visita para uma varredura em pré-ordem (r-e-d, ou pré-fixado à esquerda) na árvore. (valor: 3,0 pontos)

c) Considerando que a árvore cuja raiz é o nó de valor 33 represente uma árvore de busca binária, desenhe a nova árvore que será obtida após a realização das seguintes operações: inserir um nó de valor 21; remover o nó de valor 47; inserir um nó de valor 48. (valor: 4,0 pontos)

QUESTÃO ANTERIOR:

- ENADE: O objetivo da Teoria Geral dos Sistemas (TGS) é a formulação dos princípios válidos para os sistemas em geral, qualquer que seja a natureza dos elementos que os compõem e as relações ou forças existentes entre eles.

PADRÃO DE RESPOSTA:

Item a: Serão aceitas respostas que considerem árvore ou grafo a estrutura do enunciado. No caso de o aluno ter considerado a estrutura um grafo, as opções de resposta são as seguintes:

Resposta para grafo:

· 41, 38, 34, 47, 49, 43, 33, 15

· 15, 33, 34, 38, 49, 43, 47, 41

Caso o aluno tenha considerado a estrutura uma árvore, as opções de resposta são:

· 41, 38, 34, 47, 43, 49

· 41, 47, 49, 43, 38, 34

· 34, 38, 43, 49, 47, 41

· 49, 43, 47, 34, 38, 41

O estudante que apresentou qualquer das respostas acima recebeu nota máxima nesse item (3,0 pontos).

Análise do item

O algoritmo de busca em profundidade pode ser descrito de duas maneiras

1. busca_profundidade (no v) visita(v); para cada vizinho w de v faça se w não foi visitado busca_profundidade (w)

2. busca_profundidade (no v) para cada vizinho w de v faça se w não foi visitado busca_profundidade (w) visita(v); Assim, qualquer percurso que obedeça à execução de um dos algoritmos acima está correto. O avaliador deve verificar se o percurso indicado pelo estudante obedece a um desses padrões.

Exemplos de percursos corretos: 41, 38, 34, 47, 49, 43, 33, 15

15, 33, 34, 38, 49, 43, 47, 41

Item b:

A descrição correta do percurso é: 33, 15, 41, 38, 34, 47, 43, 49 O estudante que descreveu corretamente a ordem da visita para varredura em pré-ordem recebeu nota máxima nesse item (3,0 pontos).

Item c: resposta esperada:

1) insere(21): há apenas uma possibilidade: inserir à direita do nó 15, resultando a árvore abaixo. O estudante que fez a inserção do nó 21 recebeu a nota máxima nesse item (1,0 ponto)

2) remove(47): há duas possibilidades: um dos nós 43 ou 49 deve ser “promovido” para o lugar do nó 47, resultando em uma das figuras abaixo (na da esquerda o 49 foi promovido; na da direita o nó promovido foi o 43. Nesse item, o estudante que apresentou uma das árvores abaixo (remoção do nó 47) recebeu a nota máxima (2,0 pontos).

3) insere(48): dependendo de qual alternativa o estudante utilizou no passo 2, as duas possibilidades são, finalmente:

Uma outra possibilidade é que o estudante tenha “equilibrado” a árvore de busca, apesar de não ter sido solicitado. Assim, deve-se considerar também correta a árvore abaixo, que reordena os nós para conseguir uma árvore de menor altura:

O estudante que apresentou qualquer das respostas acima recebeu a nota máxima (1,0 ponto). Na avaliação, foi considerada a resposta em que houvesse apresentação das três opções do item em três gráficos diferentes ou em um único gráfico e também as respostas que seguiram um ordenamento diferente das etapas solicitadas nos itens 1, 2 e 3.  

PRÓXIMA QUESTÃO:

- ENADE: Considere um sistema de locação de filmes em que um cliente solicita a locação de alguns filmes em DVD e após ter se identificado ao funcionário e escolhido os filmes, ele os leva para casa, sabendo dos prazos de devolução de cada filme e do valor do aluguel a ser pago.

QUESTÃO DISPONÍVEL EM:

- Prova de Computação ENADE 2005 com Gabarito