determine quais nós ocuparam a posição de nó raiz, durante...

LEIA ATENTAMENTE AS INSTRUÇÕES DA BANCA EXAMINADORA ABAIXO.

01 - O candidato recebeu do fiscal o seguinte material:

a) este Caderno de Questões, com os enunciados das 5 (cinco) questões da Prova Discursiva, sem repetição ou falha, valendo 10,0 (dez) pontos cada questão.

b) 1 (um) caderno de Folhas de Discursivas, para o desenvolvimento das respostas às questões discursivas.

02 - O candidato deve verificar se este material está em ordem e se o seu nome e o seu número de inscrição conferem com os que aparecem na capa do caderno de Folhas de Discursivas. Caso contrário, deve notificar o fato IMEDIATAMENTE ao fiscal.

03 - Após a conferência, o candidato deverá assinar, no espaço próprio da capa do caderno de Folhas de Discursivas, com caneta esferográfica transparente de tinta na cor preta.

04 - As questões discursivas deverão ser respondidas, no caderno de Folhas de Discursivas, utilizando caneta esferográfica transparente de tinta na cor preta.

05 - O candidato deve ter muito cuidado com o caderno de Folhas de Discursivas, para não o dobrar, amassar ou manchar. O caderno de Folhas de Discursivas SOMENTE poderá ser substituído se, no ato da entrega ao candidato, já estiver danificado em suas margens superior e/ou inferior - Barra de reconhecimento para leitura óptica.

06 - SERÁ ELIMINADO desta Seleção Pública o candidato que:

a) for surpreendido, durante as provas, em qualquer tipo de comunicação com outro candidato ou utilizando máquinas de calcular ou similares, livros, códigos, manuais, apostilas, impressos ou anotações;

b) portar ou usar, durante a realização das provas, aparelhos sonoros, fonográficos, de comunicação ou de registro, eletrônicos ou não, tais como: agendas eletrônicas e/ou similares, gravadores, pen drive, mp3 player e/ou similar, fones de ouvido, chaves com alarme ou com qualquer outro componente eletrônico, relógios de qualquer natureza, telefones celulares, microcomputadores portáteis e/ou similares;

c) se ausentar da sala em que se realiza a prova levando consigo o Caderno de Questões, e/ou o caderno de Folhas de Discursivas.

d) se recusar a entregar o Caderno de Questões, e/ou o caderno de Folhas de Discursivas quando terminar o tempo estabelecido.

e) NÃO assinar a Lista de Presença e/ou a capa do caderno de Folhas de Discursivas.

Obs.: O candidato só poderá se ausentar do recinto da prova após 2 (duas) horas contadas a partir do efetivo início da mesma. Por motivos de segurança, o candidato NÃO PODERÁ LEVAR o Caderno de Questões, a qualquer momento.

07 - O tempo disponível para esta Prova Discursiva é de 4 (quatro) horas, findo o qual o candidato deverá, obrigatoriamente, entregar o caderno de Folhas de Discursivas e o Caderno de Questões.

08 - Quando terminar, o candidato deverá entregar ao fiscal o Caderno de Questões e o caderno de Folhas de Discursivas e ASSINAR a Lista de Presença.

09 - As questões da Prova Discursiva estarão disponíveis, no primeiro dia útil após a realização da mesma, no endereço eletrônico da FUNDAÇÃO CESGRANRIO (http://www.cesgranrio.org.br).

Questão n^o 3

O setor bancário está em constante transformação, com investimentos em inovações, principalmente na área de TI, para atender às demandas dos seus clientes. Uma das ferramentas para alcançar esse objetivo é a escolha de estruturas de dados eficientes, e as árvores AVL, por suas propriedades, estão dentre as estruturas preferidas para várias aplicações. Uma de suas propriedades importantes para sistemas bancários, por exemplo, é manter a complexidade na execução das operações de inserção, remoção e busca na árvore com n elementos em O(log n). O conhecimento sobre essas árvores, portanto, é assunto relevante para os departamentos de TI do setor bancário.

Nesse contexto, considere uma situação em que seja necessário implementar uma árvore AVL.

Dada a sequência de chaves numéricas 28, 54, 49, 63, 57 e 66,