Prévia do material em texto

15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 1/18
Pontuação deste teste: 3 de 6
Enviado 18 de dez de 2023 em 23:28
Esta tentativa levou 949 minutos.
0,6 / 0,6 ptsPergunta 1
Leia o artigo a seguir:
 
O Heapsort é um algoritmo de ordenação baseado numa estrutura
de dados conhecida como Heap, muito útil na construção de filas
de prioridade. Heaps são Árvores Binárias Completas que devem
respeitar algumas propriedades. Em um heap, cada nodo pai
possui no máximo dois filhos, até o seu penúltimo nível deve ter o
máximo de elementos possível e o último nível, se não estiver
completo, deve ter seus elementos agrupados a esquerda. Imagine
uma árvore de nível h = 3 (altura 4), onde o nível zero é o nodo raiz.
Nesta situação, os níveis 0, 1 e 2 precisam estar completos, ou
seja, ter o maior número de nodos possível, o que resultaria em no
mínimo 7 elementos (20 +2¹ + 2² = 7). Há dois tipos de Heap: Max
Heap, onde os nodos filhos são sempre menores que o nodo pai e
o Min Heap, que os filhos são sempre maiores que o pai, resultando
em árvores com maior (ou menor) elemento na raiz dependendo da
implementação. Árvores são estruturas de dados bem interessantes
e com ótima performance, voltaremos a falar sobre o assunto em
um tópico dedicado.
A execução do algoritmo heapsort é interessante. Pode-se separar
o algoritmo em duas fases: Na primeira fase, a qual é chamada de
heapfy, constrói-se a estrutura de árvore heap no arranjo utilizando
uma técnica de execução que vai de baixo para cima (Botton-up).
Esta técnica identifica através do número de elementos 'N' do
arranjo, quem é o nodo pai do último nó folha da árvore. Em
seguida, é verificado se algum dos filhos é maior que o nó pai. Se
for, o nodo pai troca de posição com o maior filho, num processo
conhecido como down heap (sucessivamente caso tenha mais
filhos abaixo). Repete-se este processo até completar a construção
da árvore e ajustar sua propriedade de Max Heap (neste caso).
Agora que o heap está construído com o maior elemento no topo,
inicia-se a segunda fase, onde é feito a troca de posição do maior
elemento com o elemento da última posição do arranjo. Como a
propriedade da árvore pode ter sido quebrada, então aplica-se
novamente o down heap para garantir que suas propriedades
sejam respeitadas. Este processo é repetido até que o vetor seja
completamente ordenado.
 
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 2/18
 
Fonte: CEZAR, P. Algoritmos de ordenação e análise de
complexidade. SmarTI, 20 ago. 2017. Disponível
em: https://smarti.blog.br/algoritmos-de-ordenacao/  . Acesso em:
04 out. 2022.
 
Considerando as informações, avalie as afirmações abaixo:
 
I. No Heapsort o uso de memória é mínimo porque, além do
necessário para manter a lista inicial de itens a serem classificados,
ele não precisa de espaço de memória adicional para funcionar.
 
II. A implementação recursiva do Heapsort consiste em colocar o
maior elemento em sua posição inicial e continuar fazendo o
mesmo para todos os outros elementos.
 
III. O tempo necessário para executar a ordenação por Heap
aumenta logaritmicamente, enquanto outros algoritmos podem
crescer exponencialmente de forma mais lenta.
 
É correto o que se afirma em:
  II, apenas. 
  I e II, apenas. 
  I, apenas. 
  III, apenas. 
  I e III, apenas. Correto!Correto!
https://smarti.blog.br/algoritmos-de-ordenacao/
https://smarti.blog.br/algoritmos-de-ordenacao/
https://smarti.blog.br/algoritmos-de-ordenacao/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 3/18
A alternativa está correta, pois apenas as afirmações I e III
estão corretas.
A afirmação I está correta, pois uma das vantagens do
Heapsort é o uso da memória. No Heapsort o uso de memória
é mínimo porque, além do necessário para manter a lista
inicial de itens a serem classificados, ele não precisa de
espaço de memória adicional para funcionar. Com isso, o
computador trabalha de forma mais rápida e otimizada.
A afirmação II está incorreta, pois é no Bubble sort que a ideia
é colocar o maior elemento em sua posição inicial e continuar
fazendo o mesmo para todos os outros elementos. Este é o
conceito de implementação recursiva do Bubble sort.
A afirmação III está correta, pois o tempo necessário para
executar a ordenação por Heap aumenta logaritmicamente,
enquanto outros algoritmos podem crescer exponencialmente
mais lentamente à medida que o número de itens para
ordenar aumenta. Pode-se ver que como algoritmo de
ordenação, o Heapsort é muito eficiente.
0,6 / 0,6 ptsPergunta 2
Analise as informações a seguir:
 
