1o Avaliando Aprendizado - AVA1

Prévia do material em texto

Avaliando
Aprendizado
 
Teste seu conhecimento acumulado
Disc.: ESTRUTURA DE DADOS   
Aluno(a): ALEX CAVALCANTE BRASIL 202209101503
Acertos: 1,8 de 2,0 21/09/2023
Acerto: 0,2  / 0,2
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 é:
O(n) signi�ca que para n=50  o algoritmo executará no máximo 50 operações.
O(n) signi�ca que as operações variam em proporção logarítmica à entrada.
 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 realizará 50 operações no pior caso.
c -O(log n) signi�ca que para n=64  o algoritmo realizará 6 operações no pior caso.
Respondido em 21/09/2023 10:43:06
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: 0,2  / 0,2
Uma Pilha é uma estrutura de dados que permite o armazenamento de elementos (ou nós) sequencialmente.
Sobre as Pilhas é possível a�rmar que:
Permitem inserção no seu início e remoção apenas no seu �nal.
 Permitem inserção ou remoção apenas no seu início.
Permitem inserção ou remoção apenas no seu início ou no seu �nal.
Permitem inserção no seu �nal e remoção apenas no seu início.
Permitem inserção ou remoção em qualquer de suas posições.
Respondido em 21/09/2023 10:49:53
Explicação:
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:voltar();
A Pilha, assemelhando-se ao seu conceito na vida real, permite inserções e remoções apenas no seu início (push e
pop). Dessa forma, implementa a política ¿First In, Last Out¿ (FILO) na qual o nó que chegou há menos tempo será
sempre removido primeiro. As demais respostas indicam outras estruturas como listas, �las e deques.
Acerto: 0,2  / 0,2
Seja a seguinte função em Python para percurso em uma árvore binária implementada em Python. Marque a
opção correta de qual percurso em árvores se trata essa função:
 Percurso Pré-ordem
Percurso Em-ordem
Percurso raiz-folha
Percurso Anti simétrico
Percurso Pós-ordem
Respondido em 21/09/2023 10:55:03
Explicação:
Para realizar o percurso em pré-ordem, são necessários três acessos ao nó. No caso da pré-ordem, no primeiro,
executamos a visita (print(raiz.chave)), no segundo, chamamos recursivamente o algoritmo para a sub-árvores
esquerda (Visita(raiz.esquerda)) e, no terceiro, ocorre a chamada do percurso em pré-ordem do ramo direito
(Visita(raiz.direita)).
Acerto: 0,2  / 0,2
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:
 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 ocorre quando é necessário diminuir a altura da árvore.
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 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ó.
Respondido em 21/09/2023 10:52:39
Explicação:
O particionamento de nós em uma Árvore B ocorre quando um registro precisa ser inserido em um nó com 2m
registros.
 Questão3
a
 Questão4
a
Acerto: 0,2  / 0,2
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 21/09/2023 10:44:27
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: 0,2  / 0,2
Uma lista circular é uma estrutura de dados contínua, permitindo que seja iterada sobre ela de forma in�nita.
Uma das suas aplicações em jogos digitais é:
 Em jogos multijogador em turnos, permitindo ceder o controle a um jogador por vez.
Em jogos competitivos, para garantir que não há scripts ou bots rodando no computador.
Em jogos mobile, para armazenar o número do telefone do jogador.
Em jogos multijogador para garantir que apenas um dos jogadores jogue todas as vezes.
Em jogos de um jogador para armazenar um conjunto �xo de elementos.
Respondido em 21/09/2023 10:57:08
Explicação:
A grande virtude das listas circulares é o fato delas poderem ser percorridas um elemento por vez, de forma in�nita.
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.
Acerto: 0,2  / 0,2
Seja a seguinte árvore de expressões aritméticas abaixo.
 Questão5
a
 Questão6
a
 Questão7
a
O resultado da visita em pre�xo dessa árvore é:
A * B + C
A + B * C
 + A * B C
A + ( B * C )
A + * B C
Respondido em 21/09/2023 10:53:50
Explicação:
O percurso em pre�xo é de�nido recursivamente. A partir da raiz r da árvore de expressões aritméticas T, percorre-se
a árvore de da seguinte forma:
1 - visita-se a raiz;
2 - percorre-se a sub-árvores esquerda de T, em pre�xo e
3 - percorre-se a sub-árvores direita de T, em pre�xo.
O resultado da visita é representado abaixo:
Acerto: 0,2  / 0,2
Considere a seguinte estrutura de árvore. Marque a alternativa correta:
 Questão8
a
A árvore da �gura se trata de árvore binária de busca.
A árvore acima é conhecida como árvore zig zag balanceada.
É necessário executar O(n2)  passos para deletar um elemento da árvore acima.
 Pode-se a�rmar que o número de passos para buscar um elemento na árvore acima é, no máximo, O(log
n).
Remover o nó 36 irá deixar a árvore com as propriedades de árvore binária de busca.
Respondido em 21/09/2023 10:51:02
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
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? .
28 e 224
32 e 220
26 e 74
 32 e 224
28 e 220
Respondido em 21/09/202310:45: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
Acerto: 0,0  / 0,2
 Questão9
a
 Questão10
a
Suponha que você está implementando um programa que precisa armazenar dados ordenados em uma
estrutura para serem tratados posteriormente, na ordem em 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 dado é a melhor nessa situação?
Lista duplamente encadeada.
 Pilha.
 Fila.
Lista simplesmente encadeada.
Lista em alocação contígua.
Respondido em 21/09/2023 10:46:33
Explicação:
A �la permite o tratamento de nós usando a política requerida, FIFO ¿ ¿�rst in �rst 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 �la usando lógica circular e variáveis para o início e �nal da �la. A pilha não
obedece a lógica FIFO e as listas tem complexidade de inserção e remoção O(n) sendo muito piores que a �la,
principalmente quando o número desses tipos de operação é grande.