Questões de Ciência da Computação do ano 2011

Uma consulta busca um registro, em um arquivo, utilizando um índice auxiliar, que é uma árvore binária balanceada, cujos nós têm ponteiros para os registros do arquivo principal. O arquivo A tem 12Kb de tamanho, enquanto o arquivo B tem 12Gb. A consulta é executada sobre os dois arquivos. Quantas comparações são feitas a mais, quando a consulta é executada sobre o segundo arquivo?

• A.

  20

• B.

  64

• C.

  256

• D.

  1024

• E.

  2048

A sequência que representa o percurso da árvore da figura em pós-ordem é

• A.

  P Q S T R

• B.

  S T Q P R

• C.

  P Q R S T

• D.

  R P Q T S

• E.

  S T Q R P

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²)