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

Julgue os próximos itens em relação às estruturas de dados.

As pilhas são listas encadeadas cujos elementos são retirados e acrescentados sempre ao final, enquanto as filas são listas encadeadas cujos elementos são retirados e acrescentados sempre no início.

• C. Certo
• E. Errado

A representação de uma estrutura de dados do tipo grafo pode ser por:

1. Matriz de adjacência

2. Matriz de coesão

3. Lista de adjacência

Está(ão) correta(s) a(s) afirmativa(s):

• A.

  3, apenas.

• B.

  1 e 2, apenas.

• C.

  1 e 3, apenas.

• D.

  2 e 3, apenas.

• E.

  1, 2 e 3.

Analise o seguinte cenário: · Um sistema que deve fazer uso de uma lista de dados do tipo inteiro;

· Os acessos à lista serão apenas para leitura;

· Os acessos aos elementos são feitos de forma aleatória, baseada na posição dos mesmos na lista.

Considerando apenas as informações apresentadas no cenário em questão, a estrutura de dados mais apropriada para ser utilizada é:

• A.

  Lista encadeada

• B.

  Lista duplamente encadeada

• C.

  Grafo

• D.

  Array

• E.

  Árvore

Analise as seguintes afirmativas acerca das estruturas de dados:

1. Uma fila circular não pode ser implementada usando-se arrays.

2. Em uma lista duplamente encadeada de caracteres, cada elemento da lista armazena dois caracteres, além do ponteiro para o próximo elemento da lista.

 3. Um grafo pode ser visto como uma árvore, ou seja, não pode ter ciclos.

Está(ão) incorreta(s) a(s) afirmativa(s):

• A.

  3, apenas.

• B.

  1 e 2, apenas.

• C.

  1 e 3, apenas.

• D.

  2 e 3, apenas.

• E.

  1, 2 e 3.

Assinale o nome da estrutura de dados que é uma extensão da pilha, onde podemos inserir e remover elementos em ambas as extremidades da pilha:

• A.

  Pilha double-headed

• B.

  Pilha duplamente encadeada

• C.

  Tabela de dispersão

• D.

  Deque

• E.

  Pilha2

A árvore de busca é uma estrutura de dados que permite operações eficientes de:

 1. Busca por elementos.

2. Inserção de elementos.

3. Remoção de elementos.

Está(ão) correta(s) a(s) afirmativa(s):

• A.

  3, apenas.

• B.

  1 e 2, apenas.

• C.

  1 e 3, apenas.

• D.

  2 e 3, apenas.

• E.

  1, 2 e 3.

Uma estrutura de dados onde cada nó mantém uma informação adicional, chamada fator de balanceamento, que indica a diferença de altura entre as subárvores esquerda e direita, é conhecida por árvore

• A.

  ordenada.

• B.

  AVL.

• C.

  binária.

• D.

  hiberbólica.

• E.

  de busca binária.

No contexto das vinculações de subscritos e categorias de matrizes, NÃO se inclui como uma categoria a matriz

• A.

  estática.

• B.

  dinâmica na pilha.

• C.

  associativa.

• D.

  fixa dinâmica na pilha.

• E.

  dinâmica no monte.

Os números 1,2,3,...,N foram inseridos de forma ordenada em uma árvore binária de busca, em uma árvore AVL e em um vetor para o qual foi decidido que a posição do número i seria dada pelo índice i-1. Depois, sabendo-se que nenhuma inserção posterior será realizada em nenhuma das três estruturas, decidiu-se fazer uma busca em cada uma destas. Os tempos que se podem obter para essa busca na árvore binária de busca, na árvore AVL e no vetor são, respectivamente,

• A.

  O(log N), O(log N), O(N)

• B.

  O(log N), O(log N), O(1)

• C.

  O(log N), O(1), O(log N)

• D.

  O(N), O(log N), O(log N)

• E.

  O(N), O(log N), O(1)

As árvores são estruturas de dados poderosas e se subdividem em vários tipos, cada um dos quais com suas características próprias. Relacione os tipos de árvores, apresentados na coluna da esquerda, com as suas respectivas características, indicadas na coluna da direita.

Estão corretas as associações

• A.

  I –W, II – Z , III – Y.

• B.

  I – Z , II – W , III – X.

• C.

  I –X , II – W , III – Y.

• D.

  I – Z , II – X , III – Y.

• E.

  I –Y , II – W , III – X.