ATIVIDADE 2 - ADS - ESTRUTURA DE DADOS II

Prévia do material em texto

14/08/2021 Unicesumar - Ensino a Distância
1/6
ATIVIDADE 2 - ADS - ESTRUTURA DE DADOS II - 52/2021
Período:21/06/2021 08:00 a 09/07/2021 23:59 (Horário de Brasília)
Status:ENCERRADO
Nota máxima:1,50
Gabarito:Gabarito será liberado no dia 10/07/2021 00:00 (Horário de Brasília)
Nota obtida:1,20
1ª 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. Você, enquanto estudante de um
curso de TI, deve saber que a lógica desse método de ordenação implementa dois laços de repetição, um
aninhado ao outro, o que faz com que, no pior caso, o Bubblesort realize cerca de n² comparações, para um
arranjo de tamanho n.
 
Adaptado de: OLIVEIRA, P. M. de.; PEREIRA, R. de. L. Estruturas de Dados II. Maringá: Unicesumar, 2019. 
 
Assinale a alternativa correta correspondente à forma como é feita a ordenação crescente pelo BubbleSort.
ALTERNATIVAS
Os valores são embaralhados e comparados um a um para criar a ordenação.
Os valores são agrupados, ordenados e depois divididos, repetindo-se o processo.
Os valores são divididos e isolados, são ordenados, para depois serem agrupados.
Os valores mais altos (ou mais baixos) vão flutuando em direção à extremidade do vetor, criando a ordenação da
estrutura.
Os valores de valores intermediários vão flutuando para o início do vetor, criando a ordenação da estrutura.
2ª QUESTÃO
Em tecnologia da informação, operações de busca de dados são realizadas com grande frequência. Sempre
que você inicia a execução de um programa, o seu sistema operacional realiza operações de busca. Sempre
que um processo está armazenado em memória, existem operações de busca sendo realizadas. Quando se
fala nesse tipo de operação, pode-se dizer que as árvores binárias são muito úteis no sentido de cumprir
essa tarefa. Sobre árvores de busca binária, avalie as opções, a seguir, e assinale a alternativa correta.
ALTERNATIVAS
De maneira geral, a busca sequencial simples apresenta melhores resultados que a busca em árvore binária.
Não há diferenças de velocidade na execução da busca em profundidade ou da busca binária, em uma árvore
ordenada.
Em uma árvore de busca binária, é preferível executar o algoritmo de busca em largura, sempre que se souber que
o nó alvo se encontra longe da raiz.
De maneira geral, a busca em árvore binária supera a velocidade das buscas em arranjos simples.
A árvore de busca binária pode substituir o algoritmo de Dijkstra para encontrar um caminho de custo mínimo.
3ª QUESTÃO
14/08/2021 Unicesumar - Ensino a Distância
2/6
Algoritmos e estruturas de dados formam o núcleo da ciência da computação, sendo os componentes
básicos de qualquer software. Aprender algoritmos relacionados aos arranjos, grafos e árvores é crucial para
qualquer pessoa que deseja desenvolver um software de qualidade. Em se tratando de algoritmos de
ordenação, algumas técnicas utilizam um conceito conhecido por "dividir para conquistar".
 
Adaptado de: OLIVEIRA, P. M. de.; PEREIRA, R. de. L. Estruturas de Dados II. Maringá: Unicesumar, 2019. 
 
 
Assinale a alternativa que melhor explica o conceito "dividir para conquistar".
ALTERNATIVAS
Em um primeiro momento, resolve-se o problema de maior para depois dividi-lo em soluções menores, levando em
conta que o problema maior é uma substância do problema maior.
O problema simples é aglomerado com outros problemas simples, em um problema mais complexo, de modo que a
solução seja poderosa o suficiente para eliminá-lo.
Estima-se quantas pessoas são necessárias para a resolução do problema, de modo que a solução venha pelo
volume de mão de obra empregado.
Um problema complexo é contrabalanceado com outro problema mais simples, de modo que a resolução rápida
deste traga consequências para o problema maior.
Um problema complexo é dividido em subproblemas menores, que, por sua vez, são divididos novamente e assim
por diante, até que se encontrem soluções diretas que, combinadas, resolvem o problema complexo.
4ª 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, caso este valor seja encontrado a busca para e retorna a posição.
Assinale a alternativa correta referente ao que acontece quando o valor procurado está repetido em duas ou
mais posições no arranjo.
ALTERNATIVAS
A busca sequencial simples divide o arranjo em dois, a cada chamada recursiva.
Diferentemente da busca interpolada, a busca sequencial não percorre o vetor até o final.
Assim como a busca binária, a busca sequencial depende de que o vetor esteja ordenado.
Diferentemente da busca sequencial indexada, a busca sequencial percorre todo o vetor, sempre.
A busca sequencial simples atinge seu maior desempenho quando combinada com o algoritmo de ordenação
Quicksort.
5ª QUESTÃO
14/08/2021 Unicesumar - Ensino a Distância
3/6
Um(a) desenvolvedor(a) de software, provavelmente, terá de implementar algum método de busca,
manualmente, durante sua carreira profissional. Existem diversas técnicas bastante conhecidas, utilizando
estruturas de dados variadas. Observe o pseudocódigo a seguir:
 
