Simulado estrutura de dados em python 2

Prévia do material em texto

10/05/2023, 19:57 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/6
 
Meus
Simulados
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS EM PYTHON   
Aluno(a): RODRIGO CARVALHO XAVIER SAMPAIO 202208357784
Acertos: 10,0 de 10,0 02/05/2023
Acerto: 1,0  / 1,0
A complexidade computacional é uma abstração para facilitar a comparação de algoritmos de forma
independente do ambiente de execução e de variações na sua entrada. As complexidades podem ser
representadas pelo número de operações requeridas. Dentre as seguintes complexidades de pior caso,
representadas pelo seu número de operações, qual é a melhor? (menos operações)
nlog n + 500
 100n + 5log n
2n2
(nlog n)/2
2n
Respondido em 02/05/2023 19:17:48
Explicação:
O conceito de complexidade é assintótico, ou seja, o que importa é quando o tamanho da entrada n cresce
arbitrariamente. Por isso, os termos dominantes de cada resposta são os únicos relevantes. 500n é assintoticamente
menor que n2, por exemplo, pois para n acima de 500 o quadrado de n será maior que 500n. Dessa forma podemos
ordenar em forma crescente de complexidade os termos dominantes das respostas: n, nlog n, n2, 2n. O menor deles é
n, logo a resposta correta é 100n+5log n.
Acerto: 1,0  / 1,0
O método de ordenação da bolha, ou Bubblesort tem como melhor caso a entrada já ordenada, que resulta em
complexidade O(n). Como seu pior caso, a entrada em ordem invertida, resultando em complexidade O(n2).
Baseado nessas duas a�rmações, podemos a�rmar que a sua complexidade de caso médio é:
O(log n)
O(nlog n)
O(1)
O(n)
 O(n2)
Respondido em 02/05/2023 19:18:11
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
10/05/2023, 19:57 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/6
Explicação:
Pelas características da notação O, a única a�rmação que podemos extrair é que o caso médio é melhor ou igual ao
pior caso. Portanto, é possível a�rmar que o caso médio é O(n2), ou qualquer função assintoticamente superior a n2,
como n2log n, n3, 2n etc.. Como dentre essas a única opção disponível é O(n2) essa é a resposta correta.
Podemos descartar O(1) e O(log n) por serem melhores que o melhor caso, o que contradiz a a�rmativa do melhor
caso.
Os casos O(n) e O(nlog n) seriam possíveis teoricamente para a complexidade média de um algoritmo qualquer que
seja O(n) no melhor caso e O(n2) no pior caso, mas não é possível a�rmar nenhuma das duas com as informações
dadas.
De fato, o caso médio do Bubblesort é O(n2).
Acerto: 1,0  / 1,0
No contexto de complexidade de algoritmos, usualmente é utilizada a notação O para representar as
complexidades assintóticas analisadas. Dentre as a�rmações a seguir, a correta é:
O(n) signi�ca que as operações variam em proporção logarítmica à entrada.
O(n) signi�ca que para n=50  o algoritmo executará no máximo 50 operações.
O(n) signi�ca que para n=50  o algoritmo realizará 50 operações no pior caso.
 O(n2) signi�ca que as operações variam em proporção quadrática à entrada.
c -O(log n) signi�ca que para n=64  o algoritmo realizará 6 operações no pior caso.
Respondido em 02/05/2023 20:06:04
Explicação:
Com o uso da notação O, simpli�camos o número de operações, ignorando multiplicadores constantes do termo
dominante e todos os termos de menor complexidade. Por exemplo, 5n2+3  é O(n2), mas n2 também é O(n2). Dessa
forma, não é possível calcular exatamente o número de operações quando se usa a notação O. Apenas podemos fazer
a�rmações sobre a proporcionalidade ao tamanho da entrada n. Assim, a resposta correta é que O(n2) é proporcional
ao quadrado da entrada.
Acerto: 1,0  / 1,0
Uma Lista pode ser implementada de forma contígua ou encadeada. No caso de uma lista implementada de
forma contígua, as complexidades de pior caso de busca, inserção e remoção são respectivamente:
O(log n), O(n) e O(n).
O(n), O(1) e O(n).
O(n), O(n) e O(1).
 O(n), O(n) e O(n).
O(1), O(n) e O(n).
Respondido em 02/05/2023 19:23:59
Explicação:
A busca é O(n) pois no pior caso você terá que percorrer toda a lista sequencialmente até encontrar o último
elemento. Já a inserção, no seu pior caso, colocará um elemento no início da lista, obrigando todos os demais a serem
 Questão3
a
 Questão4
a
10/05/2023, 19:57 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/6
deslocados uma posição, levando O(n) operações.
A remoção também tem nesse seu pior caso, remover o primeiro elemento, o que obrigará todos os demais a serem
¿puxados¿ uma posição levando tempo O(n).
Esse custo pode ser diminuído caso você implemente uma variável que indique o início da lista, mesmo assim, ao
remover um elemento exatamente do meio da lista, você precisará mover n/2 elementos, o que ainda é um custo
linear.
Acerto: 1,0  / 1,0
Uma Lista pode ser implementada de forma contígua ou encadeada. No caso de uma lista ordenada
implementada de forma encadeada, as complexidades de pior caso de busca, inserção e remoção são
respectivamente:
O(n), O(1) e O(n).
O(1), O(n) e O(n).
O(log n), O(n) e O(n).
O(n), O(n) e O(1).
 O(n), O(n) e O(n).
Respondido em 02/05/2023 19:18:46
Explicação:
A busca é O(n) pois no pior caso você terá que percorrer toda a lista sequencialmente até encontrar o último
elemento. Já a inserção, no seu pior caso, colocará um elemento no �nal da lista, uma operação simples, mas a busca
para achar a posição correta já é O(n). A remoção de qualquer nó também é uma operação de custo constante,
bastando reapontar um ponteiro, mas a busca pelo nó a ser removido também é O(n), o que faz a operação de
remoção também possuir complexidade O(n).
Acerto: 1,0  / 1,0
Uma lista L em alocação contígua está armazenada em memória no endereço 32. L possui elementos de 2 bytes
cada e no momento contém [10, 20, 30, 40] . Os elementos 5 e 50 serão inseridos em sequência. Em que
endereços eles serão inseridos, respectivamente, caso a lista não seja ordenada, e caso a lista seja ordenada?
 Não ordenada: 40, 42; ordenada: 32, 42.
Não ordenada: 36, 37; ordenada: 32, 33.
Não ordenada: 40, 42;  ordenada: 40, 42.
Não ordenada: 36, 37; ordenada: 32, 37.
Não ordenada: 32, 34; ordenada: 32, 34.
Respondido em 02/05/2023 19:51:23
Explicação:
A inserção na lista não ordenada ocorre ao �nal da lista, o 5o elemento será inserido na posição L[4] ou seja endereço
32 + 4 * 2 = 40 . O elemento seguinte L[5] será inserido no endereço 32 + 5 * 2 = 42. Já no caso ordenado, o primeiro
elemento deverá ser inserido na primeira posição L[0], endereço 32. Todos os demais elementos serão deslocados
uma posição. O segundo elemento será inserido ao �nal da lista em L[4]. Ou seja, endereço 32 + 4 * 2 = 42 (levando em
conta o deslocamento) . Solução é, portanto: 40,42, 32,42.
 Questão5
a
 Questão6
a
10/05/2023, 19:57 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/6
Acerto: 1,0  / 1,0
Seja a seguinte árvore de expressões aritméticas abaixo.
O resultado da visita em pre�xo dessa árvore é:
A + B * C
 + A * B C
A * B + C
A + * B C
A + ( B * C )
Respondido em 02/05/2023 20:09:01
Explicação:
O percurso em pre�xo é de�nido recursivamente. A partir da raiz r da árvore de expressões aritméticas T, percorre-se
a árvore de da seguinte forma:
1 - visita-se a raiz;
2 - percorre-se a sub-árvores esquerda de T, em pre�xo e
3 - percorre-se a sub-árvores direita de T, em pre�xo.
O resultado da visita é representado abaixo:
Acerto: 1,0  / 1,0
Seja a seguinte função em Python para percurso em uma árvore binária implementada em Python. Marque a
opção correta de qual percurso em árvores se trata essa função:
 Questão7
a
 Questão8
a
10/05/2023, 19:57 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/6
Percurso raiz-folha
Percurso Pós-ordem
 Percurso Pré-ordem
Percurso Anti simétrico
Percurso Em-ordem
Respondido em 02/05/2023 20:12:32
Explicação:
Para realizar o percurso em pré-ordem, são necessários três acessos ao nó. No caso da pré-ordem,no primeiro,
executamos a visita (print(raiz.chave)), no segundo, chamamos recursivamente o algoritmo para a sub-árvores
esquerda (Visita(raiz.esquerda)) e, no terceiro, ocorre a chamada do percurso em pré-ordem do ramo direito
(Visita(raiz.direita)).
Acerto: 1,0  / 1,0
As a�rmativas abaixo são feitas com base na estrutura de dados "Árvore Binária de Busca". Em relação ao
algoritmo de busca em uma árvore binária de busca, analise as a�rmativas abaixo:
I -A complexidade da busca é de�nida pela altura da árvore binária de busca. No pior caso O(n).
II - A busca é de�nida de forma recursiva, parte da raiz, comparando a chave buscada com a armazenada na raiz,
caso seja igual temos o sucesso da busca, caso contrário, se a chave buscada for menor, devemos proceder
recursivamente no ramo esquerdo, se a chave buscada for maior, proceder recursivamente no ramo direito.
III - Sempre é necessário percorrer toda a árvore no algoritmo de busca. Em todos os casos, mesmo em árvores
completas.
IV - A condição de parada da busca é encontrar a chave buscada ou ter que descer por um ramo vazio.
V - É possível escrever o algoritmo da busca de forma não recursiva.
II, III, IV e V são corretas.
I, II, III e IV são corretas.
I, II, III, IV e V são corretas.
 I, II, IV e V são corretas.
I, III, IV e V são corretas.
Respondido em 02/05/2023 20:17:48
Explicação:
A a�rmativa III é incorreta, não é necessário percorrer todos os nós da árvore se ela estiver perfeitamente
balanceada.
Acerto: 1,0  / 1,0
 Questão9
a
 Questão10
a
10/05/2023, 19:57 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/6
As árvores AVL constituem uma importante estrutura de dados que disponibilizam operações de busca,
inserção e remoção. Classi�que como verdadeiro ou falso as a�rmativas abaixo:
I - As árvores de Fibonacci são as árvores de altura máxima h com número mínimo do nós n e altura proporcional
a log n.
II - As árvores completas são árvores AVL.
III - É possível construir uma topologia de uma árvore AVL que não seja nem completa nem de Fibonacci com
altura proporcional a log n.
IV - Uma vez que a altura das árvores AVL é proporcional a log n, podemos garantir que a busca ocorre numa
complexidade de O(log n).
V - Na remoção, pode ser necessário realizar todas as rotações, no pior caso, do pai de uma folha que está sendo
removida até a raiz. Por esta razão, a complexidade da remoção é maior que O(log n).
I-F, II-F, III-V, IV-F, V-F.
I-V, II-V, III-F, IV-V, V-F.
I-F, II-F, III-F, IV-V, V-V.
 I-V, II-V, III-V, IV-V, V-F.
I-V, II-F, III-F, IV-V, V-V.
Respondido em 02/05/2023 20:20:49
Explicação:
Nem sempre é necessário realizar todas as operações, visto que a remoção pode eliminar uma folha e não causar
desbalanceamento na árvore.