O algoritmo Hash é conhecido como uma função matemática
criptográfica, na qual você possui dados de entrada e, após passar
pela criptografia, eles apresentam valores de saída "padronizados",
ou seja, as saídas devem possuir o mesmo tamanho (geralmente
entre 128 e 512 bits) e o mesmo número de caracteres
alfanuméricos.
A função hash criptográfica é utilizada, principalmente, para
resumir uma grande quantidade de informações em arquivos.
Imagine um banco de dados com muitas informações podendo ser
resumido em uma única sequência de letras e números! Isso traz
uma praticidade gigantesca dentro do mundo digital e da tecnologia
da informação.
 
Fonte: VALE, S. Definição, funcionamento e as aplicações do hash,
a função popular da criptografia. Voitto, 27 jun. 2020. Disponível
em: https://www.voitto.com.br/blog/artigo/o-que-e-hash-e-como-
funciona  . Acesso em: 04 out. 2022.
 
Considerando as informações, avalie as afirmações abaixo:
 
I. Hashing é usado para verificar a integridade de um arquivo
depois que ele foi transferido. Normalmente em um programa de
backup de arquivos, como o SyncBack.
 
https://www.voitto.com.br/blog/artigo/o-que-e-hash-e-como-funciona
https://www.voitto.com.br/blog/artigo/o-que-e-hash-e-como-funciona
https://www.voitto.com.br/blog/artigo/o-que-e-hash-e-como-funciona
https://www.voitto.com.br/blog/artigo/o-que-e-hash-e-como-funciona
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 4/18
II. Em algumas situações, um arquivo criptografado pode ser
projetado para nunca alterar o seu tamanho nem a data e hora da
última modificação.
 
III. Um uso principal do hashing é comparar dois arquivos. Assim,
podemos abrir dois arquivos de documentos para compará-los
palavra por palavra.
 
É correto o que se afirma em:
  I e III, apenas. 
  II, apenas. 
  I, apenas. 
  I e II, apenas. Correto!Correto!
A alternativa está correta, pois apenas as afirmações I e II
estão corretas.
A afirmação I está correta, pois o hashing é usado para
verificar a integridade de um arquivo depois que ele foi
transferido de um lugar para outro, normalmente em um
programa de backup de arquivos como o SyncBack. Para
garantir que o arquivo transferido não esteja corrompido, um
usuário pode comparar o valor de hash de ambos os arquivos.
Se forem iguais, o arquivo transferido é uma cópia idêntica.
A afirmação II está correta, pois em algumas situações, um
arquivo criptografado pode ser projetado para nunca alterar o
tamanho do arquivo nem a data e hora da última modificação
(por exemplo, arquivos de contêiner de unidade virtual).
Nesses casos, seria impossível dizer rapidamente se dois
arquivos semelhantes são diferentes ou não, mas os valores
de hash distinguiram facilmente esses arquivos se forem
diferentes.
A afirmação III está incorreta, pois para comparar dois
arquivos para igualdade não é necessário abrir dois arquivos
de documentos para compará-los palavra por palavra. Os
valores de hash calculados desses arquivos permitirão que o
proprietário saiba imediatamente se eles são diferentes.
  II e III, apenas. 
0,6 / 0,6 ptsPergunta 3
Leia o textoabaixo:
 
Tratamento de colisões: como uma função hash nos dá um
pequeno número para uma chave grande, é possível que duas
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 5/18
chaves resultem no mesmo valor. A situação em que uma chave
recém-inserida mapeia para um slot já ocupado na tabela hash é
chamada de colisão e deve ser tratada usando alguma técnica de
tratamento de colisão. A seguir estão as maneiras de lidar com as
colisões:
 
Encadeamento: A ideia é fazer com que cada célula da tabela
de hash aponte para uma lista vinculada de registros que
possuem o mesmo valor da função de hash. O encadeamento é
simples, mas requer memória adicional fora da mesa.
Endereçamento aberto: no endereçamento aberto, todos os
elementos são armazenados na própria tabela hash. Cada
entrada da tabela contém um registro ou NIL. Ao procurar um
elemento, examinamos os slots da tabela um por um até que o
elemento desejado seja encontrado ou fique claro que o
elemento não está na tabela.
 
