Simulado 1 - ESTRUTURA DE DADOS EM PYTHON

Prévia do material em texto

Disc.: ESTRUTURA DE DADOS EM PYTHON 
Aluno(a): MATEUS DE MELO RODRIGUES SOBRAL 202209290217 
Acertos: 8,0 de 10,0 30/03/2023 
 
 
 
1a 
 Questão 
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.min() retorna o valor médio da matriz. 
 matriz.sum() retorna a soma dos elementos da matriz. 
 
matriz.max() retorna o desvio padrão da matriz. 
 
matriz.mean() retorna o valor mínimo da matriz. 
 
matriz.std() retorna a variância da matriz. 
Respondido em 30/03/2023 11:55:11 
 
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. 
 
 
2a 
 Questão 
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? . 
 
 
32 e 220 
 
26 e 74 
 
28 e 220 
 32 e 224 
 
28 e 224 
Respondido em 30/03/2023 12:14:25 
 
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 
 
 
 
 
 
 
 
 
 
 
 
https://simulado.wyden.com.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=305141512&cod_prova=6122048861&f_cod_disc=
3a 
 Questão 
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: 
 
 
impose, remove/destroy. 
 append, remove/pop. 
 
append, pop/delete. 
 
insert, remove/destroy. 
 
insert, delete/pop. 
Respondido em 30/03/2023 12:15:50 
 
Explicação: 
Em Python a função append insere um elemento ao final 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. 
 
 
4a 
 Questão 
Acerto: 0,0 / 1,0 
 
Uma Deque é uma estrutura de dados mais generalista que as pilhas e filas. Para implementá-la de 
forma eficiente, você pode usar: 
 
 
Lista contígua com 1 variável: início. 
 
Pilha com 1 variável: topo. 
 Fila com 2 variáveis: início e final. 
 
Lista simplesmente encadeada com nó cabeça. 
 Lista duplamente encadeada com 2 variáveis: início e final. 
Respondido em 30/03/2023 12:09:32 
 
Explicação: 
Para implementar uma deque eficientemente, você precisa ter um ponteiro para o início e o final 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 fila é uma especialização da deque. Ou seja, toda fila é um deque, mas nem toda deque é uma fila. 
Podemos assim eliminar a resposta contendo fila. 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 final 
da fila terem complexidade O(n) por precisarem percorrer toda a estrutura, sendo também descartadas. 
 
 
5a 
 Questão 
Acerto: 0,0 / 1,0 
 
Uma lista circular é uma estrutura de dados contínua, permitindo que seja iterada sobre ela de forma 
infinita. Uma das suas aplicações em jogos digitais é: 
 
 Em jogos competitivos, para garantir que não há scripts ou bots rodando no computador. 
 
Em jogos multijogador para garantir que apenas um dos jogadores jogue todas as vezes. 
 
Em jogos mobile, para armazenar o número do telefone do jogador. 
 
Em jogos de um jogador para armazenar um conjunto fixo de elementos. 
 Em jogos multijogador em turnos, permitindo ceder o controle a um jogador por vez. 
Respondido em 30/03/2023 12:13:22 
 
Explicação: 
A grande virtude das listas circulares é o fato delas poderem ser percorridas um elemento por vez, de forma 
infinita. Apenas quando todos os elementos forem percorridos uma vez, começarão a ser percorridos pela 
segunda vez, na mesma ordem. Essa disposição é excelente para a implementação de políticas ¿Round robin¿, 
ou seja, onde cada jogador tem a sua vez de jogar e as vezes são igualmente distribuídas entre os jogadores. 
Por isso a resposta correta é em jogos multijogador em turnos, permitindo ceder o controle a um jogador por vez. 
 
 
6a 
 Questão 
Acerto: 1,0 / 1,0 
 
Suponha que você está implementando um programa que precisa armazenar dados ordenados em uma 
estrutura para serem tratados posteriormente, na ordem inversa à 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 dados é a melhor nessa situação? 
 
 
Fila. 
 
Lista simplesmente encadeada. 
 
Lista em alocação contígua. 
 
Lista duplamente encadeada. 
 Pilha. 
