APOL2 - ESTRUTURA DE DADOS - NOTA 100

Prévia do material em texto

Questão 1/10 - Estrutura de Dados
Na AULA 6 estudamos endereçamento aberto de tabelas hash com tentativa linear e tentativa quadrática.
Acerca da tentativa linear e da tentativa quadrática, assinale a alternativa INCORRETA:
Nota: 10.0
	
	A
	Na tentativa linear, quando uma colisão ocorre, a próxima posição livre, subsequente, é acessada.
	
	B
	Na tentativa quadrática, quando uma colisão ocorre, a primeira posição a ser testada após a colisão é sempre a posição seguinte do vetor.
	
	C
	Na tentativa quadrática, quando uma colisão ocorre, a nova tentativa é feita em uma posição que está a uma distância d da posição originalmente testada. Onde d será sempre o dobro da posição originalmente testada.
Você acertou!
O cálculo de d não é o dobro. A equação é apresentada na página 20 da AULA 6.
	
	D
	A função hash adotada independe do tipo de tentativa empregado (linear ou quadrática).
	
	E
	A tentativa quadrática tende a espalhar mais as chaves colididas na tabela hash.
Questão 2/10 - Estrutura de Dados
Na AULA 5 estudamos grafos e o algoritmo de caminho mínimo.
Acerca do algoritmo de caminho mínimo Djikstra, assinale a alternativa CORRETA.
Nota: 10.0
	
	A
	Este algoritmo só é capaz de definir um menor caminho caso grafo seja ponderado.
Podemos usar um grafo ponderado, mas isso não é obrigatório. Caso ele não seja ponderado, significa que todas as arestas terão peso um, e caso a métrica seja aditiva, teremos que o menor caminho será o menor número de saltos possíveis.
	
	B
	O Djikstra só é capaz de definir a melhor rota seguindo uma métrica denominada de aditiva.
Podemos usar diferentes métricas. A aditiva é a mais comum.
	
	C
	Quando não existe um caminho entre dois vértices, representamos como se a rota entre eles no vetor de distâncias tem um peso infinito (variável de valor extremamente alto).
Você acertou!
Correto. AULA 5 – TEMA 4.
	
	D
	O caminho de um vértice V0 até um vértice V2, passando por um vértice V1, utilizando métrica aditiva, será a soma dos pesos de V0 para V1 e V0 para V2.
Será a soma de V0 para V1 e V2 para V2.
	
	E
	O vértice de origem sempre terá um caminho infinito para si próprio.
O vértice de origem para ele mesmo será peso zero do caminho.
Questão 3/10 - Estrutura de Dados
Na AULA 4 estudamos a inserção em uma árvore binária. Abaixo temos um código em linguagem C com uma função de inserção na árvore binária, considerando ela como uma Binary Search Tree (BST).
1. void Inserir(ElementoDaArvoreBinaria ** ElementoVarredura, int num) {
2. 
3. if (*ElementoVarredura == NULL)
4. { 
5.      ElementoDaArvoreBinaria *NovoElemento = NULL;
6.      NovoElemento = (ElementoDaArvoreBinaria *)malloc(sizeof(ElementoDaArvoreBinaria));
7.      NovoElemento->esquerda = NULL;
8.      NovoElemento->direita = NULL;
9. 
10.     NovoElemento->dado = num;
11.     *ElementoVarredura = NovoElemento;
12.     return;
13. }
14. 
15. if (num < (*ElementoVarredura)->dado)
16. {
17.     Inserir(&(*ElementoVarredura)->esquerda, num);
18. }
19. else
20. {
21.     if (num >(*ElementoVarredura)->dado)
22.     {
23.          Inserir(&(*ElementoVarredura)->direita, num);
24.     }
25. }
26. }
Acerca de árvores binárias e do código acima, assinale a alternativa CORRETA.
Nota: 10.0
	
	A
	Nas linhas 15 a 25 a função testa para qual ramo da árvore irá seguir, direito ou esquerdo, chamando novamente a função de inserção de forma recursiva.
Você acertou!
Correto.
	
	B
	Na linha 3 temos um teste condicional simples que tem como objetivo verificar se a árvore binária está completamente vazia, ou não.
