UNOPAR - PROVA PRESENCIAL - 1 CHAMADA - ESTRUTURA DE DADOS

Prévia do material em texto

Gabarito
×
Questão 1
As árvores binárias de busca têm particularidades em operações como inserção e remoção. A inserção
em uma árvore binária de busca considera o valor da chave para definir sua localização na árvore. Uma
árvore binária tem até 2 filhos. A árvore binária de busca a chave nova é comparada com a chave do
vértice atual. Se a chave nova é menor que a chave do vértice atual, sua inserção será na subárvore
esquerda. Caso contrário, na subárvore direita. A procura pela sua posição é feita recursivamente até
que encontre um vértice que não tenha filho direito ou esquerdo para comparar a chave nova. Então,
significa que o vértice novo com a chave nova será o filho direito ou esquerdo. Na remoção de vértices
de uma árvore, há 3 casos: quando é um vértice-folha, quando tem apenas 1 filho e quando tem 2 filhos.
Para o caso 1, é só desvincular o vértice-folha. Para o caso 2, o filho do vértice a ser removido toma seu
lugar. Para o caso 3, o vértice que tem a chave com o menor valor na subárvore esquerda troca de chave
com o vértice que seria removido. Removemos o vértice que tinha a chave com o menor valor na
subárvore esquerda.
A sequência a seguir foi feita em uma árvore binária de busca:
1. Inserções de: 5, 4, 6, 1, 3, 9, 0, 7, 8
2. Remoção de: 3, 5, 6
3. Inserção de 2
Assinale a alternativa que apresenta os valores das chaves dos filhos do vértice 7. 
 A) 9
 B) 4 e 8
 C) 4
 D) 8
 E) 4 e 9
Questão 2
O estudo de estrutura de dados envolve a forma a qual dados são armazenados física e logicamente em
um computador. Um exemplo de estrutura de dados que pode-se citar são as listas. Tome como
exemplo uma lista de compras. Nesse tipo de lista, os produtos são inseridos sequencialmente um
abaixo do outro. Ao fazer as compras, você gradativamente risca cada item adicionado ao carrinho,
assim poderá saber quais itens faltam. Se analisarmos com atenção esse exemplo, podemos perceber
algumas características fundamentais de alguns tipos de lista, qual seria esse tipo de lista?
 A) Arrays
 B) Matriz
 C) FIFO (first-in, first-out)
 D) Collections Stack
 E) LIFO (Last In, First Out)
Questão 3
Leia e interprete o código Python em questão, qual será o resultado da impressão?
class Dados:
def __init__(self):
self.itens = []
def __repr__(self):
return str(self.itens)
def insere(self, valor):
self.itens.append(valor)
def remove(self):
self.itens.pop()
def main():
dados = Dados()
dados.insere(1)
dados.insere(2)
dados.insere(3)
print(dados)
dados.remove()
print(dados)
if __name__ == "__main__":
main()
 A) [1, 2, 3][1, 3]
 B) [2, 3, 1][2, 1]
 C) [1, 3, 2][1, 2]
 D) [1, 2, 3][1, 2]
 E) [1, 2, 3][1 ]
Questão 4
Sobre árvores, analise as afirmativas a seguir:
I) São estruturas lineares porque os vértices estão ligados por linhas, chamadas de arestas.
II) A altura de um vértice de uma árvore se mede contando o número de arestas a partir de um vértice
até a raiz. Já a profundidade é medida contando o número de arestas a partir do vértice até o nó mais
profundo.
III) Todos os nós têm filhos, exceto os nós folha. Todos têm pai, exceto a raiz.
IV) A aresta liga um vértice pai a um vértice filho, dando um significado de hierarquia.
V) O vértice mais profundo está no nível 3, então significa que a árvore tem altura igual a 3 e
profundidade da raiz é 0.
 A) I, III e V, apenas.
 B) III, IV e V, apenas.
 C) II, III e IV, apenas.
 D) I, II e III, apenas.
 E) II, IV e V, apenas.
Questão 5
Para calcular a altura de um vértice, contamos o número de arestas a partir dele até o vértice mais
profundo da sua ramificação, ou seja, para baixo. A ____________ de uma árvore é o número de arestas
contadas a partir da raiz até o nó mais profundo. Para calcular a ______________ de um vértice, conte o
número de arestas a partir dele até a raiz, ou seja, para cima.
 A) altura (height); altura (height)
 B) arresta (edges); profundidade (depth)
 C) profundidade (depth); profundidade (depth)
 D) altura (height) ; profundidade (depth)
 E) profundidade (depth); altura (height)
