Estrutura de Dados APOL 2

Prévia do material em texto

Questão 1/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 2/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: 10.0 
 
A A busca em uma árvore apresentará um desempenho inferior ao em uma lista encadeada devido a sua organização não linear. 
Você acertou! 
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 3/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 4/10 - Estrutura de Dados 
Na AULA 5 estudamos a árvore binária balanceada AVL. Observe um exemplo de árvore AVL abaixo: 
 
Suponha que você quer remover o nó folha de valor 99. Acerca do balanceamento e rotação desta árvore sem o 99. Assinale 
a alternativa CORRETA: 
Nota: 10.0 
 
A A árvore ficará balanceada e não precisará de rotação nenhuma. 
 
B A árvore ficará com um desbalanceamento de valor 2 na raiz. 
 
C O nó filho de valor 80 está com balanceamento 0, resultando em uma rotação simples para a direta. 
Você acertou! 
Raiz -> Desbalanceada = -2. 
Filho da esquerda -> Balanceado = 0 
Rotação simples para a direita 
 
D A árvore está com um desbalanceamento de valor -2 na raiz, resultando em uma rotação simples para a esquerda. 
 
E O nó filho de valor 80 está com balanceamento 1, resultando em uma dupla com filho para a esquerda e pai para a direita. 
 
Questão 5/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 6/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 7/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. 
 
Questão 8/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 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 5 estudamos grafos e seus algoritmos de busca. 
Acerca da busca em largura no grafo, assinale a alternativa INCORRETA. 
Nota: 0.0 
 
A A busca em largura trabalha com o uma fila, a qual mantém todos os vértices que ainda serão visitados. 
 
B Um vértice conectado por uma aresta com o vértice de origem contém distância um. 
 
C A busca em largura trabalha com o conceito de distâncias, onde sempre acessamos um vizinho que está a um salto de distância do vértice atualmente visitado e que já 
tenha sido visitado. 
Que não tenha sido visitado ainda. 
 
D Quando percorremos a lista de vizinhos de um vértice, vamos colocando cada vizinho ainda não visitado na fila, pois eles serão os próximos a serem acessados. 
 
E O vértice de origem é aquele cuja distância é zero.