ATIVIDADE 4 - ENG SOFT - ESTRUTURA DE DADOS II - 52-2020

Prévia do material em texto

28/06/2020 Unicesumar - Ensino a Distância
1/9
ATIVIDADE 4 - ENG SOFT - ESTRUTURA DE DADOS II - 52/2020
Período:15/06/2020 08:00 a 30/06/2020 23:59 (Horário de Brasília)
Status:ABERTO
Nota máxima:0,50
Gabarito:Gabarito será liberado no dia 01/07/2020 00:00 (Horário de Brasília)
Nota obtida:
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. 
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
 
 
De acordo com a definição acima, assinale a alternativa que implementa em linguagem C a estrutura de
uma árvore binária dinâmica.
ALTERNATIVAS
28/06/2020 Unicesumar - Ensino a Distância
2/9
struct str_no { 
 int v; 
 struct str_no *a; 
};
struct str_no { 
 int v; 
 struct str_no *a; 
 struct str_no *b; 
}; 
struct str_no { 
 int v; 
 struct str_no *a; 
 struct str_no *b; 
 struct str_no *c; 
}; 
struct str_no { 
 int v; 
 int *a; 
 int *b; 
 int *c; 
}; 
struct str_no { 
 int v; 
 int a; 
 int b; 
 int c; 
}; 
2ª QUESTÃO
28/06/2020 Unicesumar - Ensino a Distância
3/9
Para inserir um nó na árvore, eu preciso saber o seu valor, quem é o seu pai e se ele é um filho esquerda ou
direita. Mesmo sabendo quem é o pai, antes de fazer a inserção no vetor eu preciso encontrar a sua
localização. O conceito de balanceamento. Dizemos que uma árvore balanceada tende a manter sua altura
tão pequena quanto possível, à medida em que são realizadas novas inserções ou remoções de dados. 
 
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
 
 
Considere o seguinte conjunto de dados: 15, 75, 58, 37, 67, 54, 51, 43. Levando em conta a ordem dos
elementos recém apresentados, monte uma árvore binária de busca. 
ALTERNATIVAS
28/06/2020 Unicesumar - Ensino a Distância
4/9
3ª QUESTÃO
Para os métodos de pesquisa de grandes quantidades de dados em busca de uma determinada informação,
a organização desses dados torna o processo de busca mais eficiente. A operação de busca é uma tarefa
muito comum e de suma importância na ciência da computação. A busca por interpolação é outra forma de
pesquisar em vetores com dados ordenados. 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Analise as assertivas a seguir: 
I, Divide a região de busca usando uma equação matemática mais complexa.  
II. Essa técnica só funciona se os dados no arquivo estiverem distribuídos de maneira uniforme. 
III. Realiza um cálculo que indica a posição exata do elemento chave dentro do arranjo de dados, sem
realizar comparações. 
IV. A partir da chave de busca é possível aferir o índice da posição no qual o elemento igual àquela chave se
encontra em um vetor. 
É correto o que se afirma em: 
ALTERNATIVAS
I e II, apenas.
I e III, apenas.
I e IV, apenas.
II e III, apenas.
II, III e IV, apenas.
4ª QUESTÃO
28/06/2020 Unicesumar - Ensino a Distância
5/9
A operação de busca sequencial percorre a partir da primeira posição ou do primeiro nó da lista,
comparando o valor atual da estrutura com o argumento a ser procurado. Esse procedimento se repete até
que o valor desejado seja encontrado ou atinja o final da estrutura.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Observando o código a seguir:
 
int buscaSequencial(int vec
, int arg, int tam){
   int i = 0, achou = -1;
   while ((i < tam) && (achou == -1)){
      if (vec
i
==arg){
         achou = i;
      }
      i++;
   }
   return(achou);
}
 
