Atividade avaliativa semana 5 Projeto e Análise de Algoritmos Univesp 2021

Prévia do material em texto

Fazer teste: Semana 5 - Atividade Avaliativa 
 
Informações do teste 
 Estado de Conclusão da Pergunta: 
PERGUNTA 1 
1. A representação de uma heap pode ser feita na forma de um array com índices de 1 a 
m, onde m é o número de chaves. Com base nisso, temos: 
 
 
A raiz é armazenada em , e para acessar o filho da direita usamos a 
notação , onde i é o índice da raiz. 
 
 
Para acessar o pai de um elemento , devemos fazer: . 
 
 
Todas estão corretas. 
 
 
No caso de um max-heap, não há garantia de que o elemento irá armazenar a 
menor chave do conjunto. 
 
 
No caso de um min-heap, o elemento armazena a menor chave do conjunto. 
1 pontos 
PERGUNTA 2 
1. Dada a seguinte representação, assinale a alternativa correta: 
 
1 2 3 4 5 6 7 8 9 10 
2 5 7 6 9 12 13 15 14 10 
 
 
A representação acima não representa uma árvore binária completa. 
 
 
A representação acima é de uma min-heap de altura 3. 
 
 
Todas estão corretas. 
 
 
O filho esquerdo de 6 é o 15. 
 
 
A árvore representada acima obedece às propriedades de uma min-
heap. 
1 pontos 
PERGUNTA 3 
1. Considere as seguintes afirmativas em relação às diferenças entre max-heap e min-
heap: 
 
( ) No caso de max-heap, a raiz da árvore contém a maior chave do conjunto. 
( ) No caso de min-heap, o elemento folha mais à direita é a chave maior do conjunto. 
( ) No max-heap, a árvore sempre será completa, inclusive no último nível. 
( ) No min-heap, um nó não folha sempre terá dois filhos. 
 
Assinale a alternativa que representa as afirmativas corretas (V) e incorretas (F) acima: 
 
 
F-V-V-V. 
 
 
V-F-F-F. 
 
 
 F-V-F-F. 
 
 
V-F-F-V. 
 
 
V-F-V-V. 
1 pontos 
https://ava.univesp.br/webapps/assessment/take/launch.jsp?course_assessment_id=_44409_1&course_id=_4642_1&content_id=_606538_1&step=null
https://ava.univesp.br/webapps/assessment/take/launch.jsp?course_assessment_id=_44409_1&course_id=_4642_1&content_id=_606538_1&step=null
PERGUNTA 4 
1. A inserção de um elemento numa estrutura heap de n elementos tem complexidade: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 pontos 
PERGUNTA 5 
1. O melhor caso do algoritmo Quicksort ocorre: 
 
 
quando os elementos estão ordenados inversamente. 
 
 
quando se escolhe o elemento intermediário como pivô. 
 
 
quando há elementos repetidos no vetor. 
 
 
quando os elementos já estão ordenados. 
 
 
quando se escolhe o elemento da posição central do vetor como pivô. 
1 pontos 
PERGUNTA 6 
1. O melhor caso do algoritmo Heapsort tem complexidade: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 pontos 
PERGUNTA 7 
1. Sobre o pior caso do algoritmo Heapsort, podemos afirmar que: 
 
 
 
tem complexidade . 
 
 
ocorre para qualquer vetor de entrada. 
 
 
ocorre quando os elementos já estão ordenados. 
 
 
tem complexidade . 
 
 
corre quando os elementos estão ordenados inversamente. 
1 pontos 
PERGUNTA 8 
1. Sobre a estrutura heap, assinale a alternativa correta: 
 
 
No caso de min-heap, o conteúdo de um nó é menor ou igual ao conteúdo dos nós na 
subárvore enraizada nele. 
 
 
Somente o último nível da árvore pode possuir folhas. 
 
 
A subárvore da esquerda possui chaves menores que as da subárvore da direita. 
 
 
É representada por uma árvore binária completa. 
 
 
A subárvore da esquerda possui uma quantidade menor ou igual de nós do que a 
subárvore da direita. 
1 pontos 
PERGUNTA 9 
1. O pior caso do algoritmo Quicksort ocorre: 
 
 
quando os elementos já estão ordenados. 
 
 
 quando os elementos estão ordenados inversamente. 
 
 
quando se escolhe o primeiro ou o último elemento como pivô. 
 
 
quando se escolhe o menor ou maior elemento como pivô. 
 
 
quando há elementos repetidos no vetor. 
1 pontos 
PERGUNTA 10 
1. Na estrutura heap, podemos afirmar que: 
 
 
as folhas têm sempre altura 0. 
 
 
a altura de um nó i é o maior comprimento de um caminho de i até uma folha. 
 
 
a altura da raiz da árvore heap é , onde m é o número de chaves do conjunto. 
 
 
cada nível p da estrutura armazena exatamente nós, exceto no último nível. 
 
 
 Todas estão corretas. 
1 pontos 
Clique em Salvar e Enviar para salvar e enviar. Clique em Salvar todas as respostas para 
salvar todas as respostas.