Questão 425197

• Banca: COPEVE-UFAL
• Órgão: UFAL
• Ano: 2011
• Provas: COPEVE-UFAL - 2011 - UFAL - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Conceitos Básicos de Estrutura de Dados; Estrutura de Dados

Avaliando as sentenças seguintes a respeito de estrutura de dados,

I. A diferença entre árvore binária simples e árvores AVL é o fato de que a segunda pode se reconfigurar dinamicamente, com o intuito de manter um bom nível de balanceamento.

II. Uma pilha garante que o último elemento inserido seja localizado no seu topo. Porém, do ponto de vista conceitual, qualquer elemento da pilha pode ser removido, ainda que não esteja no seu topo.

III. Do ponto de vista conceitual, não há diferença alguma entre uma estrutura de array e uma lista encadeada.

IV. Tabelas hash são estruturas de dados indicadas para armazenar grande volume de dados. Apesar dessas estruturas permitirem acesso indexado, mais de um elemento pode ter o mesmo índice. Elementos com o mesmo índice podem ser armazenados em uma mesma lista encadeada.

verifica-se que

• A. apenas I e IV são verdadeiras.
• B. apenas I é verdadeira.
• C. apenas III e IV são verdadeiras
• D. apenas II e III são verdadeiras.
• E. apenas I, II e IV são verdadeiras.

Gabarito: A

Comentários

• I. A diferença entre árvore binária simples e árvores AVL é o fato de que a segunda pode se reconfigurar dinamicamente, com o intuito de manter um bom nível de balanceamento. 
  
  VERDADEIRO.
  Em uma árvore binária de busca, quem é maior que um nó vai para a subárvore esquerda, quem é menor vai para a subvarvore direita. 
  
  
  II. Uma pilha garante que o último elemento inserido seja localizado no seu topo. Porém, do ponto de vista conceitual, qualquer elemento da pilha pode ser removido, ainda que não esteja no seu topo. 
  
  ERRADO. Do ponto de vista de implementação tudo é possível - você pode fazer uma pilha que tenha operações de inserção e remoção no começo, no meio e no fim. A única coisa que não se tem solução é não ter bits suficientes. Porém no ponto de vista conceitural  a pilha dispõe apenas das operações PUSH ( colocar na pilha) e POP ( retirar do topo da pilha).
  
  Cada processo que roda no seu computador tem uma pilha em área de memória, além do heap, com os dados do programa.
  
  Essa pilha é fundamental para a execução das instruções. 
  
  III. Do ponto de vista conceitual, não há diferença alguma entre uma estrutura de array e uma lista encadeada. 
  
  FALSO. Um array simboliza uma estrutura contínua de memória. Isto é, você usar usar aritimetrica de ponteiro para percorrer esses endereços de memória isto é, digamos um array de inteiros de 4bytes.
  
  Array[ 0 ]  vai estar na posição x, Array[ 1 ] vai estar na posição x+4 ...
  
  Numa lista encadeada isso não ocorre, os elementos da lista estão dispostos caoticamente ( Já vi questões falando que estão aleatóriamente ) pela memória.
  
  IV. Tabelas hash são estruturas de dados indicadas para armazenar grande volume de dados. Apesar dessas estruturas permitirem acesso indexado, mais de um elemento pode ter o mesmo índice. Elementos com o mesmo índice podem ser armazenados em uma mesma lista encadeada. 
  
  ISSO. Um vetor é uma espécie de tabela hash, mapeando uma chave inteira para um valor.
  
  No caso dos vetores com endereçamento direto não há colisão porque há exatamente uma posição na memória para cada chave. O problema acontece quando temos um universo de chaves muito grandes, como por exemplo strings.
  
  Então seria inviável alocar um espaço para cada chave possivel.  O que se pode fazer é alocar um espaço na memória e cada espaço desse ter uma lista encadeada com todos os elementos cujo o hash da chave colidiram.