Atividade 4 - Estrutura de dados II

Prévia do material em texto

08/09/2021 13:25 Unicesumar - Ensino a Distância
1/9
ATIVIDADE 4 - ENG SOFT - ESTRUTURA DE DADOS II - 52/2021
Período:05/07/2021 08:00 a 19/07/2021 23:59 (Horário de Brasília)
Status:ENCERRADO
Nota máxima:1,00
Gabarito:Gabarito será liberado no dia 20/07/2021 00:00 (Horário de Brasília)
Nota obtida:0,40
1ª QUESTÃO
Considere a representação de árvore binária a seguir: 
 
De acordo com Oliveira e Pereira (2019), o percurso em-ordem visita primeiramente toda a subárvore
esquerda e, só então, a raiz é marcada como visitada, para em seguida percorrer toda a subárvore direita. 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Com base no excerto acima, assinale a alternativa que expressa o resultado do caminhamento em ordem na
figura apresentada. 
ALTERNATIVAS
17, 20, 23, 25, 40, 41, 46, 47, 48, 55.
17, 20, 25, 23, 40, 41, 46, 47, 48, 55.
40, 23, 47, 20, 17, 46, 41, 55, 25, 48.
40, 23, 47, 20, 46, 55, 17, 25, 41, 48.
55, 48, 47, 46, 41, 40, 25, 23, 20, 17.
2ª QUESTÃO
08/09/2021 13:25 Unicesumar - Ensino a Distância
2/9
Segundo Tanenbaum (1995, p. 303), á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 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. 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Analise as afirmações sobre árvore binária: 
I - Nem os nós da direita nem os da esquerda podem possuir valores superiores ao nó do pai. 
II - Todos os nós devem ter estritamente 0 ou 2 nós filhos, como forma de manter a árvore balanceada.  
III – Ao ser implementada em um vetor, as posições devem ser reservadas de acordo com o nível e
descendência e distância de cada nó pai e raiz. 
IV - Só podem ser implementadas através de alocação dinâmica, devido à impossibilidade de determinar a
quantidade de elementos que a árvore terá. 
É correto o que se afirma em: 
ALTERNATIVAS
I, apenas.
III, apenas.
I e II, apenas.
I, II e III, apenas.
I, II e IV, apenas.
3ª 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
08/09/2021 13:25 Unicesumar - Ensino a Distância
3/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; 
}; 
4ª QUESTÃO
08/09/2021 13:25 Unicesumar - Ensino a Distância
4/9
A busca sequencial é de longe a forma mais simples de pesquisa. Ela pode ser utilizada tanto para o caso
em que a tabela está armazenada num vetor como numa lista ligada.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Leia as afirmativas, a seguir, sobre o mecanismo de busca sequencial.
 
I. O processo de varredura do vetor ou lista começa na sua última posição.
II. A busca retornará a posição do vetor ou lista em que o valor de procura foi encontrado.
III. Em cada posição do vetor ou lista é realizada uma comparação entre o valor do elemento e o valor sendo
procurado.
IV. Caso o valor de procura não tenha sido encontrado, a busca repete o processo de procura no vetor ou
lista até encontrá-lo.
 
É correto o que se afirma em:
ALTERNATIVAS
I e III, apenas.
II e III, apenas.
II e IV, apenas.
II e IV, apenas.
I, III e IV, apenas.
5ª QUESTÃO
Observe a imagem a seguir, que representa uma árvore. 
 
Analise as afirmações a seguir e assinale a correta. 
ALTERNATIVAS
08/09/2021 13:25 Unicesumar - Ensino a Distância
5/9
A altura dessa árvore é 3.
O nó 8 é a raiz dessa árvore.
O nó 7 é um ancestral do nó 2.
A figura representa uma árvore binária.
O nó 11 é um descendente direto do nó 4.
6ª 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.
7ª QUESTÃO
A maioria dos métodos de busca realizam a comparação de elementos do arranjo, dois a dois, para procurar
a chave de busca. Todavia, a estrutura de dados Hash foi pensada para eliminar a necessidade de realizar
comparações durante as buscas por dados. Existe uma maneira de realizar um cálculo que indica
exatamente (ou quase) a posição do elemento chave dentro do vetor de dados, sem realizar comparações. É
como se, a partir da chave de busca, fosse possível aferir o índice da posição no qual o elemento igual
àquela chave se encontra em um vetor.
 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019.
 
Assinale a alternativa que apresenta uma desvantagem do hashing ou endereçamento de hash, como
técnica utilizada nas estruturas de armazenamento.
ALTERNATIVAS
08/09/2021 13:25 Unicesumar - Ensino a Distância
6/9
Exigirá uma estruturação pai/filho.
Tornará as atualizações mais lentas.
Será necessário descompactar os dados.
Sempre existirá a possibilidade de colisões.
Ocupará mais espaço do que um índice denso.
8ª 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
I e II, apenas.
I e III, apenas.
II e III, apenas.
II e IV, apenas.
III e IV, apenas.
9ª QUESTÃO
08/09/2021 13:25 Unicesumar - Ensino a Distância
7/9
A forma como os elementos são inseridos em uma árvore binária de busca pode fazer com que a busca se
torne altamente ineficiente. Para melhorar a eficiência, surge o conceito de balanceamento.
Conceitualmente, uma árvore balanceadatende 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. 
Nesse contexto, considere a árvore AVL a seguir: 
 
O conceito de balanceamento está relacionado à altura das subárvores que compõem uma árvore binária. A
altura (ou profundidade) de uma subárvore é igual ao número de nós visitados desde a raiz até o nó folha
mais distante (uma subárvore vazia possui altura -1, por definição). Assim sendio, um nó está balanceado
caso o valor absoluto da diferença entre as alturas das subárvores esquerda e direita seja menor ou igual a
1. 
OLIVEIRA, P. M.; PEREIRA, R. L. Estrutura de Dados II. Maringá-Pr.: Unicesumar, 2019. 
Agora, considere a inserção de um novo nó contendo o valor 200. Em seguida, execute o percurso em pré-
ordem. Assinale a alternativa resultante desse percurso. 
ALTERNATIVAS
64, 73, 88, 92, 97, 99, 109, 200
73, 88, 64, 97, 92, 99, 109, 200
88, 64, 73, 99, 97, 92, 109, 200
88, 73, 64, 200, 109, 99, 97, 92
92, 73, 64, 88, 99, 97, 109, 200
10ª QUESTÃO
08/09/2021 13:25 Unicesumar - Ensino a Distância
8/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
08/09/2021 13:25 Unicesumar - Ensino a Distância
9/9