Estrut

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (476 palavras )
  • Download(s) : 0
  • Publicado : 15 de novembro de 2012
Ler documento completo
Amostra do texto
FACULDADE LOURENÇO FILHO ENADE 2011 Prof. Ricardo Viana DATA: 01/10/2011

Algoritmos e Estruturas de Dados (Desenvolvimento e Complexidade de Algoritmos, Estruturas de Dados Lineares e NãoLineares, Pesquisa e Ordenação, Grafos).

QUESTÃO 1 Um programador propôs um algoritmo não-recursivo para o percurso em pré-ordem de uma árvore binária com as seguintes características. - Cada nó da árvorebiná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 invocadoinicialmente 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çõese 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 dopercurso. 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 árvoresã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) Apenasos 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.
1

QUESTÃO 2 Os números de Fibonacci...
tracking img