Teste_ Atividade para Avaliação - Semana 5 algoritmos II

Prévia do material em texto

1 ptsPergunta 1
Bubblesort
Heapsort
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
Mergesort
Quicksort
Heapsort
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:
1 ptsPergunta 3
Heapsort
Mergesort
Quicksort
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]), 
 r = ordena(v[meio:])) 
O algoritmo de ordenação implementado acima é o:
Insertionsort
1 ptsPergunta 4
Mergesort
Heapsort
Insertionsort
Quicksort
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:
1 ptsPergunta 5
Considere a seguinte implementação em Python de um algoritmo de ordenação:
 
def func(arr, n, i): 
 largest = i 
 l = 2 * i + 1 
Mergesort
Quicksort
Insertionsort
Heapsort
 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:
1 ptsPergunta 6
Busca sequencial.
Busca em profundidade.
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:
Busca binária.
Busca em largura.
1 ptsPergunta 7
Busca em largura.
Busca binária.
Busca sequencial.
Busca em profundidade.
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)
O algoritmo de busca implementado acima é a:
1 ptsPergunta 8
Busca sequencial.
Busca em profundidade.
Busca em largura.
Busca binária.
O algoritmo de busca que exige que os elementos estejam ordenados é:
Salvo em 1:17 
1 ptsPergunta 9
A subárvore da esquerda possui chaves menores ou iguais à chave da raiz.
A busca por uma chave será realizada, no máximo, até encontrar um nó folha.
A subárvore da direita possui chaves maiores ou iguais à chave da raiz.
Os nós internos podem ter até 3 filhos cada.
Em árvores binárias de busca:
1 ptsPergunta 10
É possível que a ordem de inserção de elementos na árvore ocasione um desbalanceamento da mesma.
A busca é eficiente pois a altura da árvore, que será sempre log2n, será a quantidade máxima de comparações a
serem feitas.
A raiz da árvore armazena o maior elemento do conjunto.
O nó folha mais abaixo e à direita da árvore armazena o maior elemento do conjunto.
Em árvores binárias de busca:
Enviar teste