Exercício de Estrutura de Dados

Prévia do material em texto

Exercício de Estrutura de Dados - Exercício de Fixação 3 - Tentativa 1 de 3
Questão 1 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.
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 cancelRespondida
C - caminho  – grau – ordem – laço – ciclo 
D - grau – ordem – ciclo – laço – caminho 
E - grau – ordem – caminho – ciclo – laço check_circleResposta correta
Questão 2 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 43.61 KB
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 desconhecido executa 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 topo da pilha P.
· (   )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,C,D,E,F”.
A sequência correta é:
A - V – V – F – F – F 
B - V – F – V – F – F 
C - V – F – F – F – Vcheck_circleResposta correta
D - F – V – V – F – V
E - F – V – F – V – V 
Questão 3 de 10
Uma árvore consiste de nós conectados entre si. O nó  _______________ de uma árvore é o nó que se encontra na região mais alta da árvore em relação aos outros nós, pois na computação uma árvore é representada de  _______________ . Uma árvore contém somente um nó raiz. Qualquer nó, exceto a raiz, tem exatamente uma linha indo para cima até outro nó. O nó acima dele é chamado de  _______________ do nó. Qualquer nó pode ter uma ou mais linhas indo para baixo até outros nós. Estes nós abaixo de um nó são chamados de seus nós  _______________ . Um nó que não tem filhos é chamado de um nó  _______________ . Só pode haver uma raiz em uma árvore, mas pode haver muitas folhas.
Identifique a sequência correta das alternativas abaixo:
A - raiz – cabeça para baixo – pai – filhos – folha.check_circleResposta correta
B - raiz – cabeça para baixo – filho – pais – folha.
C - folha – cabeça para cima – pai – filhos – raiz.
D - folha – cabeça para baixo – filho – pais – raiz.cancelRespondida
E - pai – cabeça para cima – raiz – folhas – filho.
Questão 4 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
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 desconhecido executa 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 cancelRespondida
C - V – F – F – F – V
D - F – V – V – F – Vcheck_circleResposta correta
E - F – V – F – V – V
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.
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.check_circleResposta correta
D - F – V – F – V – V.cancelRespondida
E - F – F – V – V – F.
Questão 6 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 é:
A - V – F – V – V – F
B - V – V – F – F – V
C - V – F – F – V – Vcheck_circleResposta correta
D - F – F – V – F – V
E - F – V – F – V – F
Questão 7 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 é feitaa 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.
A sequência correta é:
A - V – F – V – F – Vcheck_circleResposta correta
B - V – V – F – F – V
C - V – F – F – V – V
D - F – F – V – F – VcancelRespondida
E - F – V – F – V – F
Questão 8 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. 
Uma forma direta de calcular a complexidade de um algoritmo seria encontrando a fórmula, T(N), que resulte num número aproximado de operações realizadas pelo algoritmo para chegar ao resultado.
Sobre o cálculo de complexidade de um algoritmo, associe os seguintes termos com suas definições:
Relacione o segundo grupo com os enumerados no primeiro grupo.
I. Pior caso
II. Caso médio
III. Melhor caso
IV. Notação Big-O
(   )É caracterizado por entradas que resultam em um maior crescimento do número de operações conforme se aumenta o valor de “N”.
(   )É caracterizado por entradas que resultam em um menor crescimento do número de operações com o aumento do valor de “N”.
(   )É quando se considera todas as entradas possíveis e as respectivas probabilidades de ocorrência. Esta categoria retrata o comportamento médio do algoritmo.
(   )Está relacionado com a complexidade assintótica de um algoritmo, focando no limite superior consumido pelo mesmo.
Marque a alternativa que tem a ordem correta de numeração do segundo grupo:
A - I – II – III – IV. 
B - I – III – II – IV.check_circleResposta correta
C - II – I – III – IV.cancelRespondida
D - II – I – IV – III.
E - III – II – IV – I.
Questão 9 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.cancelRespondida
D - sequencial – grandes – binária – ordenado – bolha – inserção.check_circleResposta correta
E - sequencial – pequenas – binária – ordenado – bolha – inserção.
Questão 10 de 10
Uma forma direta de calcular a complexidade de um algoritmo seria encontrando a fórmula que resulte no número exato de operações realizadas pelo algoritmo para chegar ao resultado.
Suponha que dois algoritmos distintos para um mesmo problema possuam as seguintes fórmulas de complexidade:
image.png 9.43 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:
· (   )Em T(N), o termo linear (15*N) será dominado pelo termo quadrático (5*N^2) para qualquer situação em que N >= 4.
· (   )Em T(N), quando N > 28, a contribuição do termo linear (15*N) será de menos de 10% do total.
· (   )A partir de N=15, S(N) é mais eficiente que T(N), pois dá resultados menores.
· (   )Para valores pequenos de N, como N < 20 a função T(N) é mais eficiente que S(N).
· (   )Em S(N), a partir de N>20, a contribuição do termo linear (100*N) será maior que a do termo constante (500).
A sequência correta é:
A - V – V – F – V – Fcheck_circleResposta correta
B - V – V – V – F – F 
C - V – F – F – V – V 
D - F – F – V – F – V cancelRespondida
E - F – V – F – V – F