Arvores

QUESTÃO 19

Dado um conjunto C contendo n inteiros distintos, qual das seguintes estruturas de

dados em memória principal permite construir um algoritmo para encontrar o valor

máximo de C em tempo constante?

(A) Um vetor não ordenado.

(B) Um vetor ordenado.

(C) Uma árvore binária de busca balanceada.

(D) Uma lista encadeada simples ordenada em ordem crescente.

(E) Uma árvore rubro-negra.

QUESTÃO 20

Suponha que a tabela a seguir apresenta a freqüência de cada letra de um alfabeto em

uma string. Quantos bits seriam necessários para representar essa string usando um

código de Huffman?

(A) 392

(B) 147

(C) 113

(D) 108

(E) Nenhuma das respostas anteriores.

QUESTÃO 21

Um estudante de computação precisa resolver um problema bastante importante, que

é executar as operações que estão descritas abaixo, cuja estrutura é uma pilha. Tão

logo ele retire algum elemento desta pilha, estes deverão ser inseridos em uma fila,

cuja entrada é pela esquerda e a saída, pela direita. Assinale a alternativa que contém

a sequência correta de entrada dos elementos na fila.

PUSH P

PUSH E

PUSH R

PUSH T

PUSH O

POP

POP

PUSH S

PUSH O

PUSH L

POP

POP

POP

(A) S - O - L - T – O

(B) O - T - R - E – P

(C) P - E - R - T – O

(D) O - T - L - O – S

(E) P - O - R - L – S

10

QUESTÃO 21

Os algoritmos a seguir representam os três caminhamentos para árvores binárias.

caminhamento(binário)

se binário.esquerda ≠ NULL então caminhamento(binário.esquerda)

escrever binário.valor

se binário.direita ≠ NULL então caminhamento(binário.direita)

caminhamento(binário)

escrever binário.dado

se binário.esquerda ≠ NULL então caminhamento(binário.esquerda)

se binário.direita ≠ NULL então caminhamento(binário.direita)

caminhamento(binário)

se binário.esquerda ≠ NULL então caminhamento(binário.esquerda)

se binário.direita ≠ NULL então caminhamento(binário.direita)

escrever binário.valor

Assinale a alternativa que contém os nomes dos 3 caminhamentos, respectivamente.

(A) pré-ordem, pós-ordem, em-ordem

(B) pré-ordem, em-ordem, pós-ordem

(C) pós-ordem, pré-ordem, em-ordem

(D) em-ordem, pré-ordem, pós-ordem

(E) em-ordem, pós-ordem, pré-ordem

QUESTÃO 23

A busca antecipada de instruções é uma técnica utilizada nos processadores dos

microcomputadores atuais, de forma a acelerar a execução de um programa. As

instruções são pré-carregadas da memória

A) cache para a memória principal.

B) cache para a memória virtual.