Questões de Concurso Comentadas sobre algoritmos e estrutura de dados

Assinale a alternativa que indica corretamente o que ocorre quando um programador atribui um valor para uma posição além do tamanho do vetor. Por exemplo, suponha que um vetor VET foi definido com 10 posições e o programador tentou fazer a operação VET[15]=1.

Considere o problema de ordenar em ordem crescente o array formado pelos números [67, 23, 11, 18, 87, 44] utilizando o Método da Seleção Direta. Assinale a alternativa que mostra o posicionamento dos números no array após ter sido realizada a primeira troca.

A respeito de um algoritmo recursivo, analise as afirmativas abaixo e assinale a alternativa correta.

I. Deve conter pelo menos uma estrutura de repetição.

II. Deve conter pelo menos uma estrutura de seleção.

III. Deve invocar a si mesmo pelo menos uma vez ao ser executado.

Considere a seguinte definição: “Uma estrutura de seleção permite a escolha de um grupo de ações e estruturas, contido na estrutura de seleção, a ser executado quando determinadas condições, representadas por expressões lógicas, são ou não satisfeitas”. Com base nessa definição, analise as afirmativas abaixo e assinale a alternativa correta.

I. Uma estrutura de seleção deve conter pelo menos outra estrutura de seleção.

II. O grupo de ações existente dentro de uma estrutura de seleção pode não ser executado.

III. Uma estrutura de seleção sempre deve conter dois grupos de ações: um que é executado caso a expressão lógica seja verdadeira e outro que é executado caso a expressão lógica seja falsa.

Considere as seguintes afirmações sobre algoritmos e estruturas de dados:

I. Filas são estruturas do tipo FIFO (First In First Out).

II. A inserção no fim de uma lista duplamente encadeada e não ordenada é realizada em O(n).

O tempo de execução do algoritmo quicksort no pior caso é O(n² ).

Assinale a opção CORRETA:

Sobre linguagens recursivas e recursivamente enumeráveis, é correto afirmar que

Avalie as afirmações abaixo:

I. A classe P e a classe NP são disjuntas.

II. A classe P é um subconjunto da classe co-NP.

III. Problemas coNP-completos admitem um certificado tal que uma resposta negativa pode ser verificada em tempo polinomial.

IV. A interseção das classes NP e co-NP é vazia.

Está correto apenas o que se afirma em

A teoria de algoritmos de aproximação, às vezes chamados de algoritmos aproximativos, é extremamente útil para tratar problemas NP-difíceis.

Sobre algoritmos de aproximação, é correto afirmar que

Uma transformação polinomial é uma ferramenta fundamental na demonstração de que determinado problema é NP-difícil.

Avalie as afirmações sobre propriedades que transformações polinomiais devem satisfazer.

I. Para toda transformação polinomial, deve existir uma Máquina de Turing determinística que a computa em tempo polinomial.

II. Se uma transformação polinomial transforma um elemento de linguagem A em um elemento de linguagem B, então A é um subconjunto não necessariamente próprio de B.

III. Se uma transformação polinomial transforma um elemento de uma linguagem A em um elemento de linguagem B, e A pertence a NP, então B pertence a NP.

IV. A quantidade de espaço utilizada pela transformação pode ser limitada por uma constante.

Está correto apenas o que se afirma em

Sobre uma importante classe de complexidade, a classe dos problemas NP-completos, NÃO se pode afirmar que

Tendo como entrada um grafo acíclico dirigido ponderado G = (V, E), pode-se calcular o caminho mínimo de origem única,

A obtenção das componentes fortemente conexas de um grafo dirigido G = (V, E) é feita da seguinte forma:

Para se projetar um Algoritmo por indução, deve-se garantir que seja possível solucionar

A função da Memoização na estratégia Top-Down para a solução de problemas, utilizando Programação Dinâmica, é implementar um algoritmo