01 - Busca(A, chave, início, final)
02 - Se início <= final então
03 - meio <- (final + início) / 2
04 - Se A[meio] = chave então
05 - retorne meio
06 - Senão, se chave < A[meio] então
07 - retorne Busca(A,chave,início,meio-1)
08 - Senão, se chave > A[meio]
09 - retorne Busca(A,chave,meio+1,final)
10 - Senão
11 - retorne "elemento ausente"
 
Com base no algoritmo de busca anterior, avalie as alternativas e assinale a afirmação correta.
ALTERNATIVAS
No melhor caso, esse algoritmo executa n² operações.
Em situações específicas, pode ser que a busca sequencial indexada tenha desempenho igual ou melhor que o
algoritmo de busca anterior.
Nesse algoritmo, o pior caso ocorre quando o vetor já está ordenado.
Esse algoritmo tem melhor desempenho quando aplicado às árvores binárias.
Tal tipo de busca não necessita que o arranjo esteja ordenado para funcionar.
6ª QUESTÃO
A técnica de ordenação Mergesort consiste em dividir um problema complexo em problemas menores e
assim por diante, até que se encontre uma solução pequena e simples suficiente para que o problema seja
resolvido como um todo. Esse conceito é bem conhecido na ciência da computação, e seu nome é “dividir-
para-conquistar”. Para além de aplicações tecnológicas, o esse conceito é utilizado também em estratégias
comerciais ou mesmo sócio-políticas.
 
OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2019.
(Adaptado).
 
Assinale a alternativa correta correspondente à forma como é feita a ordenação pelo algoritmo Mergesort.
ALTERNATIVAS
14/08/2021 Unicesumar - Ensino a Distância
4/6
O vetor é dividido em duas partes, essas partes são divididas novamente, e assim por diante, até que cada parte
tenha apenas um elemento. Depois é feita a junção, ordenando essas partes e recompondo o vetor com os dados
originais ordenados.
De maneira recursiva, em dois laços de repetição, o elemento atual é removido, sua posição ideal é procurada no
vetor e, uma vez encontrada, o elemento é reinserido em sua posição quase ordenada.
De maneira iterativa, em dois laços de repetição, os elementos são comparados e trocados conforme o caso, fazendo
os valores maiores "flutuarem" para o final do arranjo, realizando a ordenação de trás para frente.
O vetor é dividido em várias partes iguais menores, em que é feita a ordenação em cada uma delas. Depois o vetor
é reunido já com valores ordenados, tomando por base a função partition() e o elemento pivô.
De maneira iterativa, o vetor original é percorrido em um único laço de repetição e os elementossão adicionados em
um segundo vetor único, fazendo a comparação para verificar a ordenação.
7ª QUESTÃO
Uma árvore binária é um tipo de grafo que tem regras específicas na sua construção. Cada nó tem no
máximo dois filhos e um único pai, excetuando-se o nó raiz da árvore principal que é órfão. Além disso, é
preciso considerar que os filhos de um nó são, na verdade, novas subárvores que, por sua vez, podem ter,
ainda, novos filhos que, quando combinados, formam a árvore como um todo.
 
