Exercício de Estrutura de Dados - Exercício de Fixação 3-3

Prévia do material em texto

Exercício de Estrutura de Dados - Exercício de 
Fixação 3 - Tentativa 3 de 3 
Questão 1 de 10 
A classificação ou ordenação de vetores aborda técnicas utilizadas para classificar o 
conteúdo de um vetor em ordem crescente ou decrescente, numérica ou alfabeticamente. 
Existem diversos algoritmos prontos e comprovados para realizar tal tarefa. 
 
Em vetores pequenos, a pesquisa ou busca de um elemento é uma atividade com pouco 
custo computacional. Porém quando se trabalha com grandes quantidades de dados, fica 
difícil a localização de um determinado elemento de forma rápida com abordagens 
simplistas. 
 
A pesquisa _______________ é bastante simples: verifica os valores em sequência. Por isto é um 
processo bastante lento, não sendo indicado para _______________ volumes de dados; porém 
pode vir a ser eficiente quando o conteúdo do vetor estiver desordenado. 
 
O método de pesquisa _______________ em vetor é mais rápido do que o anterior, porém exige 
que o vetor esteja previamente _______________ . 
 
O algoritmo de ordenação do método _______________ aplica a seguinte lógica: uma vez 
comparados dois valores adjacentes no vetor, se eles estiverem na ordem desejada, são 
mantidos em seus lugares e, se não estiverem, são invertidos. A execução sucessiva deste 
processo faz com que o vetor fique ordenado. 
 
O método de ordenação por _______________ tem uma proposta diferente. O ciclo inicia no 
segundo elemento. O elemento é retirado do arranjo de dados, fazendo uso de uma posição 
auxiliar do vetor, e inserido em seu lugar definitivo, por meio da pesquisa de sua localização 
correta e do deslocamento dos outros elementos do arranjo. 
 
Identifique a sequência correta das alternativas abaixo: 
A - sequencial – grandes – binária – desordenado – inserção – bolha. 
B - binária – pequenas – sequencial – ordenado – bolha – inserção. 
C - binária – grandes – sequencial – desordenado – inserção – bolha. 
D - sequencial – grandes – binária – ordenado – bolha – inserção. Resposta correta 
E - sequencial – pequenas – binária – ordenado – bolha – inserção. 
 
Questão 2 de 10 
O conceito de grafos vem de uma área da Matemática que se dedica a estudar as relações 
entre entidades (objetos) que possuem características relevantes. Para trabalharmos com 
grafos, precisamos conhecer as estruturas matrizes e listas, pois serão muito uteis na 
construção e manipulação de grafos pelos algoritmos. 
 
Um grafo é composto por um conjunto de nós e arestas. Um nó, vértice ou ponto representa uma 
entidade no grafo, que pode ser por exemplo, uma fruta, uma cidade, uma pessoa. Uma aresta, arco 
ou linha é uma relação que liga dois nós, que pode ser uma estrada ligando cidades, ou um grau de 
parentesco ligando pessoas, por exemplo. Uma aresta é representada por um par ordenado de nós. 
 
Seja o seguinte grafo hipotético (Imagem1): 
image.png 20.32 KB 
E a seguinte matriz de adjacência (Imagem2) 
image.png 11.36 KB 
 
 
Sendo assim, analise as sentenças a seguir e assinale V se a sentença for verdadeira e F se a 
sentença for falsa: 
 
 
• ( )A lista de adjacência do nó SP é { RJ, MG, PR, GO }. 
• ( )A lista de adjacência do nó GO é { MG, PR }. 
• ( )A matriz de adjacência apresentada na Imagem2 representa o grafo da Imagem1. 
• ( )A menor distancia entre GO e PR é 1200. 
• ( )A lista de adjacência do nó MG tem 3 elementos. 
 
 
A sequência correta é: 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111711/1621819766/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111711/1621819766/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111711/1621819772/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111711/1621819772/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111711/1621819766/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111711/1621819772/image.png
A - V – F – V – F – V 
B - V – F – F – F – V Resposta correta 
C - V – V – F – V – F 
D - F – V – V – V – F 
E - F – F – V – F – V 
 
