APOL 1 e 2 - Estrutura De Dados

Prévia do material em texto

Questão 1/10 - Estrutura de Dados
Chamamos de análise assintótica de algoritmos quando encontramos a complexidade de um algoritmo de maneira aproximada através de uma curva de tendência. Este tipo de análise e é a mais adotada para compararmos desempenho de algoritmos. Para podermos comparar a complexidade dos algoritmos, podemos analisá-los matematicamente. A notação mais comum adotada na literatura para comparar algoritmos e dizer o quão rápido um algoritmo é, é a notação Big-O (ou “Grande-O”). (Adaptada)
Acerca complexidade de um algoritmo, assinale a alternativa INCORRETA:
Nota: 10.0
	
	A
	Um algoritmo com três laços de repetição não encadeados contém uma complexidade assintótica, para o pior caso, O(n).
	
	B
	Na análise assintótica, fazemos o conjunto de dados de entrada da função custo tender ao infinito, mantendo na equação somente o termo de maior grau, ou seja, aquele que mais cresce na equação.
	
	C
	Um algoritmo com três laços de repetição aninhados contém uma complexidade assintótica, para o pior caso, O(n³).
	
	D
	A complexidade assintótica para o pior caso, também conhecida como Big O, representa o pior cenário para um algoritmo, ou seja, quando mais instruções precisam ser executadas, levando mais tempo para finalizar a execução.
	
	E
	A complexidade assintótica para o pior caso de um algoritmo contendo dois laços de repetição aninhados, sendo que o segundo laço só será executado caso uma condicional simples seja verdadeira, será O(n).
Você assinalou essa alternativa (E)
Você acertou!
AULA 1 –tema 2 e TEMA 3. O pior caso (BigO) nos diz que todas as linhas devem ser executadas, ou seja, a condicional será sempre verdadeira, e ambos laços de repetição serão sempre executados, sendo assim, complexidade O(n²).
 
Questão 2/10 - Estrutura de Dados
Considere um vetor ordenado:
O  vetor é dividido ao meio.
O número do meio é comparado com o número procurado. Se forem iguais a busca termina, senão se o número procurado é menor que o do meio, a busca é realizada no subvetor a esquerda, se é maior no subvetor a direita. O procedimento é repetido até que o vetor fique com um elemento ou se encontre o desejado.
 As instruções acima se referem a:
Nota: 10.0
	
	A
	Busca (ou Pesquisa) sequencial
	
	B
	Busca (ou Pesquisa)  Linear
	
	C
	Busca (ou Pesquisa) Binaria
Você assinalou essa alternativa (C)
Você acertou!
Aula 1  - Tema 1
	
	D
	Ordenação por troca
	
	E
	Ordenação por seleção
Questão 3/10 - Estrutura de Dados
Quanto a análise de algoritmos assinale a alternativa correta:
Nota: 0.0Você não pontuou essa questão
	
	A
	Quando se fala algoritmo mais eficiente para resolver um problema, estamos nos referindo ao algoritmo de maior complexidade.
	
	B
	 A complexidade de tempo analise a quantidade de instruções do código, não impactando diretamente em seu desempenho.
	
	C
	A quantidade de variáveis em um algoritmo e seus tamanhos impactam diretamente em seu desempenho.
Aula 1 – tema 2
	
	D
	 Quando um algoritmo  é  complexo em tempo,  ele é necessariamente complexo também em espaço.
Você assinalou essa alternativa (D)
	
	E
	A análise de algoritmos é altamente dependentemente do hardware.
Questão 4/10 - Estrutura de Dados
Uma estrutura de dados é uma pilha quando só conseguimos manipular o que está em seu topo. Uma estrutura de pilha em programação opera como princípio chamado o primeiro que entra é o último que sai. A expressão correspondente em inglês é first in last out (filo) . Uma estrutura de dados operando como uma fila, opera com o princípio de o primeiro que entra é o primeiro que sai, ou em inglês, first in first out (fifo) .
Inserindo a seguinte sequência em uma pilha:
 
