ESTRUTURA DE DADOS II - Atividade 03

Prévia do material em texto

12/14/2020 Unicesumar - Ensino a Distância
1/5
ATIVIDADE 03 - ADS - ESTRUTURA DE DADOS II - 2020
Período:15/06/2020 08:00 a 03/07/2020 23:59 (Horário de Brasília)
Status:ENCERRADO
Nota máxima:0,50
Gabarito:Gabarito será liberado no dia 08/07/2020 00:00 (Horário de Brasília)
Nota obtida:0,40
1ª QUESTÃO
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úmero 4 antes de concluir a operação como malsucedida.
ALTERNATIVAS
3
5
6
10
13
2ª QUESTÃO
Existem diversos tipos de árvores. A árvore como estrutura é muito utilizada para organizar informações. As
árvores binárias, estritamente binárias e as árvores binárias completas são tipos particularmente
interessantes para certas ocasiões. Com base em seus conhecimentos a respeito de árvores, avalie as
alternativas e assinale a correta que apresente a definição correta de uma dos tipos de árvores.
ALTERNATIVAS
A raiz de uma árvore tem nível igual à altura da árvore.
Nas árvores binárias, um nó pode ter no mínimo dois filhos, ou subárvores.
Em uma árvore binária completa, a altura do pai de um nó folha sempre terá o valor 0.
O nível de uma árvore pode ser medido como o caminho mais longo desde a raiz até um nó pai a direita.
Em uma árvore estritamente binária o nó é uma folha ou ele possui necessariamente seus dois filhos.
3ª QUESTÃO
Árvores binárias se tratarem de estruturas derivadas de grafos, o desenvolvedor pode aplicar, nas árvores, os
mesmos métodos como, por exemplo, os algoritmos de busca e caminhamento.
  
Sabendo disso, pode-se afirmar que:
 
I – Um nó, que não possui nós filhos, é chamado de folha.
II – Quando se inicia um caminho na raiz e se vai em direção às folhas, diz-se que está descendo pela árvore.
III – Quando se inicia um caminho em uma folha e se vai em direção à raiz, diz-se que está subindo pela
árvore.
IV – Não é possível determinar o nível de um nó com base no nível de seu pai.
ALTERNATIVAS
12/14/2020 Unicesumar - Ensino a Distância
2/5
Somente I e II estão corretas.
Somente II e III estão corretas.
Somente I, II e III estão corretas.
Somente I, II e IV estão corretas.
Somente I, III e IV estão corretas.
4ª QUESTÃO
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.
5ª QUESTÃO
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
12/14/2020 Unicesumar - Ensino a Distância
3/5
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.
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
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.
8ª 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
12/14/2020 Unicesumar - Ensino a Distância
4/5
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.
9ª 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
I, apenas.
I e II, apenas.
I e III, apenas.
II e III, apenas.
I, II e III.
10ª QUESTÃO
12/14/2020 Unicesumar - Ensino a Distância
5/5
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 dovetor.
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.