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

Considere um algoritmo de pesquisa binária em uma estrutura do tipo array composta de sete elementos classificados em ordem crescente. Se a chave de pesquisa for menor que o elemento do meio, essa chave:

• A.

  localizará apenas elementos da segunda metade do array;

• B.

  não poderá achar nenhum elemento com pelo menos duas iterações;

• C.

  localizará apenas elementos da primeira metade do array;

• D.

  não poderá localizar nenhum elemento;

• E.

  localizará o elemento do meio do array de forma menos eficiente que a pesquisa linear.

Analise as seguintes sentenças:

I. No algoritmo de classificação em ordem crescente por seleção, a primeira iteração seleciona o maior elemento no array e troca-o pelo primeiro elemento.

II. O algoritmo de classificação por intercalação é mais rápido e mais complexo que os algoritmos de classificação por seleção e de classificação por inserção.

III. O algoritmo de pesquisa linear é mais eficiente que o algoritmo de pesquisa binária, mas exige que o array seja classificado.

Das sentenças acima, são verdadeiras apenas:

• A.

  I;

• B.

  II;

• C.

  III;

• D.

  I e II;

• E.

  II e III.

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

O algoritmo de Dijkstra utiliza a técnica de relaxamento e produz, ao final de sua execução, uma árvore de caminhos mais curtos entre um vértice origem s e todos os vértices que são alcançáveis a partir de s.

• C. Certo
• E. Errado

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.

• C. Certo
• E. Errado

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):

• A.

  3, apenas.

• B.

  1 e 2, apenas.

• C.

  1 e 3, apenas.

• D.

  2 e 3, apenas.

• E.

  1, 2 e 3.

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:

• A.

  1 - b, 2 - c

• B.

  1 - a, 2 - c

• C.

  1 - a, 2 - b

• D.

  1 - b, 2 - b

• E.

  1 - c, 2 - b

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?

• A.

  2

• B.

  3

• C.

  4

• D.

  8

• E.

  9

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?

• A.

  O(n²)

• B.

  O(1)

• C.

  O(n)

• D.

  O(n log n)

• E.

  O(log n)

Acerca de pseudocódigo, descrição narrativa e fluxograma, que são usados para a descrição de algoritmos, julgue os próximos itens.

Para especificar os passos de um algoritmo, o pseudocódigo utiliza uma linguagem natural com característica pouco formal, o que pode causar ambiguidade e propiciar interpretações errôneas.

• C. Certo
• E. Errado

Acerca de pseudocódigo, descrição narrativa e fluxograma, que são usados para a descrição de algoritmos, julgue os próximos itens.

Uma forma universal de representação de um algoritmo, o fluxograma, ou diagrama de blocos, utiliza figuras geométricas a fim de ilustrar os passos a serem seguidos para a resolução de um problema.

• C. Certo
• E. Errado