Fonte: Hashing: conjunto 1 (Introdução). Acervo Lima. Disponível
em: https://acervolima.com/hashing-conjunto-1-introducao/  .
Acesso em: 04 out. 2022.
 
Para solucionar colisões, os métodos de endereçamento aberto
incluem hash duplo, sondagem linear e
  cibersegurança. 
  assinaturas digitais. 
  recuperação de dados. 
  sondagem quadrática. Correto!Correto!
A alternativa está correta, pois para solucionar colisões, os 
métodos de endereçamento aberto incluem hash duplo, 
sondagem linear e sondagem quadrática. O encadeamento 
separado, por outro lado, evita colisões fazendo com que cada 
célula da tabela de hash aponte para listas vinculadas de 
registros com valores de função de hash idênticos.
  classificação decimal de Dewey. 
0 / 0,6 ptsPergunta 4
Leia o texto abaixo:
 
Vetores, ou arrays são estruturas de dados lineares e estáticas,
isto é, são compostas por um número fixo (finito) de elementos de
um determinado tipo de dados. O tempo de acesso aos elementos
https://acervolima.com/hashing-conjunto-1-introducao/
https://acervolima.com/hashing-conjunto-1-introducao/
https://acervolima.com/hashing-conjunto-1-introducao/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 6/18
de um vetor é muito rápido, sendo considerado constante: o acesso
aos elementos é feito pelo seu índice no vetor. Porém, a remoção
de elementos pode ser custosa se não for desejável que haja
espaços “vazios” no meio do vetor, pois nesse caso é necessário
“arrastar” de uma posição todos os elementos depois do elemento
removido. Essa é uma estrutura muito recomendada para casos em
que os dados armazenados não mudarão, ou pouco mudarão,
através do tempo.
Uma Lista é uma estrutura de dados linear. Uma lista ligada,
também chamada de encadeada, é linear e dinâmica, é composta
por nós que apontam para o próximo elemento da lista, com
exceção do último, que não aponta para ninguém. Para compor
uma lista encadeada, basta guardar seu primeiro elemento.
As Pilhas são estruturas baseadas no princípio LIFO (last in, first
out), na qual os dados que foram inseridos por último na pilha serão
os primeiros a serem removidos. Existem duas funções que se
aplicam a todas as pilhas: PUSH, que insere um dado no topo da
pilha, e POP, que remove o item no topo da pilha.
As Filas são estruturas baseadas no princípio FIFO (first in, first
out), em que os elementos que foram inseridos no início são os
primeiros a serem removidos. Uma fila possui duas funções
básicas: ENQUEUE, que adiciona um elemento ao final da fila, e
DEQUEUE, que remove o elemento no início da fila. A operação
DEQUEUE só pode ser aplicada se a fila não estiver vazia,
causando um erro de underflow ou fila vazia se esta operação for
realizada nesta situação.
 
Fonte: MOTA, K. Estrutura de dados: conceitos básicos. Kleber
Mota, 20 ago. 2009.  Disponível
em: https://klebermota.eti.br/2009/08/20/estrutura-de-dados-
conceitos-basicos/  . Acesso em: 19 out. 2022.
 
Qual das alternativas apresenta uma das características de uma
pilha?
  É usado na resolução de problemas matriciais. 
  Ajuda na implementação de um algoritmo de classificação. 
  Pode encolher ou crescer a qualquer momento facilmente. Você respondeuVocê respondeu
A alternativa está incorreta, pois é uma lista vinculada que
pode encolher ou crescer a qualquer momento facilmente.
Alémdisso, em uma lista vinculada, é possível inserir e excluir
facilmente.
Desse modo, a alternativa correta é aquela que diz que uma
pilha é implementada através de array ou lista encadeada.
Outra característica importante é que a inserção e a exclusão
acontecem em uma extremidade, ou seja, no topo da pilha.
  É implementada através de array ou lista encadeada. Resposta corretaResposta correta
https://klebermota.eti.br/2009/08/20/estrutura-de-dados-conceitos-basicos/
https://klebermota.eti.br/2009/08/20/estrutura-de-dados-conceitos-basicos/
https://klebermota.eti.br/2009/08/20/estrutura-de-dados-conceitos-basicos/
https://klebermota.eti.br/2009/08/20/estrutura-de-dados-conceitos-basicos/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 7/18
  Usa memória extra para armazenar links. 