23, 44, 29, 12, 25, 60, 80, 29, 18
Teríamos a pilha:
I.(Topo) __________________________________________________
Retirando da pilha e inserindo na fila, teríamos a fila:
II.(começo)_________________________________________________(fim)
As estruturas pilha e fila terão, respectivamente, os valores:
Nota: 10.0
	
	A
	I.18,29,80,60,25,12,29,44,23
II.23, 44, 29, 12, 25, 60, 80, 29,18
	
	B
	I.18,29,80,60,25,12,29,44,23
II.18,29,80,60,25,12,29,44,23
Você assinalou essa alternativa (B)
Você acertou!
Aula 3 – temas 3 e 4
	
	C
	I.23, 44, 29, 12, 25, 60, 80, 29,18
II.18,29,80,60,25,12,29,44,23
	
	D
	I.23, 44, 29, 12, 25, 60, 80, 29,18
II.23, 44, 29, 12, 25, 60, 80, 29,18
	
	E
	N.D.A (Nenhuma das alternativas)
Questão 5/10 - Estrutura de Dados
Considere o trecho de código abaixo:          
a = 1 
b = a*10      
if a > b:        
    c = a        
else:  
    c = b
 Acerca do código acima são feitas as seguintes afirmativas:
 I. Cada operação (linha de código) tem complexidade assintótica O(1).
II. Todas as operações são constantes, ou seja, executa da mesma forma para entradas grandes ou pequenas.
III. A complexidade do código em questão é a soma de todas as complexidades, no caso: O(1) + O(1) + O(1)+ O(1)+ O(1)+ O(1)= O(6n).
Estão corretas as afirmativas:
Nota: 10.0
	
	A
	I somente. 
	
	B
	II somente.
	
	C
	I e II somente.
Você assinalou essa alternativa (C)
Você acertou!
Aula 1 – tema 3
	
	D
	I e III somente.
	
	E
	II e III somente.
Questão 6/10 - Estrutura de Dados
Na aula 3 de nossa disciplina estudamos estruturas de dados que se comportam como uma FILA. (Adaptada)
Acerca de FILAS, assinale a alternativa CORRETA:
Nota: 10.0
	
	A
	Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Inserir na fila significaria inserir um elemento que aponte para o valor 66.
	
	B
	Em uma fila, podemos ter a inserção dos dados no início desta fila.
	
	C
	Em uma fila, podemos ter a remoção dos dados final ou no meio desta fila.
	
	D
	Em uma fila trabalhamos com o conceito de: “o primeiro que entra é o primeiro que sai”.
Você assinalou essa alternativa (D)
Você acertou!
Aula 3 – tema 4
	
	E
	Uma fila onde o primeiro elemento é o 66, o segundo é o 33 e o terceiro é o 99. Remover da fila significaria remover o elemento 99.
Removeria o 66 (remoção no início da fila).
 
 
Questão 7/10 - Estrutura de Dados
Os métodos de ordenação são algoritmos muito utilizados quando é necessário que os dados de uma lista de valores, originalmente desordenada, sejam recuperados de maneira ágil e facilitada. Entre os métodos de ordenação eficientes, alguns dos mais conhecidos são aqueles que utilizam a estratégia da divisão e conquista, na qual um problema deve ser dividido em vários problemas menores, que serão solucionados até que o problema maior possa ser completamente resolvido.
Vetorazzo, Adriana de, S. et al. Estrutura de dados. Disponível em: Minha Biblioteca, Grupo A, 2018.pag43 (modificado)
Considerando o texto base e o conteúdo aprendido em aula são feitas as seguintes afirmações:
I. São exemplos de algoritmos de divisão e conquista o Merge  sort e o  Quicksort.
II. O Bubble sort é também conhecido como algoritmo de ordenação por intercalação.
III. O Quick sort define um elemento chamado pivô para se iniciar as comparações.
 Estão corretas as afirmativas:
Nota: 10.0
	
	A
	I somente.
	
	B
	I e II somente.
	
	C
	I e III somente.
