Baixe o app para aproveitar ainda mais
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
Compartilhar