Algoritmos e Programação de Computadores II - COM120 - Atividade Avalitativa - Semana 5

Prévia do material em texto

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 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 valor de cada Se 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 paradigma dividir para conquistar, fazendo com que tempo de busca seja reduzido, pois, a cada do algoritmo, tamanho do vetor é dividido ao Assinale a alternativa que relaciona adequadamente os dois grupos de informações. a. 2-II; 3-III. b. 1-II; 2-III; 1-III; 2-II; d. e. 2-III; Na intenção de mostrar para os alunos a importância da ordenação interna, um professor apresentou 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, algoritmo de ordenação deve ser escolhido considerando tempo utilizado pela 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 Após análise da situação apresentada, avalie as asserções a seguir e a relação proposta entre elas. I. 0 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 acesso a esses elementos ocorre de forma sequencial ou em grandes blocos. A respeito dessas asserções, assinale a alternativa correta. a. A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. b. As asserções e II são falsas. c. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I. d. A asserção é uma proposição falsa, e a II é uma proposição verdadeira. e. As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.Considere a seguinte implementação em Python de um algoritmo de busca: def chave): for i in range(len(v)): if chave return i return -1 O algoritmo de busca implementado acima é a: a. Busca sequencial. b. Busca binária. Busca em largura. d. Busca aleatória. Busca em profundidade. O algoritmo de busca que exige que os elementos estejam ordenados é: a. Busca em profundidade. b. Busca binária. Busca sequencial. d. Busca aleatória. e. Busca em largura. 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 maior valor em sua devida posição e, assim, cada elemento movimenta-se para a posição que lhe pertence Analise as alternativas a seguir e indique a que retrata algoritmo de ordenação citado. a. Heap Sort. b. Quick Sort. Bubble Sort. d. Insertion Sort. e. Merge Sort.0 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 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. ( ) Merge Sort toma como princípio de funcionamento a divisão e a conquista. II. ( ) Merge Sort aplica merge somente uma vez para conseguir ordenar um vetor. III. ( ) Não é realizado merge de dois vetores distintos, mas sim merge de duas partes ordenadas de um vetor. IV. ( ) merge é a rotina que agrega dois vetores ordenados em um terceiro não ordenado. Assinale a alternativa que apresenta a sequência correta. d.F.F.V.V. 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 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 elemento pesquisado (como a[i] 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: a. II, apenas. III, apenas. c. II apenas. II, apenas. apenas.Buscando indicar para aluno uma forma de ordenação com custo mais baixo, professor apresentou seguinte conceito: De acordo com Cormen (2002), a ideia do Heap Sort é a de utilizar uma estrutura de dados que possibilite identificar 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). T.H. 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 A complexidade assintótica do Heapsort não é mas sim O(nlogn). PORQUE II. custo para encontrar menor elemento é O(1), porém, em toda remoção do menor elemento, é preciso que se atualize heap, 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. a. As asserções e II são falsas. b.As asserções e II são proposições verdadeiras, e all é uma justificativa da I. A asserção é uma proposição verdadeira, e all é uma proposição falsa. asserções I e II são proposições verdadeiras, mas a II não é uma justificativa dal. e. A asserção é uma proposição falsa, e all é uma proposição verdadeira.