Você assinalou essa alternativa (C)
Você acertou!
Aula 2. Tema1(bubble sort), tema2 (Merge Sort),tema4(quick sort)
	
	D
	II e III somente
	
	E
	I, II e III.
Questão 8/10 - Estrutura de Dados
Observe o trecho do algoritmo abaixo e analise o seu comportamento 
X = [6, 5, 2, 3, 4, 1]
n = 0
troca = 1
while n <= len(X) and troca == 1:
    troca = 0
    for i in range(0, len(X)-1, 1):
        if X[i] > X[i+1]:
            troca = 1
            aux = X[i]
            X[i] = X[i+1]
            X[i+1] = aux
    n = n + 1
Analisando o comportamento do algoritmo que flutua para o topo o maior elemento, pode se afirmar que se trata de qual algoritmo de ordenação?
Nota: 10.0
	
	A
	Heapsort
	
	B
	Mergesort
	
	C
	Quicksort
	
	D
	Bubble sort
Você assinalou essa alternativa (D)
Você acertou!
Aula 2 tema1
	
	E
	Insertion sort
Questão 9/10 - Estrutura de Dados
Observe a descrição abaixo:
· Comparações são feitas entre elementos de um vetor
· Cada elemento de uma posição ié comparado com o elemento da posição i + 1
· Se a ordenação procurada é encontrada é feita uma troca de posições entre os elementos
A descrição em questão se trata do algoritmo de ordenação:
Nota: 10.0
	
	A
	Mergesort
	
	B
	Quicksort
	
	C
	Bubblesort
Você assinalou essa alternativa (C)
Você acertou!
Aula 2 – tema 1
	
	D
	Hashsort
	
	E
	Insertion sort
Questão 10/10 - Estrutura de Dados
A técnica de divisão e conquista consistem de 3 passos básicos: 
1.Divisão: Dividir o problema original, em subproblemas menores. 
2.Conquista: Resolver cada subproblema recursivamente. 
3.Combinação: Combinar as soluções encontradas, compondo uma solução para o problema original.
 É um exemplo de algoritmo de divisão e conquista:
Nota: 10.0
	
	A
	Insertion sort
	
	B
	Mergesort
Você assinalou essa alternativa (B)
Você acertou!
Aula 2 tema 2
	
	C
	Bubblesort
	
	D
	Selection sort
	
	E
	Searchsort
Questão 1/10 - Estrutura de Dados
"Muito esforço tem sido feito em busca de funções de hashing eficientes, isto é, que sejam computadas rapidamente e que efetuem uma distribuição uniforme de chaves. Felizmente, a função de hashing mais eficiente encontrada, chamada método da divisão, é também a mais fácil de ser implementada. O  método da divisão,  divide a chave c pelo tamanho do vetor m e usa o resto da divisão como índice. Isso funciona bem para qualquer m; mas, se m é um número primo, o espalhamento tende a ser mais uniforme."
Pereira, Silvio do Lago. Estruturas de dados em C : uma abordagem didática / Silvio do Lago Pereira. São Paulo : Érica, 2016. Pag 125
Considerando o texto base e que  você tem disponível, para utilizar como palavras-chave, valores numéricos inteiros de 4 dígitos. Você decide que irá agrupar os dígitos em pares e somá-los para usar como chave. Por exemplo, o número 1234, será: 12 + 34 = 46.
Considere ainda que você tem um vetor de dimensão 100 (posições 0 até 99) disponível para armazenamento e que irá adotar o método da divisão.
Assinale a alternativa INCORRETA:
	
	A
	A palavra-chave 0125 será inserida na posição 26. Porém, se alterarmos o tamanho do vetor para 110, a nova posição desta chave será 36.
Você assinalou essa alternativa (A)
	
	B
	A palavra-chave 4455, será inserida na última posição disponível do vetor.
	
	C
	A palavra-chave 9128, será inserida na posição 19 do vetor.
	
	D
	O maior valor possível representado com 4 dígitos será colocado na posição 98.
	
	E
	A palavra-chave 1873, será inserida na posição 91 do vetor.
