apols 1 a 5 estrutura de dados

Prévia do material em texto

Questão 1/5 - Estrutura de Dados 
No primeiro assunto de nossa disciplina investigamos o que são estruturas de dados e como podemos classificá-las em tipos. 
Acerca deste assunto, assinale a alternativa INCORRETA: 
Nota: 20.0 
 
A Um dado que pode ser decomposto em partes mais simples, é considerado um dado estruturado e, portanto, uma estrutura de dados. 
 
B Os tipos de dados manipulados por um algoritmo podem ser classificados em duas categorias distintas: os atômicos, que são dados indivisíveis, e os 
dados compostos, que podem ser divisíveis em mais partes menores. 
 
C Podemos classificar uma estrutura de dados como sendo do tipo homogênea (como registros) ou do tipo heterogênea (como vetores e matrizes). 
Você acertou! 
AULA 1 – TEMA 1. Podemos classificar uma estrutura de dados como sendo do tipo heterogênea (como registros) ou do tipo homogênea (como 
vetores e matrizes). 
 
D Uma estrutura homogênea é aquela cujo tipo dos dados nela armazenados são de um único tipo, como inteiro, real, caractere ou lógico 
 
E Uma estrutura contendo dados do tipo caractere e do tipo real pode ser considerada uma estrutura de dados heterogênea. 
 
Questão 2/5 - Estrutura de Dados 
O algoritmo de ordenação por intercalação, também conhecido como merge sort, é um dos algoritmos estudados na AULA 2. 
Acerca deste algoritmo, assinale a alternativa CORRETA. 
Nota: 20.0 
 
A A complexidade do merge sort é O(logn), pois o algoritmo trabalha com o princípio de dividir para conquistar. 
O(n.logn), pois temos duas funções. 
 
B O processo do merge sort consiste em dividir uma estrutura de dados de tamanho n (um vetor por exemplo) em 4 partes e ordenar estar partes, 
agregando-as posteriormente. 
O processo do merge sort consiste em dividir uma estrutura de dados de tamanho n (um vetor por exemplo) em n partes de tamanho unitário. 
 
C Ao dividir o conjunto de dado em duas partes menores, o merge sort sempre calcula a posição central da ruptura, que é dada pela média entre os 
valores posição inicial com a posição final, arredondando para cima. 
É feito um truncamento somente da parte inteira. 
 
D A intercalação é realizada utilizando um vetor auxiliar para ir armazenando os dados que vão sendo ordenados naquele momento. 
Você acertou! 
AULA 2 – TEMA 3. Figura 10. 
 
E A função merge sort pode ser implementada de forma recursiva, ou seja, realizando chamadas de si mesma até que o conjunto de dados seja 
indivisível. A ordenação só ocorre quando as partes menores forem agregadas novamente. 
A ordenação ocorre nas partes menores e indivisíveis. 
 
Questão 3/5 - Estrutura de Dados 
A recursividade é um recurso de programação bastante empregado, e consiste no ato de uma função em um código realizar 
chamadas de si mesmo, abrindo diferentes instâncias de uma mesma função na memória do programa. 
Acerca de recursividade e algoritmos recursivos, assinale a alternativa INCORRETA: 
Nota: 20.0 
 
A Diversos problemas computacionais que poderiam ser resolvidos utilizando algoritmos iterativos, ou seja, laços de repetição, podem também ser 
resolvidos usando recursividade. 
 
B Um algoritmo recursivo terá uma complexidade logarítmica, apresentando um desempenho inferior em tempo de execução superior a um algoritmo 
construído de forma iterativa. 
Você acertou! 
AULA 1 – TEMA 4. O desempenho em tempo de execução é superior. 
 
C Uma possível desvantagem de um algoritmo recursivo é o seu uso de memória mais elevado, uma vez que diversas instâncias de uma mesma função 
precisam ser alocadas na memória. 
 
D Um algoritmo que executa uma função denominada de soma, e que realiza a chamada de uma função denominada compara, não pode ser 
considerado um algoritmo recursivo, uma vez que não realizada chamadas de si mesma. 
 
E Um algoritmo recursivo comumente serve para resolver problemas do tipo “dividir para conquistar”, onde dividimos um problema em partes menores e 
mais fáceis de solucionar, para posteriormente agregar as pequenas soluções em uma maior. 
 
