estrutura de dados 02

Prévia do material em texto

15/09/25, 18:00 Avaliação Individual A+ Alterar modo de visualização Peso da Avaliação 2,00 Prova 84011340 Qtd. de Questões 10 Acertos/Erros 8/1 Canceladas 1 Nota 9,00 1 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 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. H. 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: vetor é dividido em várias partes iguais menores, em que é feita a ordenação em cada uma A delas. Depois o vetor é reunido já com valores ordenados, tomando por base a função partition() e o elemento pivô. 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 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. Os elementos são comparados e trocados conforme o caso, de maneira iterativa, em dois laços de D repetição, fazendo os valores maiores "flutuarem" para o final do arranjo, realizando a ordenação de trás para frente. O elemento atual é removido, de maneira recursiva, em dois laços de repetição, e sua posição E ideal é procurada no vetor e, uma vez encontrada, o elemento é reinserido em sua posição quase ordenada. 2 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: about:blank 1/715/09/25, 18:00 Avaliação Individual A 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: 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 é estritamente binária. D vértice I estaria armazenado na posição 11 do vetor. E A árvore é uma binária completa. 3 O 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 divide o vetor em vetores menores e em cada um deles aplica o método InsertionSort. Ele aplica uma busca sequencial completa. Ele mescla os métodos MergeSort e QuickSort. D Ele aplica uma busca binária utilizando o método BubbleSort. E Ele aplica o método SelectionSort utilizando recursividade. about:blank 2/715/09/25, 18:00 Avaliação Individual 4 Uma das principais características que diferencia a árvore das demais estruturas de dados é a maneira com que seus elementos se relacionam entre si. Tais relações se estabelecem, dentre outras formas, no momento da inserção de um novo elemento. Sobre a inserção de dados em árvores, analise as afirmativas a seguir: I. A operação de inserção em uma árvore de busca binária depende apenas do valor a ser inserido como entrada. II. A estrutura de registro não é possível utilizar com referência para se implementar uma árvore em um vetor estático. III. A estrutura do tipo nó é necessária para a implementação de árvores dinâmicas. Tais estruturas são registros contendo ponteiros de referência para o nó pai e os nós filhos. IV. No armazenamento de uma árvore em um vetor do tipo inteiro, a inserção dos filhos é controlada por uma fórmula matemática. Por isso, pode-se dispensar a estrutura de registro com referências para outros nós. É correto o que se afirma em: A I, III e IV, apenas. II, III e IV, apenas. I, apenas. D II e III, apenas. E III e IV, apenas. Revisar Conteúdo do Livro Atenção: Esta questão foi cancelada, porém a pontuação foi considerada. 5 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. H. et al. Introduction to Algorithms. 3. ed. Cambridge: MIT Press, 2009. Sobre os algoritmos de ordenação, analise as afirmativas a seguir: I. O 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. I, II, III e IV. C II e IV, apenas. D I, apenas. about:blank 3/715/09/25, 18:00 Avaliação Individual E I, II e III, apenas. 6 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. O 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 IV, apenas. I e IV, apenas. I, II e III, apenas. D II, III e IV, apenas. E II e III, apenas. 7 De maneira geral, utilizar árvores no desenvolvimento é bom, pois elas provêm acesso de dados direto e sequencial rápidos, têm fácil inserção e remoção de dados e ainda possuem boa taxa de utilização de memória. Para poder manipular árvores convenientemente, o desenvolvedor necessita ter conhecimento de vários conceitos. A respeito de árvores, analise as afirmativas a seguir: I. Considere que a raiz é o vértice inicial e não possui um nó-pai. II. Considere que o nó V tem uma subárvore cuja raiz dessa subárvore é o nó W. Diz-se que V é pai de W. III. Considere que o nó V tem uma subárvore cuja raiz dessa subárvore é o nó W. Diz-se que W é pai de V. IV. Considere que o nó V tem uma subárvore cuja raiz dessa subárvore é o nó W. Diz-se que W é filho de V. É correto o que se afirma em: A I, II e IV, apenas. B I, apenas. II, III e IV, apenas. D II e III, apenas. about:blank 4/715/09/25, 18:00 Avaliação Individual E III e IV, apenas. 8 A técnica de ordenação SelectionSort, assim como a BubbleSort, é de simples implementação e de alto consumo computacional. Assinale a alternativa correta que apresenta a principal diferença entre o SelectionSort e o BubbleSort: BubbleSort realiza a troca em cada par de valores invertidos; o SelectionSort faz a troca quando encontra o menor valor para a posição em processamento. B BubbleSort é majoritariamente utilizado para ordenar vetores; o SelectionSort para ordenar matrizes. BubbleSort, para concluir a ordenação, realiza apenas uma troca; o SelectionSort realiza pares de trocas para cada posição do vetor. D BubbleSort inicia a varredura do início do vetor, ao passo que o SelectionSort inicia do final do vetor. E BubbleSort necessita de memória extra para fazer o processamento; enquanto o SelectionSort utiliza metade da memória proporcionalmente. 9 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. about:blank 5/715/09/25, 18:00 Avaliação Individual (1) (2) H A F E G A D D E E F G H J (3) (4) A A D E D E F G F G Analisando os grafos apresentados, assinale a alternativa correta: A A árvore não é necessariamente um grafo. O grafo da figura (2) não pode ser considerado uma árvore. Os grafos (3) e (4) são árvores binárias completas. D grafo (1) é uma árvore binária. E No quadro (4) tem-se ao mesmo tempo uma árvore estritamente binária e uma árvore completa. 10 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. about:blank 6/715/09/25, 18:00 Avaliação Individual Fonte: adaptado de: CORMEN, T. H. 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: O vetor é dividido em várias partes iguais menores, em que é feita a ordenação em cada uma A delas. Depois o vetor é reunido já com valores ordenados, tomando por base a função partition() e o elemento pivô. 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 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. Os elementos são comparados e trocados conforme o caso, de maneira iterativa, em dois laços de D repetição, fazendo os valores maiores "flutuarem" para o final do arranjo, realizando a ordenação de trás para frente. elemento atual é removido, de maneira recursiva, em dois laços de repetição, e sua posição E ideal é procurada no vetor e, uma vez encontrada, o elemento é reinserido em sua posição quase ordenada. Imprimir about:blank 7/7