Verifica se AQUELE ELEMENTO está vazio, não a arvore toda;
	
	C
	Todo o código colocado entre as linhas 15 e 25 poderiam estar dentro de um SENÃO que faz parte da condicional da linha 4.
Não seria possível isso, pois as linhas 15 a 25 precisam ser executadas independentemente da condição da linha 3;
	
	D
	Na linha 2 temos a declaração da função, onde o primeiro parâmetro é uma variável que foi declarada com dois asteriscos (**). Deveria ser somente um, pois dois asteriscos não são permitidos na linguagem C.
É permitido e está correto. Porque temos um ponteiro para outro ponteiro, caracterizando dois asteriscos;
	
	E
	O uso do um asterisco antes do nome da variável, como na linha 3 por exemplo, significa que queremos manipular o endereço daquela variável.
O asterisco indica o conteúdo indireto para qual o ponteiro aponta.
Questão 4/10 - Estrutura de Dados
Na AULA 4 estudamos conceitos de árvores binárias. Acerca de árvores, assinale a alternativa abaixo:
1. ElementoDaArvoreBinaria *NovoElemento = NULL;
2. NovoElemento = (ElementoDaArvoreBinaria *)malloc(sizeof(ElementoDaArvoreBinaria));
3. NovoElemento->esquerda = NULL;
4. NovoElemento->direita = NULL;
5. 
6. NovoElemento->dado = num;
7. *ElementoVarredura = NovoElemento;
Acerca de árvores e seus aspectos construtivos, assinale a alternativa INCORRETA.
Nota: 10.0
	
	A
	O código refere a inicialização de um nó da árvore, onde alocamos a variável na memória e inicializamos os campos do registro.
Linha 2 contém a alocação, linhas 3, 4 e 5 contém a inicialização.
	
	B
	Baseado no código acima, podemos afirmar com certeza que o registro que armazena cada elemento da árvore contém um dado do tipo inteiro e dois ponteiros.
Você acertou!
Não sabemos o tipo do dado pelo código acima.
	
	C
	Na linha 2 alocamos uma variável na memória destinada ao programa. O espaço alocado é igual a quantidade de Bytes usada pelo registro ElementoDaArvoreBinaria.
Sim. A função malloc em C faz alocação e a função sizeof diz o tamanho a ser alocado.
	
	D
	Na linha 1, a variável NovoElemento é declarada como sendo um ponteiro para um tipo de variável chamado ElementoDaArvoreBinaria.
Sim. O asterisco indicará o ponteiro;
	
	E
	Nas linhas 3, 4 e 6 estamos acessando os campos de um registro. Em linguagem C, um campo de uma variável ponteiro é acessado com uma flecha para a direta ‘->’, e não com um PONTO. Se usarmos PONTO neste caso, como por exemplo NovoElemento.esquerda, não irá funcionar.
Exatamente;
Questão 5/10 - Estrutura de Dados
Na AULA 5 estudamos conceitos de grafos.
Acerca de grafos, seus conceitos e suas definições, assinale a alternativa INCORRETA.
Nota: 10.0
	
	A
	Um grafo é uma estrutura de dados que funciona de uma maneira não linear, podendo ser construído sem nenhum padrão definido.
	
	B
	Arestas são linhas de conexão entre grafos.
Você acertou!
São linhas de conexão entre vértices de um grafo. AULA 5 – TEMA 1.
	
	C
	Podemos mapear um mapa rodoviário como uma malha de vértices e arestas conectadas.
	
	D
	Podemos percorrer um grafo, andando por seus vértices e arestas, de maneira a encontramos os melhores caminhos nele.
	
	E
	Um grafo é composto de vértices e arestas;
Questão 6/10 - Estrutura de Dados
Na AULA 5 estudamos conceitos de grafos.
Acerca de grafos e seus aspectos construtivos, assinale a alternativa INCORRETA.
Nota: 10.0
	
	A
	Um laço ocorre quando uma aresta está conectada em um só vértice.
	
	B
	Um grafo completo é aquele que contém uma, e somente, aresta para cada par distinto de vértices.
	
	C
	Um grafo ponderado é aquele no qual todas suas arestas contém um peso.
	
	D
	Um grafo trivial é aquele que apresente somente um vértice e uma aresta;
