Estrutura de Dados - AVA1

Prévia do material em texto

20/09/2023, 22:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/6
Avaliando
Aprendizado
Teste seu conhecimento acumulado
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(n)
O(nlog n)
O(n2)
O(log n)
O(1)
Respondido em 20/09/2023 22:35:25
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
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 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 em turnos, permitindo ceder o controle a um jogador por vez.
Em jogos multijogador para garantir que apenas um dos jogadores jogue todas as vezes.
Questão1
a
Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
20/09/2023, 22:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/6
Em jogos de um jogador para armazenar um conjunto �xo de elementos.
Respondido em 20/09/2023 22:36:25
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,0  / 0,2
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:
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)
Busca: O(n) / Remoção: O(log n) / Inserção: O(log n)
 Busca: O(n) / Remoção: O(n) / Inserção: O(log n)
 Busca: O(n) / Remoção: O(n) / Inserção: O(n)
Respondido em 20/09/2023 22:37:04
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).
Acerto: 0,2  / 0,2
As árvores AVL constituem uma importante estrutura de dados que disponibilizam operações de busca,
inserção e remoção. Classi�que como verdadeiro ou falso as a�rmativas abaixo:
I - As árvores de Fibonacci são as árvores de altura máxima h com número mínimo do nós n e altura proporcional
a log n.
II - As árvores completas são árvores AVL.
III - É possível construir uma topologia de uma árvore AVL que não seja nem completa nem de Fibonacci com
altura proporcional a log n.
IV - Uma vez que a altura das árvores AVL é proporcional a log n, podemos garantir que a busca ocorre numa
complexidade de O(log n).
V - Na remoção, pode ser necessário realizar todas as rotações, no pior caso, do pai de uma folha que está sendo
removida até a raiz. Por esta razão, a complexidade da remoção é maior que O(log n).
I-V, II-V, III-F, IV-V, V-F.
 I-V, II-V, III-V, IV-V, V-F.
I-F, II-F, III-F, IV-V, V-V.
I-F, II-F, III-V, IV-F, V-F.
I-V, II-F, III-F, IV-V, V-V.
 Questão3
a
 Questão4
a
20/09/2023, 22:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/6
Respondido em 20/09/2023 22:38:09
Explicação:
Nem sempre é necessário realizar todas as operações, visto que a remoção pode eliminar uma folha e não causar
desbalanceamento na árvore.
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.sum() retorna a soma dos elementos da matriz.
matriz.max() retorna o desvio padrão da matriz.
matriz.std() retorna a variância da matriz.
matriz.mean() retorna o valor mínimo da matriz.
matriz.min() retorna o valor médio da matriz.
Respondido em 20/09/2023 22:39:09
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.
Acerto: 0,2  / 0,2
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 simplesmente encadeada.
Lista em alocação contígua.
Pilha.
 Fila.
Lista duplamente encadeada.
Respondido em 20/09/2023 22:40:19
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.
Acerto: 0,2  / 0,2
 Questão5
a
 Questão6
a
 Questão
7
a
20/09/2023, 22:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/6
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:
O objetivo principal da estrutura de dados árvore binária de busca é ordenar uma lista sem a
preocupação de implementar de forma e�cientemente.
Dado um nó qualquer da árvore binária, todos os nós à direita dele são menores ou iguais a ele.
Qualquer nó pode ter um número arbitrário de nós, sempre maior que 2.
Novas chaves maiores que a raiz sempre serão inseridas à esquerda.
 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.
Respondido em 20/09/2023 22:41:10
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 menores que a raiz e a
direita maiores.
Acerto: 0,2/ 0,2
Seja a seguinte árvore AVL abaixo. Com a inserção da chave 90, marque a opção que indica exatamente o que
acontecerá com a árvore resultante após essa inserção:
A árvore resultante irá manter o balanceamento geral da árvore.
 A árvore resultante irá desbalancear à esquerda do nó de chave 60.
A árvore resultante irá desbalancear à direita do nó de chave 80.
A árvore resultante irá desbalancear à direita do nó de chave 40.
A árvore resultante irá desbalancear à esquerda do nó de chave 10.
Respondido em 20/09/2023 22:42:12
Explicação:
Ao inserir o nó de chave 90, ele é maior que o nó 80, sendo assim, inserido ao lado direito de 80, causando
desbalanceamento do nó 60 que tem altura da subárvore direita 2 e esquerda 0.
 Questão8
a
20/09/2023, 22:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/6
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 as operações variam em proporção logarítmica à entrada.
c -O(log n) signi�ca que para n=64  o algoritmo realizará 6 operações no pior caso.
O(n) signi�ca que para n=50  o algoritmo executará no máximo 50 operações.
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.
Respondido em 20/09/2023 22:43:04
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
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?
 Pilha.
Fila.
Lista em alocação contígua.
Lista duplamente encadeada.
Lista simplesmente encadeada.
Respondido em 20/09/2023 22:43:33
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
 Questão9
a
 Questão10
a
20/09/2023, 22:44 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/6
inserção e remoção O(n) sendo muito piores que a pilha, principalmente quando o número desses tipos de operação é
grande.