0 / 0,6 ptsPergunta 5
Leia o texto a seguir:
 
A melhor representação para um grafo depende do que desejamos
fazer com ele e do quão denso ou esparso ele é. Grafos esparsos
são grafos que possuem um pequeno número de arestas em
relação ao número de vértices, ao passo que em grafos densos o
número de arestas se aproxima do máximo de arestas possível.
Existem duas representações principais para grafos. A primeira é
chamada matriz de adjacências, que nada mais é do que uma
matriz M de n linhas e n colunas em que M[i,j]=1 se existe uma
aresta do vértice i para o vértice j. Lembre-se que estamos
seguindo a convenção de que n representa o número de vértices do
grafo.
Se estivermos representando um grafo não-direcionado e existir
uma aresta entre os vértices i e j, então teremos tanto M[i,j]=1
quanto M[j,i]=1. Em outras palavras, a matriz de adjacências M que
representa um grafo não-direcionado é simétrica. Nessa
representação, o tempo gasto para determinar se um vértice u é
vizinho de um vértice v é constante, pois basta verificarmos se
M[u,v] é igual a 1.
Vejamos um exemplo de grafo e sua matriz de adjacências.
 
Fonte: Representação de Grafos. Algoritmos em Python.
Disponível
em: https://algoritmosempython.com.br/cursos/algoritmos-
python/algoritmos-grafos/representacao-grafos/  . Acesso em: 04
out. 2022.
 
Considerando o trecho e as imagens, assinale a opção correta.
https://algoritmosempython.com.br/cursos/algoritmos-python/algoritmos-grafos/representacao-grafos/
https://algoritmosempython.com.br/cursos/algoritmos-python/algoritmos-grafos/representacao-grafos/
https://algoritmosempython.com.br/cursos/algoritmos-python/algoritmos-grafos/representacao-grafos/
https://algoritmosempython.com.br/cursos/algoritmos-python/algoritmos-grafos/representacao-grafos/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 8/18
  
A matriz de adjacências, embora seja muito usada, apresenta mais
complexidade na implementação.
 
  
Na teoria dos grafos, uma matriz de adjacência é a matriz 3D que é
usada para mapear a associação entre os nós do grafo.
 
  
Existe clara distinção de tipologia quando consideramos os grafos
esparsos e os comparamos aos grafos densos.
 
  
Como se vê nas imagens, os grafos são usados para representar
muitas aplicações da vida real e são usados para representar
redes.
 
Resposta corretaResposta correta
  
Um dos motivos da matriz de adjacência ser muito usada é que
esta consome menos espaço.
 
Você respondeuVocê respondeu
A alternativa está incorreta, pois é vantajosousar uma matriz
de adjacência, mas esta consome mais espaço. Mesmo que o
grafo seja esparso, a matriz ainda consome o mesmo espaço.
Desse modo, a alternativa correta é aquela que diz que os
grafos são usados para representar muitas aplicações da vida
real, ou seja, são usados para representar redes, pois os
grafos são usados para representar muitas aplicações da vida
real, ou seja, são usados para representar redes. As redes
podem incluir caminhos numa cidade ou rede telefônica ou
rede de circuitos.
0,6 / 0,6 ptsPergunta 6
Leia o texto a seguir:
 
Definição: Uma árvore binária é balanceada se a diferença da
profundidade de duas folhas quaisquer é no máximo 1. A
profundidade de um nodo é o número de níveis da raiz até aquele
nodo. Na figura ao lado, a árvore a) é balanceada, e a árvore b) não
é balanceada.
 
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 9/18
Se uma árvore é balanceada, tanto no caso da inserção quando no
caso da busca, a cada chamada recursiva do algoritmo,
descartamos metade da árvore original. Portanto, a complexidade
assintótica desses dois procedimentos é logarítmica no tamanho
(número de nodos) da árvore. Na verdade, muitos procedimentos
que operam sobre árvores binárias de pesquisa funcionam com
base nessa mesma ideia de eliminar metade da árvore a cada
etapa do procedimento. Isso ocorre por causa da natureza
recursiva das árvores binárias de pesquisa e pela forma como os
nodos são inseridos nelas.
Entretanto, se a árvore não for balanceada, não descartaremos
metade da árvore original a cada chamada recursiva. Em casos
como o da árvore não balanceada mostrada acima, a complexidade
dos procedimentos de inserção e busca será linear no tamanho da
árvore, pois, na prática, a árvore mostrada funciona como se fosse
uma lista encadeada.
No caso de árvores binárias, é importante sempre fazer a distinção
da complexidade dos procedimentos caso a árvore seja balanceada
e caso ela não seja. Além disso, é importante estar atento a
procedimentos que parecem logarítmicos, mas que na verdade
visitam todos os nodos da árvore.
 