Questão 6
Listas _______, também conhecidas como listas ________, são estruturas de dados que armazenam nós
compostos por valores conectados por ________. Cada valor armazenado na lista deve também
armazenar o posicionamento do próximo elemento. Assim, para percorrer a lista deve-se consultar os
endereços armazenados nos ponteiros partindo da head (cabeçalho da lista) até que se encontre um
valor nulo, também citado como tail (cauda da lista).
 A) fluída; variável; ponteiros.
 B) encadeadas; variável; matriz.
 C) encadeadas; ligadas; ponteiros.
 D) pilhas; em série; matriz.
 E) inteira; completa; listas.
Questão 7
Os grafos são estruturas de dados que nos ajudam a modelar o mundo real de forma a facilitar a
solução de problemas. Nos grafos, aeroportos são representadas por vértices e as rotas de aviões que
chegam e/ou saem delas por arestas; pessoas são representadas por vértices e seus relacionamentos
são representados por arestas; casas e vias podem ser representadas por vértices e arestas. Para os
vários problemas pode haver mais de um algoritmo para resolver o problema usando grafos. Um dos
problemas recorrentes é estar em um local que saber qual é o melhor caminho para ir a outro ponto da
cidade. Geralmente, usamos um aplicativo de mapa para nos guiar.
Assinale a alternativa cujo algoritmo poderia ser usado para traçar trajetos deste tipo.
 A) Algoritmo de Dijkstra
 B) Algoritmo de Kruskal
 C) Algoritmo de Euler
 D) Algoritmo de Hamilton
 E) Algoritmo de Prim
Questão 8
Quanto aos algoritmos Prim, Kruskal e Dijkstra, podemos afirmar:
 A) O algoritmo de Dijkstra pode ser aplicado em aplicativos para
motoristas profissionais, que transportem pessoas, ou cargas.
Especialmente para entregadores que ao fazer uma viagem pode
ter vários pontos de paradas. Com este algoritmo seria possível
traçar rotas otimizadas como um todo, não somente em um trecho.
 B) Todas as alternativas estão corretas
 C) Os algoritmos de Prim e Kruskal servem para obter uma árvore
geradora de custo mínimo. Ambos chegam ao mesmo resultado,
ainda que a árvore não necessariamente é a mesma.
 D) O algoritmo de Kruskal escolhe a aresta de menor custo,
enquanto o de Prim, inicia com a escolha de vértice. As escolhas
das arestas em Kruskal não estão ligadas inicialmente, enquanto no
de Prim, a cada passo a aresta parte de um vértice que já está na
árvore MST.
 E) O algoritmo o Dijkstra tem como foco obter o caminho de menor
custo a partir de um ponto de origem.
Questão 9
Grafos são estruturas de dados formadas por vértices e arestas. Em grafos os vértices que fazem parte
do grafo podem ou não estar conectados pelas arestas. As arestas sempre estão conectadas a pelo
menos dois vértices. As arestas podem ser unidirecionais ou bidirecionais. Num mesmo grafo as arestas
são representadas por seta se a ligação entre os vértices é direcional, ou seja, A para B é diferente de B
para A. As arestas são representadas por linhas se a ligação entre os vértices é bidirecional, ou seja, A
para B é igual B para A. Os grafos servem para representar elementos conectados ou não, por exemplo,
numa região com cidades e estradas, sendo as cidades representadas pelos vértices e as estradas, as
arestas.
Com base no contexto apresentado, assinale a alternativa correta.
 A) O algoritmo de busca em profundidade é usado em sistemas de
GPS para obter os pontos turísticos ao redor de onde está.
 B) Somente o algoritmo de busca em profundidade resolve o
problema de detecção de caminho
 C) O algoritmo de busca em profundidade resolve o problema de
identificar o grau de separação entre pessoas numa rede social
 D) O algoritmo de busca em profundidade descobre os
computadores conectados numa rede ponto-a-ponto (peer-to-peer)
 E) Os algoritmos de busca em profundidade e em largura são
usados para detectar ciclos
Questão 10
Leia o fragmento, interprete o código Python em questão e assinale alternativacorreta.
class ArvoreBinariaBusca:
def __init__(self):
self.raiz = None
def inserir(self, chave):
if self.raiz is None:
self.raiz = Vertice(chave)
else:
self.raiz.inserir(chave)
self.raiz.imprimir()
def remover(self, chave):
if self.raiz is not None:
self.raiz.remover(chave)
self.raiz.imprimir()
 A) A classe ArvoreBinariaBusca, definida acima, tem os atributos:
raiz, inserir e remover. A árvore é formada por uma raiz que é um
objeto da classe Vertice.
 B) A classe ArvoreBinariaBusca, definida acima, tem os atributos:
fonte, inserir e remover. A árvore é formada por uma raiz que é um
objeto da classe Remover.
 C) A classe ArvoreBusca, definida acima, tem os atributos: raiz,
inserir e deletar. A árvore é formada por uma raiz que é um objeto
da classe Init.
 D) A classe ArvoreBinariaBusca, definida acima, tem os atributos:
