Baixe o app para aproveitar ainda mais
Prévia do material em texto
03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 1/8 Meus Simulados Teste seu conhecimento acumulado Disc.: ESTRUTURA DE DADOS Aluno(a): JONAS BATISTA DE OLIVEIRA FRANCO 202208555268 Acertos: 2,0 de 2,0 24/10/2023 Acerto: 0,2 / 0,2 Ao usar a biblioteca numpy para criar arrays, existem diversas facilidades que um programador pode utilizar, como funções especí�cas para somar todos os elementos, encontrar valores mínimo e máximo dos elementos, entre outros. Entretanto uma desvantagem de usar array da biblioteca numpy é: Não é possível adicionar novos elementos ao array. Todos os elementos devem ter o mesmo tamanho. Os índices passam a ser contados a partir de 1. Diminuição no tempo de programação. Não é possível remover elementos do array. Respondido em 24/10/2023 14:04:23 Explicação: A desvantagem é que os elementos do array devem ocupar o mesmo espaço de memória, então devem ser de mesmo tamanho. Isso não permite que você crie arrays com elementos de tamanho assimétricos. Os índices continuam sendo contados a partir de 0 e as operações de inserção e remoção continuam sendo possíveis. A diminuição no tempo de programação é uma vantagem. Questão1 a https://simulado.estacio.br/alunos/inicio.asp javascript:voltar(); 03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 2/8 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 em alocação contígua. Pilha. Fila. Lista simplesmente encadeada. Lista duplamente encadeada. Respondido em 24/10/2023 13:59:00 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 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(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) Respondido em 24/10/2023 13:59:46 Questão2 a Questão3 a 03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 3/8 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 a�rmativas abaixo são feitas com base na estrutura de dados "Árvore Binária de Busca". Em relação ao algoritmo de busca em uma árvore binária de busca, analise as a�rmativas abaixo: I -A complexidade da busca é de�nida pela altura da árvore binária de busca. No pior caso O(n). II - A busca é de�nida de forma recursiva, parte da raiz, comparando a chave buscada com a armazenada na raiz, caso seja igual temos o sucesso da busca, caso contrário, se a chave buscada for menor, devemos proceder recursivamente no ramo esquerdo, se a chave buscada for maior, proceder recursivamente no ramo direito. III - Sempre é necessário percorrer toda a árvore no algoritmo de busca. Em todos os casos, mesmo em árvores completas. IV - A condição de parada da busca é encontrar a chave buscada ou ter que descer por um ramo vazio. V - É possível escrever o algoritmo da busca de forma não recursiva. I, II, IV e V são corretas. I, III, IV e V são corretas. I, II, III e IV são corretas. II, III, IV e V são corretas. I, II, III, IV e V são corretas. Respondido em 24/10/2023 14:10:58 Explicação: A a�rmativa III é incorreta, não é necessário percorrer todos os nós da árvore se ela estiver perfeitamente balanceada. Acerto: 0,2 / 0,2 Questão4 a Questão5 a 03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 4/8 Dada a seguinte matriz M, inicializada com o código: M=[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]] O código em Python para imprimir cada elemento da coluna iniciada pelo elemento 3 é: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 print(M[2]) for linha in M: print(linha[2]) for linha in M: print(linha) for coluna in M: print(coluna) for linha in M: print(linha[3]) Respondido em 24/10/2023 14:00:28 Explicação: O laço deve percorrer uma coluna, iterando linha a linha e extraindo dela o seu terceiro elemento, ou seja linha[2]. A resposta correta itera pelas linhas e imprime o elemento [2] de cada uma. Dentre as respostas erradas, apenas escrever ¿print(linha)¿ imprimirá cada linha como um todo, resultando na impressão de toda a matriz, linha a linha. A resposta "print(coluna)" terá o mesmo resultado pois para o código linha e coluna são apenas nomes escolhidos pelo programador. Poderia ser i, aux ou qualquer outra variável escolhida. Já "print(linha[3])" está com o índice errado, imprimindo os elementos da coluna iniciada por 4. E ¿print(M[2])¿ imprime toda a linha iniciada por 9. Acerto: 0,2 / 0,2 Questão 6 a 03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 5/8 Uma Lista pode ser implementada de forma contígua ou encadeada. No caso de uma lista ordenada implementada de forma encadeada, as complexidades de pior caso de busca, inserção e remoção são respectivamente: O(n), O(1) e O(n). O(n), O(n) e O(n). O(log n), O(n) e O(n). O(1), O(n) e O(n). O(n), O(n) e O(1). Respondido em 24/10/2023 14:10:19 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 �nal da lista, uma operação simples, mas a busca para achar a posição correta já é O(n). A remoção de qualquer nó também é uma operação de custo constante, bastando reapontar um ponteiro, mas a busca pelo nó a ser removido também é O(n), o que faz a operação de remoção também possuir complexidade O(n). Acerto: 0,2 / 0,2 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. 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. 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. Em todas as estruturas de dados onde se realizabusca, 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 24/10/2023 14:06:20 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 Questão7 a 03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 6/8 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á desbalancear à direita do nó de chave 40. A árvore resultante irá manter o balanceamento geral da árvore. A árvore resultante irá desbalancear à esquerda do nó de chave 10. A árvore resultante irá desbalancear à direita do nó de chave 80. A árvore resultante irá desbalancear à esquerda do nó de chave 60. Respondido em 24/10/2023 14:07:53 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 03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 7/8 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 uma única entrada de tamanho grande, MS executará em menos tempo que BS. Para um grande conjunto de entradas variadas de tamanho grande, BS executará em menos tempo que MS, em média. Para um grande conjunto de entradas variadas de tamanho grande, MS executará em menos tempo que BS, em média. MS e BS são igualmente e�cientes em ordenar elementos, independente da entrada ou seu tamanho. Para uma única entrada de tamanho grande, BS executará em menos tempo que MS. Respondido em 24/10/2023 14:01:42 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. Questão9 a 03/11/2023, 14:10 Estácio: Alunos https://simulado.estacio.br/bdq_simulados_avaliacao_parcial_resultado.asp?cod_hist_prova=319984306&cod_prova=6757747258&f_cod_disc= 8/8 Acerto: 0,2 / 0,2 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? Não ordenada: 36, 37; ordenada: 32, 33. Não ordenada: 32, 34; ordenada: 32, 34. Não ordenada: 36, 37; ordenada: 32, 37. Não ordenada: 40, 42; ordenada: 32, 42. Não ordenada: 40, 42; ordenada: 40, 42. Respondido em 24/10/2023 14:03:49 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. Questão10 a
Compartilhar