Fonte: Árvores. Algoritmos em Python Disponível
em: https://algoritmosempython.com.br/cursos/algoritmos-
python/estruturas-dados/arvores/  . Acesso em: 04 out. 2022.
 
Considerando as informações, avalie as afirmações abaixo:
 
I. Uma árvore binária balanceada é definida como uma árvore
binária na qual a altura da subárvore esquerda e direita de qualquer
nó difere em não mais que 2.
 
II. Uma das condições para uma árvore binária com altura
balanceada é que a diferença entre a subárvore esquerda e direita
para qualquer nó não seja maior que um.
 
III. A árvore AVL é uma árvore de busca binária auto balanceada na
qual cada nó mantém informações extras chamadas de fator de
balanceamento cujo valor é -1, 0 ou +1.
https://algoritmosempython.com.br/cursos/algoritmos-python/estruturas-dados/arvores/
https://algoritmosempython.com.br/cursos/algoritmos-python/estruturas-dados/arvores/
https://algoritmosempython.com.br/cursos/algoritmos-python/estruturas-dados/arvores/
https://algoritmosempython.com.br/cursos/algoritmos-python/estruturas-dados/arvores/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 10/18
 
É correto o que se afirma em:
  I e III, apenas. 
  I e II, apenas. 
  II e III, apenas. Correto!Correto!
A alternativa está correta, pois apenas as afirmações II e III
estão corretas.
A afirmação I está incorreta, pois uma árvore binária
balanceada, também conhecida como árvore binária
balanceada em altura, é definida como uma árvore binária na
qual a altura da subárvore esquerda e direita de qualquer nó
difere em não mais que 1.
A afirmação II está correta, pois, de fato, uma das condições
para uma árvore binária com altura balanceada é que a
diferença entre a subárvore esquerda e direita para qualquer
nó não seja maior que um, a subárvore esquerda seja
balanceada e a subárvore direita seja balanceada.
A afirmação III está correta, pois a árvore AVL é uma árvore
de busca binária auto balanceada na qual cada nó mantém
informações extras chamadas de fator de balanceamento cujo
valor é -1, 0 ou +1. A árvore AVL recebeu o nome de seu
inventor Georgy Adelson-Velsky e Landis.
  II, apenas. 
  I, apenas. 
0 / 0,6 ptsPergunta 7
Leia o texto a seguir:
 
Uma das tarefas mais comuns na implementação de algoritmos,
com um grande número de aplicações possíveis, a ordenação de
elementos em um conjunto se torna também objeto constante de
estudo em termos de otimização. As muitas soluções disponíveis,
apesar de produzirem o resultado esperado, podem se mostrar
indesejadas em termos de desempenho, dependendo do cenário
em que são utilizadas [...]
 
O Funcionamento dos Algoritmos
Insertion Sort
O Insertion Sort é um algoritmo de classificação baseado em
comparação local. Nele, um subconjunto do vetor é mantido como
ordenado, o qual vai crescendo à medida que o vetor é percorrido e
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 11/18
cada elemento é devidamente posicionado. Nesse posicionamento
o novo item em foco tem que encontrar seu lugar apropriado e
então ser inserido. Dessa característica origina o seu nome
Insertion Sort, ou ordenação por inserção.
Em um passo-a-passo, o algoritmo segue as etapas abaixo ao
percorrer o vetor:
Se for o primeiro elemento, ele já está classificado.
Escolha o próximo elemento
Compare com todos os elementos na sub-lista classificada
Desloque todos os elementos na sub-lista classificada que são
maiores que o valor a ser ordenado
Insira o valor
Repita até que a sub-lista classificada seja toda a lista.
 
Fonte: LOPES, R. Implementação (em python) e análise dos
algoritmos de ordenação: insertion sort, merge sort e tim
sort. Ronan Lopes, 16 mar. 2021. Disponível
em: https://ronanlopes.me/implementacao-em-python-e-analise-
dos-algoritmos-de-ordenacao-insertionsort-mergesort-e-timsort/  .
Acesso em: 04 out. 2022.
 
