Questões de Concurso sobre Métodos de ordenação

O trecho de código em linguagem JavaScript a seguir solicita a inserção do nome de cinco produtos, que são ordenados e então exibidos.

(() => {

const produtos = [];

for (let i = 0; i < 5; i++) {

let nome;

do {

nome = prompt(`Digite o nome do produto: ${i + 1}:`).trim();

} while (!nome);

produtos.push(nome);

}

produtos.sort((a, b) => b.localeCompare(a, 'pt-BR', { sensitivity:

'base' }));

const ul = document.getElementById('lista');

produtos.forEach(p => {

const li = document.createElement('li');

li.textContent = p;

ul.appendChild(li);

});

})();

Supondo que todos os nomes inseridos sejam diferentes entre si, indique qual será a ordem exibida ao final das cinco inserções.

Em um TAD de mensagens, deseja-se reduzir aliasing e facilitar comparação por conteúdo. Marque a alternativa que melhor atende a esse objetivo.

Considere o seguinte algoritmo, em que a e b são arranjos com n elementos indexados a partir de 1:

Se n = 5 e a = [3, 1, 8, 4, 7], então, após a execução do algoritmo, o arranjo b será

O algoritmo MERGE SORT emprega a técnica “divisão e conquista” para ordenar uma lista de valores. A ordem de complexidade deste algoritmo, no pior caso, é:

Considere as afirmativas abaixo sobre estruturas de dados homogêneas e heterogêneas, incluindo vetores e matrizes, registros, listas, filas, pilhas e árvores, métodos de busca e ordenação, e recursividade. Sobre o assunto, julgue as seguintes afirmações como verdadeiras (V) ou falsas (F):

(__)A complexidade de tempo do algoritmo de ordenação Bubble Sort no pior caso é O(n²).

(__)As listas ligadas permitem inserções e remoções eficientes em qualquer posição, mas ocupam mais memória devido ao armazenamento de ponteiros.

(__)A recursividade é uma técnica de programação onde uma função faz chamadas a si mesma, podendo ser substituída por uma estrutura de repetição em qualquer situação.

Assinale a alternativa cuja respectiva ordem de julgamento esteja correta:

Considere as definições de algoritmos determinísticos e não determinísticos e as classes de problemas P e NP. De acordo com Ziviani (2007), um problema pode ser classificado como pertencente à classe NP caso ______. Assinale a alternativa que preencha corretamente a lacuna.

Considere as funções abaixo e determine a complexidade do algoritmo de ordenação da função “ordena”, usando a notação Big-O;

Na área de Análise de Algoritmos, a notação assintótica é fundamental para descrever a complexidade de algoritmos. Considere as seguintes definições e propriedades da notação assintótica: O-notation (O grande), Ω-notation (Ômega grande), e Θ-notation (Theta grande). Qual das afirmativas a seguir é a mais correta em relação à análise assintótica de algoritmos?

Considere os seguintes algoritmos, todos com complexidade assintótica O(n):

Algoritmo 1: executa uma iteração simples sobre uma lista de tamanho n.

Algoritmo 2: executa duas iterações simples sobre uma lista de tamanho n, uma após a outra.

Algoritmo 3: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação constante que leva t_C tempo.

Algoritmo 4: executa uma iteração sobre uma lista de tamanho n e, dentro dessa iteração, realiza uma operação constante k vezes, em que o tempo total das operações é k * t_D e(k * t_D > t_C).

Algoritmo 5: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação com complexidade O(1).

Qual dos algoritmos é menos eficiente em termos de tempo de execução, embora todos tenham a mesma complexidade assintótica O(n)?

Medir a complexidade dos métodos de ordenação é fundamental para entender o desempenho desses algoritmos e poder fazer escolhas adequadas dependendo do contexto do problema. Qual método de ordenação o pior caso tem a mesma complexidade do método Quick Sort no pior caso?

Observe a seguinte amostra:

10, 20, 30, 42, 50, 58

É correto afirmar que a média e a mediana desta amostra são respectivamente:

Qual é o método de ordenação que percorre a lista de elementos, comparando os adjacentes (pares consecutivos) e trocando-os de posição, caso não estejam em ordem?

