ESTRUTURA DE DADOS AULA 4

Prévia do material em texto

Teste de
Conhecimento
 
 
 avalie sua aprendizagem
 ESTRUTURA DE DADOS
4a aula
 Lupa 
 
 
Qual papel do for mais interno na função ordena abaixo ?
void ordena( int n, int v[])
{
 int i, j, x;
 for (j = 1; j < n; ++j) {
 x = v[j];
 for (i = j-1; i >= 0 && v[i] > x; --i) 
 v[i+1] = v[i];
 v[i+1] = x;
 }
}
Encontrar o elmento a ser eliminado do vetor
Encontrar o valor de v[j] deve em v[0..j-1].
Encontrar o maior valor de x que deve ser inserido em v[0..j-1].
Encontrar o menor valor v[j] que deve ser inserido em v[0..j-1].
 Encontrar o ponto onde v[j] deve ser inserido em v[0..j-1].
Gabarito
Comentado
 
 
O processo de rearranjar um conjunto de dados em uma ordem crescente ou decrescente é chamado de ordenação.
Existem várias técnicas de ordenação, entretanto a técnica que procura o menor valor entre todos os elementos do vetor
e troca-o pelo primeiro elemento; para os n - 1 elementos restantes, determinação do elemento de menor valor e troca
pelo segundo elemento e assim sucessivamente, é chamado de:
 Seleção
Binária
Inserção
Hash
Bolha
Gabarito
Comentado
 
 
 Questão1
 Questão2
3
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
Para consultarmos uma estrutura de dados, normalmente, empregamos um tipo de pesquisa de dados. O trecho de
programa a seguir refere-se a uma pesquisa por um elemento único (sua primeira ocorrência), em um conjunto de
elementos de dados armazenado em uma estrutura de acesso indexado e aleatório. Selecione a opção correspondente ao
algoritmo utilizado, no programa, para a referida pesquisa:
int busca(float v[], float valor, int n) {
int ini = 0, fim = n -1, meio;
while (ini <= fim) {
meio = (ini + fim)/2;
if (v[meio] == valor) return meio;
if (valor < v[meio]) fim = meio -1;
 else ini = meio+1;
}
return -1;
}
pesquisa indexada
pesquisa de cadeias
 pesquisa binária
pesquisa cadeias indexada
pesquisa sequencial
Gabarito
Comentado
 
 
Marque a afirmativa correta para a "Ordenação em Listas Lineares Sequenciais".
Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos.
Consiste em fazer uma busca em um vetor já ordenado, dividindo o espaço de busca ao meio e verificando se o
dado está no meio ou, antes do meio ou depois do meio.
Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
 É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente.
Consiste em fazer uma busca em um vetor desordenado, dividindo o espaço de busca ao meio e verificando se o
dado está no meio ou, antes do meio ou depois do meio.
Gabarito
Comentado
 
 
Marque a afirmativa correta para a "inserção incremental".
 Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
Os pivôs são escolhidos aleatoriamente.
A técnica é boa quando os dados ficam uniformemente distribuídos entre os seus compartimentos.
É um tipo de ordenação por intercalação
É um tipo de sequenciação por intercalação.
Gabarito
Comentado
 
 
 Questão
 Questão4
 Questão5
 Questão
6
Caso seja empregada uma busca binária em uma lista sequencial ordenada com 2048 valores, qual seria o número
máximo de comparações para encontrar um valor que esteja na lista?
12
 11
10
9
8
 
 
Explicação:
Como a busca binária sai continuamente dividindo o conjunto de dados ao meio (em duas partes), então vamos fatorar e
organizar o resultado como potência de base 2.
 Fatorando 2048 temos 2 11
 Portanto, a resposta é 11.
 
 
"Algoritmo de ordenação por trocas que varre um vetor um certo número de vezes, comparando os elementos vizinhos
dois a dois. A cada varredura, se o par de elementos está em ordem crescente, nada é feito, caso contrário os elementos
do par são permutados". Esta definição está descrevendo o algoritmo de ordenação conhecido por :
InsertionSort
QuickSort
 BubbleSort
MergeSort
SelectionSort
 
 
Explicação:
Das opções apresentadas, as únicas que são ordenações por troca são
Bubblesort e Quicksort.
Dessas duas ordenações, a única que trabalha com duplas de elementos
 vizinhos é o Bubblesort. O Quicksort, que está fora do escopo da disciplina,
trabalha com pivô.
 
 
Sabendo-se que o método de seleção também é um método de ordenação que baseia seu algoritmo em trocas entre os
elementos de um vetor, se submetermos a sequencia de inteiros armazenada em um vetor inicialmente na seguinte
ordem : 13, 23, 3, 8, 1. Pode-se dizer que quando o menor elemento do vetor alcançar sua posição final, a ordenação
apresentada no vetor é:
1,23,13,8,3
1,3,23,8,13
1,13,23,8,3
 1,23,3,8,13
1,8,3,23,13
Gabarito
Comentado
 
 
 
 Questão7
 Questão8
javascript:abre_colabore('38403','187205819','3732610496');