Respondido em 30/03/2023 11:55:20 
 
Explicação: 
A pilha permite o tratamento de nós usando a política requerida, FILO ¿ ¿first in last 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 fim, o fato de a estrutura não variar muito em 
tamanho permite o uso de uma alocação contígua e otimizada para a pilha. A fila não obedece a lógica FILO e as 
listas têm complexidade de inserção e remoção O(n) sendo muito piores que a pilha, principalmente quando o 
número desses tipos de operação é grande. 
 
 
7a 
 Questão 
Acerto: 1,0 / 1,0 
 
Seja a seguinte Árvore Binária. Marque a opção correta: 
 
 
 
A árvore acima possui raiz de valor 3. 
 
Não é possível inserir nós filhos ao nó 70. 
 A quantidade de folhas da árvore é 4. 
 
A quantidade de nós da árvore é de n ¿ 1, sem considerar o nó raiz. 
 
É possível inserir mais um filho a esquerda no nó de valor 90. 
Respondido em 30/03/2023 11:58:07 
 
Explicação: 
A quantidade de folhas da árvore é 4, ou seja, são aqueles nós que possuem grau zero. 
 
 
8a 
 Questão 
Acerto: 1,0 / 1,0 
 
A raiz é o ponto de partida para acessar todos os elementos de uma árvore. Marque a opção correta 
acerca dos principais conceitos de árvore binária de busca: 
 
 
Dado um nó qualquer da árvore binária, todos os nós à direita dele são menores ou iguais a ele. 
 Em todas as estruturas de dados onde se realiza busca, inserção e remoção não são admitidas 
duplicidade de chaves. Isto também inclui as árvores binárias de busca. 
 
Qualquer nó pode ter um número arbitrário de nós, sempre maior que 2. 
 
O objetivo principal da estrutura de dados árvore binária de busca é ordenar uma lista sem a 
preocupação de implementar de forma eficientemente. 
 
Novas chaves maiores que a raiz sempre serão inseridas à esquerda. 
Respondido em 30/03/2023 11:58:01 
 
Explicação: 
O grau máximo de um nó em uma árvore binária é 2. A unicidade de chave é um pressuposto para estruturas de 
busca. O objetivo principal de uma árvore binária de busca é implementar os algoritmos de busca, inserção e 
remoção de forma otimizada. Chaves maiores que a raiz devem ser inseridas à direita. Dado qualquer nó de uma 
árvore binária de busca, deve valer recursivamente a propriedade de que as chaves contidas à esquerda são 
menoresque a raiz e a direita maiores. 
 
 
9a 
 Questão 
Acerto: 1,0 / 1,0 
 
Um percurso é uma forma organizada de acesso à informação armazenada nos nós de uma estrutura de 
dados. Sobre Árvores Binárias de Busca, marque a opção correta: 
 
 
Toda árvore binária de busca tem altura proporcional a n, onde n é o número de nós na árvore. 
 
Toda nova chave inserida em uma árvore binária de busca é inserida na raiz da árvore. 
 
Toda árvore binária de busca tem altura proporcional a log n, onde n é o número de nós na 
árvore. 
 
Não é possível remover um nó interno com dois filhos de uma árvore binária de busca. 
 No pior cenário, uma busca por um elemento em uma árvore binária de busca pode exceder 
O(log n) , chegando a n passos nessa busca. 
Respondido em 30/03/2023 12:07:36 
 
Explicação: 
No pior cenário, os nós de uma árvore podem estar inseridos de tal forma a causar desbalanceamento 
progressivo, levando a n passos em caso de busca por um elemento. 
 
 
 
 
 
 
 
 
 
 
 
 
 
10a 
 Questão 
Acerto: 1,0 / 1,0 
 
Considere a seguinte estrutura de árvore. Marque a alternativa correta: 
 
 
 
Remover o nó 36 irá deixar a árvore com as propriedades de árvore binária de busca. 
 
A árvore da figura se trata de árvore binária de busca. 
 Pode-se afirmar 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. 
 
É necessário executar O(n2) passos para deletar um elemento da árvore acima. 
Respondido em 30/03/2023 12:02:46 
 
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).