Um programador propôs um algoritmo não-recursivo para o percurso em preordem de uma árvore binária com as seguintes características

ENADE 2008  -  QUESTÃO 14 Um programador propôs um algoritmo não-recursivo para o percurso em preordem de uma árvore binária com as seguinte...

ENADE 2008 - QUESTÃO 14

Um programador propôs um algoritmo não-recursivo para o percurso em preordem de uma árvore binária com as seguintes características.

< Cada nó da árvore binária é representado por um registro com três campos: chave, que armazena seu identificador; esq e dir, ponteiros para os filhos esquerdo e direito, respectivamente.

< O algoritmo deve ser invocado inicialmente tomando o ponteiro para o nó raiz da árvore binária como argumento.

< O algoritmo utiliza push() e pop() como funções auxiliares de empilhamento e desempilhamento de ponteiros para nós de árvore binária, respectivamente.

A seguir, está apresentado o algoritmo proposto, em que 8 representa o ponteiro nulo.

Procedimento preordem (ptraiz : PtrNoArvBin)

 Var ptr : PtrNoArvBin;

 ptr := ptraiz;

 Enquanto (ptr … λ) Faça

 escreva (ptr8.chave);

 Se (ptr8.dir … λ) Então

 push(ptr8.dir);

 Se (ptr8.esq … λ) Então

 push(ptr8.esq);

 ptr := pop();

 Fim_Enquanto

Fim_Procedimento

Com base nessas informações e supondo que a raiz de uma árvore binária com n nós seja passada ao procedimento preordem(), julgue os itens seguintes.

I O algoritmo visita cada nó da árvore binária exatamente uma vez ao longo do percurso.

II O algoritmo só funcionará corretamente se o procedimento pop() for projetado de forma a retornar 8 caso a pilha esteja vazia.

III Empilhar e desempilhar ponteiros para nós da árvore são operações que podem ser implementadas com custo constante.

IV A complexidade do pior caso para o procedimento preordem() é O(n).

Assinale a opção correta.

A) Apenas um item está certo.

B) Apenas os itens I e IV estão certos.

C) Apenas os itens I, II e III estão certos.

D) Apenas os itens II, III e IV estão certos.

E) Todos os itens estão certos. 

QUESTÃO ANTERIOR:

- Considerando o conjunto A = {1, 2, 3, 4, 5, 6}, qual opção corresponde a uma partição desse conjunto?

GABARITO:

E) Todos os itens estão certos.

RESOLUÇÃO:

Não temos resolução para essa questão! Você sabe explicar? Copie o link dessa página e envie sua resolução clicando AQUI!

PRÓXIMA QUESTÃO:

- Além do acesso a páginas html, a Internet tem sido usada cada vez mais para a cópia e troca de arquivos de músicas, filmes, jogos e programas. Muitos desses arquivos possuem direitos autorais e restrições de uso. 

QUESTÃO DISPONÍVEL EM:

- Prova de Computação ENADE 2008 com Gabarito