raiz, inserir e remover. A árvore é formada por uma raiz que é um
objeto da classe Init.
 E) A classe ArvoreBinaria, definida acima, tem os atributos: raiz,
inserir e remover. A árvore é formada por uma raiz que é um
objeto da classe Vertice.
Questão 11
Um bit corresponde um valor binário excludente, que pode ser interpretado como 0 ou 1. Por exemplo,
em uma notação binária, pode-se utilizar bits para representar números decimais. Os números 5, 6 e 7
seriam representados por quais conjuntos binários respectivamente:
 A) 101; 110; 111
 B) 111; 110; 101
 C) 110; 101; 101
 D) 101; 111; 110
 E) 101; 100; 111
Questão 12
Observe as declarações em Python a seguir, identifique a declaração correta de uma lista, sua impressão
e tipo:
 A) lista = {"A": "Abacate", "B": "Bola", "C": "Cachorro"}print(lista["A"])
# Abacate
 B) minha_lista = {1, 2, 3, 4,
5}print{minha_lista}print{type{minha_lista}}
 C) tupla = (1, 2, 3)tupla = 1, 2, 3print(type(tupla))
 D) minha_lista = [1, 2, 3, 4,
5]print(minha.lista)print(type(minha.lista))
 E) minha_lista = [1, 2, 3, 4,
5]print(minha_lista)print(type(minha_lista))
Questão 13
Os grafos podem ser denominados de acordo com algumas características, considerar as alternativas
verdadeiras para um grafos não orientado.
I) Chamamos de grafos não orientados quando não há orientação na ligação entre os vértices, há uma
relação simétrica.
II) Xadrez tem sua representação por um grafo não direcionado, pois tanto faz dizer que A joga com B e
B joga com A, não faz diferença. Variações: grafos não orientados, não direcionados, não dirigidos.
III) Grafo não-direcionado desconexo quando precisamos representar uma situação em que há
elementos, que fazem parte do grafo, mas estão desconexos. Por exemplo, usuários em uma rede social
em que ainda apenas criou seu usuário e não teve nenhuma interação.
 A) n.d.a
 B) I e II são falsas
 C) I e III apenas são verdadeiras
 D) I, II e III são falsas
 E) I, II e III são verdadeiras
Questão 14
Em Python, tanto os métodos e as propriedades de uma classe são chamados de __________. Então,
quando for mencionado _________, pode ser um método da classe ou uma propriedade.
Por convenção dos programadores Python, usamos o carácter sublinhado (mais conhecido com
__________ ou ____________) no início do nome dos atributos para indicar que são "privados". Observe que
convenção significa que é um acordo entre as pessoas. O interpretador da linguagem Python não
interpreta que sejam "privados" e não impedirá de serem chamados fora da classe.
 A) métodos; atributo; arresta ou underline
 B) privados; atributos; underscore ou underline
 C) atributos; atributo; underscore ou underline
 D) underscore; underline; atributos ou atributo
 E) profundidade; profundidade; altura ou arrestas
Questão 15
Elia os pontos importantes dos modelos de estruturas de dados, algoritmos e sistema binário,
identifique (V) para verdadeiro e (F) para falso, assinale a alternativa correta.
I) Modelos de estruturas de dados: Compreender como esses dispositivos armazenam e manipulam
informações. Forma como dados são armazenados na memória e como o sistema pode acessá-los.
II) Algoritmos: Sequência finita de instruções para se resolver um problema, pois é uma forma utilizada
para definirmos como as tarefas serão executadas. Algoritmos estão presentes em quase tudo na nossa
vida. Além dos tradicionais computadores e notebooks, smartphones e tablets, TVs inteligentes podem
executar programas personalizados. Algoritmo é a base necessária para quem quer aprender em
linguagens famosas do mercado, como C, Java, PHP e muitas outras.
III) Sistema binário: Em computação, a unidade básica de armazenamento é o bit. No sistema de
numeração binário, um conjunto de 8 bits forma 1 byte. 2^8=256 valores.
 A) I, II e III são falsas
 B) n.d.a
 C) I e III apenas são verdadeiras
 D) I, II e III são verdadeiras
 E) I e II são falsas
Questão 16
Identifique como verdadeiro ou falso os pontos principais de estruturas Bulit-in:
I) Lista: Lista de elementos. Pode receber elementos de tipos distintos, como strings, números inteiros,
booleanos ou até mesmo outras listas, tuplas e dicionários.
II) Dicionário: Um dicionário pode ser interpretado como lista composta por conjuntos de pares chave-
valor.
III) Tupla: Uma tupla pode ser considerada uma lista imutável de elementos. Uma vez criada, não pode
ser alterada.
IV) Conjunto: Conjuntos de elementos únicos.
 A) I, II, III são falsas
 B) n.d.a
 C) Todas são falsas
 D) Todas são verdadeiras
Fechar
 E) I e II apenas são verdadeiras