Estrutura de dados apol 2

Prévia do material em texto

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: 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. 
 
 
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 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 á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 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 
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 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: 0.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. 
Podemos repetir, pois cada 
lista conterá todos os 
vizinhos de cada vértice. 
 
 
Questão 9/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çãona á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 10/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;