Estácio_ GabaritoSimuladoEstrutura de dados em Python02

Prévia do material em texto

06/04/2023, 09:16 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305584452&cod_prova=6147025186&f_cod_disc=… 1/5
 
Meus Simulados
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS EM PYTHON   
Aluno(a): ELBA LUCIA DA SILVEIRA ARAUJO DA MATA 202001039368
Acertos: 8,0 de 10,0 05/04/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(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.
O(n) signi�ca que as operações variam em proporção logarítmica à entrada.
Respondido em 06/04/2023 09:05:07
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
Matrizes podem ser implementadas em Python utilizando a biblioteca numpy, trazendo diversas funções já
implementadas. Dentre os pares de função com sua funcionalidade a seguir, qual é o correto?
matriz.mean() retorna o valor mínimo da matriz.
matriz.std() retorna a variância da matriz.
matriz.max() retorna o desvio padrão da matriz.
 matriz.sum() retorna a soma dos elementos da matriz.
matriz.min() retorna o valor médio da matriz.
Respondido em 06/04/2023 08:48:32
Explicação:
Dentre os pares apresentados, o único correto é o da função sum() que é a soma dos elementos. std() e mean() são funções
estatísticas que retornam o desvio padrão e a média respectivamente. max() retorna o elemento de maior valor e min(), por
sua vez, retorna o elemento de menor valor.
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
06/04/2023, 09:16 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305584452&cod_prova=6147025186&f_cod_disc=… 2/5
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
2n
2n2
(nlog n)/2
 100n + 5log n
Respondido em 06/04/2023 08:51:37
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
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.
 A variável L apontará para 128.
L terá sido apagada.
O endereço 24 conterá a chave 5 e próximo 64.
O conteúdo armazenado no endereço 32 será apagado.
Respondido em 06/04/2023 08:50:16
Explicação:
 Questão3
a
 Questão4
a
06/04/2023, 09:16 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305584452&cod_prova=6147025186&f_cod_disc=… 3/5
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 Deque é uma estrutura de dados mais generalista que as pilhas e �las. Para implementá-la de forma e�ciente, você
pode usar:
 Lista duplamente encadeada com 2 variáveis: início e �nal.
Lista contígua com 1 variável: início.
Lista simplesmente encadeada com nó cabeça.
Pilha com 1 variável: topo.
Fila com 2 variáveis: início e �nal.
Respondido em 06/04/2023 09:02:11
Explicação:
Para implementar uma deque e�cientemente, você precisa ter um ponteiro para o início e o �nal da deque, permitindo
inserções e remoções em ambas as pontas com complexidade O(1) , sem  a necessidade de percorrer a estrutura, o que seria
O(n).
Além disso, a �la é uma especialização da deque. Ou seja, toda �la é um deque, mas nem toda deque é uma �la. Podemos assim
eliminar a resposta contendo �la. A resposta restante que possui 2 variáveis é a correta. Lista duplamente encadeada. Ela
permite a inserção e remoção nas extremidades com complexidade O(1).
A lista contígua e a simplesmente encadeada com nó cabeça levariam a operação de inserção e remoção ao �nal da �la terem
complexidade O(n) por precisarem percorrer toda a estrutura, sendo também descartadas.
Acerto: 1,0  / 1,0
Em uma implementação da estrutura de dados do tipo �la, você possui um espaço de memória contíguo a ela alocada
com capacidade para M nós. A variável da �la é F, e duas variáveis guardam os índices do início e �nal da �la (inicioF e
�nalF).  Em uma implementação otimizada de F, como podemos identi�car que a �la está cheia?
InicioF==�nalF + 1
InicioF== �nalF
 InicioF==(�nalF+1)mod M
FinalF== M
InicioF = M
Respondido em 06/04/2023 09:01:33
Explicação:
Em uma implementação otimizada da �la, é usado um sistema modular, onde o início e o �nal da �la se movem a cada inserção
e remoção. A cada inserção, �nalF aumenta em 1, até o máximo M, depois volta para 0 e assim por diante. A cada remoção
inícioF aumenta em 1, até o máximo M e depois volta a 0. dessa forma a �la está cheia quando (�nalF+1)modM é igual a inicio.
 Questão5
a
 Questão6
a
06/04/2023, 09:16 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305584452&cod_prova=6147025186&f_cod_disc=… 4/5
Acerto: 1,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:
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 essa árvore deve estar perfeitamente balanceada.
Não é árvore binária de busca pois está desbalanceada.
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ó 22 deveria estar inserido à direita do nó 20.
Respondido em 06/04/2023 08:49:01
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(1) / 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(n)
Busca: O(n) / Remoção: O(n) / Inserção: O(log n)
Respondido em 06/04/2023 08:55:12
Explicação:
No pior caso uma árvore binária de busca com n chaves tem n níveis. Assim, o pior caso da 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
A complexidade de execução é uma medida da e�ciência de um algoritmo. Ela indica o número de operações que o
algoritmo precisa realizar para completar a sua tarefa, em função do tamanho da entrada. Nesse sentido, marque a
opção correta sobre a análise de complexidade das operações de rotação em árvores AVL:
 Questão7
a
 Questão8
a
 Questão9
a
06/04/2023, 09:16 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305584452&cod_prova=6147025186&f_cod_disc=… 5/5
As rotações simples e duplas possuem complexidade de execução O(n).
As rotações simples e duplas possuem complexidade de execução O(logn).
As rotações simples e duplas possuem complexidade de execução O(n2).
 As rotações simples e duplas possuem complexidade de execução O(1).
As rotações simples e duplas possuem complexidade de execução O(n log n).
Respondido em 06/04/2023 08:54:39
Explicação:
As operações de rotação simples e duplas são utilizadas tanto na inserção quanto na remoção de nós de árvore AVL e servem
de auxílio para tornar um nó que foi desbalanceado seja balanceado novamente. Essas operações incluem trocas de ponteiros
entre os nós, ou seja, O(1), o que não penaliza a complexidade de execução das operações na árvore.
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.
 I, II, IV e V são corretas.
I, III, IV e V são corretas.
I, II, III e IV são corretas.
I, II, III, IV e V são corretas.
II, III, IV e V são corretas.
Respondido em 06/04/2023 09:07:03
Explicação:
A a�rmativa III é incorreta, não é necessário percorrer todos os nós da árvore se ela estiver perfeitamente balanceada.
 Questão10
a