Você acertou!
Somente um vértice e nenhuma aresta. AULA 1 – TEMA 1.
	
	E
	Encontramos arestas múltiplas em um grafo quando duas arestas conectam os mesmos vértices;
Questão 7/10 - Estrutura de Dados
O método da divisão é um tipo de função hash bastante empregado na construção de tabelas hash.
Assuma 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 palavra-chave. Por exemplo, o número 1234, será: 12 + 34 = 46.
Assuma também 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 dovetor para 110, a nova posição desta chave será 36.
Você acertou!
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 8/10 - Estrutura de Dados
Na AULA 5 estudamos conceitos de grafos e suas representações matemáticas
Acerca do grafo e suas representações matemáticas, assinale a alternativa INCORRETA.
Nota: 10.0
	
	A
	Na representação por lista de adjacências, temos um conjunto de listas encadeadas, onde cada lista conterá todos os vizinhos de um único vértice;
	
	B
	Uma representação por matriz de incidências representa um grafo na forma de uma matriz, onde as linhas são os vértices e as colunas as arestas;
	
	C
	Uma representação por matriz de adjacências representa um grafo na forma de uma matriz, onde as linhas e as colunas são os vértices;
	
	D
	Uma representação por lista de adjacências representa um grafo na forma de um conjunto de listas encadeadas.;
	
	E
	Na representação por lista de adjacências não podemos repetir um vértice em duas listas encadeadas distintas.
Você acertou!
Podemos repetir, pois cada lista conterá todos os vizinhos de cada vértice.
Questão 9/10 - Estrutura de Dados
Trabalhamos com diferentes tipos de endereçamento em uma tabela hash.
Acerca dos tipos de endereçamento (direto, aberto e em cadeia), 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.
Empregado quando a quantidade de palavras-chaves é pequena 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.
Armazena inclusive as que colidem. Porém, as colididas precisam ser tratadas e inseridas em outra posição.
	
	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ê acertou!
Aula 6 – 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.
As listas encadeadas armazenam todas as chaves em cada posição. Colididas ou não.
	
	E
	As funções de hash aplicadas para endereçamento em cadeia são diferentes das aplicadas no endereçamento aberto.
São as mesmas funções.
Questão 10/10 - Estrutura de Dados
Na AULA 4 estudamos as diferentes consultas em árvores binárias. Observe o código de consulta em ordem na árvore, assumindo que os dados cadastrados são do tipo inteiro. 
1. void Consultar_EmOrdem(ElementoDaArvoreBinaria * ElementoVarredura)
2. {
3.      if (ElementoVarredura)
4.      {
5.           Consultar_EmOrdem(ElementoVarredura->esquerda);
6.           printf("%d\t", ElementoVarredura->dado);
7.           Consultar_EmOrdem(ElementoVarredura->direita);
8.      }
9. }
Acerca de consulta em árvore e do código acima, alternativa CORRETA.
Nota: 10.0
	
	A
	A linha 7 poderá nunca ser executada no código acima. Basta que não exista nenhum elemento para a direita.
Existindo elemento para a direita, ou não, a linha 7 é executada, pois não temos nenhum teste condicional que impeça isso.
	
	B
	A linha 3 verifica se a variável ElementoVarredura é igual a zero.
Ela verifica se a variável está NULA (vazia). Que é um conceito diferente de verificar se é igual a valor numérico zero.
	
	C
	A impressão dos dados em pré-ordem poderia ser feita se invertêssemos as linhas 6 e 7.
O correto seria inverter as linhas 5 e 6.
	
	D
	A impressão dos dados em pós-ordem poderia ser feita se invertêssemos as linhas 5 e 7.
O correto seria inverter as linhas 6 e 7.
	
	E
	Se quiséssemos imprimir os elementos da árvore de maneira decrescente, ou seja, do maior para o menor, poderíamos trocar as linhas 5 e 7.
Você acertou!
CORRETO. A consulta EM ORDEM, por padrão é crescente. Se invertermos a ordem fica decrescente.