prova programacao 3

Prévia do material em texto

"Você deve pensar algoritmo dividir-e-conquistar como tendo três partes: 1. Dividir 0 problema em um número de subproblemas que sejam partes menores do mesmo problemas. 2. Conquistar os subproblemas resolvendo-os recursivamente. Se eles forem pequenos 0 suficiente, resolva subproblemas como problemas base. 3. Combinar as soluções dos subproblemas em uma solução para 0 problema original." https://pt.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/divide-and-conquer-algorithmm São exemplos de algoritmo de divisão e conquista Nota: 10.0 A Insertion sort Bublesort Mergesort Quicksort Você assinalou essa alternativa Você acertou! Aula temas1 Bubblesort Quicksort D Selection sort Bubblesort Questão 2/12 Programação III Considere 0 algoritmo abaixo: def bubble com flag(dados): tam len(dados for in range(0, tam, 1): flag 0 for range(0, tam 1, if dados[i] dados[i 1]: aux dados[i] dados[i] dados[i + 1] dados[i 1] aux flag 1 if flag 0: return dados Considere 0 seguinte conjunto de dados: dados [9,5,7,3,1] Quando V for igual a 1 e após executado 0 terceiro passo do laço for interno, elementos em dados terão a seguinte ordem: Nota: 10.0 A 5,7,3,1,9 5,3,1,7,9 Você assinalou essa alternativa (B) Você acertou! aula 2 tema 1 C 3,1,5,7,9 D 5,1,3,7,9 E 5,3,7,1,9 Observe trecho do algoritmo abaixo e analise seu comportamento 0 troca 1 whileOs métodos de ordenação são algoritmos muito utilizados quando é necessário que dados de uma lista de valores, originalmente desordenada, sejam recuperados de maneira ágil e Entre métodos de ordenação eficientes, alguns dos mais conhecidos são aqueles que utilizam a estratégia da divisão e conquista, na qual um problema deve ser dividido em vários problemas menores, que serão solucionados até que 0 problema maior possa ser completamente Vetorazzo, Adriana de, et al. Estrutura de dados. Disponível em: Minha Biblioteca, Grupo 2018 pag43 (modificado) Considerando texto base e conteúdo aprendido em aula são feitas as seguintes afirmações: São exemplos de algoritmos de divisão e conquista Merge sort Quicksort II. Bubble sort é também conhecido como algoritmo de ordenação por III. Quick sort define um elemento chamado pivô para se iniciar as Estão corretas as Nota: 10.0 A le III somente. Você assinalou essa alternativa Você acertou! Aula 2. Tema1(bubble sort), tema2 (Merge Sort) tema4(quick sort) D III somente E III Questão 5/12 Programação III Ler em voz alta Uma função Hash representa aplicação de um algoritmo sobre determinado arquivo que é imutável, fixo único para cada Qualquer alteração no arquivo, mesmo que seja simples configuração de acréscimo ou supressão de caractere, resultará em alteração da função Karina Bastos Blockchain smart contracts As inovações no âmbito do Direito Editora 2022 Pag 35 Quanto as funções hash, são feitas as seguintes I Algoritmo de uma expressão aritmética e/ou lógica específica para resolver uma determinada aplicação A função hash apresenta uma fórmula sendo projetada levando se em consideração apenas tamanho do conjunto de dados desenvolvimento de uma boa função de hash essencial para que 0 armazenamento dos dados, busca tratamento de colisões ocorram de forma mais eficiente Assinale alternativa que tem apenas afirmativa(s) A apenas apenas C apenas D apenas Você acertou! Aula tema "A análise de um algoritmo geralmente conta com apenas algumas operações elementares em muitos casos, apenas uma operação Além disso, essa análise costuma ser feita tendo como base um modelo independente de máquina; isto é, expressão de consumo de tempo é feita abstraindo particularidades como a linguagem de programação, detalhes de implementação computador Esse modelo de computação, conhecido como RAM (do inglês random access máquina de acesso em portuguesa) assume seguintes custos associados às operações executadas por um computador Cada operação simples (operações comparações invocações de métodos) custam exatamente um passo de tempo. Laços (loops) sub-rotinas não são considerados operações Ao contrário, eles são composição de múltiplas operações de um passo de tempo Assim, 0 tempo necessário para executar um laço ou um subprograma depende do número de iterações do laço ou da natureza específica do subprograma Cada acesso à requer exatamente um passo de tempo. Serpa, Matheus da, S et Análise de Algoritmos Disponível em: Minha Grupo 2021 pag 51-52 Observe algoritmo abaixo escrito em linguagem Pyhton def exercicios 1(dados) 2 for range(0 1) 3 dados[i] 0: #. restante do código (não relevante para questão)# Com base no texto no código considerando ainda que quantidade de elementos em correto afirmar I.A complexidade para linha 2 complexidade na linha O(n/2) III complexidade da linha complexidade do algoritmo O(n+1) Estão corretas as afirmativas Estão corretas as afirmativas: Nota: 10.0 A somente. e somente. C e III somente. Você assinalou essa alternativa (C) Você acertou! Aula 1 temas 2 e 3 D e III somente E I, III.Questão 7/12 Programação III 40 Ler em voz alta "Uma binária de busca tem seguinte propriedade: para cada da todos valores armazenados em sua subárvore esquerda (a cuja raiz filho à es querda) são menores que 0 valor armazenado em todos valores armazenados na subárvore direita são maiores ou igual Estrutura de Dados Algoritmos em C++ Tradução da edição norte Cengage Learning Brasil, E-book ISBN 9788522126651 Disponível em https //integrada minhabiblioteca com Acesso 07 2022 PAG189 Observe código class BST 2 def init dado=None): 3 self dado dado 4 self esquerda None 5 self direita None 6 7 def inserir(self, dado): 8 if(self dado 9 self dado dado 10 else 11 if(dadoQuestão 9/12 Programação III Ler em voz alta Assuma uma lista com 10 dados numéricos e inteiros colocados na seguinte ordem: [05, 14, 24, 56, 77, 78, 88] Suponha que você deseja implementar um algoritmo de busca para localizar algum dado neste vetor já ordenado de maneira crescente. Você resolve testar a busca sequencial e a busca (Adaptada) Acerca destes algoritmos e analisando 0 vetor acima, assinale a alternativa CORRETA: Nota: 10.0 A No algoritmo de busca sequencial, valor 24 seria localizado na tentativa, se fizermos uma varredura da esquerda para a direita. Na tentativa B No algoritmo de busca binária, 0 valor 24 seria localizado na Na tentativa C No algoritmo de busca sequencial, 0 valor 77 seria localizado mais rapidamente que se comparado com a busca Binária se sairia mais rápida. D No algoritmo de busca sequencial, da esquerda para a direta, valor 07 seria localizado com mesmo número de tentativas se comparado com busca binária E Em nenhum cenário de busca 0 algoritmo sequencial irá localizar 0 valor antes da busca É possível que sim, a sequencial ache antes. Dependerá 0 valor buscado e onde ele se localizado no vetor. Questão 10/12 Programação III Ler em voz alta Uma estrutura de dados operando como uma fila, opera com 0 principio de primeiro que entra é primeiro que sai, ou em first in first out (fifo) Implementar uma fila significa fazer uma inserção (queue) no final dela, e fazer a remoção (dequeue)no dela. Após realizar a sequencia de operações QUEUE (11), QUEUE (34) DEQUEUE QUEUE (23) DEQUEUE QUEUE (14) QUEUE (25) DEQUEUE () 0 conteúdo da fila Nota: 10.0 A 25 B 11,34,23,14,25 C 11,23,14,25 D 14,25 Você assinalou essa alternativa (D) Você acertou! Aula 3 tema 4 E 11,14