Buscar

Prova discursiva Estrutura de Dados 2020

Prévia do material em texto

Questão 1/3 - Estrutura de Dados 
Suponha uma estrutura de dados dinâmica e heterogênea, onde cada elemento pode ser 
representado como: 
 
Struct Elemento 
{ 
 int valor; 
 Elemento *proximo; 
} 
Explique através de um pseudocódigo, ou linguagem C, ou mesmo usando uma 
sequência de passos organizados (descrição narrativa), como se dá a INSERÇÃO de 
dados nesta estrutura apresenta, considerando que a estrutura irá operar como: 
a. First In First Out (FIFO) 
b. First In Last Out (FILO) 
Como nomenclatura, utilize as palavras head(ou top) para representar o inicio da 
estrutura, tail para representar o fim da estrutura. 
Nota: 33.3 
a) (50%) A estrutura citada no exercício (dinâmica e heterogênea) é do tipo LISTA 
ENCADEADA. FIFO explicita uma FILA. 
Portanto, a INSERÇÃO em uma FILA significa inserir NO FINAL da lista encadeada. 
Em pseudocódigo fica: 
 
Se (Head = NULO) então 
 Head = NovoElemento 
 Tail = NovoElemento 
Senão 
 Tail -> Proximo = NovoElemento 
 Tail = NovoElemento 
fimse 
 
b) (50%) A estrutura citada no exercício (dinâmica e heterogênea) é do tipo LISTA 
ENCADEADA. FILO explicita uma PILHA. 
Portanto, a INSERÇÃO em uma PILHA significa inserir NO TOPO(INICIO) da lista 
encadeada. Em pseudocódigo fica: 
 
Se (top = NULO) então 
 Top = NovoElemento 
Senão 
 NovoElemento->proximo = top 
 top = NovoElemento 
fimse 
 
(Nota para o corretor: conforme explicitado no enunciado, o aluno pode resolver este exercício não necessariamente em 
pseudocódigo. Ele poderá fazer em linguagem C, ou mesmo explicar em texto o que acontece) 
 
Resposta: First in first out -> Fila. Alocar espaço na memória Armazenar os dados no 
espaço alocado Se o head estiver vazio, insere no head. senão, vá ate que proximo seja 
nulo e insere no final atualiza as variaveis de controle first in last out -> Pilha Alocar 
espaço na memoria armazenar os dados no espaço alocado sempre inserir no top 
atualizar variaveis de controle 
 
Questão 2/3 - Estrutura de Dados 
O código abaixo, em linguagem C, serve para construir cada elemento de uma estrutura 
de dados do tipo grafo. 
 
struct ListaDeVizinhos 
{ 
 int vertice; 
 ListaDeVizinhos* prox; 
}; 
 
struct Grafo 
{ 
 int TotalVertices; 
 struct ListaDeVizinhos** ListaAdj; 
}; 
Acerca deste código de criação da estrutura do grafo, responda: 
a) O código apresentado serve para construir um grafo utilizando uma representação de 
matriz de adjacências ou de listas de adjacências? Porque? 
b) Explique para que servem, na construção do grafo, o registro chamado de Grafo e o 
registro chamado de ListaDeVizinhos, no código apresentado acima. 
Nota: 33.3 
a) (50%) Representa a criação de uma lista de adjacências. Se fosse uma matriz, 
teríamos uma estrutura de dados do tipo matriz (vetor bidimensional). 
 
b) (50%) O registro (struct) chamado de ‘Grafo’, será a base de criação do grafo. Ele 
manterá o numero total de vértices bem como uma lista/vetor de ponteiros para o inicio 
de cada lista encadeada de vizinhos. O registro ListaDeVizinhos é o que cria de fato a 
lista encadeada com os vizinhos de cada vértice. Se tivermos um grafo com 5 vértices, 
teremos 5 listas encadeadas de vizinhos. 
 
Resposta: a) Uma lista de adjacências, pois ira registrar o direcionamento das arestas 
b)A struct Grafo, ira armazenar os vértices, e a ListaDeVizinhos armazena os verticer 
ligados por arestas 
 
Questão 3/3 - Estrutura de Dados 
A sequência de Fibonacci é aquela cujo os 2 primeiros elementos da sequência são o 
valor 1 e, a partir do terceiro elemento, cada elemento da sequência é dado pela soma 
dos seus dois antecessores. 
Os primeiros elemento da sequência seriam: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 
 
Abaixo temos dois códigos distintos em linguagem C de uma função que calcula cada 
elemento da sequência de Fibonacci (ALGORITMO 1 e ALGORITMO 2). 
 
ALGORITMO 1: 
int fib(int n) 
{ 
 int i, fib1 = 1, fib2 = 1, soma; 
 
 for (i = 3; i <= n; i = i + 1) 
 { 
 soma = fib1 + fib2; 
 fib1 = fib2; 
 fib2 = soma; 
 } 
 return fib2; 
} 
 
ALGORITMO 2: 
int fib(int n) 
{ 
 if (n == 1) 
 return 1; 
 else 
 if (n == 2) 
 return 1; 
 else 
 return fib(n - 1) + fib(n - 2); 
} 
Analisando ambas funções apresentadas, responda: 
 
a) Qual a complexidade assintótica para o pior caso (notação BIG-O), para o 
ALGORITMO 1? Porque? 
b) Qual a complexidade assintótica para o pior caso (notação BIG-O), para o 
ALGORITMO 2? Porque? 
c) Considere um conjunto de dados com n = 1000. Qual dos algoritmos se sai melhor? 
Porque? Justifique através de cálculo matemático. 
d) Caso existisse um terceiro algoritmo com complexidade O(n²). Ele se sairia melhor 
ou pior do que os outros dois para n = 1000? Porque? Justifique matematicamente. 
Nota: 33.3 
a) (25%) Algoritmo 1: O(n). Porque temos um laço de repetição. 
b) (25%) Algoritmo 2: O(logn). Porque temos um algoritmo recursivo. 
c) (25%) O ALGORITMO 2 se sai melhor. Observe o cálculo matematico abaixo. Para 
n = 1000, temos um custo em tempo de execução igual a 3, enquanto que o 
ALGORITMO 1 tem custo 1000, bem pior. 
 Algoritmo 1: O(1000) = 1000. 
 Algoritmo 2: O(log 1000) = 3. 
d) (25%) ALGORITMO 3: O(1000²) = 1 milhão. Se sairia bem pior que ambos. 
 
Resposta: Algoritmo 1 tem complexidade n pois tem um laço de repetição enquanto o 
Algoritmo 2 possui complexidade 1 pois não apresenta nenhum laço de repetição Para 
um conjunto de dados n=1000 o Algoritmo 2 se sairia melhor pois ele tem 
complexidade 1 . para um O(n^2) seria pior do que os outros dois casos, uma função 
quadrática demanda mais tempo para realizar a tarefa pois os laços de repetição fazem 
com que o código execute muitas vezes os mesmos comandos então quanto maior o 
expoente maior será o numero de instruções que o algoritmo precisará executar

Outros materiais

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes