ESTRUTURA DE DADOS EM PYTHON

Prévia do material em texto

Meus Simulados
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS EM PYTHON   
Aluno(a): WALLACE FRANCIS DA SILVA CRESPO 202209251327
Acertos: 6,0 de 10,0 10/04/2023
Acerto: 0,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(n2)
 O(nlog n)
O(log n)
O(1)
O(n)
Respondido em 10/04/2023 23:24:26
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
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)/2
2n2
 100n + 5log n
nlog n + 500
2n
Respondido em 10/04/2023 23:26:12
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
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
Um vetor está armazenado em memória no endereço-base 24. Considerando que uma palavra em memória ocupa 1
byte, e esse vetor é constituído por elementos que ocupam 4 palavras, qual é o endereço de memória ocupado pelos
elementos de índices 2 e 50 respectivamente? .
28 e 224
28 e 220
26 e 74
32 e 220
 32 e 224
Respondido em 10/04/2023 23:23:38
Explicação:
Para calcular o endereço absoluto em memória você deve utilizar a fórmula A=B+t*i . No caso B é o endereço base (24), t é o
tamanho de cada elemento (4) e i é o índice do elemento (2 e 50). Aplicando a fórmula temos 32=24+2*4  e 224=24+50*4
Acerto: 0,0  / 1,0
Suponha que você está implementando um programa que precisa armazenar dados ordenados em uma estrutura para
serem tratados posteriormente, na ordem em que foram recebidos. Haverá uma grande quantidade de recebimentos e
tratamento de dados, mas o tamanho esperado da estrutura não deve variar muito. Qual tipo de estrutura de dado é a
melhor nessa situação?
Lista em alocação contígua.
 Fila.
Pilha.
 Lista duplamente encadeada.
Lista simplesmente encadeada.
Respondido em 10/04/2023 23:23:55
Explicação:
A �la permite o tratamento de nós usando a política requerida, FIFO ¿ ¿�rst in �rst out¿ -. Além disso, as operações de inserção
e remoção são O(1), ou seja, de complexidade constante, a melhor possível. Isso condiz com o requisito de que haverá muitas
operações desse tipo. Por �m, o fato de a estrutura não variar muito em tamanho permite o uso de uma alocação contígua e
otimizada para a �la usando lógica circular e variáveis para o início e �nal da �la. A pilha não obedece a lógica FIFO e as listas
tem complexidade de inserção e remoção O(n) sendo muito piores que a �la, principalmente quando o número desses tipos de
operação é grande.
Acerto: 0,0  / 1,0
 Questão3
a
 Questão4
a
 Questão5
a
Uma lista L encadeada e ordenada está armazenada em memória seguindo o exemplo abaixo. Após a remoção do nó de chave 3, quais
alterações terão ocorrido?
O endereço 32 terá seu campo próximo apontando para 24.
 O endereço 24 conterá a chave 5 e próximo 64.
 A variável L apontará para 128.
L terá sido apagada.
O conteúdo armazenado no endereço 32 será apagado.
Respondido em 10/04/2023 23:26:44
Explicação:
A remoção solicitada é do primeiro elemento da lista encadeada. Para realizar esse tipo de remoção, basta apontar a variável que guarda o
primeiro elemento (L) para o endereço do segundo elemento. Este endereço está armazenado no campo próximo do primeiro elemento. Ou
seja, a variável L deverá apontar para 128.
A resposta endereço 24 conterá a chave 5 está errada pois na lista encadeada, os elementos não precisam ser puxados após uma remoção.
A resposta endereço 32 terá seu campo próximo alterado está errada, pois isso adicionaria um elemento ao �nal da lista, no caso tornando-a
circular.
As demais respostas estão erradas pois nada será apagado.
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(n) e O(n).
O(1), O(n) e O(n).
O(n), O(n) e O(1).
O(n), O(1) e O(n).
Respondido em 10/04/2023 23:27:10
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 deslocados uma
 Questão6
a
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: 0,0  / 1,0
As árvores de busca são estruturas de dados que armazenam elementos de forma hierárquica, permitindo uma busca
e�ciente em grandes conjuntos de dados. Marque a opção correta acerca das estruturas de dados Árvores e Árvores
Binárias:
A raiz está no maior nível da árvore.
As folhas estão sempre no nível 1 da árvore.
 Nas Árvores Binárias de Busca cada nó deve ter exatamente 2 �lhos.
Os nós de uma árvore que possuem grau zero são chamados de raiz.
 Ao acessar uma árvore, deve-se acessar pela referência a sua raiz.
Respondido em 10/04/2023 23:29:11
Explicação:
A forma comum de representar uma árvore em memória é utilizando alocação dinâmica. Não representamos a árvore como
um todo, mas sim uma referência para sua raiz que guarda a chave (dado) e uma referência para a raiz das sub-árvores
esquerda e direita. Um nó pode ter 0, 1 ou 2 �lhos. As folhas podem estar em qualquer nível. A raiz pode ter grau zero quando
é raiz e folha simultaneamente. A raiz está sempre no nível 1.
Acerto: 1,0  / 1,0
Seja a seguinte árvore binária de busca, marque a opção que apresenta o percurso em pré-ordem dessa árvore:
A,B,C,D,E,F
 A,D,C,E,B,F
F,C,E,B,A,D
D,B,E,F,C,A
D,A,B,E,C,F
Respondido em 10/04/2023 23:22:47
Explicação:
 Questão7
a
 Questão8
a
A resposta correta é a questão E. O percurso em pré-ordem é de�nido como se segue. A partir da raiz r da árvore T, percorre-
se a árvore da seguinte forma:
1 - visita-se a raiz;
2 - percorre-se a subárvores esquerda de T, em pré-ordem e
3 - percorre-se a subárvores direita de T, em pré-ordem.
Resultado da pesquisa pré-ordem:Acerto: 1,0  / 1,0
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-V, II-F, III-F, IV-V, V-V.
I-V, II-V, III-F, IV-V, V-F.
I-F, II-F, III-F, IV-V, V-V.
I-F, II-F, III-V, IV-F, V-F.
 I-V, II-V, III-V, IV-V, V-F.
Respondido em 10/04/2023 23:20:39
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.
Acerto: 1,0  / 1,0
Seja a seguinte árvore AVL abaixo. Com a inserção da chave 90, marque a opção que indica exatamente o que
acontecerá com a árvore resultante após essa inserção:
 Questão9
a
 Questão10
a
A árvore resultante irá desbalancear à direita do nó de chave 80.
A árvore resultante irá manter o balanceamento geral da árvore.
A árvore resultante irá desbalancear à esquerda do nó de chave 10.
A árvore resultante irá desbalancear à direita do nó de chave 40.
 A árvore resultante irá desbalancear à esquerda do nó de chave 60.
Respondido em 10/04/2023 23:19:33
Explicação:
Ao inserir o nó de chave 90, ele é maior que o nó 80, sendo assim, inserido ao lado direito de 80, causando desbalanceamento
do nó 60 que tem altura da subárvore direita 2 e esquerda 0.