Estrutura de Dados II - Questões de Prova

Prévia do material em texto

27/06/2019 Unicesumar - Ensino a Distância
1/6
ATIVIDADE 3 - ADS - ESTRUTURA DE DADOS II - 2019B
Período:24/06/2019 08:00 a 05/07/2019 23:00 (Horário de Brasília)
Status:ABERTO
Nota máxima:0,50
Gabarito:Gabarito será liberado no dia 06/07/2019 00:00 (Horário de Brasília)
Nota obtida:
1ª QUESTÃO
A operação de busca sequencial percorre os elementos de um arranjo (vetor ou lista ligada) em busca de um
valor especificado como argumento.
Dessa forma, assinale a alternativa correta referente ao que acontece quando o valor procurado é
encontrado em dois ou mais elementos do arranjo.
ALTERNATIVAS
A busca retorna a primeira posição onde o valor foi encontrado.
A busca retorna a última posição onde o valor foi encontrado.
A busca emite uma mensagem de duplicidade e retorna -1, como se tivesse falhado.
A busca retorna um vetor com todas as posições cujo valor corresponde ao procurado.
A busca aguarda o usuário escolher dentre as posições onde o valor procurado foi encontrado.
2ª QUESTÃO
Existe uma estrutura de dados que permite inserção, remoção e busca de dados em tempo constante, no
melhor caso. É o caso das Tabelas Hash, também conhecidas como Tabelas de Dispersão ou Escrutínio.
Com base em seus conhecimentos a respeito de Tabelas de Dispersão, avalie as afirmações a seguir.
I - A função h(x) = x*x % 10 , aonde o caractere % indica o resto da divisão inteira, pode ser
considerada uma função hash adequada para uma tabela de 10 elementos.
II - O conceito de colisão em Tabelas Hash podem ser tratados por meio de tecnicas que envolvam listas
encadeadas.
III - Em certos momentos, quando ocorre uma colisão, pode ser necessário realizar uma busca sequêncial
pela tabela.
    
Dessa forma é correto o que se afirma em:
ALTERNATIVAS
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
3ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
2/6
A técnica de ordenação MergeSort utiliza um conceito conhecido por dividir para conquistar. Esse conceito
sugere que um problema complexo possa ser dividido em dois problemas menores e cada um desses sejam
divididos novamente em partes menores ainda, até que se encontre uma parte pequena e simples suficiente
para que seja resolvido.
PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).
Leia as afirmativas a seguir sobre as características da técnica MergeSort
I - O algoritmo utiliza a recursividade para percorrer o vetor procurando pelos valores.
II - No processamento, o vetor é dividido em três partes iguais, de modo a encurtar a procura.
III - O MergeSort apresenta uma abordagem mais simples do que o BubbleSort e o SelectionSort.
IV - O MergeSort pode consumir uma quantidade considerável de memória ao ordenar grandes quantidades
de dados.
É correto o que se afirmar em:
ALTERNATIVAS
I e II, apenas.
I e IV, apenas.
III e IV, apenas.
I, II e III, apenas.
I, II e IV, apenas.
4ª QUESTÃO
O algoritmo ShellSort de ordenação tem esse nome em homenagem ao seu criador, Donald Shell, publicado
pela Universidade de Cincinnat em 1959. Segundo Wirth (1989) ele é o mais eficiente dentro dos algoritmos
classificados como de complexidade quadrática.
 
