ATV 03 Estrutura de DADOS II

Prévia do material em texto

ATIVIDADE 3 - ADS - ESTRUTURA DE DADOS II - 2018B2
Período:03/07/2018 22:30 a 08/07/2018 23:59 (Horário de Brasília)
Status:ABERTO
Nota máxima:0,50
Gabarito:Gabarito será liberado no dia 09/07/2018 00:00 (Horário de Brasília)
Nota ob�da:
1ª QUESTÃO
O algoritmo de busca em profundidade em grafos conexos faz com que todo um segmento do grafo seja
visitado até o final, antes que uma nova porção seja investigada.
  
PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).
 
 
Baseado em nosso livro de estudo, leia as afirmativas a seguir sobre os passos do algoritmo de busca em
profundidade e assinale a alternativa correta.
 
I - A partir do último nó do grafo, o algoritmo monta uma pilha com os vértices adjacentes.
 II - Após percorrer os seus vértices adjacentes, o nó em processamento é marcado como visitado.
 III - Uma vez formada a pilha de nós, o algoritmo pega o último nó empilhado e repete o processo de
percorrê-lo.
 IV - O processamento do algoritmo termina quando o valor procurado é encontrado no grafo ou a pilha fica
vazia, o que significa que todos os nós foram percorridos e o valor não foi encontrado no grafo.
ALTERNATIVAS
Apenas I e II estão corretas.
Apenas II e III estão corretas.
Apenas II e IV estão corretas.
Apenas I, II e III estão corretas.
Apenas I, II e IV estão corretas.
2ª QUESTÃO
A coisa não está fácil para ninguém. A crise chegou, mas o brasileiro é muito bom em usar a criatividade para
amenizar as dificuldades. Marilsa acha que o melhor, num momento como este, é pagar as contas menores e
deixar vencer as contas maiores. Assim, você fica devendo para menos gente e fica mais fácil renegociar as
coisas, lá na frente. Ela colocou todas as contas em cima da mesa, uma ao lado da outra. Ela olhou uma por
uma, procurando a de menor valor. Retirou a conta daquele local e colocou numa pasta. Em seguida, ela
procurou a segunda menor conta e foi repetindo o processo até que todas as contas estivessem ordenadas
na pasta da menor para a de maior valor. Que algoritmo de ordenação foi utilizado pela Marilsa?
ALTERNATIVAS
BubbleSort.
SelectSort.
MergeSort.
QuickSort.
ShellSort.
3ª QUESTÃO
Um programador necessitava realizar a ordenação de um arranjo em seu código, para que certa
funcionalidade de busca obtivesse ganho em desempenho. Para isso, o desenvolvedor intuitivamente
desenvolveu o código em C, apresentado abaixo.
             
Assinale a alternativa que corresponde ao algoritmo implementado pelo programador.
 
ALTERNATIVAS
Ordenação por flutuação, BubbleSort.
Ordenação por inserção, InsertionSort.
Ordenação por seleção, SelectionSort.
Ordenação utilizando concha, ShellSort.
Ordenação por baldes, BucketSort.
4ª QUESTÃO
O método de ordenação MergeSort é um classificado como um algoritmo que utiliza a abordagem dividir para
conquistar. Ele recebe um vetor desordenado e divide-o sucessivamente em duas partes, de forma recursiva,
até que seja todo dividido em partes unitárias. Em seguida, o algoritmo utiliza uma função para juntar estas
partes.
 
Assinale a alternativa, que corresponde sobre como a função é executada para ordenar os elementos no
vetor.
ALTERNATIVAS
Ela é chamada antes de dividir o vetor em duas partes.
Variáveis do tipo int, float e double são utilizadas em seu processamento.
A função utiliza o método da bolha em seu processamento para ordenar os pedaços sendo juntados.
A função executa um procedimento alternativo caso não seja possível alocar memória para o vetor temporário.
Em cada recursão, é necessária a criação de um vetor temporário para armazenar os valores já comparados e
ordenados.
5ª QUESTÃO
Foi solicitado para que você faça a manutenção num sistema de gerenciamento de dados e, após alguma
análise, você percebeu que a técnica de ordenação usa uma variável chamada GAP. Sabendo que mais
detalhes sobre essa técnica facilitará muito o seu trabalho, qual é o nome do algoritmo de ordenação que
possui uma variável chamada GAP, utilizada para fragmentar a massa de dados em regiões menores, onde é
aplicado a ordenação por inserção?
 
