APOL 2 Estrutura de Dados

Prévia do material em texto

Questão 1/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: 
 
A O endereçamento aberto é mais empregado quando a quantidade de palavras-chaves é bastante grande 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. 
 
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. 
 
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. 
 
E As funções de hash aplicadas para endereçamento em cadeia são diferentes das aplicadas no 
endereçamento aberto. 
Questão 2/10 - Estrutura de Dados 
Na AULA 4 estudamos árvores binárias. 
Acerca de árvore binárias e a inserção dos dados em uma árvore construída para funcionar como uma Binary Search 
Tree, assinale a alternativa CORRETA. 
 
A Em uma BST trabalhando com dados numéricos inteiros, cada elemento de valor maior que seu nó pai é 
inserido no ramo esquerdo. 
 
B Em uma BST, podemos inserir elemento em qualquer posição da árvore binária. 
 
C Em uma BST trabalhando com dados numéricos inteiros, cada elemento de valor menor que seu nó pai é 
inserido no ramo direito. 
 
D Se tivermos uma árvore com somente uma raiz e com o valor 1, e inserirmos, na sequência, o valor 2, 
seguido pelo 3, 4 e 5. Isso resultará em uma árvore binária se comportando como se fosse uma lista 
encadeada simples, pendendo para o ramo esquerdo. 
 
E Caso já exista um elemento inserido, tanto no ramo esquerdo quanto no ramo direito de um nó, deve-se 
avançar para o próximo nó para tentar a inserção, pois não será possível inserir neste. 
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. 
 
A O grau do vértice V1 é 3. 
 
B Todos os vértices deste grafo têm o mesmo grau, caracterizando um grafo trivial. 
 
C Este grafo é do tipo completo. 
 
D Se removermos qualquer uma das arestas do grafo, estaríamos transformando o grafo em um do tipo completo. 
 
E A aresta que conecta V1 e V3 e V1 E v4 podem ser chamadas de laços. 
Questão 4/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. 
 
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. 
 
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 5/10 - Estrutura de Dados 
Na AULA 6 estudamos endereçamento aberto de tabelas hash com tentativa linear e tentativa quadrática. 
Acerca da tentativa linear e da tentativa quadrática, assinale a alternativa INCORRETA: 
 
A Na tentativa linear, quando uma colisão ocorre, a próxima posição livre, subsequente, é acessada. 
 
B Na tentativa quadrática, quando uma colisão ocorre, a primeira posição a ser testada após a colisão é 
sempre a posição seguinte do vetor. 
 
C Na tentativa quadrática, quando uma colisão ocorre, a nova tentativa é feita em uma posição que está a 
uma distância d da posição originalmente testada. Onde d será sempre o dobro da posição originalmente 
testada. 
 
D A função hash adotada independe do tipo de tentativa empregado (linear ou quadrática). 
 
E A tentativa quadrática tende a espalhar mais as chaves colididas na tabela hash. 
Questão 6/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. 
 
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. 
 
B Uma visualização da árvore em ordem significa lista os elementos em ordem decrescente. 
 
C Se fizermos uma listagem iniciando na direita, depois a raiz e depois o ramo esquerdo estaremos listando 
os elementos de maneira crescente. 
 
D A impressão de valores em pré-ordem resultará em uma impressão inversa/oposto da em pós-ordem. 
 
E Só é possível visualizar os dados de uma árvore binária caso não exista nenhum nó com grau 0. 
Questão 7/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. 
 
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. 
 
E Palavra-chave em uma tabela hash é aquele dado utilizado no cálculo de uma posição utilizando um 
algoritmo de hash. 
Questão 8/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. 
 
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. 
 
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. 
 
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. 
 
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. 
 
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. 
Questão 9/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.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. 
Questão 10/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. 
 
A O grafo contém arestas múltiplas, pois temos mais de um caminho para sair de V1 e chegar em V9, por 
exemplo. 
 
B O grau do vértice V9 é 3. 
 
C Todos os vértices deste grafo têm o mesmo grau. 
 
D Este grafo é do tipo completo. 
 
E O grau do vértice V4 é 3.