Questão 2/10 - Estrutura de Dados
Uma função Hash representa a aplicação de um algoritmo sobre determinado arquivo eletrônico, que é imutável, fixo e único para cada arquivo. Qualquer alteração no arquivo, mesmo que seja simples configuração de estilo, acréscimo ou supressão de caractere, resultará em alteração da função Hash. 
MARCHSIN, Karina Bastos K. Blockchain e smart contracts: As inovações no âmbito do Direito. Editora Saraiva, 2022. Pag 35
Quanto as funções hash, são feitas as seguintes afirmativas:
I. Algoritmo de hash, é uma expressão aritmética e/ou lógica específica para resolver uma determinada aplicação.
II. A função hash apresenta uma fórmula definida, sendo projetada levando-se em consideração  apenas o tamanho do conjunto de dados.
III. O desenvolvimento de uma boa função de hash é essencial para que o armazenamento dos dados, a busca e o tratamento de colisões ocorram de forma mais eficiente possível.
Assinale a alternativa que tem apenas afirmativa(s) correta(s):
	
	A
	I apenas
	
	B
	II apenas
	
	C
	I e II apenas
	
	D
	I e III apenas
Você assinalou essa alternativa (D)
	
	E
	II e III  apenas
Questão 3/10 - Estrutura de Dados
"Formalmente, define-se uma árvore T como um conjunto de nós que armazenam elementos em relacionamentos pai-filho com as seguintes propriedades:
Se T não é vazia, ela tem um nó especial chamado de raiz de T, que não tem pai.
Cada nodo v de T diferente da raiz tem um único nó pai, w; todo nó com pai w é filho de w."
GOODRICH, Michael T.; TAMASSIA, Roberto. Estruturas de Dados e Algoritmos em Java.  Grupo A, 2013.Pag 303
Dada a seguinte árvore binária:
São feitas as seguintes afirmativas:
I. O nó 2 tem 2 filhos
II. A arvore possui 4 nós folhas.
III. Temos 2 nós no nível 2 .
Levando em consideração o texto base e o conteúdo visto em aula, a alternativa corretas  é:
	
	A
	Está correta a afirmativa I apenas.
	
	B
	Está correta a afirmativa II apenas.
	
	C
	Estão corretas as afirmativas  I e II apenas.
Você assinalou essa alternativa (C)
	
	D
	Estão corretas as afirmativas  I e III apenas.
	
	E
	Estão corretas as afirmativas  II e III apenas
Questão 4/10 - Estrutura de Dados
Muitas aplicações exigem um conjunto dinâmico que suporte somente as operações de dicionário INSERT, SEARCH e DELETE. Por exemplo, um compilador que traduz uma linguagem de programação mantém uma tabela de símbolos na qual as chaves de elementos são cadeias de caracteres arbitrários que correspondem a identificadores na linguagem.
CORMEN, Thomas. Algoritmos - Teoria e Prática. Grupo GEN, 2012. Pag 184
O trecho do texto acima faz uma menção a uma estrutura de dados, conhecida como:
	
	A
	Lista
	
	B
	Fila
	
	C
	Pilha
	
	D
	Tupla
	
	E
	hash
Você assinalou essa alternativa (E)
Questão 5/10 - Estrutura de Dados
Basicamente, a função  de hashing realiza um mapeamento dos registros de um arquivo por meio de um campo “chave”. A “chave” normalmente é determinada por um campo que possui um valor unívoco e, portanto, funciona como o identificador do arquivo, como, por exemplo, o RG de uma pessoa. Com esse mapeamento, um campo ou um conjunto de campos chaves e´ relacionado a um ou mais enderec¸os ou posições onde os registros estão  armazenados.
Lima, Diana M., D. e Luis E. F. Gonzalez. Matemática aplicada à informática (Tekne). Disponível em: Minha Biblioteca, Grupo A, 2015.pag57
Acerca de hashs, vetores e tipos de endereçamento, assinale a alternativa INCORRETA:
	
	A
	O uso de tabela hash é capaz de transformar o tempo de busca de um dado em uma estrutura de dados do tipo vetor, em uma complexidade que independe do tamanho do conjunto de dados.
	
	B
	Podemos definir a posição de inserção de um dado no vetor utilizando uma função hash. Esta função será uma equação lógica e/ou matemática.
	
	C
	O endereçamento aberto em um vetor é aquele onde armazenamos um novo dado na primeira posição livre disponível no vetor.
	
	D
	O acesso a qualquer dado de um vetor com endereçamento direto é realizado com O(1), bem como o tempo de busca de uma informação neste vetor.