Questão 3 de 10 
Árvores são estruturas de dados que não obedecem a uma sequencia linear e são uma das 
mais importantes estruturas de dados. A árvore combina as vantagens das estruturas de 
dados vetor ordenado e lista encadeada em uma só estrutura, permitindo a busca de 
elementos de forma rápida como em um vetor ordenado; e a inserção e exclusão de itens 
como em uma lista encadeada. A forma de organização desta estrutura permite inúmeras 
aplicações na solução de problemas computacionais. 
 
Considerando os diferentes tipos de árvores, associe o tipo da árvore com a definição que 
melhor a representa. 
 
 
Relacione o segundo grupo com os enumerados no primeiro grupo. 
 
 
I. Árvore binária 
II. Árvore AVL 
III. Árvore rubro-negra 
IV. Árvore B+ 
V. Árvore Patrícia 
 
 
( )árvore de busca que se preocupa com o balanceamento; o balanceamento é feito com 
base na altura dos nós; o balanceamento ocorre por rotação, a fim de preservar a ordenação 
da árvore. 
( )árvore cuja principal aplicação é no tratamento de variáveis com conteúdo longo, como 
palavras e frases. 
( )árvore que, se não for vazia, possui um nó inicial, chamado raiz, com ponteiros para duas 
estruturas diferentes, denominadas subárvore da esquerda e subárvore da direita. 
( )árvore que tem esse nome porque cada nó de sua estrutura possui um atributo de cor, 
vermelho ou preto. 
( )árvore projetada para funcionar em memória secundária, como um disco rígido, por 
exemplo, e que são bastante utilizadas em sistemas de banco de dados. 
 
 
Marque a alternativa que tem a ordem correta de numeração do segundo grupo: 
A - I – II – III – V – IV. 
B - II – IV – III – I – V. 
C - II – V – I – III – IV. Resposta correta 
D - III – II – I – V – IV. 
E - III – V – I – IV – II. 
 
Questão 4 de 10 
A complexidade de um algoritmo está relacionada ao grau de esforço envolvido na solução 
de determinado problema. De uma forma simples, complexidade de algoritmos é a 
quantidade de trabalho necessária para executar uma tarefa, dando uma ideia do esforço 
computacional demandado pelo algoritmo implementado. Este trabalho envolve as funções 
fundamentais que o algoritmo é capaz de fazer, o volume de dados processado e a maneira 
como o algoritmo chega ao resultado. Entre as funções que um algoritmo é capaz de fazer, 
podemos citar o acesso aos dados, a inserção de novos dados, a remoção de dados, que são 
exemplos de funções bastante comuns na computação. Já o volume de dados refere-se à 
quantidade de elementos que são processados. 
 
O crescimento assintótico representa a velocidade com que uma função tende ao infinito. Existem 
diferentes formas de se fazer análise assintótica de um algoritmo. Pode ser O-grande, Teta-grande e 
Ômega-grande. A mais conhecida, ou mais utilizada, é a chamada de “Notação O-grande” (Big-O). O 
Big-O é uma maneira de dar um limite superior para o tempo gasto por um algoritmo. 
 
Associe a notação Big-O (primeiro grupo) com as respectivas funções de complexidade 
(segundo grupo): 
 
1. O(log n) 
2. O(n) 
3. O(n^2) 
4. O(n^3) 
5. O(n!) 
 
A. image.png 1.14 KB 
B. image.png 1.46 KB 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888179/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888179/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888188/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888188/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888179/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888188/image.png
C. image.png 1.08 KBD. image.png 1.58 KB 
E. image.png 1.22 KB 
 
Marque a alternativa que tem a ordem correta de associação de numeração (podem haver 
repetições): 
A - 1–A; 2–B; 3–C; 4–D; 5–E. 
B - 2–A; 4–B; 3–C; 2–D; 3–E. 
C - 3–A; 1–B; 4–C; 1–D; 3–E. 
D - 3–A; 4–B; 5–C; 3–D; 2–E. Resposta correta 
E - 5–A; 1–B; 4–C; 2–D; 3–E. 
 
Questão 5 de 10 
A estrutura árvore combina as vantagens das estruturas de dados vetor ordenado e lista 
encadeada em uma só estrutura: permite a busca de elementos de forma rápida como em 
um vetor ordenado; e a inserção e exclusão de itens também de forma rápida, como em uma 
lista encadeada. A principal característica das árvores é que os itens que as compõem, 
chamados de nós, são dispostos de forma hierárquica, respeitando a topologia em árvore. 
Desta forma, ao invés dos nós se conectarem em sequência, eles aparecem acima ou abaixo 
dos outros elementos da árvore. 
 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888194/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888194/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888200/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888200/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888206/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888206/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888194/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888200/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111718/1621888206/image.png
