Prévia do material em texto
24/05/2021 EPS ESTRUTURA DE DADOS a Lupa 4 aula Exercício: CCT0826_EX_A4_ 01/05/2021 Aluno(a): 2021.1 EAD Disciplina: CCT0826 - ESTRUTURA DE DADOS Existem vários tipos de algoritmos para realizar a ordenação dos elementos, onde um algoritmo de ordenação deve rearranjar o vetor de forma a estabelecer uma ordem entre os elementos. Marque a alternativa correta que cita o algoritmo cuja descrição é: "considera cada elemento uma vez inserindo-o em seu lugar correto entre os elementos que já estão em ordem". E o seu passo a passo pode ser descrito como: "o elemento é inserido entre os ordenados movendo- se os elementos maiores que ele uma posição para a direita e posteriormente inserindo-o na posição vaga". QuickSort MergeSort Bolha Seleção Inserção Respondido em 01/05/2021 22:11:19 Gabarito Comentado Existem vários algoritmos de busca em estruturas de dados, um destes realiza a busca em vetores, e requer acesso aleatório aos elementos desta estrutura e parte do pressuposto de que os dados do vetor estejam ordenados e utiliza a técnica de divisão e conquista comparando o elemento desejado com o elemento do meio do vetor. Esta técnica ainda verifica se o elemento do meio do vetor for o desejado, a busca termina. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. O algoritmo que utiliza esta metodologia é: Pesquisa sequencial Seleção Bolha Inserção Pesquisa binária Respondido em 01/05/2021 22:11:54 Gabarito Comentado Qual papel do for mais interno na função ordena abaixo ? 1/4 24/05/2021 EPS void ordena( int n, int v[]) { int i, j, x; for (j = 1; j < n; ++j) { x = v[j]; for (i = j-1; i >= 0 && v[i] > x; --i) v[i+1] = v[i]; v[i+1] = x; } } Encontrar o menor valor v[j] que deve ser inserido em v[0..j-1]. Encontrar o maior valor de x que deve ser inserido em v[0..j-1]. Encontrar o valor de v[j] deve em v[0..j-1]. Encontrar o ponto onde v[j] deve ser inserido em v[0..j-1]. Encontrar o elmento a ser eliminado do vetor Respondido em 01/05/2021 22:12:52 Gabarito Comentado Com a utilização das estruturas de dados e seus tipos, em algumas situações é imprescindível a criação de funções que façam determinada verificação ou ação nestas estruturas. Dessa forma, analise a função abaixo e marque corretamente a alternativa que descreve as funcionalidades desta. int funcao(float v[], float vl, int n) { for (int i = 0; i < n; i++) if (v[i] == vl) return i; return -1; } Retorna -1 se o valor de vl estiver dentro de v. Retorna a posição de v se o valor vl foi encontrado. Resulta em erro, se o valor de vl não estiver dentro de v. Retorna o valor de vl se o valor n foi encontrado. Retorna -1 se o valor de n foi encontrado. Respondido em 01/05/2021 22:14:52 Explicação: A função apresentada é a busca sequencial. Note que ela retorna o índice do elemento vl, quando o valor vl é encontrado e ela retorna -1 caso o valor vl não for encontrado. Gabarito Comentado Os algoritmos de busca são muito utilizados em estrutura de dados. Sendo assim, o algoritmo que realiza a busca em vetores e que exige acesso aleatório aos elementos do mesmo e que parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca comparando o elemento que se deseja com o elemento do meio do vetor, é chamado de: Tabela Hash Pesquisa de seleção Pesquisa ordenada Pesquisa sequêncial Pesquisa binária Respondido em 01/05/2021 22:15:54 Explicação: O enunciado descreve a busca binária. A busca sequencial trabalha sequencialmente testando elemento a elemento. 2/4 24/05/2021 EPS Pesquisa de seleção ou ordenada não foram abordadas. Tabela hash trabalha com função hash e não se encaixa na descrição feita. Gabarito Comentado Considere a seguinte função busca escrita em linguagem C++ : bool busca(int vetor[ ], int n, int tam) { int ini=0, mid; while (ini <= tam) { cout << " x "; mid = (ini + tam)/2; if (vetor[mid] == n) return true; else if (n > vetor[mid]) ini = mid+1; else tam = mid-1; } return false; } Qual a quantidade total de impressões da letra x nas buscas pelos números n = 4, n = 2 e n = 0 no vetor [1,2,3,4,5,6,7,8], sendo tam = 7 ? int vetor[] = {1,2,3,4,5,6,7,8}; busca(vetor, 4, 7); busca(vetor, 2, 7); busca(vetor, 0, 7); 5 4 6 8 9 Respondido em 01/05/2021 22:16:36 Explicação: Na 1a. execução da busca... para n = 4 temos impresso : x Na 2a. execução da busca ... para n = 2 temos impresso : x x Na 3a. execução da busca ... para n = 0 temos impresso : x x x Total de impressões da letra x : 6 É um método de pesquisa ou busca, cujo algoritmo parte do pressuposto de que o vetor está ordenado e realiza sucessivas divisões do espaço de busca, comparando o elemento buscado (chave) com o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. A descrição apresentada trata-se do método denominado busca ...... linear. por contagem. randômica. 3/4 24/05/2021 EPS por comparação. binária. Respondido em 01/05/2021 22:17:06 Gabarito Comentado Sobre o funcionamento da busca binária, é correto afirmar que dividindo seu vetor em duas metades. Se o item for igual ao item que está na metade do vetor, o item foi encontrado. Se o item for maior que o item que está na metade do vetor procure na primeira metade, ou seja, a da direita. Se o item for menor que o item que está na metade do vetor, o item foi encontrado. Se o item for igual ao item que está na metade do vetor, o item não foi encontrado. Se o item for menor que o item que está na metade do vetor, procure na segunda metade, ou seja, a da direita. Respondido em 01/05/2021 22:17:25 Explicação: Neste tipo de busca, o vetor deve estar ordenado. Divide-se o conjunto de dados ao meio e procura-se no meio do vetor. Se achou, retorna a posição do dado do meio. SE não achou, verifica-se se o valor procurado vem antes do valor do meio. Se for verdade, redefine-se o fim do vetor, voltando a realizar a busca à esquerda do meio. Se o valor procurado vier depois do valor do meio do vetor, então redefine-se o início e segue-se para a busca na parte à direita do meio do vetor. Gabarito Comentado 4/4