ED A4

Prévia do material em texto

1a Questão 
 
Caso seja empregada uma busca binária em uma lista sequencial ordenada com 2048 valores, qual seria o 
número máximo de comparações para encontrar um valor que esteja na lista? 
 
 
12 
 
9 
 
8 
 11 
 
10 
 
 
Explicação: 
Como a busca binária sai continuamente dividindo o conjunto de dados ao meio (em duas partes), então vamos 
fatorar e organizar o resultado como potência de base 2. 
 Fatorando 2048 temos 2 11 
 Portanto, a resposta é 11. 
 
 
 
 
 2a Questão 
 
 
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. 
 
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. 
 Retorna a posição de v se o valor vl foi encontrado. 
 
 
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 
Coment. 
 
 
 
 
 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 binária 
 
pesquisa sequencial 
 
pesquisa de cadeias 
 
pesquisa cadeias indexada 
 
pesquisa indexada 
 
 
Gabarito 
Coment. 
 
 
 
 
 4a Questão 
 
 
Suponha uma listagem, contendo número de inscrição e pontuação (ordenada pelo número de inscrição) dos 
candidatos para o cargo de Analista de Sistemas de uma grande empresa pública. São 1024 candidatos inscritos 
e o sistema implementado para consulta do resultado, permite busca binária ou busca sequencial pelo número 
de inscrição. O número máximo de comparações executadas se fosse utilizada a busca binária e se fosse 
utilizada busca sequencial, respectivamente, seria de: 
 
 10 e 1024 
 
9 e 9 
 
1024 e 512 
 
9 e 10 
 
10 e 10 
 
 
Gabarito 
Coment. 
 
 
 
 
 5a Questão 
 
 
Os métodos de ordenação são muito utilizados para facilitar a recuperação posterior de itens ordenados. 
Existem vários métodos de ordenação, por esse motivo, assinale corretamente a alternativa que mostra o nome 
do método que utiliza a estratégia de ordenação por trocas de vizinhos e é considerado o método mais simples. 
 
 
Binária 
 
Hash 
 
Inserção 
 
Seleção 
 Bolha 
 
 
Gabarito 
Coment. 
 
 
 
 
 6a Questão 
 
 
Marque a afirmativa correta para a "inserção incremental". 
 
 
A técnica é boa quando os dados ficam uniformemente distribuídos entre os seus compartimentos. 
 Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos. 
 
Os pivôs são escolhidos aleatoriamente. 
 
É um tipo de ordenação por intercalação 
 
É um tipo de sequenciação por intercalação. 
 
 
Gabarito 
Coment. 
 
 
 
 
 7a 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: 
 
 
Quicksort 
 
Bolha 
 
Heapsort 
 
Inserção 
 Seleção 
 
 
Gabarito 
Coment. 
 
 
 
 
 8a Questão 
 
 
Qual característica NÃO podemos atribuir a PESQUISA BINÁRIA. 
 
 
A lista precisa estar ordenada. 
 
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 pode estar desordenada. 
 
É eficiente quando se trata de listas ordenadas 
 
São realizadas sucessivas divisões da lista ao meio. 
 
 
Explicação: Na pesquisa binária a lista obrigatoriamente deverá estar ORDENADA.