Estruturas de Dados

Prévia do material em texto

10/11/2023, 09:51 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=320968037&cod_prova=6792420017&f_cod_disc= 1/6
 
Meus Simulados
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS   
Aluno(a): HENRIQUE NUNES DA PAIXÃO 202302971342
Acertos: 2,0 de 2,0 03/11/2023
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, MS executará em menos tempo que BS.
MS e BS são igualmente e�cientes em ordenar elementos, independente da entrada ou seu tamanho.
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.
Para um grande conjunto de entradas variadas de tamanho grande, BS executará em menos tempo que MS, em
média.
Respondido em 03/11/2023 14:26:23
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
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?
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:voltar();
10/11/2023, 09:51 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=320968037&cod_prova=6792420017&f_cod_disc= 2/6
 A variável L apontará para 128.
L terá sido apagada.
O endereço 32 terá seu campo próximo apontando para 24.
O conteúdo armazenado no endereço 32 será apagado.
O endereço 24 conterá a chave 5 e próximo 64.
Respondido em 03/11/2023 14:27:11
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
Marque a opção correta acerca da visita In-Ordem, usada em percursos de árvores binárias de busca:
O percurso in-ordem inicia a visita nas sub-árvores a direita, depois visita a raiz da árvore e depois as sub-
árvores à esquerda em ordem simétrica.
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois as sub-
árvores à direita em ordem assimétrica.
 O percurso in-ordem inicia a visita nas sub-árvores a esquerda em ordem simétrica, depois visita a raiz da
árvore e depois as sub-árvores à direita em ordem simétrica.
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois as sub-
árvores à direita em ordem simétrica, terminando pela raiz principal.
O percurso in-ordem inicia a visita pela raiz da árvore, depois visita as sub-árvores a esquerda e depois as sub-
árvores à direita em ordem simétrica.
Respondido em 03/11/2023 14:28:22
Explicação:
 Questão3
a
10/11/2023, 09:51 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=320968037&cod_prova=6792420017&f_cod_disc= 3/6
O percurso em ordem simétrica (In-ordem) é de�nido como se segue. A partir da raiz r da árvore T, percorre-se a árvore da
seguinte forma:
1 - percorre-se a sub-árvores esquerda de T, em ordem simétrica e
2 - visita-se a raiz;
3 - percorre-se a sub-árvores direita de T, em ordem simétrica.
Acerto: 0,2  / 0,2
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.
É necessário executar O(n2)  passos para deletar um elemento da árvore acima.
Remover o nó 36 irá deixar a árvore com as propriedades de árvore binária de busca.
Respondido em 03/11/2023 14:30:19
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).
Acerto: 0,2  / 0,2
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.max() retorna o desvio padrão da matriz.
matriz.std() retorna a variância da matriz.
 matriz.sum() retorna a soma dos elementos da matriz.
matriz.min() retorna o valor médio da matriz.
matriz.mean() retorna o valor mínimo da matriz.
Respondido em 03/11/2023 14:31:16
Explicação:
 Questão4
a
 Questão5
a
10/11/2023, 09:51 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=320968037&cod_prova=6792420017&f_cod_disc= 4/6
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.
Acerto: 0,2  / 0,2
Uma Deque é uma estrutura de dados mais generalista que as pilhas e �las. Para implementá-la de forma e�ciente, você
pode usar:
Pilha com 1 variável: topo.
Lista simplesmente encadeada com nó cabeça.
Fila com 2 variáveis: início e �nal.
Lista contígua com 1 variável: início.
 Lista duplamente encadeada com 2 variáveis: início e �nal.
Respondido em 03/11/2023 14:32:56
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: 0,2  / 0,2
Seja a seguinte árvore binária. Analise as a�rmativas e marque a correta.
 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.
A árvore acima possui 4 nós folhas.
É possível inserir mais um nó �lho ao nó 30.
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.
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.
Respondido em 03/11/2023 14:33:39
Explicação:
 Questão6
a
 Questão7
a
10/11/2023, 09:51 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=320968037&cod_prova=6792420017&f_cod_disc= 5/6
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. Arvores binárias só podem ter nós com grau 2.
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 à direita de um nó x acontece quando um desbalanceamento de x acontece à direita.
Uma rotação dupla à esquerda de um nó x acontece quando um desbalanceamento de x acontece à esquerda.
 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 03/11/2023 14:34:24
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
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(1)
O(log n)
O(nlog n)
O(n)
 O(n2)
Respondido em 03/11/2023 14:35:29
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: 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?
 Questão8
a
 Questão9
a
 Questão10
a
10/11/2023, 09:51 Estácio: Alunos
https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=320968037&cod_prova=6792420017&f_cod_disc= 6/6
InicioF==�nalF + 1
InicioF = M
FinalF== M
InicioF== �nalF
 InicioF==(�nalF+1)mod M
Respondido em 03/11/2023 14:36:18
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.