Projeto e Análise de Algoritmos - Nota 10 - Semana 4 - Univesp

Prévia do material em texto

Fazer teste: Atividade para Avaliação - Semana 4Projeto e Análise de Algoritmos - EEM002 - Turma 001 4 - A estrutura heap e análise do algoritmo Heapsort
Fazer teste: Atividade para Avaliação - Semana 4 
Informações do teste
Descrição
Instruções
Várias tentativas Este teste permite 3 tentativas. Esta é a tentativa número 3.
Forçar conclusão Este teste pode ser salvo e retomado posteriormente.
Suas respostas foram salvas automaticamente.
Atividade para avaliação
1. Para responder a esta atividade, selecione a(s) alternativa(s) que você considerar correta(s);
2. Após selecionar a resposta correta em todas as questões, vá até o �m da página e pressione “Enviar teste”.
3. A cada tentativa, as perguntas e alternativas são embaralhadas
Consulte os gabaritos dessa disciplina no menu lateral.
Olá, estudante!
Pronto! Sua atividade já está registrada no AVA.
PERGUNTA 1
Dado o seguinte array, A = [27, 18, 14, 17, 12, 11, 13, 16, 15], assinale a alternativa correta: 
O último nível teria três nós alinhados do lado esquerdo.
O nó 12 seria um nó folha.
Os nós 15 e 16 seriam as únicas folhas na Heap. 
Se A fosse imaginado como uma Heap, o nó 12 seria �lho do nó 14.
Podemos dizer que é a representação interna de uma min-heap.
1 pontos   Salva
PERGUNTA 2
Assumindo que temos a Heap dada pelo array A = [54, 36, 28, 34, 24, 26, 22, 30, 32]. O Heapsort irá reorganizar essa estrutura de modo a ordenar o array em
ordem crescente. Para tanto, a primeira iteração do Heapsort geraria o array A = [36, 34, 28, 32, 24, 26, 22, 30, 54], sendo que os primeiros 8 elementos formam a
Heap e o último elemento faz parte do array ordenado. A segunda iteração do Heapsort geraria: 
[34, 32, 28, 30, 24, 26, 22, 36, 54].
[34, 32, 22, 24, 26, 30, 28, 36, 54].
[34, 28, 32, 24, 26, 22, 30, 36, 54].
[34, 32, 34, 26, 22, 30, 28, 36, 54]. 
[34, 26, 22, 24, 32, 30, 28, 36, 54]. 
1 pontos   Salva
PERGUNTA 3
O array A = [27, 12, 15, 3, 13, 10, 2, 0, 1, 4, 5] não pode ser considerado uma Heap (max-heap) porque um dos nós viola as propriedades da Heap. Qual das
alternativas a seguir mostra o que pode ser feito para que o array represente uma Heap. 
Para que o array passe a representar uma Heap, no mínimo três elementos devem mudar de posição.
Os elementos 12 e 13 devem trocar de posição. 
O elemento 0 deve trocar de posição com o elemento 2.
Os elementos 27 e 12 devem trocar de posição. 
Os elementos 15 e 13 devem trocar de posição.
1 pontos   Salva
PERGUNTA 4
Qual das alternativas a seguir apresenta uma informação verdadeira sobre Heaps. 
Em uma Heap, o nó de índice 4 é pai dos nós de índices 6 e 7.
O nível p de uma heap possui exatamente 2p nós, exceto o último, que pode ter 2p nós ou menos.
As Heaps, internamente, são arrays ordenados de forma crescente (min-heap) ou decrescente (max-heap).
Em uma Heap com n nós, a altura de todos os nós é log(n).
A altura de um nó i é o maior comprimento de um caminho de i até a raiz. Essa propriedade comum às árvores também vale para uma Heap. 
1 pontos   Salva
PERGUNTA 5
Assinale a alternativa correta sobre a transformação de um array em Heap. 
Se no array apenas um dos nós viola a propriedade de Heap, então a transformação em Heap deve ocorrer em tempo constante.
Se no array apenas um dos nós viola a propriedade de Heap, então a transformação em Heap deve ocorrer em tempo O(log n).
Se no array vários nós violarem a propriedade de Heap, então é possível garantir que conseguiremos um algoritmo que executa em tempo O(log n).
Se no array vários nós violarem a propriedade de Heap, então o melhor algoritmo que podemos construir terá complexidade Ω(n log(n)).
Se no array vários nós violarem a propriedade de Heap, então é possível garantir que conseguiremos um algoritmo que executa em tempo constante.
1 pontos   Salva
PERGUNTA 6 1 pontos   Salva
? Estado de Conclusão da Pergunta:
https://ava.univesp.br/webapps/blackboard/execute/courseMain?course_id=_2041_1
https://ava.univesp.br/webapps/blackboard/content/listContent.jsp?course_id=_2041_1&content_id=_353730_1&mode=reset
 Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para salvar todas as respostas.