Considerando o contexto de Árvores Binárias, analise os seguintes algoritmos: 
image.png 50.73 KBAssocie cada algoritmo com o método 
de percurso que ele implementa: 
A - Alg1 – percurso Pré-ordem; Alg2 – Percurso Em-ordem; Alg3 – percurso Pós-ordem Resposta 
correta 
B - Alg1 – percurso Pré-ordem; Alg3 – Percurso Em-ordem; Alg2 – percurso Pós-ordem 
C - Alg2 – percurso Pré-ordem; Alg1 – Percurso Em-ordem; Alg3 – percurso Pós-ordem 
D - Alg2 – percurso Pré-ordem; Alg3 – Percurso Em-ordem; Alg1 – percurso Pós-ordem 
E - Alg3 – percurso Pré-ordem; Alg2 – Percurso Em-ordem; Alg1 – percurso Pós-ordem 
 
Questão 6 de 10 
A estrutura árvore combina as vantagens das estruturas de dados vetor ordenado e lista 
encadeada em uma só estrutura: permite a busca de elementos de forma rápida como em 
um vetor ordenado; e a inserção e exclusão de itens também de forma rápida, como em uma 
lista encadeada. A principal característica das árvores é que os itens que as compõem, 
chamados de nós, são dispostos de forma hierárquica, respeitando a topologia em árvore. 
Desta forma, ao invés dos nós se conectarem em sequência, eles aparecem acima ou abaixo 
dos outros elementos da árvore. 
 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111709/1621818811/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111709/1621818811/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111709/1621818811/image.png
Seja a seguinte árvore: 
image.png 20.21 KB 
Sobre a árvore acima, responda as seguintes questões. 
 
 
Sendo assim, analise as sentenças a seguir e assinale V se a sentença for verdadeira e F se a 
sentença for falsa: 
 
 
• ( )O nó B é pai do nó A. 
• ( )O nó A é o nó raiz da árvore. 
• ( )Os nós D e F são nós filhos do nó B. 
• ( )Os nós G e H são nós folhas. 
• ( )Um percurso em pré-ordem nesta árvore resulta na seguinte sequencia: A, B, C, D, E, F, G, H, 
I. 
 
 
A sequência correta é: 
A - V – F – V – F – F. 
B - V – V – F – F – V. 
C - F – V – V – V – F. Resposta correta 
D - F – V – F – V – V. 
E - F – F – V – V – F. 
 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111708/1621818422/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111708/1621818422/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111708/1621818422/image.png
Questão 7 de 10 
A classificação ou ordenação de vetores aborda técnicas utilizadas para classificar o 
conteúdo de um vetor em ordem crescente ou decrescente, numérica ou alfabeticamente. 
Existem diversos algoritmos prontos e comprovados para realizar tal tarefa. 
 
Analise o seguinte algoritmo de ordenação: 
image.png 40.48 KB 
 
 
Sendo assim, analise as sentenças a seguir e assinale V se a sentença for verdadeira e F se a 
sentença for falsa: 
 
 
• ( )LIM representa o tamanho do vetor. 
• ( )O número de trocas entre elementos é maior que o número de comparações entre 
elementos. 
• ( )Nas linhas 10 até 12 é feita a troca entre 2 elementos do vetor. 
• ( )O contador J é utilizado apenas para encontrar o menor elemento do vetor. 
• ( )Se o vetor tiver 30 elementos, serão feitas apenas 30 trocas de valores (no máximo). 
 
 
A sequência correta é: 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111716/1621886347/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111716/1621886347/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111716/1621886347/image.png
A - V – F – V – V – F 
B - V – V – F – F – V 
C - V – F – F – V – V Resposta correta 
D - F – F – V – F – V 
E - F – V – F – V – F 
 
Questão 8 de 10 
Em vetores pequenos, a pesquisa ou busca de um elemento é uma atividade com pouco 
custo computacional. Porém quando se trabalha com grandes quantidades de dados, fica 
difícil a localização de um determinado elemento de forma rápida com abordagens 
simplistas. 
 
