Logo Passei Direto
Buscar

Estrutura de Dados

Colégio Objetivo
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):


a) Quick sort e merge sort.
b) Merge sort e bubble sort.
c) Quick sort e insertion sort.
d) Bubble sort.
e) Insertion sort.
User badge image
Estudando com Questões

há 3 anos

User badge image
Estudando com Questões

há 3 anos

AV 1_ ALGORITMOS E COMPLEXIDADE
8 pág.

AV 1_ ALGORITMOS E COMPLEXIDADE

ESTÁCIO

Respostas

User badge image

Ed Verified user icon

há 10 meses

Vamos analisar cada alternativa em relação à complexidade assintótica \( O(n \log n) \): a) Quick sort e merge sort. - O Quick sort tem complexidade média de \( O(n \log n) \). - O Merge sort tem complexidade de \( O(n \log n) \). Esta alternativa é correta. b) Merge sort e bubble sort. - O Merge sort tem complexidade de \( O(n \log n) \). - O Bubble sort tem complexidade de \( O(n^2) \). Esta alternativa é incorreta. c) Quick sort e insertion sort. - O Quick sort tem complexidade média de \( O(n \log n) \). - O Insertion sort tem complexidade de \( O(n^2) \) no pior caso. Esta alternativa é incorreta. d) Bubble sort. - O Bubble sort tem complexidade de \( O(n^2) \). Esta alternativa é incorreta. e) Insertion sort. - O Insertion sort tem complexidade de \( O(n^2) \) no pior caso. Esta alternativa é incorreta. Portanto, a alternativa que apresenta somente algoritmos com complexidade assintótica \( O(n \log n) \) é: a) Quick sort e merge sort.

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

User badge image

Ed Verified user icon

há 2 anos

A alternativa correta é a letra A) Quick sort e merge sort. Ambos os algoritmos possuem complexidade assintótica O(n log n) quando a função de complexidade f(n) é igual a O(n log n).

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

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

Essa pergunta também está no material:

AV 1_ ALGORITMOS E COMPLEXIDADE
8 pág.

AV 1_ ALGORITMOS E COMPLEXIDADE

ESTÁCIO

Mais perguntas desse material

Classifique cada uma das seguintes afirmacoes em 'V' (se verdadeira) ou 'F' (se falsa) e escolha a alternativa que corresponde à sequência correta de indicações.
I- Um registro reúne uma coleção de informações, facilitando a sua organização e o seu uso.
II- Cada informação distinta de um registro é considerada um atributo ou campo.
III- O atributo pode ser definido como qualquer tipo de dado que a linguagem utiliza ou como outra estrutura de dados: vetor, matriz ou mesmo outro registro.

I- Um registro reúne uma coleção de informações, facilitando a sua organização e o seu uso.
II- Cada informação distinta de um registro é considerada um atributo ou campo.
III- O atributo pode ser definido como qualquer tipo de dado que a linguagem utiliza ou como outra estrutura de dados: vetor, matriz ou mesmo outro registro.
V, V, V
V, F, V
F, V, F
V, F, F
F, F, V

Uma tarefa essencial quando começamos a aprender uma nova linguagem de programação é conhecer e saber manipular as suas estruturas básicas de dados. Nesse sentido, um vetor é uma coleção de variáveis de:


Tipo de dado homogêneo distribuído pela memória.
Tipo de dado homogêneo em sequência na memória.
Diferentes tipos de dados em sequência na memória.
Registros alocadas em sequência na memória.
Diferentes tipos de dados distribuídos pela memória.

Analise o seguinte código:

public static double recursive (double d) {
if (d <= 1) { urn 1;
} else {
return d * recursive(d - 1);
}
}

Assinale o conteúdo que será exibido na saída do programa quando a função for chamada com o parâmetro 6:


360
720
1440
240
120

Analise as afirmações a seguir a respeito de algoritmos recursivos.
I. Diz-se que uma rotina é recursiva se a sua definição envolver uma chamada a ela mesma. Neste sentido, o termo recursão é equivalente ao termo indução utilizado por matemáticos.
II. Cada algoritmo recursivo possui um algoritmo iterativo equivalente e vice-versa, mas que pode ter mais ou menos complexidade em sua construção.
III. Uma função recursiva possui duas partes: caso base e caso recursivo.
IV. Um algoritmo pode ser chamado de iterativo quando ele requer a repetição implícita de um processo até que determinada condição seja satisfeita.
V. A recursividade possibilita a escrita de um código mais enxuto, com maior legibilidade e simplicidade.
Assinale a alternativa que possui alguma afirmação INCORRETA.

I. Diz-se que uma rotina é recursiva se a sua definição envolver uma chamada a ela mesma. Neste sentido, o termo recursão é equivalente ao termo indução utilizado por matemáticos.
II. Cada algoritmo recursivo possui um algoritmo iterativo equivalente e vice-versa, mas que pode ter mais ou menos complexidade em sua construção.
III. Uma função recursiva possui duas partes: caso base e caso recursivo.
IV. Um algoritmo pode ser chamado de iterativo quando ele requer a repetição implícita de um processo até que determinada condição seja satisfeita.
V. A recursividade possibilita a escrita de um código mais enxuto, com maior legibilidade e simplicidade.
II e III
III e IV
I e V
I e IV
I e II

Correlacione os algoritmos internos de ordenação de listas com sua descrição:

I. Bubble sort
II. Ordenação por seleção
III. Ordenação por inserção
IV. Shell sort
V. Quick sort