Sobre os algoritmos de ordenação Mergesort, Heapsort e Quicksort, é correto a�rmar que: 
O Mergesort é um algoritmo que usa a estratégia de divisão e conquista que possui tempo computacional da ordem O(n2).
O Quicksort é um algoritmo que usa a estratégia de divisão e conquista que possui tempo computacional da ordem O(n log(n)).
O Heapsort é um algoritmo que usa a estratégia de divisão e conquista que possui tempo computacional da ordem O(n2).
O Mergesort é um algoritmo que usa a estratégia de divisão e conquista que possui tempo computacional da ordem O(n log(n)).
O Heapsort é um algoritmo que usa a estratégia de divisão e conquista que possui tempo computacional da ordem O(n log(n)).
 po tos   Sa a
PERGUNTA 7
Sobre as de�nições de Heap, assinale a alternativa correta: 
No caso de uma Min-Heap, o conteúdo de um nó é menor ou igual ao conteúdo dos nós �lhos na visualização em árvore da Heap. 
No último nível de uma Heap, as folhas estão o mais à esquerda possível, indicando que no penúltimo nível todos os nós possuem apenas �lhos do lado
esquerdo.
Em uma Heap, os conteúdos dos elementos da árvore à esquerda de um nó são menores do que o conteúdo dos elementos da árvore à direita desse nó.
O fato de uma Heap ser uma árvore binária é condição su�ciente para permitir que seja implementada como um array.
Uma Heap é uma estrutura que pode ser visualizada como uma árvore, sendo que o último nível da árvore deve estar incompleto, dado que a Heap é
de�nida como uma árvore quase completa. 
1 pontos   Salva
PERGUNTA 8
Sobre o algoritmo Quicksort, é correto a�rmar que: 
Na etapa de divisão, cada uma das partes do array particionado tem o mesmo tamanho, ou uma diferença de apenas um elemento de tamanho.
Na etapa de divisão, um vetor A[p ... r] é particionado devolvendo um índice q tal que A[p ... q-1] <= A[q] <= A[q+1 ... r].
A escolha de um pivô é uma etapa importante e deve ser feita aleatoriamente, dado que a escolha arbitrária altera o tempo computacional no pior caso.
No melhor caso, o algoritmo do Quicksort executa em tempo O(n), assemelhando-se ao algoritmo do Insertionsort.
O algoritmo é muito lento em média, devido ao seu desempenho ser da ordem O(n2). Em termos práticos, o algoritmo não é melhor do que o Insertionsort.
1 pontos   Salva
PERGUNTA 9
Sobre o algoritmo HeapSort, é correto a�rmar que: 
O algoritmo executa em tempo O(n log(n)) desde que a entrada seja um Heap máximo. Caso contrário, a construção dessa Heap Máximo é um passo que
custa θ(n2) de tempo.
O algoritmo executa em tempo O(n log(n)) no caso médio e O(n2) no pior caso.
A cada iteração do Heapsort, um elemento é movido da Heap para a sua posição �nal no array ordenado. Isso pode exigir que a Heap seja rearranjada.
A cada iteração do Heapsort o número de elementos da Heap decresce de 1 e o número de elementos do array ordenado aumenta de 1. Nesse caso, como
temos n elementos, o algoritmo executa em tempo O(n).
O Heapsort precisará de até n iterações, sendo n o número de elementos. Cada iteração exige uma chamada para o algoritmo de reorganização da Heap, que
por sua vez executa em tempo θ(n).
1 pontos   Salva
PERGUNTA 10
Supondo que temos uma estrutura que está muito próxima de se tornar uma max-heap. Para tanto, basta resolver um problema no nó raiz, único nó que viola a
propriedade da Heap por ser menor que todos os outros nós. Neste cenário, sendo n o número de nós na árvore, assinale a alternativa que indica o número de
passos do algoritmo MAX-HEAPIFY que corrige o problema desse nó raiz. 
log(n)
n
sqrt(n)
n2
n log(n) 
1 pontos   Salva
Salvar todas as respostas Salvar e Enviar
 Estado de Conclusão da Pergunta: