Apol objetiva 2 - Estrutura de dados

Prévia do material em texto

Questão 1/10 - Estrutura de Dados 
Existem duas ordens comuns nas quais os vértices podem ser visitados durante o percurso em um grafo. O primeiro, chamado de percurso em profundidade, 
o segundo tipo de percurso, chamado de percurso em largura. 
O percurso em largura em grafos utiliza qual estrutura de dados? 
Nota: 10.0 
 
A Pilha 
 
B Fila 
Você assinalou essa alternativa (B) 
Você acertou! 
Aula 6 – tema 4 
 
C Hash 
 
D Dicionário 
 
E Árvore 
 
Questão 2/10 - Estrutura de Dados 
As estruturas de dados conhecidas como árvores de busca binária, são estruturas em árvore binária que possuem no nó esquerdo uma informação menor ou 
igual à informação da chave. Já no nó direito a informação deve ser maior ou igual à informação da chave. 
VETORAZZO, Adriana de S.; SARAIVA, Mauício de O.; BARRETO, Jeanine dos S.; JR., Ramiro S C. Estrutura de dados. Editora Grupo A, 2018.pag 139 
 
 
Fonte: Pereira, Silvio do Lago. Estruturas de dados em C : uma abordagem didática / Silvio do Lago Pereira. - São Paulo : Érica, 2016.Pag 136 
Leia o texto base, observe a figura acima e considere as seguintes afirmativas: 
I. A figura é uma arvore binária de busca, pois a esquerda da raiz que tem valor 5, os número são menores que 5 e à direita são maiores que 5. 
II.A projeção da figura da arvore binária produz um sequencia ordenada crescente da esquerda para a direita. 
III. A figura é uma arvore binária, mas não é uma arvore binaria de busca. Para ser uma arvore binária de busca o valor 8 deveria ser raiz do valor 9. 
 
Estão corretas as afirmativas: 
Nota: 10.0 
 
A I apenas 
 
B II apenas 
 
C I e II apenas 
Você assinalou essa alternativa (C) 
Você acertou! 
Aula 4.Tema 2 
 
D I e III apenas 
 
E II e III apenas 
 
Questão 3/10 - Estrutura de Dados 
"A utilização da funcão de hashing possibilita a indexação dos dados, transformando uma chave k em um endereço físico, relativo ou absoluto h(k), provendo 
maior rapidez e segurança na busca por informações dentro de um arquivo. Há pórém o problema das colisões." 
Lima, Diana M., D. e Luis E. F. Gonzalez. Matemática aplicada à informática (Tekne). Disponível em: Minha Biblioteca, Grupo A, 2015.pag 57 – modificado 
Quanto a função hashing e colisões, assinale a alternativa correta: 
Nota: 10.0 
 
A Uma função hash pode ser livre de colisões, para isso basta utilizar o hash universal. 
 
B No endereçamento aberto, cada posição da estrutura de dados pode conter múltiplas palavra-chave. 
 
C Na tentativa linear, sempre que uma colisão ocorre, tenta-se posicionar a nova chave no próximo espaço imediatamente livre do array. 
Você assinalou essa alternativa (C) 
Você acertou! 
Aula 5 - Tema 4 
 
D No endereçamento em cadeia as colisões podem ser tratadas de 2 maneiras: TENTATIVA LINEAR ou TENTATIVA QUADRÁTICA. 
 
E Na tentativa quadrática, sempre que uma colisão ocorre, tenta-se posicionar a nova chave no próximo espaço imediatamente livre do array. 
 
Questão 4/10 - Estrutura de Dados 
Existem duas ordens comuns nas quais os vértices podem ser visitados durante o percurso em um grafo. O primeiro, chamado de percurso em profundidade, 
o segundo tipo de percurso, chamado de percurso em largura. 
O percurso em profundidade em grafos utiliza qual estrutura de dados? 
Nota: 10.0 
 
A Pilha 
Você assinalou essa alternativa (A) 
Você acertou! 
Aula 6 – tema 4 
 
B Fila 
 
C Hash 
 
D Dicionário 
 
E Árvore 
 