Você assinalou essa alternativa (D)
	
	E
	Palavra-chave em uma tabela hash é aquele dado utilizado no cálculo de uma posição utilizando um algoritmo de hash.
Questão 6/10 - Estrutura de Dados
“Dois matemáticos russos, G. M. Adel’son-Vel’skiî e E. M. Landis, publicaram em 1962 um artigo que descreve um algoritmo para manter o equilíbrio global de uma árvore de busca binária. Seu algoritmo controla a diferença de altura das subárvores. À medida que itens são adicionados à árvore (ou removidos dela), o fator de balanceamento** (isto é, a diferença entre as alturas das subárvores) de cada subárvore do ponto de inserção até a raiz é mantido. Se a um dado momento, o fator de balanceamento sair do intervalo -1 ... +1, a subárvore sofre uma rotação para retornar ao equilíbrio. As árvores que utilizam essa abordagem são conhecidas como árvores AVL, em homenagem aos seus inventores. Como antes, definimos a altura de uma árvore como o número de nós no maior caminho da raiz a um nó folha, inclusive a raiz.”
 KOFFMAN, Elliot B.; WOLFGANG, Paul A T. Objetos, Abstração, Estrutura de Dados e Projeto Usando C++. Grupo GEN, 2008. E-book. ISBN 978-85-216-2780-7. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/978-85-216-2780-7/. Acesso em: 07 dez. 2022. Capítulo 11.
Observe um exemplo de árvore AVL abaixo:
Considere  que o fator de balanceamento é calculado considerando  a árvore da direita – esquerda. Suponha que você quer remover o nó folha de valor 99. Acerca do balanceamentoe rotação desta árvore sem o 99.
Assinale a alternativa CORRETA:
	
	A
	A árvore ficará balanceada e não precisará de rotação nenhuma.
	
	B
	A árvore ficará com um desbalanceamento de valor 2 na raiz.
	
	C
	O nó filho de valor 80 está com balanceamento 0, resultando em uma rotação simples para a direta.
Você assinalou essa alternativa (C)
	
	D
	A árvore está com um desbalanceamento de valor -2 na raiz, resultando em uma rotação simples para a esquerda.
	
	E
	O nó filho de valor 80 está com balanceamento 1, resultando em uma dupla com filho para a esquerda e pai para a direita.
Questão 7/10 - Estrutura de Dados
Observe o grafo:
Considerando o grafo ilustrado acima, assinale a opção em que é apresentada a descrição em vértices (V) e arestas (A).
	
	A
	V = {A,B,C,D,E } 
A = {(A, B), (A,C), (A, E), (C, E), (C, D),(E,A)}
	
	B
	V = {A,B,C,D,E } 
A = {(A, B),(A,C), (A,E),(C, D), (C, E)}
	
	C
	V = {A,B,C,D,E } 
A = {(E, A),(A,B) (B,C),  (C, E), (C, D)}
	
	D
	V = {A,B,C,D,E } 
A = {(A, B), (B,C), (A, C), (C, E), (C, D),(E,A)}
Você assinalou essa alternativa (D)
	
	E
	V = {A,B,C,D,E } 
A = {(C, E),(E,A),(A,B) (B,C),  (C, E), (C, D)}
 
