apol 2 tentativa 2 Estrutura de dados

Prévia do material em texto

Questão 1/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 2/10 - Estrutura de Dados
"Uma árvore binária de busca tem a seguinte propriedade: para cada nó n da árvore, todos os valores armazenados em sua subárvore à esquerda (a árvore cuja raiz é o filho à es-querda) são menores que o valor v armazenado em n, e todos os valores armazenados na subárvore à direita são maiores ou igual a v."
DROZDEK, Adam. Estrutura de Dados e Algoritmos em C++ – Tradução da 4ª edição norte-americana. Cengage Learning Brasil, 2018. E-book. ISBN 9788522126651. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788522126651/. Acesso em: 07 dez. 2022.PAG189
Observe o código abaixo:
1 class BST:
2    def __init__(self,dado=None):
3        self.dado = dado
4        self.esquerda = None
5        self.direita = None
6
7    def inserir(self, dado):
8        if(self.dado ==None):
9            self.dado = dado
10        else:
11            if(dado <self.dado):
12                if(self.esquerda):
13                    self.esquerda.inserir(dado)
14                else:
15                    self.esquerda = BST(dado)
16            else:
17                if(self.direita):
18                    self.direita.inserir(dado)
19                else:
20                    self.direita = BST(dado)
Considerando o texto, o conteúdo visto em aula e o código acima, assinale a alternativa INCORRETA:
Nota: 10.0
	
	A
	O trecho de código que representa a inserção do nó raiz está nas linhas 8 e 9.
	
	B
	O trecho de código que  armazena os nós maiores que a raiz é representado pelas linhas 16 a 20.
	
	C
	O trecho de código que armazena os nós menores que a raiz é representado pelas linhas de 8 a 13.
Você assinalou essa alternativa (C) Você acertou! O trecho de código que armazena os nós menores que a raiz é representado pelas linhas de 11 a 15 Aula 4 – tema 2
	
	D
	A função init é um construtor da classe BST, inicializando as variáveis esquerda e direita com o valor None.
	
	E
	A função inserir é uma função recursiva, sendo chamada nas linhas 13 e 18.
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
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 5/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:
Arvore 1
Árvore 2
Àrvore 3
Considerando o texto base e o conteúdo visto em aula, assinale a alternativa correta:
Nota: 10.0
	
	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.
Você assinalou essa alternativa (C) Você acertou! Aula 4 . Tema 1
	
	D
	São arvores binárias a Àrvore 1,  Árvore 2 e a Árvore 3.
	
	E
	Apenas a árvore 2 é uma árvore binária.
Questão 6/10 - Estrutura de Dados
Observe o código de consulta em ordem na árvore, assumindo que os dados cadastrados são do tipo inteiro.
1 def emOrdem(self,lst):
2    if (self.esquerda):
3        self.esquerda.emOrdem(lst)
4    lst.append(self.dado)
5    if(self.direita):
6        self.direita.emOrdem(lst)
7    return lst
Acerca de consulta em árvore e do código acima, alternativa INCORRETA:
Nota: 10.0
	
	A
	Retirando a linha 4 e colocando logo após a definição da função (inserindo portanto na linha 2), a consulta em pré ordem aconteceria.
	
	B
	A função deve receber como parâmetro uma lista, representada por lst
	
	C
	A consulta em pos ordem ocorrerá se invertermos o bloco do segundo if pelo primeiro if .
	
	D
	A linha 2 verifica se a variável esquerda é igual a None.
Você assinalou essa alternativa (D)
Você acertou!
None denota falta de valor
Aula 4 - Tema 2
	
	E
	A função retorna uma lista ordenada crescente.
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.
No caso de uma arvore AVL balanceada, o fator de balanceamento sempre será:
Nota: 10.0
	
	A
	menor ou igual a 2.
	
	B
	igual a 0 ou -1.
	
	C
	igual a -1, 0 ou 1.
Você assinalou essa alternativa (C)
Você acertou!
Aula 4 – tema 4
	
	D
	maior que 1.
	
	E
	igual a 1.
Questão 8/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
Você assinalouessa alternativa (B)
	
	C
	II e III  apenas
	
	D
	I, II e III
	
	E
	Todas estão erradas.
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:
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 10/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: 0.0Você não pontuou essa questão
	
	A
	Pilha
Você assinalou essa alternativa (A)
	
	B
	Fila
Aula 6 – tema 4
	
	C
	Hash
	
	D
	Dicionário
	
	E
	Árvore