ATV Estrutura de dados 4

Prévia do material em texto

16/05/2019 Unicesumar - Ensino a Distância
1/5
ATIVIDADE 4 - ENG SOFT - ESTRUTURA DE DADOS II - 2018B2
Período:26/06/2018 22:30 a 03/07/2018 23:59 (Horário de Brasília)
Status:ENCERRADO
Nota máxima:0,50
Gabarito:Gabarito será liberado no dia 05/07/2018 00:00 (Horário de Brasília)
Nota obtida:0,40
1ª QUESTÃO
Uma árvore binária é um conjunto finito de elementos que está vazio ou é particionado em três
subconjuntos disjuntos. O primeiro subconjunto contém um único elemento, chamado raiz da árvore. Os
outros dois subconjuntos são em si mesmos árvores binárias, chamadas subárvores esquerda e direita da
árvore original. Uma subárvore esquerda ou direita pode estar vazia. Cada elemento de uma árvore binária é
chamado nó da árvore (TENEMBAUM, 1995).
 TENENBAUM, Aaron M. et al. Estruturas de dados usando C. São Paulo: Makron Books, 1995.
 
Assinale a alternativa referente à estrutura de dados, onde sua composição pode ser considerada com uma
árvore binária.
ALTERNATIVAS
Vetor.
Matriz.
Registro.
Pilha.
Grafo.
2ª QUESTÃO
O algoritmo de Dijkstra foi publicado em 1958 e tem como objetivo solucionar o problema do caminho mais
curto entre dois vértices em grafos conexos com arestas de pesos não negativos.
 
Assinale a alternativa correta referente ao apelido dado à estratégia usada no algoritmo de Dijkstra.
ALTERNATIVAS
Método da bolha.
Abordagem cavalo de tróia.
Algoritmo guloso.
Abordagem dividir para conquistar.
Algoritmo de complexidade quadrática.
3ª QUESTÃO
A busca em largura percorre um grafo na ordem de seus níveis de profundidade, isto é, começa da raiz
(nível 0), vai para o nível 1, depois o nível 2 e assim por diante, até o último nível de profundidade do grafo.
 
Assim sendo, assinale a alternativa correta referente ao tipo de estrutura usado na busca em largura.
ALTERNATIVAS
16/05/2019 Unicesumar - Ensino a Distância
2/5
Vetor.
Matriz.
Fila.
Pilha.
Lista encadeada.
4ª QUESTÃO
A busca em profundidade percorre um grafo pelos seus nós esquerdos até a sua extermidade e em seguida
vai voltando os nós para percorrer seus lados direitos. Para implementar esse mecanismo de procura, um
tipo específico de estrutura de dados é usado.
 
Assinale a alternativa correta referente a esse tipo de estrutura.
ALTERNATIVAS
Vetor.
Matriz.
Fila.
Pilha.
Lista encadeada.
5ª QUESTÃO
Um desenvolvedor de software certamente terá de implementar algum método de busca, durante sua
carreira profissional. Existem diversas técnicas bastante conhecidas, utilizando estruturas de dados variadas.
  
PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).
 
 
Avalie as afirmações sobre busca em estruturas de dados e assinale a alternativa correta.
I – A busca linear indexada é uma otimização da busca linear simples. Quando se encontra um valor maior
do que o valor alvo, o algoritmo para, identificando que o alvo não se encontra no vetor.
II – A busca por interpolação não requer que o vetor esteja ordenado.
III – A busca binária em vetores tem velocidade muito superior à busca em árvore binária.
IV – A busca por interpolação pode ser tão lenta quanto à busca sequencial. Já a busca binária jamais será
inferior à busca sequencial.         
ALTERNATIVAS
Apenas as alternativas I e II estão corretas.
Apenas as alternativas II e III estão corretas.
Apenas as alternativas I e IV estão corretas.
Apenas as alternativas I, II e III estão corretas.
Apenas as alternativas I, III e IV estão corretas.
16/05/2019 Unicesumar - Ensino a Distância
3/5
6ª QUESTÃO
Algumas técnicas de busca exigem que o conjunto de dados esteja ordenado para que haja eficiência na
procura por um elemento pertencente a esse conjunto.
  
PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).
 
 
Avalie as afirmativas sobre os algoritmos BubbleSort e SelectionSort e assinale a alternativa correta.
I – A técnica de ordenação BubbleSort também é conhecida por ordenação por flutuação ou método da
bolha.
II – Apesar de ser uma técnica de simples implementação, o SelectionSort possui alto consumo
computacional.
 III – O método SelectionSort seleciona e ordena um elemento arbitrário do arranjo e, então, chama a si
mesmo recursivamente, para ordenar uma porção menor do arranjo.
IV – Ambos, SelectionSort e BubbleSort, estão entre os piores desempenhos entre os algoritmos de
ordenação existentes.
ALTERNATIVAS
Apenas a alternativa I está correta.
Apenas a alternativa II está correta.
Apenas as alternativas I e III estão corretas.
Apenas as alternativas II e III estão corretas.
Apenas as alternativas I, II e IV estão corretas.
7ª QUESTÃO
Cada algoritmo de ordenação possui suas particularidades. Dependendo da maneira que se encontram
distribuídos os dados no arranjo, pode ser que haja diferença no tempo de execução dos algoritmos.
  
PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).
 
Avalie as afirmativas sobre algoritmos de ordenação a seguir.
  
 I. -    O InsertionSort também é conhecido como método de ordenação por inserção.
 II. -   Assim como o BubbleSort, o InsertionSort também utiliza a função "troca" para realizar a ordenação
dos elementos.
 III. -  Do mesmo modo que o SelectionSort, o algoritmo InsertionSort possui dois laços de repetição
aninhados, sugerindo lentidão na execução.
 IV. -  Pelo fato de possuir dois laços de repetição aninhados, o InsertionSort não é capaz de ser mais veloz
que os algoritmos SelectionSort e BubbleSort.
 V.  -  O InsertionSort não é um algoritmo inerentemente recursivo.
  
 É correto o que se afirma em:
  
16/05/2019 Unicesumar - Ensino a Distância
4/5
ALTERNATIVAS
I, apenas.
I, e II, apenas. 
I, II, III, apenas.
I, II, III e V, apenas.
I, II, III, IV e V.
8ª QUESTÃO
Para se ganhar em desempenho, algumas soluções recursivas apresentam melhores resultados, em
detrimento de soluções iterativas. O QuickSort é uma alternativa de ordenação de vetores que emprega
recursividade.
 
 
PEREIRA, Rogério de Leon. Estruturas de Dados II. Maringá: Unicesumar, 2018. (Adaptado).
 
 
Sobre esse algoritmo, avalie as afirmativas e marque a alternativa correta.
I – O algoritmo denominado QuickSort também é conhecido por classificação por troca de partição.
II – Assim como o MergeSort, o QuickSort emprega a estratégia “dividir para conquistar”.
III – A função, que realiza a escolha do pivô em nada, se assemelha à técnica de busca com árvore binária,
pois não faz distinção entre os valores dos elementos.
 
IV – O QuickSort é o algoritmo de ordenação mais veloz que existe. Nenhum outro algoritmo consegue
bater sua velocidade, independente da instância do problema.
ALTERNATIVAS
Apenas as alternativas I e II estão corretas.
Apenas as alternativas I e III estão corretas.
Apenas as alternativas II e III estão corretas.
Apenas as alternativas II e IV estão corretas
Apenas as alternativas I, II e IV estão corretas.
9ª QUESTÃO
A utilização de um vetor para guardar o valor dos nós e de uma estrutura, é implementado  para montar
uma árvore binária, sendo uma das duas principais formas de implementação de em linguagem C.
 
Com base no livro de estudo, assinale a alternativa referente à outra forma de se implementar árvores
binárias, sem o uso de um vetor para guardar o valor dos nós.
 
ALTERNATIVAS
16/05/2019 Unicesumar - Ensino a Distância
5/5
Por meio de grafos fechados.
Utilizando uma pilha de valores aleatórios.
Armazenando os nós em um arquivo em disco.
Implementação de uma matriz de transformação.
Criando dinamicamente os nós e referenciando seu pai, filhos esquerdo e direito por meio de ponteiros.
10ª QUESTÃO
As árvores estritamente binárias caracterizam-se porpossuir sempre dois subconjuntos (nós esquerdo e
direito), sendo que os nós finais (folhas) não possuem subconjuntos. Com isto, é possível determinar a
quantidade de nós existentes a partir do número de folhas e vice-versa.
 
Dada uma árvore estritamente binária com 131 nós, assinale a alternativa correta referente ao
número de folhas que ela contém.
ALTERNATIVAS
66.
67.
132.
133.
263.