Baixe o app para aproveitar ainda mais
Prévia do material em texto
Estrutura de Dados – Apol 2 Nota 100 Questão 1/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: 10.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. Você acertou! 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. Questão 2/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 3/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 4/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 5/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 6/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 7/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 simplespara 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 8/10 - Estrutura de Dados Na AULA 4 estudamos árvores binárias. Acerca de árvore binárias e a visualização dos dados em uma árvore construída para funcionar como uma Binary Search Tree, e considerando uma árvore binária onde os elementos menores ficam no ramo esquerdo e os maiores no ramo direito, assinale a alternativa CORRETA. Nota: 10.0 A Como a árvore binária não apresenta sequência/ordem fixas, podemos listar seus dados de diferentes maneiras: pré-ordem, ordem e pós-ordem. Você acertou! B Uma visualização da árvore em ordem significa lista os elementos em ordem decrescente. Ordenação crescente; C Se fizermos uma listagem iniciando na direita, depois a raiz e depois o ramo esquerdo estaremos listando os elementos de maneira crescente. Decrescente; D A impressão de valores em pré-ordem resultará em uma impressão inversa/oposto da em pós-ordem. Não existe a relação de oposição entre eles. E Só é possível visualizar os dados de uma árvore binária caso não exista nenhum nó com grau 0. Não existe a relação entre grau e a visualização da árvore. Questão 9/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 10/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.
Compartilhar