2 questoes de vestibular (TDA) e (HEAPS)

tokk0
(usa CentOS)

Enviado em 10/06/2014 - 08:38h

Eu sei qual a resposta + não consigo entende-la o porque de ser elas alguém poderia me explicar o básico ou me direcionar a um lugar que descubra ?

4) (ENADE 2011 – Computação) As filas de prioridades (heaps) são estruturas de dados importantes no projeto de algoritmos. Em especial, heaps podem ser utilizados na recuperação de informação em grandes bases de dados constituídos por textos. Basicamente, para se exibir o resultado de uma consulta, os documentos recuperados são ordenados de acordo com a relevância presumida para o usuário. Uma consulta pode recuperar milhões de documentos que certamente não serão todos examinados. Na verdade, o usuário examina os primeiros m documentos dos n recuperados, em que m é da ordem de algumas dezenas. Considerando as características dos heaps e sua aplicação no problema descrito acima, avalie as seguintes afirmações.

I. Uma vez que o heap é implementado como uma árvore binária de pesquisa essencialmente completa, o custo computacional para sua construção é O(n log n).
II. A implementação de heaps utilizando-se vetores é eficiente em tempo de execução e em espaço de armazenamento, pois o pai de um elemento armazenado na posição i se encontra armazenado na posição 2i+1.
III. O custo computacional para se recuperar de forma ordenada os m documentos mais relevantes armazenados em um heap de tamanho n é O(m log n).
IV. Determinar o documento com maior valor de relevância armazenado em um heap tem custo computacional O(1).

Está correto apenas o que se afirma em:
A) I e II.
B) II e III.
C) III e IV.
D) I, II e IV.
E) I, III e IV.

5) (ENADE 2011 – Computação) O conceito de Tipo de Dados Abstrato (TDA) é popular em linguagens de programação. Nesse contexto, analise as afirmativas a seguir.

I. A especificação de um TDA é composta das operações aplicáveis a ele, da sua representação interna, e das implementações das operações.
II. Dois mecanismos utilizáveis na implementação de um TDA em programas orientados a objetos são a composição e a herança.
III. Se S é um subtipo de outro T, então entidades do tipo S em um programa podem ser substituídas por entidades do tipo T, sem alterar a corretude desse programa.
IV. O encapsulamento em linguagens de programação orientadas a objetos é um efeito positivo do uso de TDA.

É correto apenas o que se afirma em:

A) I.
B) II.
C) I e III.
D) II e IV.
E) III e IV.