WIRTH, Niklaus. Algoritmos e estrutura de dados. Rio de Janeiro. Prentice-Hall do Brasil, 1989
Assinale a alternativa correta referente à principal característica do algoritmo ShellSort.
ALTERNATIVAS
Ele aplica uma busca sequencial completa.
Ele mescla os métodos MergeSort e QuickSort.
Ele aplica o método SelectionSort utilizando recursividade.
Ele aplica uma busca binária utilizando o método BubbleSort.
Ele divide o vetor em vetores menores e em cada um deles aplica o método InsertionSort.
5ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
3/6
A ordenação Insertionsort também é conhecida como ordenação por inserção. É de implementação simples
e traz bons resultados. Considere o trecho de código abaixo.
01 - int insertionionSort(int vec[], int tam) {
02 - int i, j, qtd=0;
03 - for(i = 1; i < tam; i++){
04 - j = i;
05 - while((vec[j] < vec[j - 1]) && (j!=0)){
06 - troca(&vec[j], &vec[j-1]);
07 - j--;
08 - qtd++;
09 - }
10 - }
11 - return(qtd);
12 - }
Com base no exposto, analise as afirmações a seguir:
I - A verificação " (vec[j] < vec[j - 1]) " da linha 5 funciona de maneira similar à busca sequencial
indexada.
II - O laço interno, que vai das linhas 5 a 9 é sempre executado até que a variável j atinja o valor 0.
III - Pode-se dizer que do índice 0 até i-1 temos a porção ordenada do vetor vec .
Dessa forma é correto o que se afirma em:
ALTERNATIVAS
I ,apenas.
III, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
6ª QUESTÃO
A busca binária é uma forma eficiente de se efetuar busca em arranjos de dados, pois reduz pela metade a
quantidade de possíveis candidatos a cada iteração. Entretanto, uma condição é necessária para ela ser
usada. Assinale a alternativa correta referente à esta condição.
ALTERNATIVAS
Os dados do vetor ou estrutura devem ser do tipo char .
A estrutura ou arranjo deve ter seus dados ordenados.
O vetor ou arranjo deve ter escopo global dentro do programa.
O número total de elementos da estrutura de dados deve ser par.
Não pode haver números float ou double (com decimais) na estrutura de dados.
7ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
4/6
A técnica de ordenação SelectionSort, assim como a BubbleSort, é de simples implementação e de alto
consumo computacional.
OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2019.
(Adaptado).
Asinale a alternativa correta referente à principal diferença entre o SelectionSort e o BubbleSort.
ALTERNATIVAS
O BubbleSort é majoritariamente utilizado para ordenar vetores; o SelectionSort para ordenar matrizes.
O BubbleSort inicia a varredura do início do vetor, ao passo que o SelectionSort inicia do final do vetor.
Para concluir a ordenação, o BubbleSort realiza apenas uma troca; o SelectionSort realiza pares de trocas para cada
posição do vetor.
O BubbleSort necessita de memória extra para fazer o processamento, enquanto o SelectionSort utiliza metade da
memória proporcionalmente.
O BubbleSort realiza a troca em cada par de valores invertidos; o SelectionSort faz a troca quando encontra o menor
valor para a posição em processamento.
8ª QUESTÃO
A técnica de ordenação BubbleSort também é conhecida por ordenação por flutuação ou por método da
bolha. Ela é de simples implementação e de alto custo computacional.
OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2019.
(Adaptado)
Leia as afirmativas a seguir sobre os passos da ordenação por BubbleSort
I - O processamento inicia na primeira posição do vetor.
II - Em cada iteração é feita uma comparação do elemento atual com o próximo elemento do vetor.
III - Em cada comparação, se os valores estiverem invertidos, é efetuada a troca deles.
IV - O processamento finaliza depois da primeira troca de valores.
É correto o que se afirma em:
ALTERNATIVAS
I e II, apenas.
I e III, apenas.
II e IV, apenas.
I, II e III, apenas.
II, III e IV, apenas.
9ª QUESTÃO
27/06/2019 Unicesumar - Ensino a Distância
5/6
A busca sequencial indexada consiste em ordenar o vetor antes de se iniciar a busca ou mesmo criar uma
tabela auxiliar ao arranjo de dados que conterá a chave da busca e o endereço do registro no arranjo
principal.
Dado um vetor com os 13 primeiros elementos da sequência de Fibonacci { 0, 1, 1, 2, 3, 5, 8, 13,
21, 34, 55, 89, 144 } , assinale a alternativa referente ao número correto de iterações que a busca
sequencial indexada fará para tentar encontrar o número30 antes de concluir a operação como
malsucedida.
ALTERNATIVAS
3.
5.
7.
10.
13.
10ª QUESTÃO
Considere que a função hash de uma tabela de dispersão é a seguinte: h(x) = x² mod 10 . Sabendo disso,
imagine que, em memória, nossa tabela hash se encontra com a seguinte configuração, nas quais somente
os elementos 11, 72, 88, 26, 25 e 23 foram inseridos (não necessariamente nessa ordem):
Com base nisso, avalie as afirmações que se seguem.
I - Podemos afirmar que o elemento 88 foi inserido somente após a inserção do elemento 72.
II - Podemos afirmar que o elemento 25 foi inserido antes da inserção do elemento 72.
III - O elemento 26 foi inserido anteriormente ao 25.
Dessa forma é correto o que se afirma em:
ALTERNATIVAS
27/06/2019 Unicesumar - Ensino a Distância
6/6
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.