Apol 2 Estrutura de dados

Prévia do material em texto

ta: 10.0 Questão 1/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 2/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 3/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 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. 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 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 
Na AULA 5 estudamos a árvore binária balanceada AVL. Observe um exemplode á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 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 
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 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.