Questão 4/5 - Estrutura de Dados 
Uma implementação do algoritmo de ordenação do tipo bubble sort pode ser visto abaixo. As partes que envolvem impressão de 
dados na tela e leitura de dados foram omitidas para um melhor entendimento do que é necessário na questão. 
 
X[TAMANHOVETOR], i, j, aux: inteiro 
para i de 1 até TAMANHOVETOR faça 
 para j de 0 até (TAMANHOVETOR - 2) faça 
 se (X[j] > X[j + 1]) então 
 aux <- X[j] 
 X[j] <- X[j + 1] 
 X[j + 1] <- aux 
 fimse 
 fimpara 
fimpara 
Acerca deste algoritmo, assinale a alternativa CORRETA: 
 
Nota: 20.0 
 
A O algoritmo apresentado no exercício realizado a ordenação de dados numéricos, inteiros, em ordem decrescente. 
Ordenação é crescente. 
 
B As linhas de código que correspondem a troca dos valores usando uma variável auxiliar poderiam ser também escritas da seguinte maneira: 
aux <- X[j+1] 
X[j+1] <- X[j] 
X[j] <- aux 
Você acertou! 
AULA 2 – TEMA 2. CORRETO. 
 
C Se precisarmos ordenar dados não numéricos, como caracteres, precisaremos repensar em toda a lógica do bubble sort, não sendo possível adaptar 
o código facilmente. 
Basta adaptarmos a linha da condicional para funcionar com outro tipo de dado. 
 
D Não é possível implementar o bubble sort com laços de repetição do tipo enquanto. 
É possível implementar com qualquer tipo de laço, para, enquanto ou repita. 
 
E A complexidade deste algoritmo, para o pior caso, é O(logn). 
Complexidade O(n²). 
 
Questão 5/5 - Estrutura de Dados 
O algoritmo de ordenação rápida, também conhecido como quick sort, é um dos algoritmos estudados na AULA 2. 
Acerca deste algoritmo, assinale a alternativa CORRETA. 
Nota: 20.0 
 
A A complexidade do quick sort é O(n²). Isso significa que ele sempre terá a mesma eficiência de um bubble sort. 
Somente o pior caso do bubble e do quick são iguais. Se considerarmos cenários melhores o quick sort se sai bem melhor que o bubble sort. Veja o 
experimento feito na AULA PRÁTICA 1 para mais detalhes. 
 
B O quick sort trabalha com o conceito de pivô, que é o elemento usado nas comparações, comparando sempre o seu valor com todos os valores do 
lado direito do pivô, enquanto que o lado esquerdo permanece já ordenado. 
Ambos os lados são comparados, esquerdo e direito. 
 
C O quick sort trabalha com o conceito de pivô, que é o elemento usado nas comparações, comparando sempre o seu valor com todos os valores do 
lado esquerdo do pivô, enquanto que o lado direito permanece já ordenado. 
Ambos os lados são comparados, esquerdo e direito. 
 
D O quick sort trabalha com uma troca de valores utilizando uma variável auxiliar, da mesma maneira feita no bubble sort. 
Você acertou! 
AULA 2 – TEMA 4 – CORRETO. 
 
E O quick sort só pode ser executado para um tamanho de conjunto de dados máximo igual a 1000, pois mais do que isso o uso de memória pelo 
algoritmo é muito grande. 
O limite máximo dependerá da memória disponível, não sendo limitado ao valor de 1000. 
 
 
Apol 2... 
 
 
 
Questão 1/5 - Estrutura de Dados 
No terceiro assunto de nossa disciplina estudamos estruturas de dados que se comportam como uma PILHA. 
Acerca de PILHA, assinale a alternativa INCORRETA: 
Nota: 20.0 
 
A Em uma pilha construída utilizando listas encadeadas. Desempilhar nela significa remover o primeiro elemento desta pilha. 
Sim. Remoção no topo. 
 
B Uma pilha pode só pode ser construída empregando uma estrutura de dados que trabalhe de maneira não sequencial. 
Você acertou! 
Podemos construir com vetores (sequencial) ou listas (não sequencial). 
 
C Uma pilha trabalha com inserção e remoção no topo da pilha. Sendo impossível manipular qualquer outra posição da pilha. 
Sim. Estrutura do tipo FILO.D Em uma pilha construída utilizando listas encadeadas. Empilhar nela significa inserir antes do primeiro elemento desta pilha. 
Sim. Inserção no topo. 
 
E Em uma, a cada nova inserção, os elementos anteriores vão ficando para o final da pilha, só sendo possível removê-los desempilhando. 
Sim. FILO. 
 
