Questões de Programação III

Prévia do material em texto

Questão 1/10 Programação III Ler em voz alta "Visto de forma abstrata, um grafo Ge' simplesmente um conjunto V de ve rtices e uma colec a~o de pares de ve rtices de V, chamados de arestas. Assim, um grafo uma forma de representar conexo~es ou relac,o~es entre pares de objetos de algum conjunto V." GOODRICH, Michael T.; Estruturas de Dados e Algoritmos em Grupo A, 2013. pag 613 Abaixo temos uma imagem de um grafo. V₈ V₄ V 6 V₅ Acerca do grafo acima, considerando 0 texto base e 0 conteúdo visto em aula, assinale a alternativa CORRETA. A grafo contém arestas múltiplas, pois temos mais de um caminho para sair de V1 e chegar em V9, por exemplo o grau do vértice V9 é 3. Todos os vértices deste grafo têm 0 mesmo grau. D Este grafo é do tipo completo. E grau do vértice V4 é 3. Você assinalou essa alternativa (E) Questão 2/10 Programação III Ler em voz alta "Matematicamente, um grafo é um conjunto V de vértices e um conjunto E de arestas, de modo que cada aresta em E conecta dois dos vértices em V. termo nó também é usado aqui como sinônimo de vértice. Vértices e arestas podem ser rotulados ou não rotulados. Quando as arestas são rotuladas com números, números podem ser vistos como pesos, e 0 grafo é considerado um grafo ponderado." LAMBERT, Kenneth Fundamentos de Python: estruturas de dados. Ed. Cengage Learning Brasil, 2022. pag 356 Observe figura abaixo: A 2 E 3 2 1 1 D Considerando texto base ea figura acima, são feitas as seguintes afirmativas: 5 vértices e 0 conjunto de vértices V é (A,B,C,D,E) II. Temos 5 arestas e 0 conjunto de arestas E é (1,2,3) III. Grafo é um grafo dirigido pois possui números nas arestas Estão corretas as afirmativas: A apenas Você assinalou essa alternativa (A) apenas C apenas D e III apenas E III apenasQuestão 3/10 - Programação III Ler A definição de uma boa função hash é fundamental para termos uma tabela hash com um bom desempenho. Acerca de funções hash, são feitas as seguintes afirmativas: I. Uma função hash necessita inserir dados que minimizem 0 número de colisões, reduzindo também 0 tempo gasto resolvendo colisões e reavendo 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. III. A função hash que utiliza 0 método da divisão só pode ser aplicado para palavras-chave do tipo numérica. Estão corretas as afirmativas: A somente. Você assinalou essa alternativa (A) somente. C III D III somente E III. Questão 4/10 Programação III Observe 0 código de consulta em ordem na árvore, assumindo que os dados cadastrados são do tipo inteiro. 1 def emOrdem(self,Ist): 2 if (self.esquerda): 3 4 5 if(self direita): 6 7 return Ist Acerca de consulta em árvore e do código acima, alternativa INCORRETA: A Retirando a linha 4 e colocando logo após a definição da função (inserindo portanto na linha 2), a consulta em pré ordem aconteceria A função deve receber como parâmetro uma lista, representada por Ist A consulta em pos ordem ocorrerá se invertermos 0 bloco do segundo if pelo primeiro if Você assinalou essa alternativa (C) D A linha 2 verifica se a variável esquerda é diferente de None/Null. E A função retorna uma lista ordenada Questão 5/10 - Programação III Ler em voz alta Dois matemáticos russos, G. M. e E.M. Landis, publicaram em 1962 um artigo que descreve um algoritmo para manter equilíbrio global de uma árvore de busca binária. Seu algoritmo controla a diferença de altura das subárvores. À medida que itens são adicionados à árvore (ou removidos dela), 0 fator de balanceamento** (isto é, a diferença entre as alturas das subárvores) de cada subárvore do ponto de inserção até a raiz é mantido Koffman, Elliot, B. e Paul A. T. Wolfgang. Objetos, Abstração, Estrutura de Dados e Projeto Usando Disponível em: Minha Biblioteca, Grupo GEN, 2008. No caso de uma arvore AVL balanceada, 0 fator de balanceamento sempre será: A menor ou igual a 2. B igual ou igual -1, 0 ou 1. Você assinalou essa alternativa D maior que 1. E igual 1.Questão 6/10 - Programação III Ler em voz alta após hash, duas chaves podem ser mapeadas para a mesma posição. Chamamos essa situação de colisão. Felizmente, existem técnicas eficazes para resolver 0 conflito criado por colisões." CORMEN, Algoritmos Teoria e Prática Grupo GEN, 2012. ISBN Disponível em: A maneira como é tratada as colisões depende muito do tipo de Acerca dos tipos de endereçamento, assinale a alternativa CORRETA: A endereçamento aberto é mais empregado quando a quantidade de palavras-chaves é bastante grande se comparado com 0 tamanho da tabela hash. No endereçamento aberto a tabela hash é construída com um vetor, que armazenará todas as chaves que não colidirem. C No endereçamento aberto, quando uma colisão ocorre, ela precisa ser tratada com algum algoritmo, como 0 de tentativa linear e a quadrática. Você assinalou essa alternativa (C) 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. E As funções de hash aplicadas para endereçamento em cadeia são diferentes das aplicadas no endereçamento aberto. Questão 7/10 Programação III Um percurso é uma forma sistemática de visitar e processar nós de uma Um percurso em profundidade pode ser de três tipos básicos: percorre a sub árvore esquerda, depois visita a raiz da árvore percorre a sub árvore direita Pré-ordem: visita a raiz da depois percorre a subárvore esquerda final- mente, percorre a subárvore Pós-ordem: percorre a subárvore esquerda, depois percorre a subárvore direita finalmente, visita a raiz da árvore. Pereira, Silvio do Lago. Estruturas de dados em C uma abordagem didática Silvio do Lago Pereira São Paulo Érica, 2016. Pag 134 modificado Considere seguinte arvore binária: 5 2 8 0 6 9 Qual é a ordem de visita seguindo 0 percurso em pré ordem? A 0,2,5,6,8,9 0,2,6,9,8,5 C 0,2,6,8,9,5 D 5,2,0,8,6,9 Você assinalou essa alternativa (D) E 5,2,8,0,6,9 Questão 8/10 Programação III 40 Ler em alta "A propriedade de auto balanceamento de uma árvore AVL é mantida por meio do fator de Quando diferença na altura das subárvores esquerda direita atinge um valor maior do que (ou menor do que a árvore precisa ser balanceada por meio de operações de rotação. Rodrigues, Thiago, et al Estrutura de Dados em Java Ed 2021 pag 151 Observe um exemplo de árvore AVL abaixo 90 80 99 50 85 Suponha que você quer remover folha de valor 99 Acerca do balanceamento rotação desta árvore sem Assinale alternativa CORRETA: A A árvore ficará balanceada e não precisará de rotação A árvore ficará com um desbalanceamento de valor 2 na raiz C nó filho de valor 80 está com balanceamento 0. resultando em uma rotação simples para a essa D A está com um desbalanceamento de valor -2 na raiz, resultando em uma rotação simples para a esquerda E nó filho de valor 80 está com balanceamento 1, resultando em uma dupla com filho para a esquerda e pai para aExistem duas ordens comuns nas quais os vértices podem ser visitados durante 0 percurso em um grafo. 0 primeiro, chamado de percurso em profundidade, 0 segundo tipo de percurso, chamado de percurso em largura. 0 percurso em largura em grafos utiliza qual estrutura de dados? A Pilha Fila Você assinalou essa alternativa C Hash D Dicionário E Árvore Questão 10/10 Programação III Ler em voz alta "A utilização da de hashing possibilita a indexação dos dados, transformando uma chave k em um endereço físico, relativo ou absoluto h(k), provendo maior rapidez e segurança na busca por informações dentro de um arquivo. Há pórém 0 problema das colisões." Lima, Diana M., D e Luis E.F. Matemática aplicada à informática (Tekne). Disponível Minha Grupo 2015 pag 57 modificado Quanto a função hashing e colisões, assinale a alternativa A Uma função hash pode ser livre de colisões, para isso basta utilizar hash No endereçamento aberto, cada posição da estrutura de dados pode conter múltiplas palavra-chave. Na tentativa linear, sempre que uma colisão ocorre, tenta-se posicionar a nova chave no próximo espaço imediatamente livre do array. Você assinalou essa alternativa D No endereçamento em cadeia as colisões podem ser tratadas de 2 maneiras: TENTATIVA LINEAR ou TENTATIVA QUADRÁTICA E Na tentativa quadrática, sempre que uma colisão ocorre, tenta-se posicionar a nova chave no próximo espaço imediatamente livre do array.