Refletindo sobre a complexidade na implementação de algoritmos,
avalie as seguintes asserções e a relação proposta entre elas.
 
I. Para que algumas instruções sejam consideradas um algoritmo,
elas devem ser claras e inequívocas, ou seja, cada uma de suas
etapas deve ser clara em todos os aspectos e devem levar a
apenas um significado.
 
PORQUE
 
II. O algoritmo deve ser viável, simples, genérico e prático, para que
possa ser executado com os recursos disponíveis. Desta forma,
deve se relacionar com alguma tecnologia de ponta ou mais
avançada.
 
A respeito dessas asserções, assinale a opção correta:
  
As asserções I e II são proposições verdadeiras, mas a II não é
uma justificativa da I.
 
Você respondeuVocê respondeu
https://ronanlopes.me/implementacao-em-python-e-analise-dos-algoritmos-de-ordenacao-insertionsort-mergesort-e-timsort/
https://ronanlopes.me/implementacao-em-python-e-analise-dos-algoritmos-de-ordenacao-insertionsort-mergesort-e-timsort/
https://ronanlopes.me/implementacao-em-python-e-analise-dos-algoritmos-de-ordenacao-insertionsort-mergesort-e-timsort/
https://ronanlopes.me/implementacao-em-python-e-analise-dos-algoritmos-de-ordenacao-insertionsort-mergesort-e-timsort/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 12/18
A alternativa está incorreta, pois a asserção I é uma
proposição verdadeira, e a II é uma proposição falsa.
A asserção I é verdadeira, pois para que algumas instruções
sejam consideradas um algoritmo, elas devem ser claras e
inequívocas, ou seja, cada uma de suas etapas deve ser
clara em todos os aspectos e deve levar a apenas um
significado. Além disso, deve apresentar saídas bem
definidas, ou seja, o algoritmo deve definir claramente qual
saída será produzida e também deve serbem definida.
A asserção II é falsa, pois o algoritmo deve ser viável,
simples, genérico e prático, para que possa ser executado
com os recursos disponíveis. Contudo, não deve conter
alguma tecnologia de ponta ou mais avançada. Além disso, o
algoritmo projetado deve ser independente da linguagem, ou
seja, deve ter apenas instruções simples que possam ser
implementadas.
  
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa da I.
 
  
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
 
  
A asserção I é uma proposição verdadeira, e a II é uma proposição
falsa.
 
Resposta corretaResposta correta
  As asserções I e II são proposições falsas. 
0 / 0,6 ptsPergunta 8
Leia o texto abaixo:
 
Gratuito e de código aberto, o Python foi lançado em 1991.
Atualmente, possui um modelo de desenvolvimento comunitário,
aberto e gerenciado pela organização sem fins lucrativos Python
Software Foundation.
A linguagem, que pode ser utilizada para diversos fins, funciona
emitindo comandos intuitivos, como, por exemplo, “print” para
imprimir um texto na tela, “open” para abrir um arquivo, ou “find”
para encontrar uma palavra.
Um dos usos do Python é automatizar tarefas, no entanto, a
linguagem também permite coletar, organizar e salvar informações
de páginas na internet; monitorar redes sociais; construir um site ou
app; criar jogos; rodar algoritmos de machine learning; criar
aplicações de inteligência artificial (IA), dentre outros.
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 13/18
 
Fonte: SÉRVIO, G. O que é e para que serve o Python? Olhar
Digital, 04 out. 2021. Disponível
em: https://olhardigital.com.br/2021/10/04/tira-duvidas/o-que-e-para-
que-serve-o-python/  . Acesso em: 04 out. 2022.
 
Considerando as informações, avalie as afirmações abaixo:
 
I. O Python foi desenvolvido por Guido van Rossum no final dos
anos 80 e início dos anos 90.
 
II. Python suporta vários paradigmas de programação, incluindo
linguagem de programação Procedimental e Orientada a Objetos.
 
III. Python é classificado como uma das linguagens de
programação mais populares do mundo devido à sua
complexidade.
 
IV. Python usa ponto e vírgula para completar um comando, ao
contrário de outras linguagens que usam novas linhas.
 
É correto o que se afirma em:
  II, apenas. Você respondeuVocê respondeu