Questão 2/5 - Estrutura de Dados 
No terceiro assunto de nossa disciplina estudamos estruturas de dados que se comportam como uma FILA. 
Acerca de FILAS, assinale a alternativa CORRETA: 
Nota: 20.0 
 
A Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Inserir na fila significaria inserir um elemento que aponte para o valor 
66. 
Inseriria depois do valor 99 (inserção no final da fila). 
 
B Em uma fila, podemos ter a inserção dos dados início desta fila. 
Inserção somente no final. 
 
C Em uma fila, podemos ter a remoção dos dados final ou no meio desta fila. 
Remoção somente no início. 
 
D Em uma fila trabalhamos com o conceito de: “o primeiro que entra é o primeiro que sai”. 
Você acertou! 
Correto. FIFO. 
 
E Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Remover da fila significaria remover o elemento 99. 
Removeria o 66 (remoção no início da fila). 
 
Questão 3/5 - Estrutura de Dados 
No terceiro assunto de nossa disciplina estudamos uma nova estrutura de dados denominada de LISTA ENCADEADA. 
Acerca de listas encadeadas, assinale a alternativa CORRETA: 
Nota: 20.0 
 
A Uma lista encadeada trabalha com alocação sequencial na memória. De maneira similar a uma estrutura de dados do tipo vetor. 
Uma lista é não sequencial. 
 
B Uma lista encadeada trabalha com o conceito de índice. Ou seja, podemos acessar qualquer posição da lista usando o seu índice como referência. 
Não existe o conceito de índice em uma lista encadeada. 
 
C O acesso a qualquer dado em uma lista pode ser feito com a mesma eficiência em tempo de execução, caracterizando uma complexidade de acesso 
aos dados como O(1). 
Complexidade de acesso é O(n). 
 
D Podemos localizar o próximo elemento da lista encadeada através do uso de uma variável que armazena o endereço do próximo elemento da lista. 
Você acertou! 
CORRETO. Basta usar uma variável do tipo ponteiro. 
 
E Cada elemento de uma lista encadeada só poderá armazenar dados do tipo numérico. Não é permitido o uso de dados do tipo caractere ou lógico, 
por exemplo. 
Qualquer tipo de dados é permitido. 
 
Questão 4/5 - Estrutura de Dados 
Assuma um vetor de dimensão 10 com dados numéricos e inteiros colocados na seguinte ordem: 
 
| 05 | 07 | 08 | 14 | 24 | 29 | 56 | 77 | 78 | 88 | 
Suponha que você deseja implementar um algoritmo de busca para localizar algum dado neste vetor já ordenado de maneira 
crescente. Você resolve testar a busca sequencial e a busca binária. 
Acerca destes algoritmos e analisando o vetor acima, assinale a alternativa CORRETA: 
Nota: 20.0 
 
A No algoritmo de busca sequencial, o valor 24 seria localizado na 6ª tentativa, se fizermos uma varredura da esquerda para a direita. 
Na 5ª tentativa. 
 
B No algoritmo de busca binária, o valor 24 seria localizado na 3ª tentativa. 
Na 1ª tentativa. 
 
C No algoritmo de busca sequencial, o valor 77 seria localizado mais rapidamente que se comparado com a busca binária. 
Binária se sairia mais rápida. 
 
D No algoritmo de busca sequencial, o valor 07 seria localizado mais rapidamente que se comparado com a busca binária. 
Você acertou! 
CORRETO. Levará menos iterações. 
 
E Em nenhum cenário de busca o algoritmo sequencial irá localizar o valor antes da busca binária. 
É possível que sim, a sequencial ache antes. Dependerá o valor buscado e onde ele se localizado no vetor. 
 
Questão 5/5 - Estrutura de Dados 
Uma função que implementa o algoritmo bubble sort pode ser vista abaixo. Todo o resto do algoritmo foi omitido para que 
analisemos somente o método de ordenação. No código, TAMANHOVETOR refere a um valor inteiro que corresponde a 
dimensão do vetor de dados. 
 
1 - void BubbleSort(int vet[]) { 
2 - int aux; 
3 - for (int n = 1; n <= TAMANHOVETOR; n++) { 
4 - for (int i = 0; i < (TAMANHOVETOR - 1); i++) { 
5 - if (vet[i] < vet[i + 1]) { 
6 - aux = vet[i]; 
7 - vet[i] = vet[i + 1]; 
8 - vet[i + 1] = aux; 
9 - } } } } 
Acerca deste algoritmo, assinale a alternativa CORRETA: 
Nota: 20.0 
 
