Apol objetiva 2 Estrutura de dados

Prévia do material em texto

Questão 1/10 - Estrutura de Dados 
Uma razão para estudarmos grafos é encontrar um caminho entre vértices. Quanto a vértices e caminhos, assinale a sentença correta. 
Nota: 10.0 
 
A Em um caminho simples, os vértices e arestas são distintos, exceto que o primeiro e o último vértices podem ser o mesmo. 
Você assinalou essa alternativa (A) 
Você acertou! 
Aula 6 tema 1 
 
B Um ciclo é um caminho simples em que apenas o primeiro e o último vértices estão conectados. 
 
C Um caminho é uma seqüência de arestas em que cada aresta adjacente é paralela ao seu predecessor. 
 
D Um nó vizinho de um vértice não pode estar conectado a outro vértice distinto. 
 
E Em um grafo não orientado, um ciclo deve conter no mínimo quatro vértices. 
 
Questão 2/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 125 
Considerando 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 3/10 - Estrutura de Dados 
Considere a seguinte árvore binária. 
 
 
 
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.(Adaptado) 
Qual é a ordem de visita seguindo a consulta em ordem? 
Nota: 10.0 
 
A jumps, brown,quick,the,fox,over 
 
B the, fox, brown, jumps, quick ,over 
 
C the, brown,fox,jumps,over,quick 
Você assinalou essa alternativa (C) 
Você acertou! 
Aula 4 – tema 3 
 
D jumps, brown,the,fox,quick,over 
 
E over,quick,jumps,fox,the,brown 
 
Questão 4/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: 0.0Você não pontuou essa questão 
 
A I apenas 
 
B II apenas 
 
C I e II apenas 
Aula 4.Tema 2 
 
D I e III apenas 
Você assinalou essa alternativa (D) 
 
E II e III apenas 
 
Questão 5/10 - Estrutura de Dados 
“... após o hash, duas chaves podem ser mapeadas para a mesma posição. Chamamos essa situação de colisão. Felizmente, existem técnicas eficazes para 
resolver o conflito criado por colisões.” 
CORMEN, Thomas. Algoritmos - Teoria e Prática.Grupo GEN, 2012. E-book. ISBN 9788595158092. Disponível em: 
https://integrada.minhabiblioteca.com.br/#/books/9788595158092/. PAG 186 
A maneira como é tratada as colisões depende muito do tipo de endereçamento.Acerca dos tipos de endereçamento, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A O endereçamento aberto é mais empregado quando a quantidade de palavras-chaves é bastante grande se comparado com o tamanho da tabela hash. 
 
B No endereçamento aberto a tabela hash é construída com um vetor, que armazenará todas as chaves que não colidirem. 
 
C No endereçamento aberto, quando uma colisão ocorre, ela precisa ser tratada com algum algoritmo, como o de tentativa linear e a quadrática. 
Você assinalou essa alternativa (C) 
Você acertou! 
Aula 5 – TEMAS 3 e 4 
 
D No endereçamento em cadeia não precisamos tratar colisões, pois cada nova chave pode ser anexada em uma lista encadeada que contém todas as chaves que colidiram. 
 
E As funções de hash aplicadas para endereçamento em cadeia são diferentes das aplicadas no endereçamento aberto. 
 
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." 
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 7/10 - Estrutura de Dados 
"A propriedade de auto balanceamento de uma árvore AVL é mantida por meio do fator de equilíbrio. Quando a diferença na altura das subárvores esquerda 
e direita atinge um valor maior do que 1 (ou menor do que - 1), a árvore precisa ser balanceada por meio de operações de rotação." 
Rodrigues, Thiago, N. et al. Estrutura de Dados em Java. Ed. Grupo A, 2021.pag 151 
 Observe um exemplo de árvore AVL abaixo: 
 
 
 
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! 
aula 4 - tema 4 
Raiz -> Desbalanceada = -2. 
Filho da esquerda -> Balanceado = 0 
Rotação simples para a direita 
 
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 paipara a direita. 
 
Questão 8/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: 0.0Você não pontuou essa questão 
 
A Pilha 
Aula 6 – tema 4 
 
B Fila 
Você assinalou essa alternativa (B) 
 
C Hash 
 
D Dicionário 
 
E Árvore 
 
Questão 9/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 
 
E Todas estão erradas. 
Você assinalou essa alternativa (E) 
 
Questão 10/10 - Estrutura de Dados 
Observe a figura abaixo: 
 
 
 
Podemos afirmar que a figura pode ser representada por uma estrutura de dados. Qual a estrutura de dados que melhor representa a figura 
acima? 
Nota: 10.0 
 
A Árvore AVL 
 
B Grafo 
Você assinalou essa alternativa (B) 
Você acertou! 
Aula 6 - tema 1 
 
C Heap 
 
D Hash 
 
E Fila