Adaptado de: OLIVEIRA, P. M. de.; PEREIRA, R. de. L. Estruturas de Dados II. Maringá: Unicesumar, 2019. 
 
 
Assinale a alternativa correta, referente à definição de árvore estritamente binária.
ALTERNATIVAS
Árvore que não possui folhas, ou seja, expande-se infinitamente.
Árvore que, particularmente, possui duas raízes ao invés de uma.
Árvore que possui apenas um nó do lado esquerdo e uma subárvore do lado direito.
Árvore na qual todo nó que não é folha tem sempre subárvores direita e esquerda não vazias.
Árvore na qual os nós são formados apenas de folhas, ou seja, apenas um nível de subárvores.
8ª QUESTÃO
Um(a) desenvolvedor(a) de software provavelmente terá de implementar algum método de busca,
manualmente, durante sua carreira profissional. Existem diversas técnicas bastante conhecidas, utilizando
estruturas de dados variadas. Observe o pseudocódigo a seguir:
 
1 - Busca(arranjo A, elemento chave)
2 - Para i <- 0 até comprimento[A] - 1 faça
3 - Se A[i] = chave então
4 - retorne i
5 - Se não, se A[i] > chave então
6 - retorne "elemento ausente"
7 - retorne "elemento ausente"
 
Com base no algoritmo de busca anterior, avalie as alternativas e assinale a afirmação correta.
ALTERNATIVAS
14/08/2021 Unicesumar - Ensino a Distância
5/6
No melhor caso, esse algoritmo executa n² operações, onde n é o tamanho do arranjo A.
Nesse algoritmo, o melhor caso ocorre quando o vetor já está ordenado.
Esse algoritmo de busca necessita que o arranjo esteja ordenado para funcionar.
Esse algoritmo tem melhor desempenho, quando aplicado em árvores.
Geralmente, a busca binária tem desempenho igual ou inferior a do algoritmo de busca acima.
9ª QUESTÃO
Segundo Wirth (1989), o Shellsort é o mais eficiente, dentre os algoritmos classificados como de
complexidade quadrática. Você, enquanto programador(a), deve ter ciência das opções de algoritmos
quatrátidos que existem e, com isso, optar pela utilização de uma, ou outra técnica, dependendo das
necessidades que sua aplicação exige.
 
Adaptado de: WIRTH, K. Algoritmos e Estruturas de Dados. Rio de Janeiro: Prentice-Hall do Brasil, 1989. 
 
Tomando por base seus conhecimentos a respeito do algoritmo Shellsort, leia atentamente as alternativas e
marque a resposta correta.
ALTERNATIVAS
O Shellsort é uma otimização do algoritmo Bubblesort.
O algoritmo Shellsort necessita de vetores auxiliares para realizar ordenação.
O nome do algoritmo Shellsort se deve ao fato de ele implementar o conceito de "concha" de dados.
O conceito de GAP, utilizado no Shellsort, é uma maneira de aproximar elementos que estão muito distantes dentro
de um mesmo vetor.
Devido a sua similaridade com a busca binária, de maneira geral, o Shellsort utiliza uma estrutura em árvore para
realizar sua busca.
10ª QUESTÃO
A árvore como estrutura é muito utilizada para organizar informações armazenadas tanto na memória
principal como na secundária. Isso se dá devido ao fato de ser fácil e rápida a pesquisa de dados em árvores.
Já a busca binária é um dos métodos existentes para efetuar a busca em um arranjo ordenado e geralmente
é aplicada em situações nas quais é possível armazenar dados em vetor estático, em detrimento de listas
dinâmicas.
 
Adaptado de: OLIVEIRA, P. M. de.; PEREIRA, R. de. L. Estruturas de Dados II. Maringá: Unicesumar, 2019. 
 
 
Tomando por base seus conhecimentos em busca binária em vetores estáticos, avalie as afirmações que se
seguem:
 
I - Ela percorre o arranjo do seu final ao seu início, sequencialmente, em busca do valor procurado.
II -  Ela faz uso de uma fórmula especial e complexa, que leva em conta o conteúdo do vetor, para dividir o
arranjo em duas metades para poder fazer a procura.
III - Ela calcula a posição do elemento intermediário, com base nas posições do início e do fim do arranjo, e
compara o valor procurado ao elemento do meio do respectivo arranjo.
 
Com base no exposto é possível dizer que é verdadeiro o que se afirma em:
ALTERNATIVAS
14/08/2021 Unicesumar - Ensino a Distância
6/6
I, apenas.
II, apenas.
III, apenas.
I e III, apenas.
II e III, apenas.