A Na linha 5, o sinal de MENOR está incorreto. O algoritmo do bubble sort deve apresentar um sinal de MAIOR nesta linha. 
Tanto faz o sinal. Invertendo sinal inverte a forma como irá ordenar, o que não caracteriza um erro. 
 
B Não é possível substituir os laços de repetição do tipo PARA (FOR) por um laço do tipo REPITA (DO-WHILE). 
É possível implementar com qualquer laço de repetição. 
 
C Não é possível substituir os laços de repetição do tipo PARA (FOR) por um laço do tipo ENQUANTO (WHILE). 
É possível implementar com qualquer laço de repetição. 
 
D Na linha 3, seria possível fazer a variável n iniciar em zero e terminar em (TAMANHOVETOR-1) 
Você acertou! 
CORRETO. AULA 2 – TEMA 2 e conceitos básicos de programação e algoritmos. 
 
E A variável chamada de aux neste código tem como objetivo armazenar temporariamente o vetor de dados completo, para posteriormente ser 
ordenado. 
Ela serve para ajudar na troca individual de cada elemento. 
 
 
 
 
Apol 3... 
 
Questão 1/5 - Estrutura de Dados 
No terceiro assunto da disciplina estudamos a estrutura de dados do tipo lista encadeada. O código abaixo representa cada 
elemento de uma lista duplamente encadeada. 
 
1. registro ElementoDaLista_Dupla 
2. dado: inteiro 
3. prox: ElementoDaLista[->) 
4. ant: ElementoDaLista[->) 
5. fimregistro 
Acerca de lista encadeadas duplas, assinale a alternativa INCORRETA: 
Nota: 20.0 
 
A O código de criação da estrutura de uma lista encadeada dupla, conforme apresentado acima, é igual para uma circular e uma não circular. 
 
B O código acima representa uma lista não circular, pois uma lista dupla e circular deveria conter um ponteiro para o próximo elemento da lista, outro 
ponteiro para o elemento anterior da lista e também um ponteiro para o primeiro elemento da lista. 
Você acertou! 
Não existe o ponteiro para o primeiro elemento. Somente o ultimo elemento aponta de volta para o primeiro. 
 
C O código acima pode representar uma lista encadeada dupla não circular, pois conterá um ponteiro para o próximo elemento da lista e um para o 
elemento anterior da lista. 
 
D Se removermos a linha 4, transformamos a lista encadeada dupla em uma simples. 
 
E Um inserção no final da lista encadeada e circular, significaria fazer com o que o novo elemento inserido no final tivesse seu ponteiro para o próximo 
elemento apontando de volta para o início da lista encadeada. 
 
Questão 2/5 - 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: 20.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çãoentre 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 3/5 - Estrutura de Dados 
Na AULA 4 estudamos árvores binárias. 
Acerca de árvore binárias, seus conceitos e suas definições, Assinale a alternativa INCORRETA. 
Nota: 20.0 
 
A Uma característica das árvores binárias é que elas são uma estrutura de dados organizadas de maneira não linear, diferente de uma lista encadeada. 
 
B Uma árvore binária, quando aplicada para uso em algoritmos de busca de dados, deverá ter seus dados inseridos de uma maneira organizada para 
facilitar a busca. 
 
C O grau de um nó na árvore binária é calculado a partir de um número de ramificações que cada nó tem; 
 
D O grau de uma árvore binária pode ser sempre, e somente, 1 ou 2; 
Você acertou! 
Pode ser 0, 1 ou 2. AULA 4 – TEMA1; 
 
E Toda árvore contém um nó inicial denominado de nó raíz; 
 
Questão 4/5 - Estrutura de Dados 
Pilhas apresentam características de inserção e remoção na estrutura de dados seguindo a regra do primeiro que entra é o 
último que sai. Observe o código da pilha abaixo construída utilizando listas encadeadas. O código realiza a inserção de um 
novo elemento nesta pilha. 
 
1. NovoElemento->dado = numero 
2. se (Top == NULO) então 
3. NovoElemento->prox = NULO 
4. Senão 
5. NovoElemento->prox = Top 
6. fimse 
7. Top = NovoElemento 
Considerando que NovoElemento é um novo elemento que será inserido nesta pilha e top é o elemento que está no topo da 
pilha, assinale a alternativa CORRETA acerca de pilhas implementadas com listas encadeadas: 
Nota: 20.0 
 