Questão 5/10 - Estrutura de Dados 
“Visto de forma abstrata, um grafo G e´ simplesmente um conjunto V de ve´rtices e uma colec¸a~o E de pares de ve´rtices de V, chamados de arestas. 
Assim, um grafo e´ uma forma de representar conexo~es ou relac¸o~es entre pares de objetos de algum conjunto V.” 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java.Grupo A, 2013. pag 613 
Abaixo temos uma imagem de um grafo. 
 
 
Acerca do grafo acima, considerando o texto base e o conteúdo visto em aula, assinale a alternativa CORRETA. 
Nota: 10.0 
 
A O grafo contém arestas múltiplas, pois temos mais de um caminho para sair de V1 e chegar em V9, por exemplo 
 
B O grau do vértice V9 é 3. 
 
C Todos os vértices deste grafo têm o mesmo grau. 
 
D Este grafo é do tipo completo. 
 
E O grau do vértice V4 é 3. 
Você assinalou essa alternativa (E) 
Você acertou! 
Aula 6 – Tema 1 
 
Questão 6/10 - Estrutura de Dados 
“Dois matemáticos russos, G. M. Adel’son-Vel’skiî e E. M. Landis, publicaram em 1962 um artigo que descreve um algoritmo para manter o equilíbrio 
global de uma árvore de busca binária. Seu algoritmo controla a diferença de altura das subárvores. À medida que itens são adicionados à árvore (ou 
removidos dela), o fator de balanceamento** (isto é, a diferença entre as alturas das subárvores) de cada subárvore do ponto de inserção até a raiz é 
mantido. Se a um dado momento, o fator de balanceamento sair do intervalo -1 ... +1, a subárvore sofre uma rotação para retornar ao equilíbrio. As 
árvores que utilizam essa abordagem são conhecidas como árvores AVL, em homenagem aos seus inventores. Como antes, definimos a altura de 
uma árvore como o número de nós no maior caminho da raiz a um nó folha, inclusive a raiz.” 
 
 KOFFMAN, Elliot B.; WOLFGANG, Paul A T. Objetos, Abstração, Estrutura de Dados e Projeto Usando C++. Grupo GEN, 2008. E-book. ISBN 978-85-216-
2780-7. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2780-7/. Acesso em: 07 dez. 2022. Capítulo 11. 
Observe um exemplo de árvore AVL abaixo: 
 
 
Considere que o fator de balanceamento é calculado considerando a árvore da direita – esquerda. Suponha que você quer remover o nó folha de valor 99. 
Acerca do balanceamento e rotação desta árvore sem o 99. 
Assinale a alternativa CORRETA: 
Nota: 10.0 
 
A A árvore ficará balanceada e não precisará de rotação nenhuma. 
 
B A árvore ficará com um desbalanceamento de valor 2 na raiz. 
 
C O nó filho de valor 80 está com balanceamento 0, resultando em uma rotação simples para a direta. 
Você assinalou essa alternativa (C) 
Você acertou! 
Raiz -> Desbalanceada = -2. 
Filho da esquerda -> Balanceado = 0 
Rotação simples para a direita 
 
Aula 4 – tema 4 
 
D A árvore está com um desbalanceamento de valor -2 na raiz, resultando em uma rotação simples para a esquerda. 
 
E O nó filho de valor 80 está com balanceamento 1, resultando em uma dupla com filho para a esquerda e pai para a direita. 
 
Questão 7/10 - Estrutura de Dados 
"Dois matemáticos russos, G. M. Adel’son-Vel’skiî e E. M. Landis, publicaram em 1962 um artigo que descreve um algoritmo para manter o equilíbrio global 
de uma árvore de busca binária. Seu algoritmo controla a diferença de altura das subárvores. À medida que itens são adicionados à árvore (ou removidos 
dela), o fator de balanceamento** (isto é, a diferença entre as alturas das subárvores) de cada subárvore do ponto de inserção até a raiz é mantido." 
Koffman, Elliot, B. e Paul A. T. Wolfgang. Objetos, Abstração, Estrutura de Dados e Projeto Usando C++. Disponível em: Minha Biblioteca, Grupo GEN, 2008. 
O nome da estrutura de dados descrita no texto é conhecido como árvore: 
Nota: 10.0 
 
A Heap. 
 
B de busca binária. 
 
C Ordenada. 
 
D binária. 
 
E AVL. 
Você assinalou essa alternativa (E) 
Você acertou! 
Aula 4 – tema 4 
 
