Baixe o app para aproveitar ainda mais
Prévia do material em texto
Avaliando Aprendizado Teste seu conhecimento acumulado Disc.: ESTRUTURA DE DADOS Aluno(a): JUARY GOMES DOS SANTOS 202303519291 Acertos: 2,0 de 2,0 27/11/2023 Acerto: 0,2 / 0,2 O uso de funções recursivas pode facilitar a implementação de diversos algoritmos. Toda recursão depende de dois elementos: o caso base e o passo recursivo. Dentre as opções a seguir, a que apresenta um passo recursivo é: fat(1)=1 par(n)=par(n) �b(n)=n-1 + n-2 f(n)=g(n-1) fat(n)=n*fat(n-1) Respondido em 27/11/2023 22:01:10 Explicação: O passo recursivo é o elemento que faz o cálculo da função recursiva mover-se em direção ao resultado. Deve envolver a chamada da própria função com um valor diferente de entrada. Isso só acontece na resposta correta: fat(n)=n*fat(n-1) , passo recursivo da função de cálculo de fatorial. fat(1)=1 é o caso base dessa mesma função. par(n)=par(n) é uma tautologia, e não uma recursão. As demais respostas são funções que não chamam a si mesmas, não podendo ser passos recursivos. 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? Lista em alocação contígua. Lista simplesmente encadeada. Pilha. Lista duplamente encadeada. Fila. Respondido em 27/11/2023 22:04:40 Questão / 1 a Questão / 2 a https://simulado.estacio.br/alunos/inicio.asp https://simulado.estacio.br/alunos/inicio.asp javascript:voltar(); javascript:voltar(); 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. Acerto: 0,2 / 0,2 Seja a seguinte árvore, marque a opção correta que indica o porquê a árvore abaixo não é uma árvore binária de busca: Não é árvore binária de busca pois essa árvore deve estar perfeitamente balanceada. Não é árvore binária de busca pois está desbalanceada. 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 esta árvore deve estar com os níveis de suas folhas todas igualmente perfeitas. Não é árvore binária de busca pois o nó 35 deveria estar inserido à direita do nó 20. Respondido em 27/11/2023 22:09:21 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. 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 simples à esquerda de um nó x acontece quando um desbalanceamento de x acontece à esquerda. 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 à direita de um nó x acontece quando um desbalanceamento de x acontece à direita. Questão / 3 a Questão / 4 a Uma rotação dupla à direita de um nó x acontece quando um desbalanceamento de x acontece à direita. Respondido em 27/11/2023 22:10:40 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 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 224 26 e 74 28 e 224 28 e 220 32 e 220 Respondido em 27/11/2023 22:13:21 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,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 de um jogador para armazenar um conjunto �xo de elementos. Em jogos multijogador para garantir que apenas um dos jogadores jogue todas as vezes. Respondido em 27/11/2023 22:14:26 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 Questão / 5 a Questão / 6 a Questão / 7 a Seja a seguinte Árvore Binária. Marque a opção correta: É possível inserir mais um �lho a esquerda no nó de valor 90. Não é possível inserir nós �lhos ao nó 70. A árvore acima possui raiz de valor 3. A quantidade de folhas da árvore é 4. A quantidade de nós da árvore é de n ¿ 1, sem considerar o nó raiz. Respondido em 27/11/2023 22:09:33 Explicação: A quantidade de folhas da árvore é 4, ou seja, são aqueles nós que possuem grau zero. Acerto: 0,2 / 0,2 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: 0(n3). 0(n2). 0(log n). 0(n). 0(n log n). Respondido em 27/11/2023 22:15:17 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). 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 um grande conjunto de entradas variadas de tamanho grande, BS executará em menos tempo que MS, em média. MS e BS são igualmente e�cientes em ordenar elementos, independente da entrada ou seu tamanho. Questão / 8 a Questão / 9 a Para um grande conjunto de entradas variadas de tamanho grande, MS executará em menos tempo que BS, em média. Para uma única entrada de tamanho grande, MS executará em menos tempo que BS. Para uma única entrada de tamanho grande, BS executará em menos tempoque MS. Respondido em 27/11/2023 22:16:36 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 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 ou remoção em qualquer de suas posições. Permitem inserção ou remoção apenas no seu início ou no seu �nal. 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 no seu �nal e remoção apenas no seu início. Respondido em 27/11/2023 22:17:16 Explicação: 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. Questão / 10 a
Compartilhar