A A linha 2 verifica se o topo da pilha está vazio. Caso esteja vazio, significa que não é possível inserir um novo elemento na pilha. 
É possível inserir, e a inserção se dá no próprio topo. 
 
B Se tivermos um só elemento na pilha, significa que a lista não terá um topo. 
Terá um topo e será o próprio único elemento. 
 
C Caso o topo não esteja vazio, fazemos o elemento do topo apontar para o novo elemento. 
O novo elemento apontará para o topo. Linha 5. 
 
D Na linha 7, o topo da pilha vira o novo elemento inserida, fazendo com que o antigo topo seja apagado. 
O antigo topo não é apagado, pois na linha 5 fazemos o novo elemento apontar para ele. 
 
E O topo da pilha é o único elemento que fica armazenado em uma variável conhecida pelo programa. Todos os outros elementos são acessados a 
partir dos ponteiros de referencia de cada elemento. 
Você acertou! 
Correto. Como este código está implementado com listas encadeadas, armazenamos somente o primeiro elemento. 
 
Questão 5/5 - Estrutura de Dados 
No terceiro assunto da disciplina estudamos a estrutura de dados do tipo lista encadeada. O código abaixo representa a inserção 
em uma posição específica da lista encadeada simples. 
 
1. NovoElemento->dado = numero 
2. se (posicao == 0) então 
3. Head = NovoElemento 
4. Head->prox = NULO 
5. Senão 
6. ElementoVarredura = Head 
7. para i de 0 até posicao faça 
8. ElementoVarredura = ElementoVarredura->prox 
9. Fimpara 
10. ElementoAuxiliar = ElementoVarredura->prox 
11. ElementoVarredura->prox = NovoElemento 
12. NovoElemento->prox = ElementoAuxiliar 
13. Fimse 
Considerando que NovoElemento é um novo elemento que será inserido nesta lista, ElementoVarredura é uma variável que 
servirá para localizar o local de inserção, ElementoAuxiliar é uma variável temporária para auxiliar na inserção do dado, Head 
caracteriza o primeiro elemento da lista e prox é o ponteiro para o próximo elemento da lista. Assinale a alternativa INCORRETA 
sobre este algoritmo. 
Nota: 20.0 
 
A Nas linhas 7 a 9 temos o laço de repetição que localiza a posição em que o elemento será inserido. 
 
B Na linha 8, a variável ElementoVarredura salta de elemento em elemento da lista, sempre utilizando como referencia o ponteiro para o próximo 
elemento. 
 
C Nas linhas 10, 11 e 12 fazemos uma troca entre 2 valores da lista encadeada utilizando uma variável auxiliar. 
Você acertou! 
Errado, pois não temos uma troca, mas sim a inserção do novo elemento. 
 
D Na linha 10 uma variável auxiliar armazena temporariamente o elemento subsequente ao da posição desejada para inserção. 
 
E Na linha 12, o novo elemento, agora já inserido na respectiva posição da lista, aponta para o elemento armazenado na variável auxiliar, que 
corresponde ao elemento subsequente ao da posição inserida. 
 
 
Apol 4... 
 
Questão 1/5 - Estrutura de Dados 
Na AULA 5 estudamos conceitos de grafos. 
Acerca de grafos, seus conceitos e suas definições, assinale a alternativa INCORRETA. 
Nota: 20.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/5 - 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: 20.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/5 - 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: 0.0 
 
A O grau do vértice V1 é 3. 
O grau é 4. Pois é o número de arestas incidentes. 
 
B Todos os vérticesdeste 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. 
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 4/5 - 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: 20.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 5/5 - 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: 0.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. 
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. 
 
 
Apol 5... 
 
Questão 1/5 - 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: 20.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 2/5 - 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: 20.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 3/5 - 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. 
Nota: 20.0 
 
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. 
Você acertou! 
O tempo de busca com endereçamento direto é atrelado ao algoritmo de busca adotado. AULA 6 – TEMA 1. 
 
E Palavra-chave em uma tabela hash é aquele dado utilizado no cálculo de uma posição utilizando um algoritmo de hash. 
 
Questão 4/5 - 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 profundidade 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 5/5 - 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: 
Nota: 20.0 
 
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. 
Você acertou! 
O cálculo de d não é o dobro. A equação é apresentada na página 20 da AULA 6. 
 
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.