Prova Estrutura de Dados II - Unigran

Prévia do material em texto

GABARITO
Protocolo: 847271
Página 1 - 04/06/2024 às 15:50
Prova
Data de aplicação: 13/03/2024
Curso: Engenharia de Software
Disciplina: Estrutura de Dados II
Ano: 20241 / Semestre: 4
RGM: 123.1478 / Aluno: GILVAN GABRIEL CORREIA DE ALENCAR
PROVA 01
Questão 1
Em uma tabela hash com colisões resolvidas por encadeamento fechado, contendo 09 posições, quantas
colisões irão ocorrer sobre o conjunto de chaves {5, 28, 19, 15, 33, 12, 17, 10}? O mapeamento das chaves é
realizado por meio da função hash h(k) = k mod 9.
Resposta do aluno: irão ocorrer 3 colisões 0= 5 1= 28 - 19 - 10 2= 3= 12 4= 5= 6= 15 - 33 7= 8= 17 9=
Parecer do professor: Correto!
Questão 2
Dada a árvore abaixo, apresente quais são os nós folhas da árvore.
Resposta do aluno: 2,5,7
Parecer do professor: Correto!
Questão 3
Uma estrutura de dados que possui dois campos: um ponteiro e campo de informação denomina-se:
a) lista encadeada dupla.
b) lista encadeada simples. (correta)
c) pilha.
d) árvore binária.
e) vetor.
Questão 4
A estrutura de dados que consiste no armazenamento de cada elemento em um endereço calculado a partir da
aplicação de uma função sobre a chave de busca denomina-se:
GABARITO
Protocolo: 847271
Página 2 - 04/06/2024 às 15:50
a) lista encadeada.
b) tabela hash. (correta)
c) árvore AVL.
d) árvore B.
e) árvore binária.
Questão 5
Suponha que temos números entre 1 e 1000 em uma árvore de pesquisa binária e queremos procurar pelo
número 363. Quais das sequências a seguir não poderia ser uma sequência de nós examinados?
a) 2, 252, 401, 398, 330, 344, 397, 363.
b) 994, 220, 911, 244, 798, 258, 362, 363.
c) 925, 202, 911, 240, 912, 245, 363. (correta)
d) 2, 399, 387, 219, 266, 382, 381, 278, 363.
e) 935, 278, 347, 621, 299, 392, 358, 363.
Questão 6
A busca binária é conhecida também como busca logarítmica. Sobre a busca binária, assinale a alternativa
INCORRETA.
a) Para um conjunto de 15 elementos, ocorreria, no mínimo, 1 comparação e, no máximo, 4 comparações.
b) Quando comparada com a busca sequencial, a busca binária, há uma redução logarítmica dos elementos a
serem pesquisados.
c) Em uma sequência ordenada de forma crescente, caso o elemento procurado seja menor que o elemento do
meio, continua-se a busca com o subconjunto da direita. Em caso contrário, com o subconjunto da esquerda.
(correta)
d) Considerando uma sequência qualquer, deve-se dividir o conjunto ao meio e verificar se o elemento
procurado é igual ao elemento central.
e) Se o elemento procurado estiver entre os últimos ou não estiver no conjunto, a busca linear poderá ser mais
lenta do que a busca binária.
Questão 7
Em relação a estrutura de dados árvore, avalie se são verdadeiras (V) ou falsas (F) as afirmativas a seguir.
I O número de nível mais alto de uma árvore é conhecido como grau de uma árvore.
II Quando um nó possui grau zero, diz-se que ele é um nó terminal ou folha.
III Árvores são estruturas de dados estáticas em que os dados possuem uma ordem pré-definida, os elementos
são dispostos de acordo com uma hierarquia e existe um nó principal conhecido como raiz.
As afirmativas I, II e III são, respectivamente:
a) V, F e V.
b) V, F e F.
c) F, F e F.
d) V, V e F.
e) F, V e F. (correta)
Questão 8
Três aspectos são fundamentais no que se refere a estruturas de dados: a abstração, a distinção entre
estruturas estáticas e dinâmicas e o conceito de ponteiro. A partir dessa informação, assinale a opção correta.
a) Na estrutura do tipo fila, as inserções e remoções são executadas por uma única extremidade da estrutura,
de modo que o último elemento a entrar na estrutura é o primeiro a ser removido.
GABARITO
Protocolo: 847271
Página 3 - 04/06/2024 às 15:50
b) As pilhas, conhecidas como estruturas FIFO (first-in, first-out), possuem duas principais operações,
denominadas push e pop; a primeira insere um elemento na estrutura, a segunda remove um elemento da
estrutura.
c) Em uma tabela hash os elementos são mapeados por meio de uma função de dispersão. Na situação em que
dois o mais elementos são mapeados para uma mesma posição na tabela, situação denominada de colisão, há
necessidade de se aplicar um tratamento. (correta)
d) A estrutura do tipo matriz é conhecida como um arranjo retangular chamado arranjo homogêneo ou matriz,
em que o termo homogêneo significa que todos os elementos do arranjo são de tipos diferentes.
e) Listas, que podem ser classificadas como estrutura estática, consistem em uma coleção de elementos que
aparecem em ordem combinatória.
Questão 9
A sequência de chaves 20 – 30 – 25 – 31 – 12 – 15 – 8 – 6 – 9 – 14 – 18 é organizada em uma árvore binária de
busca. Em seguida, a árvore é percorrida em pré-ordem. Qual é a sequência de nós visitados?
a) 20 – 12 – 8 – 6 – 9 – 15 – 14 – 18 – 30 – 25 – 31 (correta)
b) 6 – 9 – 8 – 14 – 18 – 15 – 12 – 25 – 31 – 30 – 20
c) 6 – 8 – 9 – 12 – 14 – 15 – 18 – 20 – 25 – 30 – 31
d) 20 – 30 – 31 – 25 – 12 – 15 – 18 – 14 – 8 – 9 – 6
e) 6 – 8 – 9 – 14 – 15 – 18 – 12 – 25 – 30 – 31 – 20
Questão 10
Sobre as estruturas de dados conhecidas como árvores, selecione a alternativa CORRETA.
a) Uma árvore binária é aquela que tem como conteúdo somente valores binários.
b) Uma árvore é composta por duas raízes, sendo uma principal e a outra secundária.
c) As operações básicas sobre árvores são extrair-raiz e alterar-folha.
d) O percurso de uma árvore binária, conhecido como pós-ordem, visita a sub-árvore direita, depois a raiz e
depois a subárvore esquerda.
e) O percurso de uma árvore binária, conhecido como pré-ordem, visita a raiz, depois a sub-árvore esquerda e
depois a sub-árvore direita. (correta)
PROVA 02
Questão 1
Qual número de níveis da árvore de busca binária formada pela inserção das chaves 4, 1, 0, 5, 3, 7, 2, 6, 9 e 8
(nesta ordem)?
Resposta do aluno: 4 niveis
Parecer do professor: São 5 níveis
Questão 2
Na construção de uma árvore AVL a partir da inserção das chaves 20, 10, 5, 30, 25, 27 e 28 9 (nesta ordem),
quais são as rotações necessárias aplicadas para que a árvore se mantenha balanceada?
Resposta do aluno: rotação in ordem
Parecer do professor: Correto!
Questão 3
Considere que a empresa "Manausprev" armazena os nomes dos beneficiários de aposentadorias em uma
Árvore de Busca Binária. Ao se armazenar, nesta ordem, os nomes Marcos, José, Carolina, Paula, Rui, Pedro e
Maria, a Árvore de Busca Binária resultante
GABARITO
Protocolo: 847271
Página 4 - 04/06/2024 às 15:50
a) é completa.
b) tem 3 níveis para armazenar os 7 nomes.
c) possui como folhas os nomes Rui e Maria.
d) requer no máximo 3 comparações para localizar qualquer um dos 7 nomes.
e) requer no máximo 4 comparações para localizar qualquer um dos 7 nomes. (correta)
Questão 4
Seja T uma árvore balanceada do tipo AVL vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam
inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pós-ordem é:
a) 10, 8, 5, 7, 12, 11 e 13.
b) 10, 7, 5, 8, 12, 11 e 13.
c) 5, 7, 8, 10, 11, 12 e 13.
d) 5, 8, 7, 11, 13, 12 e 10. (correta)
e) 5, 10, 12, 8, 7, 11 e 13.
Questão 5
Em uma árvore de busca binária do tipo AVL, as alturas das duas sub-árvores de um nó qualquer diferem em no
máximo 1. A construção de uma árvore desse tipo, inicialmente vazia, por meio da inserção sucessiva de nós,
utiliza uma certa operação para manter o balanceamento desejado quando necessário. Essa operação é:
a) empilhamento.
b) desempilhamento.
c) concatenação.
d) rotação. (correta)
e) poda.
Questão 6
Sejam [3, 1, 2, 7, 5, 4, 6], [3, 1, 2, 6, 4, 5, 7] e [4, 2, 1, 3, 6, 5, 7] as sequências produzidas pelo percurso em
pré-ordem das árvores binárias de busca T1, T2 e T3, respectivamente, é correto afirmar que é(são) árvore(s)
balanceada(s) do tipo AVL:
a) T1.
b) T1 e T2.
c) T1 e T3.
d) T2 e T3. (correta)
e) T1, T2 e T3.
Questão 7
Seja T uma árvore balanceada do tipo AVL vazia. Supondo que os elementos 5, 10, 12, 8, 7, 11 e 13 sejam
inseridos nessa ordem em T, a sequência que corresponde a um percurso de T em pré-ordem é:
a) 10, 8, 5, 7, 12, 11 e 13.
b) 5, 7, 8, 10, 11,12 e 13.
c) 5, 8, 7, 11, 13, 12 e 10.
d) 5, 10, 12, 8, 7, 11 e 13.
e) 10, 7, 5, 8, 12, 11 e 13. (correta)
Questão 8
Uma estrutura de dados onde cada nó mantém uma informação adicional, chamada fator de balanceamento,
que indica a diferença de altura entre as subárvores esquerda e direita, é conhecida por árvore:
a) de busca binária.
GABARITO
Protocolo: 847271
Página 5 - 04/06/2024 às 15:50
b) ordenada.
c) AVL. (correta)
d) binária.
e) hiberbólica.
Questão 9
Dada a árvore de busca binária abaixo, assinale a alternativa que representa o seu percurso in-ordem:
a) 50, 17, 72, 12, 23, 54, 76, 9, 14, 19, 67
b) 9, 12, 14, 17, 19, 23, 50, 54, 67, 72, 76 (correta)
c) 9, 14, 12, 19, 23, 17, 67, 54, 76, 72, 50
d) 50, 17, 12, 9, 14, 23, 19, 72, 54, 67, 76
e) 76, 72, 67, 54, 50, 23, 19, 17, 14, 12, 9
Questão 10
Pesquisar um valor que corresponda a um valor chave em uma árvore AVL com 128 elementos requer no
máximo:
a) oito comparações.
b) quatro comparações.
c) cinco comparações.
d) seis comparações.
e) sete comparações. (correta)