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

Para poder ser aplicado, o algoritmo de pesquisa binária exige que os elementos do array:

O algoritmo de ordenação baseado em vários percursos sobre o array, realizando, quando necessárias, trocas entre pares de elementos consecutivos denomina-se método:

Considere o seguinte algoritmo, responsável por realizar a ordenação de um array de dados.

Podemos afirmar que o método de ordenação utilizado pelo algoritmo é o:

Para projetar algoritmos eficientes um desenvolvedor deve estar preocupado com a complexidade deste algoritmo, desde sua concepção.

Considere a seguinte função T(n) que mede os recursos (ex. tempo de execução) que um algoritmo necessita no pior caso para processar uma entrada qualquer de tamanho n:

T(n) = O(log(n))

Sabendo que O(log(n)) é a ordem da complexidade de tempo do algoritmo seguindo a notação "big O", é correto afirmar que este algoritmo tem complexidade de ordem: 

Assinale a alternativa que apresenta corretamente a sequência de passos computacionais que transforma a entrada na saída, ou seja, procedimentos necessários para resolver um determinado problema.

Analise o trecho de código a seguir. Avariável x representa o elemento de referência passado como parâmetro while( inicio <= termino ) { meio = ( inicio + termino ) / 2; if( a[ meio ].compareTo( x ) < 0 ) inicio = meio + 1; else if( a[ meio ].compareTo( x ) > 0 ) termino = meio - 1; else return meio; } A qual algoritmo esse código pertence?

Qual é o método de ordenação mais eficiente entre os listados a seguir?

Qual é o tipo de algoritmo de ordenação que tem como princípio percorrer o vetor diversas vezes, a cada passagem fazendo o maior elemento se mover para o final da estrutura?

Observe a seguir um código simples para execução de um loop.

for (int i = 0; i < 3; i++);

p=p+1;

Após analisar esse código, pode-se afirmar que o comando p=p+1 será executado:

Avalie se são verdadeiras (V) ou falsas (F) as afirmativas a seguir.

I O método de busca “pesquisa binária” necessita de um ordenamento prévio do vetor.

II O método “pesquisa binária” possui o tempo de busca maior que o método “busca sequencial”.

III O método “busca sequencial” é mais indicado quando se sabe antecipadamente que a maior parte dos registros necessita ser pesquisada.

As afirmativas I, II e III são, respectivamente:

Os comandos de repetição são utilizados em algoritmos para realizar, principalmente, repetição de instruções. Assinale a alternativa que NÃO apresenta comando de repetição.

Uma sequência de números é um Tipo Abstrato de Dados (TAD) que representa um conjunto finito de valores ordenados, no qual um valor pode ocorrer em duplicidade. Considere as seguintes afirmações sobre a implementação de uma sequência de números utilizando arranjos e listas ligadas:

I Arranjos permitem acesso a qualquer elemento da sequência com complexidade de tempo média constante.

II Listas ligadas não permitem a inserção de um elemento no início da sequência com complexidade de tempo média constante.

III Listas ligadas requerem que a sequência seja armazenada em uma faixa contínua de endereços de memória

IV Arranjos não permitem a inserção de um elemento no meio da sequência com complexidade de tempo média constante.

Estão corretas as afirmações

Analise o retorno para o seguinte algoritmo.

A saída produzida pelo código acima é

Observe a seguinte lógica de programação.

Este algoritmo escreve a saída

Considerando-se a definição sobre autômatos finitos e linguagens, assinale a única alternativa que contém a disposição correta (da esquerda para a direita) dos tipos de gramática segundo o critério da abrangência das linguagens geradas (gramática mencionada gera linguagem que abrange a linguagem gerada pela gramática a sua direita – hierarquia de Chomsky).

Leia as afirmativas a seguir a respeito das principais classes de comportamento assintótico. I) A complexidade logarítmica é típica de algoritmos que resolvem problemas, transformando-os em problemas menores e depois agrupando as soluções dos problemas menores. II) A complexidade quadrática é típica de algoritmos onde os dados são processados ao pares muitas vezes com um anel dentro de outro. III) Um algoritmo com complexidade exponencial é mais rápido que um algoritmo linear. IV) Um algoritmo com complexidade n! (n fatorial) apresenta um comportamento pior que um algoritmo com complexidade 2ⁿ . V) A complexidade do algoritmo de pesquisa binária é logarítmica. Assinale a alternativa que apresenta somente as afirmativas CORRETAS.

Leia as afirmativas a seguir considerando que f(n) e g(n) são funções positivas. I) Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo f(n) possui Ordem de complexidade g(n). II) Se g(n) é O(f(n)), f(n) é um limite superior para g(n). III) Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)). IV) Se g(n) = n² e f(n) = (n+1)² temos que g(n) é O(f(n)) e f(n) é O(g(n)). V) Se g(n) = 2ⁿ⁺¹ e f(n) = 2ⁿ temos que g(n) = O(f(n)). Assinale a alternativa que apresenta somente as afirmativas CORRETAS.

Considere a função de complexidade f(n) = 3n³ + 4n² +2n. Selecione a opção abaixo contendo o menor valor para a constante c, c>0, para que g(n) = c.n³ domine assintoticamente f(n), para n>= 1.