teste de conhecimento, estrutura de dados em python

Prévia do material em texto

10/05/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/5
Teste de
Conhecimento
 avalie sua aprendizagem
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 é:
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)
ESTRUTURA DE DADOS EM PYTHON
Lupa  
 
DGT1335_202208357784_TEMAS
Aluno: RODRIGO CARVALHO XAVIER SAMPAIO Matr.: 202208357784
Disc.: ESTRUTURA DE DADOS E  2023.1 EAD (G) / EX
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para
sua avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
7390ALGORITMOS E A LINGUAGEM PYTHON
 
1.
c -O(log n) signi�ca que para n=64  o algoritmo realizará 6 operações no pior caso.
O(n) signi�ca que as operações variam em proporção logarítmica à entrada.
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 para n=50  o algoritmo executará no máximo 50 operações.
Data Resp.: 10/05/2023 19:59: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.
 
2.
nlog n + 500
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
10/05/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/5
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? .
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:
(nlog n)/2
100n + 5log n
2n
2n2
Data Resp.: 10/05/2023 19:59:49
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.
 
3.
28 e 224
26 e 74
28 e 220
32 e 224
32 e 220
Data Resp.: 10/05/2023 20:02:54
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
7391LISTAS, PILHAS, FILAS E DEQUES
 
4.
O(n), O(n) e O(1).
O(log n), O(n) e O(n).
O(n), O(n) e O(n).
O(n), O(1) e O(n).
O(1), O(n) e O(n).
Data Resp.: 10/05/2023 19:59:59
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.
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).
10/05/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/5
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?
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?
Seja a seguinte árvore, marque a opção correta que indica o porquê a árvore abaixo não é uma árvore binária de
busca:
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.
 
5.
Não ordenada: 32, 34; ordenada: 32, 34.
Não ordenada: 36, 37; ordenada: 32, 37.
Não ordenada: 36, 37; ordenada: 32, 33.
Não ordenada: 40, 42;  ordenada: 40, 42.
Não ordenada: 40, 42; ordenada: 32, 42.
Data Resp.: 10/05/2023 20:00:06
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.
 
6.
Lista simplesmente encadeada.
Lista em alocação contígua.
Lista duplamente encadeada.
Pilha.
Fila.
Data Resp.: 10/05/2023 20:00:34
Explicação:
A pilha permite o tratamento de nós usando a política requerida, FILO ¿ ¿�rst 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 �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 pilha. A �la 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.
7408ÁRVORES EM PHYTON
 
7.
10/05/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/5
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:
Uma árvore binária de busca auto balanceada é uma estrutura de dados avançada, que otimiza os tempos de
inserção, deleção e busca. Um módulo Python que implementa e executa essas atividades e�cientemente é a sbbst
(do inglês, self-balancing binary search tree). A complexidade de espaço do módulo sbbst:
Não é árvore binária de busca pois essa árvore deve estar perfeitamente balanceada.
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.
Não é árvore binária de busca pois está desbalanceada.
Não é árvore binária de busca pois o nó 35 deveria estar inserido à direita do nó 20.
Data Resp.: 10/05/202320:01:26
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.
 
8.
Busca: O(n) / Remoção: O(n) / Inserção: O(log n)
Busca: O(n) / Remoção: O(log n) / Inserção: O(log n)
Busca: O(n) / Remoção: O(n) / Inserção: O(n)
Busca: O(log n) / Remoção: O(n) / Inserção: O(log n)
Busca: O(1) / Remoção: O(log n) / Inserção: O(log n)
Data Resp.: 10/05/2023 20:02:31
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).
7392ÁRVORES DE BUSCA
 
9.
0(n2).
0(n log n).
0(n).
0(n3).
10/05/2023, 20:03 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/5
Em uma Árvore B, temos que: Cada nó contém no mínimo m registros (m+1 descendentes) e no máximo 2m
registros (e 2m+1 descendentes), exceto o nó que é raiz que pode conter entre 1 e 2m registros e todos os nós
folhas aparecem no mesmo nível.  Sobre Árvores B, é correto a�rmar:
0(log n).
Data Resp.: 10/05/2023 20:02:10
Explicação:
O módulo sbbst possui espaço O(n)  na memória (onde n  equivale a quantidade de nós de uma árvore).
 
10.
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser buscado em um nó com
2m + 1 registros.
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó com
menos de 2m registros.
O particionamento de nós ocorre quando é necessário diminuir a altura da árvore.
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó com
2m registros.
O particionamento de nós em uma Árvore B ocorre quando a chave do registro a ser inserido contém um
valor(conteúdo) intermediário entre os valores das chaves dos registros contidos no mesmo nó.
Data Resp.: 10/05/2023 20:02:23
Explicação:
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó com 2m
registros.
    Não Respondida      Não Gravada     Gravada
Exercício inciado em 10/05/2023 19:59:33.