O algoritmo k-vizinhos mais próximo (k-NN) é utilizado em tarefas de análise preditiva. Analise as afirmativas a seguir relativas ao algoritmo k-NN.

I O algoritmo k-NN classifica os pontos com base nas distâncias entre eles e seus k vizinhos mais próximos.

II O valor de k deve ser escolhido aleatoriamente e não tem impacto no desempenho do modelo k-NN.

III O algoritmo k-NN é sensível à escala das variáveis de entrada e geralmente requer normalização dos dados antes de ser aplicado.

É correto o que se afirma em

Considere o conceito de complexidade polinomial, definido como O(p(n)), onde p(n) é um polinômio e O representa o limite superior da complexidade de um algoritmo. Algoritmos que pertencem à classe P são aqueles que possuem soluções algorítmicas cuja complexidade é limitada por um polinômio de grau k, ou seja, O(n^k) para alguma constante k. Esse tipo de problema é considerado solucionável em tempo "razoável" ou eficiente. Dado esse contexto, analise as afirmativas a abaixo sobre a classe P e a complexidade polinomial.

I. Algoritmos de ordenação como a ordenação por inserção têm uma complexidade polinomial de O(n²), o que os coloca na classe P.

II. A classe P engloba todos os problemas que podem ser resolvidos por algoritmos em tempo polinomial, independente de hardware.

III. Algoritmos de pesquisa binária, embora eficientes, não são classificados como pertencentes à classe P, pois sua complexidade é logarítmica, e não polinomial.

IV. Um algoritmo que possui uma complexidade de tempo O(n^k), onde k é constante, resolve o problema no pior caso em tempo polinomial e, portanto, pertence à classe P.

Estão corretas as afirmativas:

Algoritmos para assimilação de dados geralmente envolvem cálculos complexos que dependem de diversos fatores, como o tamanho dos espaços de estados, número de pontos da grade em questão, tamanho da janela de assimilação, etc. Frequentemente, observa-se que dois algoritmos usados para solucionar um mesmo problema podem ter eficiências diferentes, por conta de diferenças em suas implementações.

Uma maneira de se mensurar e representar a complexidade de um algoritmo é contabilizar o número de operações de ponto-flutuante (flops) necessárias para executá-lo e utilizar a notação “O-grande”.

Considere o algoritmo a seguir, implementado em uma linguagem de pseudocódigo autoexplicativa.

A complexidade desse algoritmo será

Considere a seguinte sequência de passos para ordenar o vetor:

O algoritmo de ordenação utilizado foi o

Qual alternativa apresenta somente a cláusula e as palavras-chave que podem ser utilizadas para ordenação na linguagem SQL?

Dadas as diferentes técnicas e fatores que influenciam a escolha do melhor algoritmo de ordenação, considere o seguinte cenário: o desenvolvedor precisa ordenar um grande conjunto de dados parcialmente ordenados, em um sistema que possui memória limitada e um processador de baixo desempenho.

Qual é a abordagem mais apropriada para escolher o algoritmo de ordenação ideal?

Analise o algoritmo a seguir, que é apresentado na forma de uma psedolinguagem (Português Estruturado).

Assinale a alternativa que apresenta o valor impresso ao final da execução desse algoritmo, considerando que os valores lidos para b1 e b2 tenham sido, respectivamente, 3 e 6.

Relacione adequadamente as colunas a seguir sobre os métodos de ordenação à sua descrição correspondente.

1. Bubble Sort.

2. Merge Sort.

3. Quick Sort.

4. Selection Sort.

5. Insertion Sort.

( ) Divide a lista em sublistas menores; ordena essas sublistas e as mescla para obter a lista ordenada.

( ) Algoritmo de comparação que percorre repetidamente a lista; compara elementos adjacentes e troca-os se estiverem na ordem errada.

( ) Divide a lista em duas partes; ordena-as individualmente e combina-as para obter a lista ordenada.

( ) Algoritmo que seleciona iterativamente o elemento mínimo da lista e coloca-o na posição correta.

( ) Algoritmo de comparação que escolhe um elemento como pivô; divide a lista em dois subconjuntos e ordena-os recursivamente.

A sequência está correta em