A alternativa está incorreta, pois apenas as afirmações I e II
estão corretas.
A afirmação I está correta, pois o Python foi desenvolvido por
Guido van Rossum no final dos anos 80 e início dos anos 90
no Instituto Nacional de Pesquisa em Matemática e Ciência
da Computação na Holanda.
A afirmação II está correta, pois o Python suporta vários
paradigmas de programação, incluindo linguagem de
programação Procedimental, Orientada a Objetos e
Funcional. A filosofia de design do Python enfatiza a
legibilidade do código com o uso de recuo significativo.
A afirmação III está incorreta, pois o Python é bastante fácil
de aprender, portanto, quando estamos começando a
aprender qualquer linguagem de programação, o Python pode
ser sua ótima escolha.
A afirmação IV está incorreta, pois o Python usa novas linhas
para completar um comando, ao contrário de outras
linguagens de programação que geralmente usam ponto e
vírgula ou parênteses.
  I e II, apenas. Resposta corretaResposta correta
  II e III, apenas. 
https://olhardigital.com.br/2021/10/04/tira-duvidas/o-que-e-para-que-serve-o-python/
https://olhardigital.com.br/2021/10/04/tira-duvidas/o-que-e-para-que-serve-o-python/
https://olhardigital.com.br/2021/10/04/tira-duvidas/o-que-e-para-que-serve-o-python/
https://olhardigital.com.br/2021/10/04/tira-duvidas/o-que-e-para-que-serve-o-python/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 14/18
  I e III, apenas. 
  III e IV, apenas. 
0,6 / 0,6 ptsPergunta 9
Interprete as informações abaixo:
 
Balanceamento
Os métodos a seguir descrevem o balanceamento baseado no
algoritmo AVL.
A maioria dos métodos envolve a modificação direta de um ponteiro
de nó, portanto recebemos este ponteiro por referência. Isto evita
um eventual uso de um ponteiro para ponteiro (node_t**).
 
Cálculo de índice de balanceamento
Este método calcula o índice de balanceamento para um nó
arbitrário. Este cálculo é feito através da diferença entre esquerda e
direita, onde esquerda é a "altura" da subárvore esquerda do nó, e
direita é a "altura" da subárvore direita do nó.
Uma subárvore não-nula já contabiliza a soma de uma unidade no
valor da altura daquela subárvore. Todavia, caso aquela subárvore
seja nula, sua "altura" será zero.
Este valor de "altura" é, portanto, não exatamente a altura da
subárvore em si, mas sim a quantidade máxima de passos para
que o nó atual chegue ao nó-folha mais baixo.
 
Fonte: VIEIRA, L. S. Árvore AVL. Luksamuk, 22 out. 2020.
Disponível em: https://luksamuk.codes/pages/avltree.html  .
Acesso em: 04 out. 2022.
 
Refletindo sobre as árvores AVL e seus balanceamentos, avalie as
seguintes asserções e a relação proposta entre elas.
 
I. O fator de equilíbrio de um nó em uma árvore AVL é a diferença
entre a altura da subárvore esquerda e a da subárvore direita desse
https://luksamuk.codes/pages/avltree.html
https://luksamuk.codes/pages/avltree.html
https://luksamuk.codes/pages/avltree.html
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 15/18
nó. A propriedade de autobalanceamento de uma árvore AVL é
mantida pelo fator de balanceamento.
 
PORQUE
 
II. Se o fator de equilíbrio de qualquer nó for 0, significa que a
subárvore esquerda e a subárvore direita contêm a mesma altura.
Se o fator de equilíbrio de qualquer nó for -1, significa que a
subárvore esquerda está um nível abaixo da subárvore direita.
 
A respeito dessas asserções, assinale a opção correta:
  
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa da I.
 
Correto!Correto!
A alternativa está correta. 
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa da I.
A asserção I é verdadeira, pois o fator de equilíbrio de um nó
em uma árvore AVL é a diferença entre a altura da subárvore
esquerda e a da subárvore direita desse nó. Fator de
Equilíbrio = (Altura da Subárvore Esquerda - Altura da
Subárvore Direita) ou (Altura da Subárvore Direita - Altura da
Subárvore Esquerda). A propriedade de autobalanceamento
de uma árvore AVL é mantida pelo fator de balanceamento. O
valor do fator de equilíbrio deve ser sempre -1, 0 ou +1.
A asserção II é verdadeira e é justificativa da I, pois se o fator
de equilíbrio de qualquer nó for 0, significa que a subárvore
esquerda e a subárvore direita contêm a mesma altura. Se o
fator de equilíbrio de qualquer nó for -1, significa que a
subárvore esquerda está um nível abaixo da subárvore direita.
Isso ocorre pois o fator de equilíbrio associado a cada nó está
entre -1 e +1, o que caracteriza o fator de balanceamento de
uma árvore AVL.
  
