SIMULADO ciclo 2 - estrutura de dados

Prévia do material em texto

17/10/2023 17:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/6
Avaliando
Aprendizado
 
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS   
Aluno(a): JAQUELINE DOS SANTOS 202303372621
Acertos: 2,0 de 2,0 17/10/2023
Acerto: 0,2  / 0,2
Ao usar a biblioteca numpy para criar arrays, existem diversas facilidades que um programador pode utilizar, como
funções especí�cas para somar todos os elementos, encontrar valores mínimo e máximo dos elementos, entre outros.
Entretanto uma desvantagem de usar array da biblioteca numpy é:
Diminuição no tempo de programação.
Não é possível adicionar novos elementos ao array.
Os índices passam a ser contados a partir de 1.
 Todos os elementos devem ter o mesmo tamanho.
Não é possível remover elementos do array.
Respondido em 17/10/2023 17:20:37
Explicação:
A desvantagem é que os elementos do array devem ocupar o mesmo espaço de memória, então devem ser de mesmo
tamanho. Isso não permite que você crie arrays com elementos de tamanho assimétricos. Os índices continuam sendo
contados a partir de 0 e as operações de inserção e remoção continuam sendo possíveis. A diminuição no tempo de
programação é uma vantagem.
Acerto: 0,2  / 0,2
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(n), O(1) e O(n).
O(1), O(n) e O(n).
 O(n), O(n) e O(n).
O(log n), O(n) e O(n).
O(n), O(n) e O(1).
Respondido em 17/10/2023 17:24:23
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
posição, levando O(n) operações.
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
Jaqueline
Jaqueline
17/10/2023 17:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/6
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,2  / 0,2
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:
Nas Árvores Binárias de Busca cada nó deve ter exatamente 2 �lhos.
As folhas estão sempre no nível 1 da árvore.
 Ao acessar uma árvore, deve-se acessar pela referência a sua raiz.
A raiz está no maior nível da árvore.
Os nós de uma árvore que possuem grau zero são chamados de raiz.
Respondido em 17/10/2023 17:26:32
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: 0,2  / 0,2
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 simples à 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 dupla à direita de um nó x acontece quando um desbalanceamento de x acontece à direita.
Respondido em 17/10/2023 17:28:33
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,2  / 0,2
Dada a seguinte matriz M, inicializada com o código:
M=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
O código em Python para imprimir cada elemento da coluna iniciada pelo elemento 3 é:
1 2 3 4
5 6 7 8
9 10 11 12
 Questão3
a
 Questão4
a
 Questão5
a
17/10/2023 17:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/6
13 14 15 16
for linha in M:
            print(linha[3])
for linha in M:
            print(linha)
print(M[2])
 for linha in M:
            print(linha[2])
for coluna in M:
            print(coluna)
Respondido em 17/10/2023 17:24:36
Explicação:
O laço deve percorrer uma coluna, iterando linha a linha e extraindo dela o seu terceiro elemento, ou seja linha[2]. A resposta
correta itera pelas linhas e imprime o elemento  [2] de cada uma.
Dentre as respostas erradas, apenas escrever ¿print(linha)¿ imprimirá cada linha como um todo, resultando na impressão de
toda a matriz, linha a linha.
A resposta "print(coluna)" terá o mesmo resultado pois para o código linha e coluna são apenas nomes escolhidos pelo
programador. Poderia ser i, aux ou qualquer outra variável escolhida.
Já "print(linha[3])" está com o índice errado, imprimindo os elementos da coluna iniciada por 4. E ¿print(M[2])¿ imprime toda a
linha iniciada por 9.
Acerto: 0,2  / 0,2
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 24 conterá a chave 5 e próximo 64.
O endereço 32 terá seu campo próximo apontando para 24.
O conteúdo armazenado no endereço 32 será apagado.
 A variável L apontará para 128.
L terá sido apagada.
Respondido em 17/10/2023 17:30:23
 Questão6
a
17/10/2023 17:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/6
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: 0,2  / 0,2
Seja a seguinte árvore binária. Analise as a�rmativas e marque a correta.
Supondo que a árvore em questão é uma árvore binária de busca, a inserção de um novo nó com chave 47 pode
ser feita em qualquer subárvore vazia.
Ao buscar pelo nó 45 na árvore acima, um algoritmo de busca em Python irá realizar sempre O(n) passos. Isto
ocorre uma vez que é necessário analisar todos os nós da árvore para encontrar o nó 45.
A árvore acima possui 4 nós folhas.
 A �gura ilustra uma árvore binária de busca porque para todos os nós vale a seguinte propriedade: os nós
contidos na subárvores esquerda são menores que a raiz e os contidos na subárvore direita são maiores.
É possível inserir mais um nó �lho ao nó 30.
Respondido em 17/10/2023 17:32:28
Explicação:
A árvore é uma árvore binária de busca porque dado um nó qualquer da árvore, os nós contidos na subárvore esquerda são
menores que a raiz e os a direita, maiores que a raiz. A busca só seria executada em O(n) caso a árvore fosse uma árvore zig
zag.  47 só poderia ser inserido à direita de 45. A árvore tem 3 folhas. Arvoresbinárias só podem ter nós com grau 2.
Acerto: 0,2  / 0,2
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:
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(logn).
 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).
As rotações simples e duplas possuem complexidade de execução O(n).
Respondido em 17/10/2023 17:33:50
 Questão7
a
 Questão8
a
17/10/2023 17:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/6
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: 0,2  / 0,2
O método de ordenação da bolha, ou Bubblesort (BS) tem complexidade de pior caso O(n2) e melhor caso O(n).
Suponha que exista um algoritmo de ordenação MS que tem complexidade de melhor caso O(nlog n) e de pior caso
O(nlog n). Podemos a�rmar que:
Para uma única entrada de tamanho grande, BS executará em menos tempo que MS.
 Para um grande conjunto de entradas variadas de tamanho grande, MS executará em menos tempo que BS, em
média.
MS e BS são igualmente e�cientes em ordenar elementos, independente da entrada ou seu tamanho.
Para uma única entrada de tamanho grande, MS executará em menos tempo que BS.
Para um grande conjunto de entradas variadas de tamanho grande, BS executará em menos tempo que MS, em
média.
Respondido em 17/10/2023 17:35:53
Explicação:
Pela natureza do tratamento de complexidade de algoritmos e o uso da notação O, a única a�rmativa verdadeira é a de que em
média, com um grande número de entradas distintas e de tamanho grande, MS executará mais rápido que BS pois sua
complexidade assintótica O(nlogn) é melhor que a de BS O(n2).
A a�rmação inversa está errada pelo mesmo argumento, O(nlogn) é melhor que O(n2).
As a�rmações que tratam de uma única entrada são falsas, pois você sempre pode escolher uma entrada que seja de melhor
caso para um dos algoritmos e seja ruim para o outro.
Por �m, a a�rmação de que ambos são igualmente e�cientes é desmentida pelo pior caso.
Acerto: 0,2  / 0,2
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 = M
 InicioF==(�nalF+1)mod M
FinalF== M
InicioF== �nalF
Respondido em 17/10/2023 17:36:35
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ão9
a
 Questão10
a
17/10/2023 17:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/6