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

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

Com relação à estrutura de dados árvore de busca binária, é incorreto afirmar que:

• A.

  a inserção ocorre sempre em uma folha.

• B.

  a remoção nem sempre ocorre em uma folha.

• C.

  todos os elementos na subárvore esquerda de cada nó k têm valor menor ou igual ao valor no nó k.

• D.

  todos os elementos na subárvore direita de cada nó k têm valor maior do que o valor no nó k.

• E.

  todas as folhas estão no mesmo nível.

A estrutura de dados utilizada no tratamento de colisão denominado endereçamento fechado (Closed Address Hashing) em tabelas hash é:

• A.

  lista ligada.

• B.

  árvore.

• C.

  vetor.

• D.

  array.

• E.

  heap.

Considerando o algoritmo acima, julgue os itens a seguir, a respeito de estrutura de dados, métodos de busca e inserção e ordenação.

Enquanto uma lista encadeada somente pode ser percorrida de um único modo, uma árvore binária pode ser percorrida de muitas maneiras diferentes.

• C. Certo
• E. Errado

Considerando uma lista encadeada L, em que cada elemento contém um objeto de algum tipo e o endereço do elemento seguinte, julgue os itens que se seguem.

Nessa situação, o uso de um vetor v[0 ... n - 1], com elementos do mesmo tipo da lista encadeada L, permite a implementação de uma pilha, sendo necessário armazenar, em uma variável auxiliar, que elemento está no topo da pilha.

• C. Certo
• E. Errado

FIFO refere-se a estruturas de dados do tipo

• A.

  fila.

• B.

  árvore binária.

• C.

  pilha.

• D.

  matriz quadrada.

• E.

  cubo.

No que se refere às estruturas de dados, julgue os itens subsequentes.

Considerando-se a implementação de um grafo denso, direcionado e ponderado, se o número de vértices ao quadrado tem valor próximo ao número de arcos, o uso de uma matriz de adjacência simétrica apresenta vantagens em relação ao uso de uma lista de adjacência.

• C. Certo
• E. Errado

No que se refere às estruturas de dados, julgue os itens subsequentes.

Tabelas de dispersão aplicadas a arquivos requerem funções de escrutínios dinâmicas.

• C. Certo
• E. Errado

No que se refere às estruturas de dados, julgue os itens subsequentes.

As árvores binárias possuem vantagens em relação às listas encadeadas somente quando estão balanceadas, justificando-se o uso de um método de balanceamento de uma árvore binária quando elementos estão sendo constantemente acrescidos e removidos da árvore.

• C. Certo
• E. Errado