Baixe o app para aproveitar ainda mais
Prévia do material em texto
Exercício de Estrutura de Dados - Exercício de Fixação 3 - Tentativa 2 de 3 Questão 1 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. 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 • ( )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. Questão 2 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 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 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 – V Resposta correta 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 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”. https://storage.googleapis.com/painel-docente-prod/questions_db/question/111712/1621820630/image.png https://storage.googleapis.com/painel-docente-prod/questions_db/question/111712/1621820630/image.png https://firequiz.fael.edu.br/false https://firequiz.fael.edu.br/false https://storage.googleapis.com/painel-docente-prod/questions_db/question/111712/1621820651/image.png https://storage.googleapis.com/painel-docente-prod/questions_db/question/111712/1621820651/image.png https://storage.googleapis.com/painel-docente-prod/questions_db/question/111712/1621820630/image.png https://storage.googleapis.com/painel-docente-prod/questions_db/question/111712/1621820651/image.png A sequência correta é: A - V – V – F – F – F B - V – F – V – F – F C - V – F – F – F – V Resposta correta D - F – V – V – F – V E - F – V – F – V – V Questão 4 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 Resposta correta 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. 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 categoriaretrata 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. Resposta correta C - II – I – III – IV. D - II – I – IV – III. E - III – II – IV – I. 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 }. 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 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 – V Resposta correta C - V – V – F – V – F D - F – V – V – V – F E - F – F – V – F – V Questão 7 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, apenas Resposta correta D - I e III, apenas E - I e II, apenas 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. Resposta 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. 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 • ( )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 – 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 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 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 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 – V Resposta correta E - F – V – F – V – V 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
Compartilhar