Estudos Diciplinares

6.

Apresentada a arvore acima qual forma de atravessamento resultará na expressão a+b*c:

A) prefixa

B) posfixa

C) alterfixa

D) infixa

E) recursixa

7. (ENADE 2008) 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 λ representa o ponteiro nulo.

Procedimento preordem (ptraiz : PtrNoArvBin)

Var ptr : PtrNoArvBin;

ptr := ptraiz;

Enquanto (ptr ≠ λ) Faça

escreva (ptr↑.chave);

Se (ptr↑.dir ≠ λ) Então

push(ptr↑.dir);

Se (ptr↑.esq ≠ λ) Então

push(ptr↑.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 λ 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.

8. (ENADE 2011) No desenvolvimento de um software que analisa bases de DNA, representadas pelas letras A, C, G, T, utilizou-se as estruturas de dados: pilha e fila. Considere que, se uma sequência representa uma pilha, o topo é o elemento mais à esquerda; e se uma sequência representa uma fila, a sua frente é o elemento mais à esquerda.

Analise o seguinte cenário: “a sequência inicial ficou armazenada na primeira estrutura de dados na seguinte ordem: (A,G,T,C,A,G,T,T). Cada elemento foi retirado da primeira estrutura de dados e inserido na segunda estrutura de dados, e a sequência