Logo Passei Direto
Buscar

Estrutura de Dados

Outros
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas. 1. Os algoritmos possuem a mesma complexidade assintótica PORQUE 1. Para o melhor caso, ambos possuem a complexidade O(n). A respeito dessas asserções, assinale a opção correta:
a primeira asserção é uma proposição verdadeira e a segunda uma proposição falsa.
as duas asserções são proposições verdadeiras e a segunda não é a justificativa correta da primeira.
tanto a primeira quanto a segunda asserções são proposições falsas.
a primeira asserção é uma proposição falsa e a segunda uma proposição verdadeira.
as duas asserções são proposições verdadeiras, mas a segunda é uma justificativa correta da primeira.
User badge image
Praticando Para Aprender

há 7 meses

User badge image
Praticando Para Aprender

há 7 meses

Estácio_ 111 (2)
7 pág.

Estácio_ 111 (2)

ESTÁCIO

Respostas

User badge image

Ed Verified user icon

há 7 meses

Para avaliar as asserções, precisamos analisar a relação entre a complexidade assintótica dos algoritmos e o que é dito sobre o melhor caso. 1. Primeira asserção: "Os algoritmos possuem a mesma complexidade assintótica." - Para que essa afirmação seja verdadeira, ambos os algoritmos devem ter a mesma complexidade em todos os casos (melhor, pior e caso médio). 2. Segunda asserção: "Para o melhor caso, ambos possuem a complexidade O(n)." - Essa afirmação é verdadeira se, de fato, ambos os algoritmos têm complexidade O(n) no melhor caso. Agora, se a primeira asserção é verdadeira, a segunda pode ser uma justificativa, mas não necessariamente a única. Se a primeira asserção for verdadeira, a segunda deve ser verdadeira, mas a relação de justificativa pode não ser a única. Portanto, a opção correta depende da análise das complexidades em outros casos (pior e médio). Se ambos os algoritmos têm a mesma complexidade em todos os casos, a primeira asserção é verdadeira e a segunda é uma justificativa correta. Se não, a primeira pode ser falsa. Com base nas informações dadas, a resposta mais adequada seria: As duas asserções são proposições verdadeiras, mas a segunda é uma justificativa correta da primeira.

Essa resposta te ajudou?

0
Dislike0
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Estácio_ 111 (2)
7 pág.

Estácio_ 111 (2)

ESTÁCIO

Mais perguntas desse material

Uma lista ordenada de N números é inserida em uma pilha e depois retirada, sendo que, a cada POP, o elemento retirado é inserido em um vetor de elementos. Após a completa inserção de todos os elementos neste vetor, são feitas buscas de números na mesma. O tempo médio de busca de um número neste elemento é:
O(log N)
O(N2)
O(Nlog N)
O(1)
O(N)

O código abaixo é uma implementação:
public class Misterio { public static long Misterio(long x) { if (x == 1) return 1; else return x * Misterio(x-1); }} Qual é a função do código?
Recursiva do fatorial
Recursiva da exponenciação
Iterativa da exponenciação
Recursiva da série de Fibonacci
Iterativa da série de Fibonacci

Correlacione os algoritmos internos de ordenação de listas com sua descrição:
A sequência correta, de cima para baixo, é:
I. Bubble sort
II. Ordenação por seleção
III. Ordenação por inserção
IV. Shell sort
V. Quick sort
I, II, III, IV, V
V, II, III, IV, I
V, IV, II, III, I
I, III, II, IV, V
I, IV, V, III, II

Se f é uma função de complexidade para um algoritmo F, então, O(f) é considerada a complexidade assintótica ou o comportamento assintótico do algoritmo F. Assinale a alternativa que apresenta somente algoritmos com complexidade assintótica, quando f(n) = O(n log n):
Insertion sort.
Bubble sort.
Quick sort e merge sort.
Merge sort e bubble sort.
Quick sort e insertion sort.

Árvore AVL é uma árvore de busca autobalanceada. Isso significa que:
as alturas das duas subárvores a partir de cada nó diferem no máximo em duas unidades.
as alturas das duas subárvores a partir de cada nó diferem no máximo em uma unidade.
as alturas das duas subárvores a partir de cada nó são exatamente iguais.
pode possuir até duas raízes.
cada nó da árvore possui até três descendentes.

Após a inserção de um nó, é necessário verificar cada um dos nós ancestrais desse nó inserido, relativamente à consistência com as regras estruturais de uma árvore AVL.
Analisando-se as afirmações acima, conclui-se que:
O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por -2, -1, 0, 1, 2.
as duas afirmações são verdadeiras, e a segunda justifica a primeira.
as duas afirmações são verdadeiras, e a segunda não justifica a primeira.
a primeira afirmação é verdadeira, e a segunda é falsa.
a primeira afirmação é falsa, e a segunda é verdadeira.
as duas afirmações são falsas.

Mais conteúdos dessa disciplina