A asserção I é uma proposição verdadeira, e a II é uma proposição
falsa.
 
  
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
 
  
As asserções I e II são proposições verdadeiras, mas a II não é
uma justificativa da I.
 
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 16/18
  As asserções I e II são proposições falsas. 
0 / 0,6 ptsPergunta 10
Leia o texto e analise as imagens abaixo:
 
Quando tratamos de estrutura de dados estamos sempre
interessados na eficiência de operações fundamentais de coleções,
como busca, inserção e remoção. Nesse sentido, o array, embora
seja uma estrutura elementar, é uma excelente escolha para
diversos cenários, pois nos fornece acesso, inserçãoe remoção em
tempo O(1). Isto é, se soubermos o índice em que um elemento
está, o tempo de acesso a esse elemento é extremamente
eficiente. O mesmo ocorre para adicionar um elemento em uma
posição arbitrária, pois o custo dessa operação é dado pela
operação primitiva de atribuição (ex: array[4] =
"computacao@ufcg"). Por fim, a remoção pode também ser
efetuada em O(1) atribuindo o valor da posição para null (ex:
array[8] = null).
Vamos analisar o cenário em que desejamos armazenar objetos do
tipo Aluno [...]. Para fins de simplificação, o objeto do tipo aluno
possui dois atributos: matrícula e nome.
 
Vamos também assumir que a matrícula identifica unicamente um
aluno do curso e que é um inteiro no domínio [0…1999]1. Nesse
material chamamos de chaves os atributos dessa natureza. Dentro
desse cenário, um array é uma estrutura muito adequada, porque
podemos armazenar o aluno na posição do array cujo valor é o
mesmo de sua matrícula. Não somente a inserção, mas a busca e a
remoção desse objeto pode ser realizada em tempo O(1), pois há
uma correspondência direta entre o identificador único do
aluno (a chave) e o índice em que ele se encontra no array.
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 17/18
 
Fonte: BRUNET, J. A. Tabelas Hash. João Arthur Brunet, 24 out.
2019. Disponível
em: https://joaoarthurbm.github.io/eda/posts/hashtable/  . Acesso
em: 04 out. 2022.
 
Refletindo sobre as tabelas hash, avalie as seguintes asserções e a
relação proposta entre elas.
 
I. A implementação de tabela de hash mais complexa usa o
encadeamento com linguagem de alto nível para resolver colisões.
Isso combina as melhores propriedades de matrizes e listas
vinculadas.
 
PORQUE
 
II. A eficiência de uma tabela de hash depende do fato de que o
tamanho da tabela é proporcional ao número de registros. Se o
número de registros for conhecido, a tabela deve ser
redimensionada.
 
Com base nas asserções, assinale a opção correta:
  
A asserção I é uma proposição falsa, e a II é uma proposição
verdadeira.
 
  
A asserção I é uma proposição verdadeira, e a II é uma proposição
falsa.
 
  As asserções I e II são proposições falsas. Resposta corretaResposta correta
  
As asserções I e II são proposições verdadeiras, e a II é uma
justificativa da I.
 
Você respondeuVocê respondeu
https://joaoarthurbm.github.io/eda/posts/hashtable/
https://joaoarthurbm.github.io/eda/posts/hashtable/
https://joaoarthurbm.github.io/eda/posts/hashtable/
15/03/2024, 10:26 AO2 Substitutiva: Estrutura de Dados
https://famonline.instructure.com/courses/31357/quizzes/158609?module_item_id=878237 18/18
A alternativa está incorreta, pois as asserções I e II são
proposições falsas.
A asserção I é falsa, pois a implementação de tabela de hash
mais comum usa encadeamento com listas vinculadas para
resolver colisões. Isso combina as melhores propriedades de
matrizes e listas vinculadas. As operações da tabela de hash
são executadas em duas etapas: uma chave é convertida em
um índice inteiro usando uma função de hash; esse índice
decide a lista vinculada à qual o registro do par chave-valor
pertence.
A asserção II é falsa, pois se o número de registros não for
conhecido antecipadamente, a tabela deve ser
redimensionada quando as listas se tornarem muito longas:
uma nova tabela maior é alocada, cada registro é removido
da tabela antiga e inserido na nova tabela.
  
As asserções I e II são proposições verdadeiras, mas a II não é
uma justificativa da I.