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

Sobre complexidade de algoritmos, analise as assertivas abaixo.

I. Um algoritmo com complexidade O(n²) levará sempre mais tempo para executar do que um algoritmo com complexidade O(n).

II. O algoritmo de busca binária em um vetor ordenado tem complexidade O(log₂n).

III. A notação Grande-O (em inglês, Big-O) define uma cota assintótica superior a menos de constantes.

Quais estão corretas?

• A.

  Apenas I.

• B.

  Apenas II.

• C.

  Apenas I e II.

• D.

  Apenas II e III.

• E.

  I, II e III.

Sejam as seguintes proposições sobre o algoritmo de busca bináriaemvetor:

I. Para que o algoritmo produza um resultado correto, o vetor sobre o qual ele é aplicado tem que estar ordenado segundo a chave de busca utilizada.

II. Embora ele seja mais eficiente do que o algoritmo de busca sequencial, a complexidade de ambos é a mesma.

III. Existem implementações iterativas e recursivas deste algoritmo.

Marque a alternativa correta em relação às proposições acima.

• A.

  Apenas as proposições I e II são verdadeiras.

• B.

  Apenas as proposições II e III são verdadeiras.

• C.

  Apenas as proposições I e III são verdadeiras.

• D.

  As proposições I, II e III são verdadeiras.

• E.

  As proposições I, II e III são falsas.

Julgue os itens seguintes, relativos a grafos.

A implementação de um grafo do tipo ponderado e direcionado na forma de uma matriz de adjacência utiliza menor quantidade de memória que a implementação desse mesmo grafo na forma de uma lista encadeada.

• C. Certo
• E. Errado

Julgue os itens seguintes, relativos a grafos.

Um algoritmo que visita todos os vértices de um grafo, cada um somente uma vez, está percorrendo o grafo. Esse algoritmo pode percorrer o grafo em largura ou em profundidade.

• C. Certo
• E. Errado

Julgue os itens seguintes, relativos a grafos.

Um grafo não direcionado é dito conectado quando há pelo menos um caminho entre dois vértices quaisquer do grafo.

• C. Certo
• E. Errado

Julgue os itens seguintes, relativos a grafos.

Uma árvore de espalhamento de um grafo ponderado conectado é mínima se a soma dos pesos de todas as arestas for mínima.

• C. Certo
• E. Errado

Julgue os itens seguintes, relativos a grafos.

Um grafo completo contém pelo menos um subgrafo ponderado.

• C. Certo
• E. Errado

Com relação a métodos de pesquisa de dados, julgue os itens subsecutivos.

A pesquisa sequencial e o método da bolha são métodos pouco eficientes de busca de dados.

• C. Certo
• E. Errado

Com relação a métodos de pesquisa de dados, julgue os itens subsecutivos.

A busca binária é realizada em um grupo de dados previamente ordenado.

• C. Certo
• E. Errado

Acerca da utilização de algoritmos e fluxogramas em lógica de programação, julgue os itens a seguir.

A busca de padrões chamada de força bruta é realizada enumerando-se todas as possíveis configurações das entradas envolvidas e escolhendo-se a melhor entre as configurações enumeradas.

• C. Certo
• E. Errado