Estruturas de Dados av2

Prévia do material em texto

19/05/2026, 19:28 Avaliação Individual A+ Alterar modo de visualização Peso da Avaliação 1,50 Prova 121628767 Qtd. de Questões 10 Acertos/Erros 10/0 Nota 10,00 1 Existem diversas técnicas tradicionais para se realizar a ordenação de um arranjo. Ao desenvolvedor, caberia apenas a escolha de uma dessas técnicas para compor seu programa, caso necessário. Sobre a ordenação de vetores, analise as afirmativas a seguir: I.O algoritmo BubbleSort possui fácil implementação, e consequentemente baixo custo computacional. II. MergeSort é uma otimizaçao do ShellSort, na qual uma partição é dividida por meio do seu elemento pivô. III. algoritmo SelectionSort, assim como o InsertionSort, é de fácil implementação, é um dos algoritmos de ordenação mais veloz. IV. algoritmo ShellSort de ordenação é o mais eficiente e é considerado uma técnica refinada do método de ordenação por inserção. É correto o que se afirma em: A II, III e IV, apenas. IV, apenas. I e IV, apenas. D I, II e III, apenas. E II e III, apenas. 2 A ordenação de dados é muito utilizada no desenvolvimento de sistemas, pois permite organizar informações para facilitar o processo de busca e análise. Diversos métodos são utilizados para essa tarefa, e um deles é o método da bolha (Bubblesort). Esse método, embora não seja o mais eficiente, destaca-se por sua simplicidade. Considerando o método "Bubblesort" para ordenação de um vetor, assinale a alternativa correta sobre o seu funcionamento: about:blank 1/819/05/2026, 19:28 Avaliação Individual A A ordenação no método da bolha é realizada percorrendo o vetor uma única vez e trocando os elementos imediatamente se estiverem fora de ordem. B método da bolha compara os elementos do vetor apenas uma vez, garantindo uma ordenação eficiente. método da bolha utiliza um índice de controle que percorre o vetor de forma decrescente, trocando os elementos adjacentes quando necessário. D método da bolha é mais eficiente quando o vetor já está parcialmente ordenado, sendo menos adequado para vetores desordenados. E número de repetições no método da bolha é igual ao número de elementos do vetor menos 1, e em cada repetição compara-se os elementos vizinhos, efetuando trocas quando necessário. 3 método de ordenação por QuickSort, também conhecido por classificação por troca de partição, foi publicado em 1962 e é considerado o algoritmo de ordenação mais utilizado no mundo. Fonte: adaptado de: CORMEN, T. H. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009. Sobre o processamento do método QuickSort, analise as afirmativas a seguir: I. método pode escolher um elemento qualquer do vetor que será o pivô. II. pivô, durante o processo de partição, já estará na sua posição final do vetor. III. As sublistas são percorridas de forma recursiva até que haja apenas um elemento nas sublistas criadas recursivamente. IV. A partir do método Merge(), a lista é dividida em sublistas, uma para valores menores, outra para valores maiores, o pivô e a terceira que é o próprio pivô. É correto o que se afirma em: A I, II e III, apenas. B I, apenas. II e III, apenas. D III e IV, apenas. about:blank 2/819/05/2026, 19:28 Avaliação Individual E I, II, III e IV. 4 A escolha de grafos é comum em problemas como o de roteamento de pacotes em rede ou determinação de caminhos mínimos em um mapa geográfico. Já as árvores são mais apropriadas para estruturas de armazenamento em memória e pesquisa de dados. (1) (2) H A F E C G A D D E E C F G H J (3) (4) A A C D E D E F G F G Analisando os grafos apresentados, assinale a alternativa correta: A A árvore (1) não é necessariamente um grafo. B grafo da figura (2) não pode ser considerado uma árvore. about:blank 3/819/05/2026, 19:28 Avaliação Individual No quadro (4), tem-se, ao mesmo tempo, uma árvore estritamente binária e uma árvore completa. D grafo (2) é uma árvore estritamente binária. E Os grafos (3) e (4) são árvores binárias completas. 5 Pode-se classificar os algoritmos de ordenação, quanto à sua complexidade de informação. Além disso, outros parâmetros são úteis para avaliar tais técnicas, por exemplo, o espaço de memória que utiliza ou sua velocidade de execução. Fonte: adaptado de: CORMEN, T. H. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009. Sobre as técnicas de ordenação, analise as afirmativas a seguir: I. InsertionSort tem alto desempenho, quando o vetor está ordenado ou parcialmente ordenado. II. ShellSort, apesar de se basear no InsertionSort para realizar ordenação, de maneira geral, apresenta bom desempenho. III. algoritmo QuickSort se apropria da técnica "dividir para conquistar", tornando-o um dos algoritmos de ordenação mais rápidos. IV. InsertionSort, em ocasiões em que o vetor está ordenado, ou parcialmente ordenado, é capaz de superar o QuickSort em velocidade de ordenação. É correto o que se afirma em: A III, apenas. B I, II e III, apenas. I, II, III e IV. D I e II, apenas. E II, III e IV, apenas. 6 Cada algoritmo de ordenação possui suas particularidades. Dependendo da maneira que se encontram distribuídos os dados no arranjo, pode ser que haja diferença no tempo de execução dos algoritmos. Fonte: adaptado de: CORMEN, T. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009. about:blank 4/819/05/2026, 19:28 Avaliação - Individual Sobre os algoritmos de ordenação, analise as afirmativas a seguir: I. InsertionSort não é um algoritmo inerentemente recursivo. II. InsertionSort também é conhecido como método de ordenação por inserção. III. InsertionSort, assim como o BubbleSort, também utiliza a função "troca" para realizar a ordenação dos elementos. IV. Pelo fato de possuir dois laços de repetição aninhados, o InsertionSort não é capaz de ser mais veloz que os algoritmos SelectionSort e BubbleSort. É correto o que se afirma em: A II e III, apenas. B I, II, III e IV. I, II e III, apenas. D II e IV, apenas. E I, apenas. 7 Uma maneira simples e rápida de implementar uma árvore binária é empregando o uso de um vetor estático. A seguir podemos visualizar um exemplo de árvore binária: A B C D E F G H J Considere que, nem sempre que um nó for a raiz de uma árvore, ele ocupará a primeira posição do vetor, considere que a posição inicial (índice inicial) do vetor é igual a 1. Considere, ainda, que ao se inserir os filhos de um nó que ocupa a posição P, o filho esquerdo deverá ser inserido na posição 2*P, e o filho direito na posição Com base na árvore ilustrada e considerando uma implementação estática baseada nas fórmulas apresentadas, assinale a alternativa correta: about:blank 5/819/05/2026, 19:28 Avaliação Individual A Os vértices que são filhos direitos sempre estarão em posições pares. B Caso a árvore fosse binária completa com altura 2, seriam necessárias no mínimo 15 posições no vetor para armazenar todos os seus vértices. A árvore é uma binária completa. D A árvore é estritamente binária. E vértice I estaria armazenado na posição 11 do vetor. 8 A técnica de ordenação Mergesort consiste em dividir um problema complexo em problemas menores e assim por diante, até que se encontre uma solução pequena e simples suficiente para que o problema seja resolvido como um todo. Esse conceito é bem conhecido na ciência da computação, e seu nome é "dividir para conquistar". Para além de aplicações tecnológicas, esse conceito é utilizado também em estratégias comerciais ou mesmo sociopolíticas. Fonte: adaptado de: CORMEN, T. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009. Assinale a alternativa correta que apresenta a forma como é feita a ordenação pelo algoritmo Mergesort: elemento atual é removido, de maneira recursiva, em dois laços de repetição, e sua posição A ideal é procurada no vetor e, uma vez encontrada, o elemento é reinserido em sua posição quase ordenada. B vetor original é percorrido em um único laço de repetição, de maneira iterativa, e os elementos são adicionados em um segundo vetor único, fazendo a comparação para verificar a ordenação. vetor é dividido em duas partes, essas partes são divididas novamente, e assim por diante, até que cada parte tenha apenas um elemento. Depois é feita a junção, ordenando essas partes e recompondo o vetor com os dados originais ordenados. vetor é dividido em várias partes iguais menores, em que é feita a ordenação em cada uma D delas. Depois o vetor é reunido já com valores ordenados, tomando por base a função partition() e o elemento pivô. about:blank 6/819/05/2026, 19:28 Avaliação Individual Os elementos são comparados e trocados conforme o caso, de maneira iterativa, em dois laços de E repetição, fazendo os valores maiores "flutuarem" para o final do arranjo, realizando a ordenação de trás para frente. 9 Os algoritmos de ordenação utilizam métodos capazes de ordenar, de maneira exata, um conjunto de dados armazenados em um vetor. Fonte: adaptado de: CORMEN, T. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009. Sobre os algoritmos BubbleSort e SelectionSort, analise as afirmativas a seguir: I. A técnica de ordenação BubbleSort também é conhecida por ordenação por flutuação ou método da bolha. II. SelectionSort, apesar de ser uma técnica de simples implementação, possui alto consumo computacional. III. As técnicas de SelectionSort e BubbleSort estão entre os piores desempenhos entre os algoritmos de ordenação existentes. IV. método SelectionSort seleciona e ordena um elemento arbitrário do arranjo e, então, chama a si mesmo, recursivamente, para ordenar uma porção menor do arranjo. É correto o que se afirma em: A I e IV, apenas. IV, apenas II e III, apenas. D I, II e III, apenas. E II, III e IV, apenas. 10 algoritmo ShellSort de ordenação tem esse nome em homenagem ao seu criador, Donald Shell, publicado pela Universidade de Cincinnat em 1959. Segundo Wirth (1989), ele é o mais eficiente dentro dos algoritmos classificados como complexidade quadrática. Fonte: adaptado de: WIRTH, N. Algoritmos e estrutura de dados. Rio de Janeiro: Prentice-Hall do Brasil, 1989. Assinale a alternativa correta que apresenta a principal característica do algoritmo ShellSort: A Ele aplica o método SelectionSort utilizando recursividade. B Ele aplica uma busca binária utilizando o método BubbleSort. about:blank 7/819/05/2026, 19:28 Avaliação - Individual Ele divide o vetor em vetores menores e em cada um deles aplica o método InsertionSort. D Ele aplica uma busca sequencial completa. E Ele mescla os métodos MergeSort e QuickSort. Imprimir about:blank 8/8