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

Acerca de algoritmos, estruturas de dados e lógica de programação, julgue os itens subsequentes.

A árvore geradora mínima de um grafo conexo não direcionado construída com o algoritmo de Kruskal é única. Nessa árvore geradora mínima, a substituição de arestas de mesmo peso não afetará o custo total da árvore.

Sobre algoritmos de busca em listas que utilizam o artifício chamado de sentinela, analise as seguintes afirmativas:

1. Um registro sentinela contém a chave procurada.

2. Condição de parada da busca é encontrar a chave procurada.

3. Considerando índices variando de 1 a N, onde N é a quantidade de elementos na lista, a busca pode só encontrar a chave procurada na posição N + 1.

 Está(ão) correta(s) a(s) afirmativa(s):

Considere os seguintes nomes e categorias de algoritmos de ordenação:

1. BubbleSorter

2. HeapSorter

 a. Categoria Inserção

b. Categoria Troca

c. Categoria Seleção

Assinale a alternativa que contém apenas relações corretas entre nome de algoritmo e sua categoria:

Seja o seguinte vetor, ordenado de forma ascendente:

Caso se utilize um algoritmo de busca binária, quantas iterações serão necessárias para que o valor 80 seja encontrado?

Considerando-se a análise assintótica (Notação Big O), qual é a complexidade do caso médio do algoritmo de ordenação chamado de Ordenação por Inserção?