Assinale a alternativa correta.
ALTERNATIVAS
Quicksort.
MergeSort.
ShellSort.
SelectSort.
InsertionSort.
6ª QUESTÃO
Uma árvore binária é uma estrutura de dados que possui regras bem rígidas em sua formulação que têm a
ver com a quantidade de nós, raízes e subárvores. Uma árvore binária de busca é um tipo especial de árvore
binária que leva em conta outras regras na sua elaboração. Considerando que a imagem abaixo representa
uma árvore binária de busca, onde poderíamos inserir o valor 40?
  
ALTERNATIVAS
À direita do número 44.
À esquerda do número 33.
À esquerda do número 44.
À direita do número 33, entre 33 e 44.
À esquerda do número 55, entre o número 55 e o número 11.
7ª QUESTÃO
Os métodos de ordenação BubbleSort, SelectionSort e InsertionSort são classificados como algoritmos de
complexidade quadrática. Contudo, o InsertionSort possui uma pequena diferença em sua execução, a qual
afeta o desempenho em comparação com os outros dois métodos.
 
Assinale a alternativa que apresenta está diferença.
ALTERNATIVAS
Ele tem a capacidade de ordenar matrizes, além de vetores.
Ele aplica uma junção otimizada dos métodos BubbleSort e SelectionSort.
Ele não precisa percorrer os dois laços de repetição por inteiro.
Ele processa os dois laços de repetição de forma paralela, otimizando tempo.
Ele "descarta" elementos já posicionados corretamente no vetor, processando apenas o restante.
8ª QUESTÃO
Um dos algoritmos de ordenação mais eficientes chama-se QuickSort. Abaixo é apresentado o código de um
programa em linguagem C, que implementa essa técnica de ordenação.
 
Tomando por base seus conhecimentos a respeito do algoritmo QuickSort e no código fonte acima, avalie as
afirmações abaixo:
I –   Ao alterar a comparação do comando if, na linha 3, mudando de “right > left” para “right < left”, tem-se
a ordenação em ordem decrescente.
 II –  A função “particiona” da linha 4 é responsável por realizar a junção das partições do vetor de maneira
ordenada.
 III – A função “particiona” recebe como parâmetros os valores “left” e “right”, que indicam as posições inicial e
final, respectivamente, do arranjo a ser particionado.
 IV – Ao se inverter as linhas 5 e 6, o algoritmo realiza a ordenação de maneira decrescente.
É correto o que se afirma em:
 
ALTERNATIVAS
I e II, apenas.
I e III, apenas.
II e III, apenas.
II e IV, apenas.
I, II e IV, apenas.
9ª QUESTÃO
Imagine que você é um motoboy e deve realizar uma entregar em um bairro na sua cidade. Pode-se utilizar o
algoritmo de Dijkstra para encontrar o melhor caminho até o seu destino. Identifique, dentre as aplicações
listadas nas afirmativas abaixo, em quais delas o algoritmo de Dijkstra também se aplica, para encontrar uma
solução.
I –   Determinar qual o roteiro mais curto em roteamento de pacotes da internet.
 II –  Encontrar o resultado de uma expressão aritmética.
 III – Realizar a impressão de uma progressão geométrica por um programa.
 IV – Encontrar um caminhamento de custo mínimo em um grafo que possui arestas com peso negativo.
São aplicações do algoritmo de Dijkstra:            
ALTERNATIVAS
I, apenas.
II, apenas.
I e III, apenas.
I, II e IV, apenas.
I, II, III e IV.
10ª QUESTÃO
O algoritmo de busca em largura em grafos conexos percorre primeiramente todos os nós mais próximos do
nó atual, depois os menos distantes, os mais distantes e assim por diante.
 
 
PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).
 
 
Assinale a alternativa correta referente à estrutura de dados utilizada no algoritmo de busca em largura.
ALTERNATIVAS
Fila.
Pilha.
Vetor.
Matriz.
Lista encadeada.