Questão 8/10 - Estrutura de Dados
Observe a figura a seguir:
Uma razão para estudarmos grafos é encontrar um caminho entre vértices. ... Um vértice é adjacente a um outro vértice se existe uma aresta para ele a partir do outro vértice. ..Um caminho é uma seqüência de vértices em que cada vértice sucessivo é adjacente ao seu predecessor.
Koffman, Elliot, B. e Paul A. T. Wolfgang. Objetos, Abstração, Estrutura de Dados e Projeto Usando C++. Disponível em: Minha Biblioteca, Grupo GEN, 2008.
Considerando o texto base, o conteúdo visto em aula e o grafo acima são feitas as seguintes afirmativas
I. Philadelphia é adjacente a Pittsburgh que é adjacente a Cleveland.
II. Philadelphia é adjacente a Columbus, mas não a Cleveland.
III. A seguinte seqüência de vértices é um caminho Philadelphia ? Pittsburgh ? Columbus ? Indianapolis ? Chicago. 
 
Estão corretas as afirmativas: 
	
	A
	I apenas.
	
	B
	II apenas.
	
	C
	I e II apenas.
	
	D
	I e III apenas.
Você assinalou essa alternativa (D)
	
	E
	II e III  apenas.
Questão 9/10 - Estrutura de Dados
Observe o código de consulta em ordem na árvore, assumindo que os dados cadastrados são do tipo inteiro.
1 def emOrdem(self,lst):
2    if (self.esquerda):
3        self.esquerda.emOrdem(lst)
4    lst.append(self.dado)
5    if(self.direita):
6        self.direita.emOrdem(lst)
7    return lst
Acerca de consulta em árvore e do código acima, alternativa INCORRETA:
	
	A
	Retirando a linha 4 e colocando logo após a definição da função (inserindo portanto na linha 2), a consulta em pré ordem aconteceria.
	
	B
	A função deve receber como parâmetro uma lista, representada por lst
	
	C
	A consulta em pos ordem ocorrerá se invertermos o bloco do segundo if pelo primeiro if .
	
	D
	A linha 2 verifica se a variável esquerda é igual a None.
Você assinalou essa alternativa (D)
	
	E
	A função retorna uma lista ordenada crescente.
Questão 10/10 - Estrutura de Dados
"Uma árvore binária de busca tem a seguinte propriedade: para cada nó n da árvore, todos os valores armazenados em sua subárvore à esquerda (a árvore cuja raiz é o filho à es-querda) são menores que o valor v armazenado em n, e todos os valores armazenados na subárvore à direita são maiores ou igual a v."
DROZDEK, Adam. Estrutura de Dados e Algoritmos em C++ – Tradução da 4ª edição norte-americana. Cengage Learning Brasil, 2018. E-book. ISBN 9788522126651. Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788522126651/. Acesso em: 07 dez. 2022.PAG189
Observe o código abaixo:
1 class BST:
2    def __init__(self,dado=None):
3        self.dado = dado
4        self.esquerda = None
5        self.direita = None
6
7    def inserir(self, dado):
8        if(self.dado ==None):
9            self.dado = dado
10        else:
11            if(dado <self.dado):
12                if(self.esquerda):
13                    self.esquerda.inserir(dado)
14                else:
15                    self.esquerda = BST(dado)
16            else:
17                if(self.direita):
18                    self.direita.inserir(dado)
19                else:
20                    self.direita = BST(dado)
Considerando o texto, o conteúdo visto em aula e o código acima, assinale a alternativa INCORRETA:
	
	A
	O trecho de código que representa a inserção do nó raiz está nas linhas 8 e 9.
	
	B
	O trecho de código que  armazena os nós maiores que a raiz é representado pelas linhas 16 a 20.
	
	C
	O trecho de código que armazena os nós menores que a raiz é representado pelas linhas de 8 a 13.
Você assinalou essa alternativa (C)
	
	D
	A função init é um construtor da classe BST, inicializando as variáveis esquerda e direita com o valor None.
	
	E
	A função inserir é uma função recursiva, sendo chamada nas linhas 13 e 18.