Questões sobre Dados

O algoritmo de ordenação de pior complexidade temporal no caso médio, dentre os que se seguem, é

• A.

  Merge sort.

• B.

  Bubble sort.

• C.

  Heapsort.

• D.

  Quicksort.

• E.

  Binary tree sort.

Uma árvore AVL é uma árvore binária de busca autobalanceada que respeita algumas propriedades fundamentais. Como todas as árvores, ela tem uma propriedade chamada altura, que é igual ao valor da altura de sua raiz.

Sabendo que a altura de uma folha é igual a um e que a altura de um nó pai é igual ao máximo das alturas de seus filhos mais um, qual estrutura NÃO pode representar uma árvore AVL?

• A.

  Uma árvore vazia

• B.

  Uma árvore com dois nós

• C.

  Uma árvore com três nós e altura igual a dois

• D.

  Uma árvore com três nós e altura igual a três

• E.

  Uma árvore com seis nós e altura igual a três

• A.

  

• B.

  

• C.

  

• D.

  

• E.

  

Um programador precisa realizar buscas em um enorme cadastro de pessoas (tamanho igual a n) armazenado na memória principal. Para realizar um processo eficiente de busca, ele decidiu usar uma árvore AVL e obteve um tempo de execução de ordem f. Um colega, preocupado com a eficiência do processo de busca, sugeriu-lhe que usasse um vetor com 10 árvores AVL, onde o índice da árvore seria dado pelo último dígito do CPF de cada pessoa, dígito este que é uniformemente distribuído. Assim, cada árvore teria aproximadamente 1/10 do número de pessoas e o processo de busca poderia ser mais eficiente. Se o programador implementar a solução proposta pelo seu colega, a ordem do tempo de execução do processo de busca será

• A.

  f

• B.

  f /10

• C.

  f / n

• D.

  f / log₂10

• E.

  f/10n

As árvores usadas como estruturas de pesquisa têm características especiais que garantem sua utilidade e propriedades como facilidade de acesso aos elementos procurados em cada instante. A esse respeito, considere as afirmações abaixo. I – A árvore representada na figura (I) acima não é uma árvore AVL, pois as folhas não estão no mesmo nível. II – A sequência 20, 30, 35, 34, 32, 33 representa um percurso sintaticamente correto de busca do elemento 33 em uma árvore binária de busca. III – A árvore representada na figura (II) acima é uma árvore binária, apesar da raiz não ter filhos. É(São) correta(s) APENAS a(s) afirmativa(s)

• A.

  I.

• B.

  II.

• C.

  III.

• D.

  I e II.

• E.

  II e III.

Uma árvore B é um tipo de árvore que se mantém balanceada com o decorrer do tempo. Para tanto, ela usa uma série de operações que garantem a manutenção de uma série de propriedades importantes, uma das quais é a ordem da árvore que pode ser definida como o número máximo de elementos que podem ser armazenados em um nó da árvore. Com base nesses conceitos, qual das situações a seguir representa uma propriedade das árvores B?

• A.

  Em uma árvore B de ordem maior do que 1, não é permitido que uma folha armazene apenas um elemento.

• B.

  Em uma árvore B de ordem d, a raiz armazena um número de elementos

• C.

  Em uma árvore B de ordem d, pode haver folhas em alturas diferentes da árvore até que tenham sido inseridos, pelo menos, 2d+1 elementos.

• D.

  Em um nó de uma árvore B que contenha n elementos não vazios, podem-se ter, no máximo, n/2 ponteiros apontando para vazio (nil ou null).

• E.

  Em um nó interno de uma árvore B que contenha n elementos, têm-se exatamente n+1 ponteiros que não apontam para vazio (nil ou null).

O quicksort é um algoritmo que funciona usando o paradigma de dividir e conquistar, usando uma rotina de particionamento que divide o vetor de estruturas em dois pedaços em torno de um pivô. O pedaço da esquerda só contém elementos com chaves menores ou iguais que o elemento corrente e o pedaço da direita, só elementos com chaves maiores que o elemento corrente. O algoritmo procede, então, para o subproblema de ordenar cada um dos pedaços e seu desempenho total é um dos mais eficientes para ordenação de estruturas de dados. Qual das seguintes descrições representa uma correta característica do algoritmo quicksort?

• A.

  O algoritmo de particionamento é o ponto fraco do quicksort, podendo exigir até n2 operações de trocas em cada iteração, o que faz com que ele precise ser fortemente otimizado.

• B.

  O algoritmo de particionamento só funciona nos casos em que o número de elementos no vetor é par, pois é necessário, para o correto cálculo do pivô, que o lado esquerdo e o direito tenham exatamente o mesmo tamanho.

• C.

  Seu tempo de execução, no pior caso, é  que ocorre no caso especial em que a rotina de particionamento gera subproblemas com n-1 elementos e outro com 0 elemento.

• D.

  Seu tempo de execução de melhor caso é que ocorre no caso especial em que o vetor de estruturas já está ordenado.

• E.

  Seu tempo de execução é de  no caso do particionamento ser desbalanceado na proporção de 2 elementos para um lado, para cada elemento do outro lado.

Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em uma árvore de busca binária. Após a completa inserção de todos os elementos nesta árvore, são feitas buscas de números na mesma. O tempo médio de busca de um número nesta árvore é

• A.

  O(1)

• B.

  O(log N)

• C.

  O(N)

• D.

  O(Nlog N)

• E.

  O(N²)

Após a inserção de um nó, é necessário verificar cada um dos nós ancestrais desse nó inserido, relativamente à consistência com as regras estruturais de uma árvore AVL.

PORQUE

O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por {−2, −1, 0, +1, +2}.

Analisando-se as afirmações acima, conclui-se que

• A.

  as duas afirmações são verdadeiras, e a segunda justifica a primeira.

• B.

  as duas afirmações são verdadeiras, e a segunda não justifica a primeira.

• C.

  a primeira afirmação é verdadeira, e a segunda é falsa.

• D.

  a primeira afirmação é falsa, e a segunda é verdadeira.

• E.

  as duas afirmações são falsas.

• A.

  3, 6, 8

• B.

  4, 2, 6

• C.

  4, 9, 7

• D.

  5, 3, 9

• E.

  5, 7, 8