O algoritmo de busca que exige que os elementos estejam ordenados é:
Resposta correta: D) Busca binária.
Explicação: a busca binária requer que os elementos estejam ordenados e divide o espaço de busca pela metade a cada iteração.
A pesquisa em memória primária tem a capacidade de encontrar a informação (que é dividida em registros contendo uma chave) desejada em um grande volume de dados. A busca por essa informação requer a escolha de um método de busca que considere a quantidade de dados envolvidos e a periodicidade das operações de inserção e remoção. Considerando a pesquisa em memória primária, avalie as afirmações a seguir em relação aos métodos de pesquisa e as relacione adequadamente aos termos a que se referem.
1. Pesquisa sequencial.
2. Pesquisa binária.
3. Transformação de chave (hashing).
I. Os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de busca.
II. Percorre-se uma lista comparando a chave de busca com o valor de cada posição. Se o valor da chave for igual para alguma posição, então devolva esta posição. Caso a lista toda tenha sido percorrida então devolva -1, indicando que a chave não foi encontrada.
III. Adota o paradigma dividir para conquistar, fazendo com que o tempo de busca seja reduzido, pois, a cada iteração do algoritmo, o tamanho do vetor é dividido ao meio.
Assinale a alternativa que relaciona adequadamente os dois grupos de informações.Resposta correta: D) 1-II; 2-III; 3-I.
Explicação: A correspondência correta é que a Pesquisa Sequencial é II, a Transformação de chave (hashing) é I e a Pesquisa Binária é III, com a opção que reúne 1-II, 2-III, 3-I.
Considere a seguinte implementação em Python de um algoritmo de busca:
def busca(v, chave):
for i in range(len(v)):
if chave == v[i]:
return i
return -1
O algoritmo de busca implementado acima é a:
Resposta correta: C) Busca sequencial.
Explicação: O código percorre a lista linearmente verificando cada elemento até encontrar a chave.
O algoritmo de ordenação Quick Sort escolhe um pivô que corresponde ao primeiro elemento da lista e o troca de posição com o elemento do meio da lista. É iniciada a varredura da lista comparando os elementos com esse pivô, de forma que os elementos _____________ que ele são colocados ou mantidos na lista do lado esquerdo, e os elementos _____________ que ele são colocados ou mantidos na lista do lado direito. Ao realizar esse processo de forma _____________, chega-se ao final com uma lista totalmente ordenada. Preencha as lacunas escolhendo a alternativa correta.
Resposta correta: C) menores — maiores — recursiva.
Explicação: O Quick Sort particiona usando menores e maiores em relação ao pivô, realizando chamadas recursivas para cada partição.
O algoritmo de ordenação Merge Sort é um dos mais eficientes, dividindo de forma repetitiva uma lista em sublistas, até que reste somente um elemento em cada uma dessas sublistas. Após isso, ele começa a fundir essas sublistas e acaba produzindo a lista inicial, porém com seus elementos organizados.
Com base nas informações apresentadas, identifique se são (V) verdadeiras ou (F) falsas as afirmativas a seguir.
I. ( ) O Merge Sort toma como princípio de funcionamento a divisão e a conquista.
II. ( ) O Merge Sort aplica o merge somente uma vez para conseguir ordenar um vetor.
III. ( ) Não é realizado o merge de dois vetores distintos, mas sim o merge de duas partes ordenadas de um vetor.
IV. ( ) O merge é a rotina que agrega dois vetores ordenados em um terceiro não ordenado.
Assinale a alternativa que apresenta a sequência correta.Resposta correta: A) V, F, V, F.
Explicação: O Merge Sort utiliza divisão e conquista; o merge ocorre entre duas sublistas ordenadas, não entre itens fora de ordem.
Considere o detalhamento a seguir em relação a um algoritmo de ordenação que se baseia em comparação local:
1. Se o elemento for o primeiro, ele já encontra-se classificado;
2. É feita a escolha do próximo elemento;
3. Ele é comparado com os elementos na sublista classificada inicialmente;
4. São movidos os elementos na sublista classificada que são maiores que o elemento a ser ordenado;
5. O elemento é inserido;
6. O processo de 1 a 5 é repetido até a sublista classificada ser toda a lista.
Analise as alternativas e indique aquela que contém o algoritmo de ordenação cujo processo de ordenação corresponde aos passos citados.Resposta correta: D) Insertion Sort.
Explicação: O enunciado descreve o insertion sort, onde se constrói uma sublista classificada inserindo o elemento na posição correta.
Na intenção de mostrar para os alunos a importância da ordenação interna, um professor apresentou o seguinte conceito: a ordenação de elementos fundamenta-se em sua organização de forma crescente ou decrescente, a fim de facilitar a pesquisa desses elementos, portanto a ordenação foca em facilitar buscas por um elemento que são realizadas em um determinado conjunto de dados. Desse modo, o algoritmo de ordenação deve ser escolhido considerando o tempo utilizado pela ordenação. Após a explicação, um aluno questiona: a escolha do algoritmo de ordenação interna deve basear-se no número de elementos, e não no tempo que a ordenação leva. Após análise da situação apresentada, avalie as asserções a seguir e a relação proposta entre elas.
I. O aluno está certo, a escolha pelo algoritmo de ordenação interna deve tomar como base a quantidade de elementos que compõem a lista.
PORQUE
II. Na existência de uma grande quantidade de elementos a serem ordenados, eles não se acomodam na memória principal, e o acesso a esses elementos ocorre de forma sequencial ou em grandes blocos.
A respeito dessas asserções, assinale a alternativa correta.
Resposta correta: C) As asserções I e II são falsas.
Explicação: A escolha pelo algoritmo de ordenação interna não deve depender apenas da quantidade de elementos, especialmente quando o tempo de ordenação e o uso de memória são fatores relevantes; a II não é uma justificativa válida para I neste contexto.
Os algoritmos de ordenação reúnem um conjunto de instruções que recebem um array ou lista como entrada e organizam os itens em uma ordem específica. Existe um algoritmo de ordenação em que são realizadas diversas passagens por meio de uma lista, comparando os elementos vizinhos e trocando-os, caso estejam fora de ordem. Dessa forma, a cada passagem pela lista, coloca-se o maior valor em sua devida posição e, assim, cada elemento movimenta-se para a posição que lhe pertence.
Resposta correta: B) Bubble Sort.
Explicação: O enunciado descreve o Bubble Sort, onde repetidas passagens trocam adjacentes para colocar o maior elemento na posição final.
Há um algoritmo eficiente para encontrar um elemento presente em uma lista ordenada que, repetidas vezes, separa a parte da lista que contém o elemento, a fim de reduzir as possíveis localizações a somente uma localização, sendo assim, a __________ inicia com um palpite da localização do elemento procurado que sempre é o elemento localizado no __________ do vetor, caso o palpite seja correto, significa que o elemento foi encontrado, mas se o palpite for errado então o próximo palpite fica restrito a uma parte do vetor porque ele encontra-se __________.
Resposta correta: C) busca binária — meio — ordenado.
Explicação: Em busca binária, o índice "meio" é utilizado, o vetor está ordenado, e a busca restringe-se à metade correspondente a cada passo.
Buscando indicar para o aluno uma forma de ordenação com custo mais baixo, o professor apresentou o seguinte conceito: De acordo com Cormen (2002), a ideia do Heap Sort é a de utilizar uma estrutura de dados que possibilite identificar o menor elemento a um custo mais baixo do que na utilização de um vetor. Considerando um heap, temos que a complexidade assintótica do Heap Sort é O(logn).
CORMEN, T. H. Algoritmos: teoria e prática. São Paulo: Editora Campus, 2002.
Após análise do problema apresentado, observe as asserções a seguir e a relação proposta entre elas.
I. A complexidade assintótica do Heapsort não é O(logn), mas sim O(nlogn).
PORQUE
II. O custo para encontrar o menor elemento é O(1), porém, em toda remoção do menor elemento, é preciso que se atualize o heap, o que leva a uma complexidade O(logn) e, considerando n elementos do vetor de entrada, temos O(nlogn).
A respeito dessas asserções, assinale a alternativa correta.
Resposta correta: E) As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.
Explicação: I afirma a complexidade O(n log n) para Heapsort; II explica a razão da complexidade, pois cada remoção do menor envolve O(log n) para manter o heap.
Os algoritmos de busca são aplicados em problemas em que existe uma chave de busca e uma coleção de elementos que têm um identificador único. O objetivo é verificar se há algum elemento nessa coleção que seja idêntico à chave de busca fornecida.
Com relação à busca linear ou sequencial, observe as afirmações a seguir.
I. Sua utilização é adequada nos casos em que existem informações adicionais sobre os elementos que se deseja pesquisar.
II. A busca linear finaliza ao se encontrar o elemento pesquisado (como a[i] == x) ou após ter sido percorrida toda a lista e ele não ter sido encontrado.
III. A busca linear compara se a chave de busca é igual ao elemento posicionado no meio da lista e retorna para a posição.
IV. A implementação da busca linear ou sequencial é feita usando-se uma função recursiva.
Está correto que se afirma em:
Resposta correta: E) II, apenas.
Explicação: A busca linear é definida para percorrer a lista até encontrar o elemento ou até o fim; não requer busca no meio nem necessariamente recursão.