Questão 24 Considere as seguintes estruturas de dados:
(I) Tabela Hash
(II) Fila
(III) Árvore de pesquisa
(IV) Pilha

Qual ou quais das estruturas acima requer mais do que tempo médio constante para inserção de um elemento?

a) Somente (I)
b) Somente (II)
c) Somente (III)
d) Somente (IV)
e) Todas.

Gabarito: c (Selecione o texto a esquerda para ver a resposta ou consulte o fim do post).

Explicação: Esta questão exige o conhecimento de como realizar inserção em cada uma destas estruturas.

Vamos analisar cada uma delas:
(I) Tabela Hash: posição = função_de_disperção(chave); hash[posição]=chave;//Apenas uma conta e uma atribuição!
Tempo médio: O(1) que é constante

(II) Fila: posição = início_da_fila; fila[posição]=chave; //Apenas duas atribuições!
Tempo médio: O(1) que é constante

(III) Árvore de pesquisa: posição = busca_binária(chave); arvore[posição]=chave; //Busca binária para encontrar posição e uma atribuição!
Tempo médio: O(lg n) da busca binária que não é constante

(IV) Pilha: posição = topo_da_pilha; fila[posição]=chave; //Apenas duas atribuições!
Tempo médio: O(1) que é constante

Obs: Foram apresentadas pseudo-inserções somente com a parte que nos interessa para a questão!

A única que não é constante é a árvore de pesquisa que necessita de lg n. Alternativa c é a resposta correta!

Não concorda? 
Comente, opine e demonstre seu conhecimento!

Gabarito: c