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

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
As estruturas de dados árvores são de suma importância na computação e permitiram que algoritmos complexos de geração de conhecimento fossem criados. Em relação a estrutura árvore é possível dizer que:
I. O número de sub árvores de um nodo denomina-se grau.
II. Uma árvore binária não pode ser nula.
III. Toda árvore, inclusive as nulas, possui um nodo especial denominado raiz.
Assinale a alternativa correta:
A. A - III, apenas
B. B - I, II e III
C. C - I, apenascheck_circleResposta correta
D. D - I e III, apenascancelRespondida
E. E - I e II, apenas
Questão 2 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 – F check_circle Resposta correta
B - V – V – V – F – F cancel Respondida
C - V – F – F – V – V 
D - F – F – V – F – V 
E - F – V – F – V – F
Questão 3 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 
C - V – F – F – F – V
D - F – V – V – F – Vcheck_circleResposta correta
E - F – V – F – V – V
Questão 4 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.
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-ordemcheck_circleResposta correta
B - Alg1 – percurso Pré-ordem; Alg3 – Percurso Em-ordem; Alg2 – percurso Pós-ordemcancelRespondida
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 5 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
C.image.png 1.08 KB
D.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.check_circleResposta correta
E - 5–A; 1–B; 4–C; 2–D; 3–E.cancelRespondida
Questão 6 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 é:
A - V – F – V – F – V 
B - V – F – F – F – Vcheck_circleResposta correta
C - V – V – F – V – F 
D - F – V – V – V – F 
E - F – F – V – F – V 
Questão 7 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óticorepresenta 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.05 KB
B.image.png 1.38 KB
C.image.png 1.57 KB
D.image.png 1.2 KB
E.image.png 1.29 KB
Marque a alternativa que tem a ordem correta de numeração do segundo grupo (podem haver repetições):
A - 1–A; 2–B; 3–C; 4–D; 5–E.
B - 2–A; 1–B; 3–C; 2–D; 3–E.
C - 2–A; 3–B; 4–C; 1–D; 5–E.
D - 3–A; 1–B; 4–C; 2–D; 3–E.
E - 5–A; 1–B; 4–C; 2–D; 3–E.check_circleResposta correta
Questão 8 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.
E - pai – cabeça para cima – raiz – folhas – filho.
Questão 9 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.
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 10 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.check_circleResposta correta
E - sequencial – pequenas – binária – ordenado – bolha – inserção.
Parte superior do formulário
Tentativa 2 de 3
Questão 1 de 10
Uma estrutura de árvore combinada como vantagens das estruturas de dados em uma única 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. Os itens principais que são definidos como árvores, são chamados de árvores, que são definidos como hierárquicos. Desta forma, ao invés de nós se conectarem em sequência, eles aparecem acima ou abaixo dos outros elementos da árvore.
Seja a seguinte árvore:
imagem.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 para verdadeira e F se a sentença para 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 sequência: 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.cancelarRespondida
E - F - F - V - V - F.
Parte inferior do formulário
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.
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 cancelRespondida
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 check_circleResposta correta
Questão 3 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érticesadjacentes 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 – VcancelRespondida
E - F – V – F – V – V 
Questão 4 de 10
As estruturas de dados árvores são de suma importância na computação e permitiram que algoritmos complexos de geração de conhecimento fossem criados. Em relação a estrutura árvore é possível dizer que:
I. O número de sub árvores de um nodo denomina-se grau.
II. Uma árvore binária não pode ser nula.
III. Toda árvore, inclusive as nulas, possui um nodo especial denominado raiz.
Assinale a alternativa correta:
A - III, apenas
B - I, II e III
C - I, apenascheck_circleResposta correta
D - I e III, apenas
E - I e II, apenas
Questão 5 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.check_circleResposta correta
E - sequencial – pequenas – binária – ordenado – bolha – inserção.
Questão 6 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 
C - V – F – F – F – V
D - F – V – V – F – Vcheck_circleResposta correta
E - F – V – F – V – V
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 é:
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 – FcancelRespondida
Questão 8 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.
E - pai – cabeça para cima – raiz – folhas – filho.
Questão 9 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
C.image.png1.08 KB
D.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.check_circleResposta correta
E - 5–A; 1–B; 4–C; 2–D; 3–E.
Exercício de Estrutura de Dados - Exercício de Fixação 3 - Tentativa 3 de 3
Questão 1 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
C.image.png 1.08 KB
D.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.check_circleResposta correta
E - 5–A; 1–B; 4–C; 2–D; 3–E.
Questão 2 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.
D - II – I – IV – III.
E - III – II – IV – I.cancelRespondida
Questão 3 de 10
Uma estrutura de árvore combinada como vantagens das estruturas de dados em uma única 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. Os itens principais que são definidos como árvores, são chamados de árvores, que são definidos como hierárquicos. Desta forma, ao invés de nós se conectarem em sequência, eles aparecem acima ou abaixo dos outros elementos da árvore.
Seja a seguinte árvore:
imagem.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 para verdadeira e F se a sentença para 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 sequência: 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.
E - F - F - V - V - F.
Questão 4 de 10
As estruturas de dados árvores são de suma importância na computação e permitiram que algoritmos complexos de geração de conhecimento fossem criados. Em relação a estrutura árvore é possível dizer que:
I. O número de sub árvores de um nodo denomina-se grau.
II. Uma árvore binária não pode ser nula.
III. Toda árvore, inclusive as nulas, possui um nodo especial denominado raiz.
Assinale a alternativa correta:
A - III, apenas
B - I, II e III
C - I, apenascheck_circleResposta correta
D - I e III, apenas
E - I e II, apenas
Questão 5 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.05 KB
B.image.png 1.38 KB
C.image.png 1.57 KB
D.image.png 1.2 KB
E.image.png 1.29 KB
Marque a alternativa que tem a ordem correta de numeração do segundo grupo (podem haver repetições):
A - 1–A; 2–B; 3–C; 4–D; 5–E.
B - 2–A; 1–B; 3–C; 2–D; 3–E.
C - 2–A; 3–B; 4–C; 1–D; 5–E.
D - 3–A; 1–B; 4–C; 2–D; 3–E.
E - 5–A; 1–B; 4–C; 2–D; 3–E.check_circleResposta correta
Questão 6 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 executaum “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 – VcancelRespondida
E - F – V – F – V – V 
Questão 7 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 
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 8 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 9 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 é:
A - V – F – V – F – V 
B - V – F – F – F – Vcheck_circleResposta correta
C - V – V – F – V – F 
D - F – V – V – V – F 
E - F – F – V – F – V 
Questão 10 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 
C - V – F – F – F – VcancelRespondida
D - F – V – V – F – Vcheck_circleResposta correta
E - F – V – F – V – V