Baixe o app para aproveitar ainda mais
Prévia do material em texto
14/11/2020 Teste: Atividade para Avaliação - Semana 5 https://cursos.univesp.br/courses/3222/quizzes/13144/take 1/7 1 ptsPergunta 1 Heapsort Bubblesort Mergesort Quicksort Considere a seguinte implementação em Python de um algoritmo de ordenação: def ordena(v): n = len(v) for i in range(n): for j in range(n - i - 1): if v [ j ] > v[ j + 1 ]: v[ j ], v[ j + 1 ] = v[ j + 1 ], v[ j ] O algoritmo de ordenação implementado acima é o: 1 ptsPergunta 2 Insertionsort Considere a seguinte implementação em Python de um algoritmo de ordenação: def ordena(v): for i in range(1, len(v)): chave = v [ i ] j = i - 1 while j >= 0 and v[ j ] > chave: v[j + 1] = v[ j ] j -= 1 v[j + 1] = chave O algoritmo de ordenação implementado acima é o: 14/11/2020 Teste: Atividade para Avaliação - Semana 5 https://cursos.univesp.br/courses/3222/quizzes/13144/take 2/7 Quicksort Mergesort Heapsort 1 ptsPergunta 3 Considere a seguinte implementação em Python de um algoritmo de ordenação: def func(l, r): if len(l) == 0: return r if len(r) == 0: return l res = [] idx_l = idx_r = 0 while len(res) < len(l) + len(r): if l[idx_l] <= r[idx_r]: res.append(l[idx_l]) idx_l += 1 else: res.append(r[idx_r]) idx_r += 1 if idx_r == len(r): res += l[idx_l:] break if idx_l == len(l): res += r[idx_r:] break return res def ordena(v): if len(v) < 2: return v meio = len(v) // 2 return func( l = ordena(v[:meio]), 14/11/2020 Teste: Atividade para Avaliação - Semana 5 https://cursos.univesp.br/courses/3222/quizzes/13144/take 3/7 Mergesort Heapsort Insertionsort Quicksort r = ordena(v[meio:])) O algoritmo de ordenação implementado acima é o: 1 ptsPergunta 4 Quicksort Heapsort Considere a seguinte implementação em Python de um algoritmo de ordenação: from random import randint def ordena(v): if len(v) < 2: return v l, p, h = [ ], [ ], [ ] ch = v[randint(0, len(v) - 1)] for x in v: if x < ch: l.append(x) elif x == ch: p.append(x) elif x > ch: h.append(x) return ordena(l) + p + ordena(h) O algoritmo de ordenação implementado acima é o: 14/11/2020 Teste: Atividade para Avaliação - Semana 5 https://cursos.univesp.br/courses/3222/quizzes/13144/take 4/7 Insertionsort Mergesort 1 ptsPergunta 5 Quicksort Insertionsort Heapsort Mergesort Considere a seguinte implementação em Python de um algoritmo de ordenação: def func(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] func(arr, n, largest) def ordena(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): func(arr, n, i) for i in range(n - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] func(arr, i, 0) O algoritmo de ordenação implementado acima é o: 14/11/2020 Teste: Atividade para Avaliação - Semana 5 https://cursos.univesp.br/courses/3222/quizzes/13144/take 5/7 1 ptsPergunta 6 Busca binária. Busca sequencial. Busca em profundidade. Busca em largura. 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: 1 ptsPergunta 7 Considere a seguinte implementação em Python de um algoritmo de busca: def busca(v, i, f, chave): if f < i: return -1 m = (i + f) // 2 if v[m] == chave: return m if chave < v[m]: return busca(v, i, m - 1, chave) else: return busca(v, m + 1, f, chave) 14/11/2020 Teste: Atividade para Avaliação - Semana 5 https://cursos.univesp.br/courses/3222/quizzes/13144/take 6/7 Busca binária. Busca em profundidade. Busca em largura. Busca sequencial. O algoritmo de busca implementado acima é a: 1 ptsPergunta 8 Busca em profundidade. Busca em largura. Busca binária. Busca sequencial. O algoritmo de busca que exige que os elementos estejam ordenados é: 1 ptsPergunta 9 Os nós internos podem ter até 3 filhos cada. A subárvore da esquerda possui chaves menores ou iguais à chave da raiz. A subárvore da direita possui chaves maiores ou iguais à chave da raiz. A busca por uma chave será realizada, no máximo, até encontrar um nó folha. Em árvores binárias de busca: 1 ptsPergunta 10 Em árvores binárias de busca: 14/11/2020 Teste: Atividade para Avaliação - Semana 5 https://cursos.univesp.br/courses/3222/quizzes/13144/take 7/7 Salvo em 13:21 A raiz da árvore armazena o maior elemento do conjunto. A busca é eficiente pois a altura da árvore, que será sempre log2n, será a quantidade máxima de comparações a serem feitas. É possível que a ordem de inserção de elementos na árvore ocasione um desbalanceamento da mesma. O nó folha mais abaixo e à direita da árvore armazena o maior elemento do conjunto. Enviar teste
Compartilhar