Teste_ Atividade para avaliação - Semana 5

Prévia do material em texto

10/09/2020 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/3115/quizzes/12206/take 1/4
1 ptsPergunta 1
É representada por uma árvore binária completa.
O último nível da árvore possui folhas mais à direita.
No caso de max-heap, o conteúdo de um nó é maior ou igual ao conteúdo dos nós na subárvore enraizada nele.
Nenhuma das demais alternativas.
A subárvore da esquerda possui chaves menores que as da subárvore da direita.
Sobre a estrutura heap, assinale a alternativa correta: 
1 ptsPergunta 2
no min-heap, um nó não folha sempre terá dois filhos.
Nenhuma das demais alternativas.
no caso de min-heap, o elemento folha mais à direita é a chave maior do conjunto.
no caso de max-heap, a raiz da árvore contém a maior chave do conjunto.
no max-heap, a árvore sempre será completa, inclusive no último nível.
Uma das diferenças entre max-heap e min-heap é que: 
1 ptsPergunta 3
Para acessar o pai de um elemento A[i], devemos fazer: A .
No caso de um min-heap, o elemento A[0] armazena a maior chave do conjunto.
Todas as demais alternativas estão erradas.
A raiz é armazenada em A[1], e usamos a notação 2i+1 para acessar o filho da direita, em que i é o índice da raiz.
No caso de um max-heap, o elemento A[m] armazena a menor chave do conjunto.
A representação de uma heap pode ser feita na forma de um array com índices de 1 a m, em
que m é o número de chaves. Com base nisso, temos que: 
10/09/2020 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/3115/quizzes/12206/take 2/4
1 ptsPergunta 4
as folhas têm sempre altura 1.
cada nível p da estrutura armazena exatamente nós, inclusive no último nível.
a altura de um nó i é o menor comprimento de um caminho de i até uma folha.
a altura da raiz da árvore heap é , na qual m é o número de chaves do conjunto.
Todas as demais alternativas estão incorretas.
Na estrutura heap, podemos afirmar que: 
1 ptsPergunta 5
O filho esquerdo da chave 15 é o elemento 9.
A árvore, representada acima, obedece às propriedades de uma max-heap.
Todas as demais alternativas estão erradas.
A representação acima é de uma max-heap de altura 4.
A chave 5, armazenada na última posição do vetor, não poderia ser alocada em nenhuma outra posição.
Dada a seguinte representação, assinale a alternativa correta: 
1 ptsPergunta 6
O(n)
O(n log n)
O(log n)
O(n²)
A manutenção de uma estrutura heap consiste em reorganizar chaves específicas que ferem a
propriedade de max-heap ou min-heap devido à inserção ou remoção de um elemento. A
complexidade desse algoritmo, considerando uma estrutura com n chaves, é de: 
10/09/2020 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/3115/quizzes/12206/take 3/4
Nenhuma das demais alternativas.
1 ptsPergunta 7
O(n log n)
Nenhuma das demais alternativas.
O(n³)
O(n²)
O pior caso do algoritmo Quicksort tem complexidade: 
1 ptsPergunta 8
(n)
Nenhuma das demais alternativas.
(log n)
(n log n)
(n²)
O melhor caso do algoritmo Quicksort tem complexidade: 
1 ptsPergunta 9
O(n³)
O(n²)
O(n log n)
Nenhuma das demais alternativas.
O pior caso do algoritmo Heapsort tem complexidade: 
10/09/2020 Teste: Atividade para avaliação - Semana 5
https://cursos.univesp.br/courses/3115/quizzes/12206/take 4/4
Salvo em 22:58 
1 ptsPergunta 10
O(n log n)
O(n²)
Nenhuma das demais alternativas.
O(n³)
O melhor caso do algoritmo Heapsort tem complexidade: 
Enviar teste