( ) Escolhe-se um pivô e particiona-se a lista em duas sublistas - uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivô, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio, é de O(n log n).

( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do vetor. Repetem-se essas duas operações com os n − 1 itens restantes; depois, com os n − 2 itens; até que reste apenas um elemento.

( ) Método preferido dos jogadores de cartas. A cada momento, existem duas partes na lista ¿ uma ordenada (destino) e outra não ordenada (fonte). Inicialmente, a lista destino tem apenas o primeiro elemento, e a fonte, os demais elementos. Em cada passo, a partir de i=2, seleciona-se o i-ésimo item da lista fonte. Deve-se colocá-lo no lugar apropriado na lista destino, de acordo com o critério de ordenação.

( ) É uma extensão de outro algoritmo de ordenação conhecido e permite trocas de elementos distantes um do outro, não necessariamente adjacentes. Os itens separados de h posições são rearranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é

( ) Escolhe-se um pivô e particiona-se a lista em duas sublistas - uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivô, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio, é de O(n log n).
( ) Encontra-se o menor item do vetor. Troca-se com o item da primeira posição do vetor. Repetem-se essas duas operações com os n − 1 itens restantes; depois, com os n − 2 itens; até que reste apenas um elemento.
( ) Método preferido dos jogadores de cartas. A cada momento, existem duas partes na lista ¿ uma ordenada (destino) e outra não ordenada (fonte). Inicialmente, a lista destino tem apenas o primeiro elemento, e a fonte, os demais elementos. Em cada passo, a partir de i=2, seleciona-se o i-ésimo item da lista fonte. Deve-se colocá-lo no lugar apropriado na lista destino, de acordo com o critério de ordenação.
( ) É uma extensão de outro algoritmo de ordenação conhecido e permite trocas de elementos distantes um do outro, não necessariamente adjacentes. Os itens separados de h posições são rearranjados. Todo h-ésimo item leva a uma lista ordenada. Tal lista é
( ) Escolhe-se um pivô e particiona-se a lista em duas sublistas - uma com os elementos menores que ele e outra com os maiores, que, ao serem ordenadas e combinadas com o pivô, geram uma lista ordenada. O processo é aplicado às partições para ordená-las. Embora tenha uma complexidade de pior caso de O(n2 ), no caso médio, é de O(n log n).
V, II, III, IV, I
I, II, III, IV, V
IV, III, II, I, V
V, III, II, IV, I
I, III, II, IV, V

dita estar h-ordenada.

( ) Varre-se a lista, trocando de posição os elementos adjacentes fora de ordem.
Varre-se a lista até que não haja mais trocas. Neste caso, a lista está ordenada. A sequência correta, de cima para baixo, é:

V, II, III, IV, I
I, III, II, IV, V
I, IV, V, III, II
I, II, III, IV, V
V, IV, II, III, I


a) I, III, II, IV, V
b) I, II, III, IV, V
c) I, IV, V, III, II
d) V, IV, II, III, I
e) V, II, III, IV, I

Após a inserção de um nó, é necessário verif icar cada um dos nós ancestrais
desse nó inserido, relativamente à consistência com as regras estruturais de uma
árvore AVL.
PORQUE
O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao
conjunto formado por {−2, −1, 0, +1, +2}.

Analisando-se as afirmacoes acima, conclui-se que:

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.
O fator de balanceamento de cada nó, em uma árvore AVL, deve pertencer ao conjunto formado por {−2, −1, 0, +1, +2}.
a) a primeira afirmação é verdadeira, e a segunda é falsa.
b) as duas afirmações são verdadeiras, e a segunda justifica a primeira.
c) as duas afirmações são verdadeiras, e a segunda não justifica a primeira.
d) as duas afirmações são falsas.
e) a primeira afirmação é falsa, e a segunda é verdadeira.

(CESGRANRIO - Transpetro - Analista de Sistemas Júnior - Processos de Negócio -
2018)
Uma das medidas de qualidade do código de um sof tware é a Complexidade, que
pode ser medida por meio da complexidade ciclomática.
Considere um grafo de f luxo que possui 5 nós e 12 arcos. Qual a complexidade
ciclomática desse grafo?


a) 9
b) 15
c) 17
d) 19
e) 11

(FCC - ARTESP - Agente de Fiscalização à Regulação de Transporte - Tecnologia de
Informação - 2017)
Considere a estrutura abaixo que representa um problema de rotas em pequena
escala:

Considere, por hipótese, que se solicitou a um Agente de Fiscalização à Regulação de Transporte da ARTESP utilizar alguma estratégia lógica para, partindo do ponto 1,
chegar ao ponto 6 usando a menor rota. De um mesmo ponto pode haver mais de
uma rota, com distâncias diferentes. A lógica correta utilizada pelo Agente, em função
dos pontos a serem percorridos, foi:


{1} {2,3} {2,4} {5,6} {6}, caminho mais curto 1-2-5-6.
{1} {2} {4} {6}, caminho mais curto 1-2-4-6.
{6} {5,4} {3,1} {1}, caminho mais curto 6-4-3-1, que é igual a 1-3-4-6.
{1} {3,2} {4,5} {6}, caminho mais curto 1-3-4-6.
{6} {4} {5,3} {2,1} {1}, caminho mais curto 6-4-3-5-2-1, que é igual a 1-2-5-3-4-6.

Mais conteúdos dessa disciplina