Apol 2 Estrutura de Dados 2020

Prévia do material em texto

SE AJUDOU DEIXE UMA CURTIDA 
Questão 1/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 do vetor 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 2/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. 
 
Questão 3/10 - Estrutura de Dados 
Na AULA 5 estudamos conceitos de grafos. Abaixo temos uma imagem de um grafo. 
 
Acerca do grafo acima, 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. 
Arestas múltiplas são para arestas com os mesmos vértices de origem e destino. 
 
B O grau do vértice V9 é 3. 
O grau é 4. Pois é o número de arestas incidentes. 
 
C Todos os vértices deste grafo têm o mesmo grau. 
Temos graus diferentes: 2, 3 e 4. 
 
D Este grafo é do tipo completo. 
No grafo completo, todos os vértices precisam estar conectados entre si por somente uma aresta. Neste grafo faltam diversas conexões. 
 
E O grau do vértice V4 é 3. 
Você acertou! 
Correto. Pois é o número de arestas incidentes. 
 
Questão 4/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 5/10 - Estrutura de Dados 
Na AULA 4 estudamos árvores binárias. 
Acerca de árvore binárias e a busca dos dados em uma árvore construída para funcionar como uma 
Binary Search Tree, assinale a alternativa INCORRETA. 
Nota: 0.0 
 
A A busca em uma árvore apresentará um desempenho inferior ao em uma lista encadeada devido a sua organização não linear. 
O desempenho é superior. O(logn), enquanto que a lista é O(n) para a busca. 
 
B A varredura em uma árvore do tipo BST é eficiente devido ao fato dos elementos estarem já organizados, com valores menores para um lado e maiores para o outro lado. 
 
C A busca em uma BST delimita a área de busca sempre pela metade, reduzindo um problema de dimensão n, em dois problemas n/2. 
 
D A complexidade assintótica para a busca na árvore pode ser considerada O(logn). 
 
E Ao chegar no final de um ramo, ou seja, ambos ponteiros do nó forem nulos, significa que o valor buscado não existe na árvore binária. 
 
Questão 6/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 7/10 - Estrutura de Dados 
Na AULA 5 estudamos grafos e seus algoritmos de busca. 
Acerca da busca em profundidade no grafo, assinale a alternativa INCORRETA. 
Nota: 10.0 
 
A A busca em profundidade trabalha com o uma pilha que mantém todos os vértices que ainda não tiveram todos os seus vizinhos visitados nela. 
 
B A busca em profundidade pode ser implementada com qualquer tipo de representação de grafos: matriz ou lista. 
 
C Uma variável mantém salvo todos os vértices já visitados, pois podemos passar somente uma vez por cada vértice. 
 
D Um vértice, quando visitado pela primeira vez, tem sua lista de vizinhos acessada imediatamente e seu número é colocado na pilha.E Um vértice sai da pilha quando o algoritmo pula para o próximo vizinho deste vértice. 
Você acertou! 
Um vértice só sai da pilha quando é localizado o elemento que contém um ponteiro nulo da sua lista encadeada de vizinhos. 
 
Questão 8/10 - Estrutura de Dados 
Na AULA 6 estudamos a estrutura de dados do tipo hash. 
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 direto 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 direito é realizado com O(1), bem como o tempo de busca de uma informação neste vetor. 
Você acertou! 
O tempo de busca com endereçamento direto é atrelado ao algoritmo de busca adotado. AULA 6 – TEMA 1. 
 
E Palavra-chave em uma tabela hash é aquele dado utilizado no cálculo de uma posição utilizando um algoritmo de hash. 
 
Questão 9/10 - Estrutura de Dados 
Na AULA 5 estudamos conceitos de grafos. Abaixo temos uma imagem de um grafo. 
 
Acerca do grafo acima, assinale a alternativa CORRETA. 
Nota: 10.0 
 
A O grau do vértice V1 é 3. 
O grau é 4. Pois é o número de arestas incidentes. 
 
B Todos os vértices deste grafo têm o mesmo grau, caracterizando um grafo trivial. 
Tem o mesmo grau, mas o grafo é chamado de ponderado. 
 
C Este grafo é do tipo completo. 
Você acertou! 
Sim. Todos os vértices estão conectados por uma e somente uma aresta. 
 
D Se removermos qualquer uma das arestas do grafo, estaríamos transformando o grafo em um do tipo completo. 
O grafo já é completo. Se remover uma aresta qualquer, ele deixa de ser completo. 
 
E A aresta que conecta V1 e V3 e V1 E v4 podem ser chamadas de laços. 
Laço é uma aresta com um só vértice. 
 
Questão 10/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, assinale a alternativa CORRETA: 
Nota: 10.0 
 
A 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. 
Uma função hash não apresenta uma fórmula definida, e deve ser projetada levando em consideração o tamanho do conjunto de dados, seu comportamento e os tipos de dados-chave utilizados. 
 
B O uso de estrutura de tabela hash sempre apresentará um desempenho de busca superior ao endereçamento direito. 
Nem sempre. Se a função hash adotada é muito complexa, talvez apresente um desempenho inferior. Portanto, escolher a função hash adequada é fundamental. 
 
C 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. 
Você acertou! 
Correto. AULA 6 – TEMA 2. 
 
D A função hash que utiliza o método da divisão só pode ser aplicado para palavras-chave do tipo numérica. 
Qualquer tipo de dado pode ser usado no método da divisão. 
 
E O método da divisão utiliza o quociente da divisão de dois valores para encontrar a posição de uma palavra-chave. 
Não é o quociente da divisão, mas sim o resto da divisão.