ESTRUTURA DE DADOS EM PYTHON-simulado1

Prévia do material em texto

04/04/2023, 11:35 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/5
 
Meus
Simulados
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS EM PYTHON   
Aluno(a): RODRIGO SCHIAVO LEITE 202208477501
Acertos: 3,0 de 10,0 28/03/2023
Acerto: 0,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 é:
c -O(log n) signi�ca que para n=64  o algoritmo realizará 6 operações no pior caso.
 O(n2) signi�ca que as operações variam em proporção quadrática à 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(n) signi�ca que as operações variam em proporção logarítmica à entrada.
Respondido em 28/03/2023 13:18:41
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
O uso de funções recursivas pode facilitar a implementação de diversos algoritmos. Toda recursão depende de
dois elementos: o caso base e o passo recursivo. Dentre as opções a seguir, a que apresenta um passo recursivo
é:
par(n)=par(n)
f(n)=g(n-1)
�b(n)=n-1 + n-2
fat(1)=1
 fat(n)=n*fat(n-1)
Respondido em 28/03/2023 12:51:58
Explicação:
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
04/04/2023, 11:35 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/5
O passo recursivo é o elemento que faz o cálculo da função recursiva mover-se em direção ao resultado. Deve
envolver a chamada da própria função com um valor diferente de entrada. Isso só acontece na resposta correta:
fat(n)=n*fat(n-1) , passo recursivo da função de cálculo de fatorial.
fat(1)=1  é o caso base dessa mesma função. par(n)=par(n)  é uma tautologia, e não uma recursão. As demais respostas
são funções que não chamam a si mesmas, não podendo ser passos recursivos.
Acerto: 1,0  / 1,0
Em Python é possível implementar um array utilizando o tipo padrão list. Essa implementação permite o uso das
seguintes funções para inserir e remover um elemento, respectivamente:
 append, remove/pop.
insert, remove/destroy.
insert, delete/pop.
impose, remove/destroy.
append, pop/delete.
Respondido em 28/03/2023 12:52:49
Explicação:
Em Python a função append insere um elemento ao �nal da lista. As funções "remove" e "pop" podem remover um
elemento, de maneiras diferentes. Remove tira um elemento conhecido usando o seu conteúdo, já pop remove um
elemento usando seu índice, ou seja, a sua posição na lista.
Acerto: 0,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: 32, 34; ordenada: 32, 34.
 Não ordenada: 40, 42;  ordenada: 40, 42.
Não ordenada: 36, 37; ordenada: 32, 33.
Não ordenada: 36, 37; ordenada: 32, 37.
Respondido em 28/03/2023 13:18:34
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.
Acerto: 0,0  / 1,0
Uma Pilha é uma estrutura de dados que permite o armazenamento de elementos (ou nós) sequencialmente.
Sobre as Pilhas é possível a�rmar que:
 Questão3
a
 Questão4
a
 Questão5
a
04/04/2023, 11:35 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/5
Permitem inserção ou remoção apenas no seu início ou no seu �nal.
 Permitem inserção no seu início e remoção apenas no seu �nal.
 Permitem inserção ou remoção apenas no seu início.
Permitem inserção no seu �nal e remoção apenas no seu início.
Permitem inserção ou remoção em qualquer de suas posições.
Respondido em 28/03/2023 13:10:41
Explicação:
A Pilha, assemelhando-se ao seu conceito na vida real, permite inserções e remoções apenas no seu início (push e
pop). Dessa forma, implementa a política ¿First In, Last Out¿ (FILO) na qual o nó que chegou há menos tempo será
sempre removido primeiro. As demais respostas indicam outras estruturas como listas, �las e deques.
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.
Pilha.
Lista simplesmente encadeada.
 Fila.
 Lista duplamente encadeada.
Respondido em 28/03/2023 12:59:26
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
Seja a seguinte árvore, marque a opção correta que indica o porquê a árvore abaixo não é uma árvore binária de
busca:
 Questão6
a
 Questão7
a
04/04/2023, 11:35 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/5
Não é árvore binária de busca pois essa árvore deve estar perfeitamente balanceada.
 Não é árvore binária de busca pois o nó 22 deveria estar inserido à direita do nó 20.
Não é árvore binária de busca pois esta árvore deve estar com os níveis de suas folhas todas igualmente
perfeitas.
 Não é árvore binária de busca pois o nó 35 deveria estar inserido à direita do nó 20.
Não é árvore binária de busca pois está desbalanceada.
Respondido em 28/03/2023 13:13:07
Explicação:
Uma árvore binária de busca são árvores que obedecem às seguintes propriedades:
Dado um nó qualquer da árvore binária, todos os nós à esquerda dele são menores ou iguais a ele.
Dado um nó qualquer da árvore binária, todos os nós à direita dele são maiores ou iguais a ele.
Observe que a sub-árvore 20-22 não respeita a regra básica, portanto, o nó 22 deveria estar a direita do nó 20.
Acerto: 0,0  / 1,0
As operações de busca, remoção e inserção de nós em uma árvore binária de busca levam determinado tempo
de execução de seus algoritmos. Esses tempos são dados pela alternativa:
Busca: O(n) / Remoção: O(log n) / Inserção: O(log n)
 Busca: O(log n) / Remoção: O(n) / Inserção: O(log n)
Busca: O(n) / Remoção: O(n) / Inserção: O(log n)
Busca: O(1) / Remoção: O(log n) / Inserção: O(log n)
 Busca: O(n) / Remoção: O(n) / Inserção: O(n)
Respondido em 28/03/2023 13:00:14
Explicação:
No pior caso uma árvore binária de busca com n chaves tem n níveis. Assim, o pior casoda busca, é buscar o nó mais
profundo da árvore que demandará n comparações. Como a busca é subrotina da inserção e da remoção, então as três
operações terão complexidade de pior caso de O(n).
Acerto: 1,0  / 1,0
Existem vários tipos diferentes de árvores de busca, como árvores binárias, AVL e árvores B. Nesse sentido,
marque a opção correta sobre os procedimentos de rotação em árvores AVL:
Uma rotação dupla à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
esquerda.
Uma rotação dupla à direita de um nó x acontece quando um desbalanceamento de x acontece à direita.
 Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
direita.
Uma rotação simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à
esquerda.
Uma rotação simples à direita de um nó x acontece quando um desbalanceamento de x acontece à
direita.
Respondido em 28/03/2023 13:04:59
 Questão8
a
 Questão9
a
04/04/2023, 11:35 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/5
Explicação:
Em uma árvore AVL, uma rotação simples à esquerda de um nó acontece quando um desbalanceamento de  acontece
à direita. Se um nó  desbalanceia para um lado, ele deve rotacionar de forma inversa para �car balanceado.
Acerto: 0,0  / 1,0
Considere a seguinte estrutura de árvore. Marque a alternativa correta:
 Pode-se a�rmar que o número de passos para buscar um elemento na árvore acima é, no máximo, O(log
n).
A árvore acima é conhecida como árvore zig zag balanceada.
 A árvore da �gura se trata de árvore binária de busca.
Remover o nó 36 irá deixar a árvore com as propriedades de árvore binária de busca.
É necessário executar O(n2)  passos para deletar um elemento da árvore acima.
Respondido em 28/03/2023 13:16:32
Explicação:
Apesar de que a árvore considerada não é árvore binária de busca, observa-se que os nós estão dispostos de forma
balanceada e em níveis, portanto o número de passos para buscar um elemento na árvore acima é, no máximo, 0(log
n).
 Questão10
a