Assinale a alternativa correta referente ao que acontece quando o valor procurado é encontrado em dois ou
mais elementos do vetor.
ALTERNATIVAS
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 retorna a posição no vetor onde o último valor correspondente foi encontrado.
A busca retorna a posição no vetor onde o primeiro valor correspondente foi encontrado.
A busca aguarda o usuário escolher dentre as posições onde o valor procurado foi encontrado.
5ª QUESTÃO
28/06/2020 Unicesumar - Ensino a Distância
6/9
A função hash deve ser capaz de converter um dado, ou um conjunto de dados, em um índice, que é a
posição na qual tais dados serão armazenados.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Diante da definição, considere um arquivo sequencial, com 10.000 registros, cujas chaves identificadoras são
números inteiros de até 8 dígitos. Para criar um índice tipo hashing para esse arquivo, contendo endereços
de 0 até 11.999, a definição mais adequada para uma função de hashing f(x), onde x é uma chave e (a % b) é
o resto da divisão de a por b, seria _______________.
 
Assinale a função que completa corretamente a lacuna.
ALTERNATIVAS
f = x / 10000
f = x / 11999
f = x % 12000
f = x % 1000 + 12
f = (x ? 11999) /10000
6ª QUESTÃO
A operação de busca é uma tarefa muito comum na ciência da computação, o conhecimento desses
métodos é de suma importância para todo o profissional que deseja se tornar um bom programador.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Diante desse contexto, avalie as afirmações sobre busca em estruturas de dados:
 
I. A busca por interpolação não requer que o vetor esteja ordenado.
II. A busca binária em vetores tem velocidade muito superior à busca em árvore binária.
III. A busca por interpolação pode ser tão lenta quanto à busca sequencial. Já a busca binária jamais será
inferior à busca sequencial.
IV. 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.
 
É correto o que se afirma em:
ALTERNATIVAS
28/06/2020 Unicesumar - Ensino a Distância
7/9
I e II, apenas.
I e III, apenas.
II e III, apenas.
II e IV, apenas.
III e IV, apenas.
7ª 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
A estrutura ou arranjo deve ter seus dados ordenados.
Os dados do vetor ou estrutura devem ser do tipo char.
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.
8ª QUESTÃO
A técnica de busca sequencial indexada consiste em criar uma tabela auxiliar ao arquivo de dados. Nessa
tabela, deve constar pelo menos dois campos: a chave de busca e o endereço do registro na tabela original.
A tabela de índice pode ser ordenada de forma ascendente, descendente ou de qualquer outra forma que
seja mais compatível com as principais buscas que utilizarão a chave contida na tabela auxiliar.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
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}, quantas iterações que a busca sequencial indexada fará para tentar encontrar o número 30 antes
de concluir a operação como malsucedida?
 
Assinale a alternativa que responde corretamente a questão.
ALTERNATIVAS
3
5
10
13
30
28/06/2020 Unicesumar - Ensino a Distância
8/9
9ª QUESTÃO
Considere uma tabela hash com as seguintes características:
1. As chaves são as letras A, B, C, D, H, J, K, M, N, O, P, R, S, T, U;
2. A tabela possui 11 posições, referenciadas pelos índicesde 0 até 10;
3. A função de hash é definida como hash(x)=posição(x) % 11 onde x é a chave, e posição(x) é a posição da
chave no alfabeto ABCDEFGHIJKLMNOPQRSTUVWXYZ, tal que posição(“A”) retorna 1 e posição(“Z”) retorna
26.
 
Analise as afirmativas sobre a tabela após seu preenchimento com as chaves listadas acima.
I. A chave “K” foi alocada à posição zero;
II. Nenhuma chave foi alocada à posição 6;
III.Apenas uma letra foi alocada à posição 9;
 IV. As chaves “B” e “N” colidiram na posição 3.
 
Está correto o que se afirma em:
ALTERNATIVAS
I e II, apenas.
I e III, apenas.
I, II e III, apenas.
I, III e IV, apenas.
II, III e IV, apenas.
10ª QUESTÃO
Estudar os métodos de como pesquisar grandes quantidades de dados em busca de uma determinada
informação é uma tarefa muito comum na ciência da computação, e de suma importância para todo bom
programador.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Tomando como base os métodos de busca estudados, o produto da ação de algoritmos que fazem o
mapeamento de uma sequência de bits de tamanho arbitrário para uma sequência de bits de tamanho fixo
menor, com resistência à colisão e cujo processo reverso também não seja realizável, denomina-se
____________.
 Assinale a alternativa que completa corretamente a afirmação acima.
ALTERNATIVAS
28/06/2020 Unicesumar - Ensino a Distância
9/9
token linear.
resultado hash.
cifra sequencial.
mensagem binária.
cadeia de interpolação.