apol 2 tentativa 1 Estrutura de DAdos

Prévia do material em texto

Questão 1/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 2/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 3/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
Questão 4/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 5/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: 10.0
	
	A
	I e II apenas
Você assinalou essa alternativa (A)
Você acertou!
Aula 4. Tema 1
	
	B
	I e III apenas
	
	C
	II e III  apenas
	
	D
	I, II e III
	
	E
	Todas estão erradas.
Questão 6/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.
Nota: 10.0
	
	A
	I somente.
	
	B
	I e II somente. 
	
	C
	I e III somente.
Você assinalou essa alternativa (C)
Você acertou!
Aula 4 – tema 5
	
	D
	II e III somente.
	
	E
	I, II e III.
Questão 7/10 - Estrutura de Dados
Basicamente, a função  de hashing realiza um mapeamento dos registros de um arquivo por meio de um campo “chave”. A “chave” normalmente é determinada por um campo que possui um valor unívoco e, portanto, funciona como o identificador do arquivo, como, por exemplo, o RG de uma pessoa. Com esse mapeamento, um campo ou um conjunto de campos chaves e´ relacionado a um ou mais enderec¸os ou posições onde os registros estão  armazenados.
Lima, Diana M., D. e Luis E. F. Gonzalez. Matemática aplicada à informática (Tekne). Disponível em: Minha Biblioteca, Grupo A, 2015.pag57
Acerca de hashs, vetores e tipos de endereçamento, assinale a alternativa INCORRETA:
Nota: 10.0
	
	A
	O uso de tabela hash é capaz de transformar o tempo de busca de um dado em uma estrutura de dados do tipo vetor, em uma complexidade que independe do tamanho do conjunto de dados.
	
	B
	Podemos definir a posição de inserção de um dado no vetor utilizando uma função hash. Esta função será uma equação lógica e/ou matemática.
	
	C
	O endereçamento aberto em um vetor é aquele onde armazenamos um novo dado na primeira posição livre disponível no vetor.
	
	D
	O acesso a qualquer dado de um vetor com endereçamento direto é realizado com O(1), bem como o tempo de busca de uma informação neste vetor.
Você assinalou essa alternativa (D)
Você acertou!
O tempo de busca com endereçamento direto é atrelado ao algoritmo de busca adotado. AULA 5 – TEMA 4.
	
	E
	Palavra-chave em uma tabela hash é aquele dado utilizado no cálculo de uma posição utilizando um algoritmo de hash.
Questão 8/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 9/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:
2def __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 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  é:
Nota: 10.0
	
	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)
Você acertou! Aula 4. tema1
	
	D
	Estão corretas as afirmativas  I e III apenas.
	
	E
	Estão corretas as afirmativas  II e III apenas