apol2 1

Prévia do material em texto

Questão 1/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: 
Você não pontuou essa questão 
 
A O endereçamento aberto é mais empregado quando a quantidade de palavras-chaves é bastante grande se comparado com o tamanho da tabela hash. 
Você assinalou essa alternativa (A) 
 
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. 
 
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 2/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: 
 
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) 
 
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 3/10 - Estrutura de Dados 
Observe a seguinte arvore AVL: 
Ao se inserir o valor 40 nessa árvore, as seguintes afirmativas são feitas: 
I. O fator de balanceamento da raiz 50 passa a ser -2 e a árvore fica desbalanceada. 
II. A árvore fica desbalanceada e uma rotação simples à direita é suficiente para balancear a árvore. 
III. A arvore fica desbalanceada e uma rotação dupla a direita (rotação esquerda-direita) é necessária. 
 
A I somente. 
 
B I e II somente. 
 
C I e III somente. 
Você assinalou essa alternativa (C) 
 
D II e III somente. 
 
E I, II e III. 
 
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: 
 
A I apenas 
 
B II apenas 
 
C I e II apenas 
Você assinalou essa alternativa (C) 
 
D I e III apenas 
 
E II e III apenas 
 
Questão 5/10 - Estrutura de Dados 
Frequentemente, é útil determinar o caminho mais curto entre dois vértices em um grafo. Em aula foi visto o algoritmo de Dijkstra 
para encontrar o caminho mais curto. Quanto ao algoritmos de Dijskstra visto em aula podemos afirmar: 
 
A Algoritmo de Dijkstra considera apenas os pesos negativos para encontrar a maior rota. 
 
B Algoritmo de Dijskstra utiliza métrica aditiva, ou seja essa métrica encontra a maior rota considerando os pesos somados estre os caminhos. 
 
C Algoritmos de Dijkstra utiliza métrica preditiva, ou seja, essa métrica encontra a menor rota considerando o menor peso somado entre os caminhos. 
 
D Algoritmo de Dijkstra utiliza métrica aditiva, ou seja, essa métrica vai encontrar a menor rota considerando o menor peso somado entre os caminhos. 
Você assinalou essa alternativa (D) 
 
E Algoritmo de Dijkstra utiliza matriz de incidência para sua representação. 
 
Questão 6/10 - Estrutura de Dados 
Observe a figura a seguir: 
Uma razão para estudarmos grafos é encontrar um 
caminho entre vértices. ... Um vértice é adjacente a um 
outro vértice se existe uma aresta para ele a partir do 
outro vértice. ..Um caminho é uma seqüência de vértices 
em que cada vértice sucessivo é adjacente ao seu 
predecessor. 
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. 
 
Considerando o texto base, o conteúdo visto em aula e o 
grafo acima são feitas as seguintes afirmativas 
I. Philadelphia é adjacente a Pittsburgh que é adjacente 
a Cleveland. 
II. Philadelphia é adjacente a Columbus, mas não a Cleveland. 
III. A seguinte seqüência de vértices é um caminho Philadelphia ? Pittsburgh ? Columbus ? Indianapolis ? Chicago. 
 
Estão corretas as afirmativas: 
 
A I apenas. 
 
B II apenas. 
 
C I e II apenas. 
 
D I e III apenas. 
Você assinalou essa alternativa (D) 
 
E II e III apenas. 
 
Questão 7/10 - Estrutura de Dados 
A definição de uma boa função hash é fundamental para termos uma tabela hash com um bom desempenho. 
Acerca de funções hash, são feitas as seguintes afirmativas: 
I. Uma função hash necessita inserir dados que minimizem o número de colisões, reduzindo também o tempo gasto resolvendo 
colisões e reavendo os dados. 
II.Uma função hash apresenta sempre a mesma fórmula bem definida, e independe do tamanho do conjunto de dados, e dos tipos de 
dados-chave utilizados. 
III. A função hash que utiliza o método da divisão só pode ser aplicado para palavras-chave do tipo numérica. 
Estão corretas as afirmativas: 
Você não pontuou essa questão 
 
A I somente. 
 
B I e II somente. 
 
C I e III somente. 
 
D II e III somente 
Você assinalou essa alternativa (D) 
 
E I, II e III. 
 
Questão 8/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? 
Você não pontuou essa questão 
 
A Árvore AVL 
 
B Grafo 
 
C Heap 
 
D Hash 
Você assinalou essa alternativa (D) 
 
E Fila 
 
Questão 9/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: 
Você não pontuou essa questão 
 
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. 
 
B A palavra-chave 4455, será inserida na última posição disponível do vetor. 
 
C A palavra-chave 9128, será inserida na posição 19 do vetor. 
Você assinalou essa alternativa (C) 
 
D O maior valor possível representado com 4 dígitos será colocado na posição 98. 
 
E A palavra-chave 1873, será inserida na posição 91 do vetor. 
 
Questão 10/10 - Estrutura de Dados 
"Formalmente, define-se uma árvore T como um conjunto de nós que armazenam 
elementos em relacionamentos pai-filho com as seguintes propriedades: 
Se T não é vazia, ela tem um nó especial chamado de raiz de T, que não tem pai. 
Cada nodo v de T diferente da raiz tem um único nó pai, w; todo nó com pai w é filho 
de w." 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos 
em Java. Grupo A, 2013.Pag 303 
Dada a seguinte árvore binária: 
 
São feitas as seguintes afirmativas: 
 
I. O nó 2 tem 2 filhos 
II. A arvore possui 4 nós folhas. 
III. Temos 2 nós no nível 2 . 
Levando em consideração o texto base e o conteúdo visto em aula, a alternativa corretas é: 
 
A Está correta a afirmativa I apenas. 
 
B Está correta a afirmativa II apenas. 
 
C Estão corretas as afirmativas I e II apenas. 
Você assinalou essa alternativa (C) 
 
D Estão corretas as afirmativas I e III apenas. 
 
E Estão corretas as afirmativas II e III apenas