apol2

Prévia do material em texto

Questão 1/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: 
 
A Heap. 
 
B de busca binária. 
 
C Ordenada. 
 
D binária. 
 
E AVL. 
Você assinalou essa alternativa (E) 
 
Questão 2/10 - Estrutura de Dados 
Muitas aplicações exigem um conjunto dinâmico que suporte somente as operações de dicionário INSERT, SEARCH e DELETE. Por 
exemplo, um compilador que traduz uma linguagem de programação mantém uma tabela de símbolos na qual as chaves de elementos 
são cadeias de caracteres arbitrários que correspondem a identificadores na linguagem. 
CORMEN, Thomas. Algoritmos - Teoria e Prática. Grupo GEN, 2012. Pag 184 
O trecho do texto acima faz uma menção a uma estrutura de dados, conhecida como: 
 
A Lista 
 
B Fila 
 
C Pilha 
 
D Tupla 
 
E hash 
Você assinalou essa alternativa (E) 
 
Questão 3/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. 
No caso de uma arvore AVL balanceada, o fator de balanceamento sempre será: 
 
A menor ou igual a 2. 
 
B igual a 0 ou -1. 
 
C igual a -1, 0 ou 1. 
Você assinalou essa alternativa (C) 
 
D maior que 1. 
 
E igual a 1. 
 
Questão 4/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. 
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. 
 
E I, II e III. 
Você assinalou essa alternativa (E) 
 
Questão 5/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: 
Você não pontuou essa questão 
 
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 6/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. 
Você assinalou essa alternativa (C) 
 
D II e III somente 
 
E I, II e III. 
 
Questão 7/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 8/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. 
 
B No endereçamento aberto a tabela hash é construída com um vetor, que armazenará todas as chaves que não colidirem. 
Você assinalou essa alternativa (B) 
 
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 9/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 feitasas 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 
 
Questão 10/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. 
 
D O maior valor possível representado com 4 dígitos será colocado na posição 98. 
Você assinalou essa alternativa (D) 
 
E A palavra-chave 1873, será inserida na posição 91 do vetor.