Questão 1348837

• Banca: CESPE / CEBRASPE
• Órgão: INMETRO
• Ano: 2010
• Provas: CESPE - 2010 - INMETRO - Pesquisador Tecnologista em Metrologia e Qualidade - Informática Aplicada à Metrologia Legal
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Filas; Listas

A armazenagem de dados é importante para que, quando for necessário, esses dados possam ser apresentados automaticamente em uma ordem predeterminada. Os dados podem ser recuperados na mesma ordem de armazenamento ou em ordem diferente. Considerando que as estruturas de dados auxiliam na realização de tais operações, assinale a opção correta.

• A. Considere que cinco documentos (doc1, doc2, doc3, doc4 e doc5) estejam em uma fila para impressão e que o operador deseje imprimir imediatamente os documentos doc1, doc3 e doc5, deixando doc2 e doc4 em ordem na fila. Considere, ainda, que a operação de fila insere (x) insira o elemento x no final da fila, e que remove( ) seja a função que promove o retorno do elemento retirado à fila. Nessa situação, a sequência de operações para o resultado pretendido é: remove( ), insere(remove( )), remove( ), insere(remove( )), remove( ).
• B. Na implementação das listas de encadeamento circulares, cada elemento da lista possui um ponteiro para o elemento que o precede. Assim, ao se retirar um elemento da lista, pode-se definir o ponteiro nextdo elemento precedente para o elemento posterior àquele que será removido.
• C. Considere que Roberto tenha feito uso de uma lista encadeada simples para programar o armazenamento e o posterior acesso aos dados acerca dos equipamentos instalados em sua empresa. Considere, ainda, que, após realizar uma consulta acerca do equipamento X, Roberto precisou acessar outro equipamento Y que se encontrava, nessa lista, em posição anterior ao equipamento X. Nessa situação, pela forma como os ponteiros são implementados em uma lista encadeada simples, o algoritmo usado por Roberto realizou a consulta ao equipamento Y sem reiniciar a pesquisa do começo da lista.
• D. Em uma árvore de busca binária, o sucessor de um elemento x é o último elemento de valor inferior a x. Assim, para se achar o sucessor desse elemento x, é suficiente caminhar a partir de x, seguindo tantos ponteiros direitos quanto possível, até se alcançar o fim da ramificação. O elemento, ao final da ramificação, será o sucessor de x.
• E. As representações de vetores em árvores binárias que são balanceadas pela esquerda contêm brechas formadas por nodos não utilizados. Em árvores binárias balanceadas pela esquerda, os nodos ficam sem utilização entre as posições n/2 e n.

Gabarito: A

Comentários

• Não entendi essa função remove(). Ela já faz o elemento retornar à fila?
  

• doc1, doc2, doc3, doc4, doc5

  Primeiro remove: remove( ), insere(remove( )), remove( ), insere(remove( )), remove( )

  doc2, doc3, doc4, doc5

  Depois  insere(remove( )). remove( ), insere(remove( )), remove( ), insere(remove( )), remove( )

  doc3, doc4, doc5, doc2 

  Depois do terceiro comando  remove( ), insere(remove( )), remove( ), insere(remove( )), remove( )

  doc4, doc5, doc2 

  Depois do quarto comando  remove( ), insere(remove( )), remove(), insere(remove( )), remove( )

  doc5, doc2, doc4

  Finalmente o último remove remove( ), insere(remove( )), remove( ), insere(remove( )), remove( )

  doc2, doc4

  Gabarito A.