Analise o seguinte algoritmo de pesquisa: 
image.png 33.49 KB 
 
 
Sendo assim, analise as sentenças a seguir e assinale V se a sentença for verdadeira e F se a 
sentença for falsa: 
 
 
• ( )A variável OK é um status que marca se o elemento CHAVE foi encontrado. 
• ( )O algoritmo procura o elemento CHAVE, toda vez, da posição 1 até a posição 100 do vetor, 
indo a procura sempre até a posição 100. 
• ( )Nas linhas 9 até 11 é feita a verificação se o elemento CHAVE está no vetor. 
• ( )CHAVE pode ser encontrada várias vezes no vetor. 
• ( )Quando OK se torna 1, o algoritmo para. 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111715/1621886106/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111715/1621886106/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111715/1621886106/image.png
 
 
A sequência correta é: 
A - V – F – V – F – V Resposta correta 
B - V – V – F – F – V 
C - V – F – F – V – V 
D - F – F – V – F – V 
E - F – V – F – V – F 
 
Questão 9 de 10 
Percorrer um grafo em algoritmos significa visitar todos os vértices do grafo. A busca em 
profundidade, num contexto de árvore, visita os nós-filhos antes de visitar os nós-irmãos. Já a 
busca em largura, num contexto de árvores, visita os nós-irmãos antes de visitar os nós-
filhos. No contexto de grafos, visita-se os vértices adjacentes em uma ordem particular para 
implementar-se diferentes buscas. 
 
Observe o seguinte algoritmo: 
image.png 40.21 KB 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111713/1621821012/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111713/1621821012/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111713/1621821012/image.png
E considere o seguinte grafo como exemplo (Imagem1): 
image.png 9.95 KB 
 
 
Sendo assim, analise as sentenças a seguir e assinale V se a sentença for verdadeira e F se a 
sentença for falsa: 
 
 
• ( )O algoritmo desconhecidoexecuta um “percurso em profundidade” nos nós de um grafo. 
• ( )O algoritmo desconhecido executa um “percurso em largura” nos nós de um grafo. 
• ( )T contém sempre o valor que está no inicio da fila F. 
• ( )Um nó W poderá ser visitado mais do que uma vez. 
• ( )Se o grafo de entrada for o da Imagem1 então a ordem em que os nós serão “escritos” será: 
“A,B,D,C,E,F”. 
 
 
A sequência correta é: 
A - V – V – F – F – F 
B - V – F – V – F – F 
C - V – F – F – F – V 
D - F – V – V – F – V Resposta correta 
E - F – V – F – V – V 
 
Questão 10 de 10 
O conceito de grafos vem de uma área da Matemática que se dedica a estudar as relações 
entre entidades (objetos) que possuem características relevantes. Para trabalharmos com 
grafos, precisamos conhecer as estruturas matrizes e listas, pois serão muito uteis na 
construção e manipulação de grafos pelos algoritmos. 
 
Um grafo é composto por um conjunto de nós e arestas. Um nó, vértice ou ponto representa 
uma entidade no grafo, que pode ser por exemplo, uma fruta, uma cidade, uma pessoa. Uma 
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111713/1621821016/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111713/1621821016/image.png
https://storage.googleapis.com/painel-docente-prod/questions_db/question/111713/1621821016/image.png
aresta, arco ou linha é uma relação que liga dois nós, que pode ser uma estrada ligando 
cidades, ou um grau de parentesco ligando pessoas, por exemplo. Uma aresta é 
representada por um par ordenado de nós. 
 
O _______________ de um nó é o número de arestas ligadas a este nó. 
 
A _______________ de um grafo é dada pela cardinalidade do conjunto de vértices do grafo, 
isto é, o total de vértices (nós) que o grafo tem. 
 
O _______________ é uma sequência de nós interligados, ligando um nó (origem) a um outro 
nó (destino). 
 
O _______________ é um caminho cuja origem é igual ao destino e o comprimento é maior ou 
igual a 2. Já um _______________ é um caminho com origem e destino iguais e comprimento 1. 
 
Identifique a sequência correta das alternativas abaixo: 
A - grau – ordem – caminho – laço – ciclo 
B - ordem – grau – caminho – ciclo – laço 
C - caminho – grau – ordem – laço – ciclo 
D - grau – ordem – ciclo – laço – caminho 
E - grau – ordem – caminho – ciclo – laço Resposta correta