Aula 2 - Exercícios - Estrutura de dados

Prévia do material em texto

Exercício: CCT0753_EX_A4_201708216677_V7 15/09/2018 12:40:03 (Finalizada)
Aluno(a): PAULO CESAR ALVES SOARES 2018.3 EAD
Disciplina: CCT0753 - ESTRUTURA DE DADOS 201708216677
 
 
 1a Questão
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);
4
5
9
8
 6
 
 
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
 
 
 
 2a Questão
Marque a afirmativa correta para a "Busca ou pesquisa binária".
Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente.
Consiste em fazer uma busca em um vetor desordenado, dividindo o espaço de busca ao meio e verificando se o dado está no meio ou, antes
do meio ou depois do meio.
 Consiste em fazer uma busca em um vetor já ordenado, dividindo o espaço de busca ao meio e verificando se o dado está no meio ou, antes
do meio ou depois do meio.
Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos.
 
 
 
 3a Questão
Para consultarmos uma estrutura de dados, normalmente, empregamos um tipo de pesquisa de dados. O trecho de programa a seguir refere-se a uma
pesquisa por um elemento único (sua primeira ocorrência), em um conjunto de elementos de dados armazenado em uma estrutura de acesso indexado
e aleatório. Selecione a opção correspondente ao algoritmo utilizado, no programa, para a referida pesquisa:
int busca(float v[], float valor, int n) {
int ini = 0, fim = n -1, meio;
while (ini <= fim) {
meio = (ini + fim)/2;
if (v[meio] == valor) return meio;
if (valor < v[meio]) fim = meio -1;
 else ini = meio+1;
}
return -1;
}
pesquisa cadeias indexada
 pesquisa binária
pesquisa indexada
pesquisa de cadeias
pesquisa sequencial
 
 
 
 4a Questão
Analise o seguinte trecho de algoritmo de ordenação de dados, cujos elementos estão dispostos em um vetor de
nome v com n elementos.
...
{
int i, j, aux;
for (j = 1; j < n; j++)
for (i=j; i > 0 && v[i-1]> v[i]; i--) {
aux = v[i-1];
v[i-1] = v[i];
v[i] = aux;
}
}
...
Assinale o método ao qual o trecho de algoritmo pertence.
 Inserção
Quicksort
Seleção
Heapsort
Bolha
 
 
 
 5a Questão
O resultado do concurso para o cargo de uma empresa está armazenado em um vetor, que contém em cada um de seus elementos o número de
inscrição, o nome e a nota obtida pelo candidato. Este vetor está ordenado pelo número de inscrição. Para realização de uma consulta que, dado um
número de inscrição, apresenta o nome e nota do candidato, um programador utilizou um algoritmo de busca que realiza sucessivas divisões no vetor,
comparando o número de inscrição procurado com o número de inscrição do candidato posicionado no meio do vetor. Se o candidato posicionado do
meio do vetor tiver o número de inscrição igual ao número de inscrição procurado, a busca termina com sucesso. Caso contrário, se candidato
posicionado do meio do vetor tiver número de inscrição menor que o procurado, então a busca continua na metade posterior do vetor. E finalmente, se
candidato posicionado do meio do vetor tiver número de inscrição maior que o procurado, a busca continua na metade anterior do vetor. O algoritmo
utilizado pelo programador trata-se do método denominado busca:
por contagem.
 binária.
randômica.
linear.
por comparação.
 
 
 
 6a Questão
Qual característica NÃO podemos atribuir a PESQUISA BINÁRIA.
 A lista pode estar desordenada.
São realizadas sucessivas divisões da lista ao meio.
Quando o valor pesquisado é maior do que a chave do MEIO da lista, devemos dispensar a metade que vem antes do meio da lista.
A lista precisa estar ordenada.
É eficiente quando se trata de listas ordenadas
 
 
Explicação: Na pesquisa binária a lista obrigatoriamente deverá estar ORDENADA.
 
 
 
 7a Questão
Considere as afirmativas a seguir.
I. Uma forma muito simples de fazer uma busca em um vetor consiste em percorrer o vetor, elemento a elemento, para verificar se o elemento
procurado é igual a um dos elementos do vetor.
II. A pesquisa sequencial é extremamente simples e eficiente quando o número de elementos do vetor for muito grande.
III. Na pesquisa binária, a cada interação do algoritmo o tamanho do vetor é dividido ao meio.
IV. A pesquisa binária funciona corretamente quanto o conjunto de dados estiver desordenado.
Assinale a alternativa correta.
Somente as afirmativas I e II são corretas.
Somente as afirmativas II, III e IV são corretas.
 Somente as afirmativas I e III são corretas.
Somente as afirmativas III e IV são corretas.
Somente as afirmativas I e IV são corretas.
 
 
Explicação:
Analisando cada afirmativa :
I. Uma forma muito simples de fazer uma busca em um vetor consiste em percorrer o vetor, elemento a elemento, para verificar se o elemento
procurado é igual a um dos elementos do vetor.
Correto. SEria uma busca sequencial.
II. A pesquisa sequencial é extremamente simples e eficiente quando o número de elementos do vetor for muito grande.
Falso. Se tivermos que procurar um elemento que está no fim do vetor ou que não seja encontrado, o tempo de execução será proporcional ao número
de elementos. Então, quanto maior a lista, mais tempo levaremos.
III. Na pesquisa binária, a cada interação do algoritmo o tamanho do vetor é dividido ao meio.
Correto.
IV. A pesquisa binária funciona corretamente quanto o conjunto de dados estiver desordenado.
Falso. Por definição, a busca binária só pode atuar em listas ordenadas.
Logo, apenas as afirmativas I e III estão corretas.
 
 
 
 8a Questão
O resultado do concurso para o cargo de uma empresa está armazenado em um vetor, que contém em cada um de seus
elementos o nome e a nota obtida pelo candidato. Deseja-se que este vetor seja ordenado pela nota, em ordem decrescente.
Sendo o vetor pequeno (poucos elementos), o programador responsável por desenvolver este algoritmo, escolheu um método de
ordenação que executa os seguintes passos:
Selecione candidato com maior nota entre todos e troque-o com o candidato que está na primeira posição do vetor;
Selecione o segundo maior e troque-o com o candidato que está na segunda posição;
Os passos descritos anteriormente são seguidos para a terceira nota, quarta nota e assim por diante até que reste apenas
um candidato.
O algoritmo utilizado pelo programador trata-se do método de ordenação denominado:
Heapsort
Inserção
Bolha
Quicksort
 Seleção