Questão 8/10 - Estrutura de Dados 
"Muito esforço tem sido feito em busca de funções de hashing eficientes, isto é, que sejam computadas rapidamente e que efetuem uma distribuição 
uniforme de chaves. Felizmente, a função de hashing mais eficiente encontrada, chamada método da divisão, é também a mais fácil de ser implementada. 
O método da divisão, divide a chave c pelo tamanho do vetor m e usa o resto da divisão como índice. Isso funciona bem para qualquer m; mas, se m é um 
número primo, o espalhamento tende a ser mais uniforme." 
Pereira, Silvio do Lago. Estruturas de dados em C : uma abordagem didática / Silvio do Lago Pereira. São Paulo : Érica, 2016. Pag 125Considerando o texto base e que você tem disponível, para utilizar como palavras-chave, valores numéricos inteiros de 4 dígitos. Você decide que irá 
agrupar os dígitos em pares e somá-los para usar como chave. Por exemplo, o número 1234, será: 12 + 34 = 46. 
 
Considere ainda que você tem um vetor de dimensão 100 (posições 0 até 99) disponível para armazenamento e que irá adotar o método da divisão. 
Assinale a alternativa INCORRETA: 
Nota: 10.0 
 
A A palavra-chave 0125 será inserida na posição 26. Porém, se alterarmos o tamanho do vetor para 110, a nova posição desta chave será 36. 
Você assinalou essa alternativa (A) 
Você acertou! 
aula 5. Tema 2 
Neste caso, a chave continuará na posição 26 para o vetor 100 e para o 110. 
 
B A palavra-chave 4455, será inserida na última posição disponível do vetor. 
44+55 = 99 MOD 100 = 99. 99 é a ultima posição possível deste vetor 
 
C A palavra-chave 9128, será inserida na posição 19 do vetor. 
91+28 = 119 MOD 100 = 19. 
 
D O maior valor possível representado com 4 dígitos será colocado na posição 98. 
O maior valor com 4 dígitos é 9999 = 99+99 = 198 MOD 100 = 98 
 
E A palavra-chave 1873, será inserida na posição 91 do vetor. 
18+73 = 91 MOD 100 = 91 
 
Questão 9/10 - Estrutura de Dados 
Em uma árvore binária, cada nó tem no máximo dois filhos, chamados de filho esquerdo e filho direito. Em uma árvore binária, quando um nó tem apenas um 
filho, você o distingue como filho à esquerda ou à direita. 
LAMBERT, Kenneth A. Fundamentos de Python: estruturas de dados.pag 280 
 
Observe as árvores abaixo: 
 
 
 
Considerando o texto base e o conteúdo visto em aula, assinale a alternativa correta: 
Nota: 0.0Você não pontuou essa questão 
 
A São arvores binárias a Árvore 1 e a Árvore 2. 
 
B São arvores binárias a Árvore 1 e a Árvore 3. 
 
C São arvores binárias a Árvore 2 e a Árvore 3. 
Aula 4 . Tema 1 
 
D São arvores binárias a Àrvore 1, Árvore 2 e a Árvore 3. 
Você assinalou essa alternativa (D) 
 
E Apenas a árvore 2 é uma árvore binária. 
 
Questão 10/10 - Estrutura de Dados 
As Árvores binárias têm várias propriedades interessantes quanto as relações entre sua altura e seu número de nós. Denota-se o conjunto de nodos de 
mesma profundidade d de uma árvore T como sendo o nível d de T. Em uma árvore binária, o nível 0 tem no máximo um nó (a raiz), o nível 1 tem no máximo 
2 (os filhos da raiz), o nível 2 tem no máximo 4, e assim por diante . Generalizando, pode-se dizer que o nível d tem no máximo 2d (2 elevado a d) nós. 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java. Grupo A, 2013. E-book. ISBN 9788582600191. D. Pag 320 
(modificado) 
Considere as seguintes afirmativas: 
 
I. Uma árvore binária com profundidade 4 tem no máximo 16 nós no nível 4. 
II. O número máximo de nós nos níveis de uma árvore binária cresce de forma exponencial à medida que se desce na árvore. 
III. Uma árvore binária com altura 1 consiste apenas do nó raiz. 
 
Considerando o texto base e o conteúdo estudado em aula, estão corretas as afirmativas: 
Nota: 0.0Você não pontuou essa questão 
 
A I e II apenas 
Aula 4. Tema 1 
 
B I e III apenas 
 
C II e III apenas 
 
D I, II e III 
Você assinalou essa alternativa (D) 
 
E Todas estão erradas.