ATIVIDADE 3 – ADSIS – ESTRUTURA DE DADOS I – 52_2024

ATIVIDADE 3 – ADSIS – ESTRUTURA DE DADOS I – 52_2024

 

QUESTÃO 1

As filas, enquanto estruturas de dados fundamentais, desempenham um papel crucial em numerosas aplicações computacionais. O conceito de fila é essencial em uma variedade de cenários, desde o gerenciamento de tarefas em sistemas operacionais até a transmissão de dados em redes de computadores. A estrutura de dados de fila garante uma ordem precisa de processamento, permitindo que as operações sejam realizadas de forma previsível e eficiente. Isso se reflete no uso generalizado de filas em algoritmos de busca, escalonamento de recursos e até mesmo em simulações computacionais.

Fonte: Elaborado pelo professor, 2024.

 

Qual é a função de um algoritmo de enfileiramento (FILA) implementado em linguagem C?

 

Alternativas

 Alternativa 1 – Realizar operações de busca em uma lista encadeada.

 Alternativa 2 – Organizar os dados em uma estrutura hierárquica de árvore.

 Alternativa 3 – Organizar os dados em uma estrutura linear de acesso FIFO (First In, First Out).

 Alternativa 4 – Armazenar os dados em uma estrutura linear de acesso LIFO (Last In, First Out).

 Alternativa 5 – Permitir a exclusão de elementos aleatórios com complexidade de tempo constante.

 

QUESTÃO 2

Existem inúmeras formas de representar computacionalmente um grafo, cada qual com suas vantagens e desvantagens em relação a complexidade de implementação, uso de memória, custo computacional de algoritmos como inserção, remoção, alteração e percurso. Dentre as formas de se representar grafos, podemos citar o vetor de arestas, as listas de adjacências e as matrizes de adjacências, dentre outras.

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.

 

Assim sendo, observe a matriz abaixo:

 

Levando em conta que a matriz a cima representa um grafo com 4 vértices V = {a, b, c, d}, avalie as afirmações a seguir:

 

I – Esse é um, sem dúvida, um grafo não-orientado.

II – Esse grafo poderia ser representado, alternativamente, por uma lista de adjacências.

III – Esse é um grafo ponderado.

 

De acordo com as afirmações acima, é possível dizer que está(ão) correta(s) a(s) afirmativa(s):

 

Alternativas

 Alternativa 1 – I, apenas.

 Alternativa 2 – II, apenas. 

 Alternativa 3 – III, apenas.

 Alternativa 4 – I e II, apenas.

 Alternativa 5 – II e III, apenas.

 

QUESTÃO 3

Em computação, a pilha é um tipo de estrutura na qual os dados são adicionados e removidos exclusivamente do topo. Essas estruturas são comumente referidas como Last In, First Out (LIFO), o que significa que o último dado a ser inserido será o primeiro a ser removido.

Fonte: Elaborado pelo professor, 2024.

 

Qual é o resultado da operação em uma pilha que tinha vários elementos, mas no momento da execução de desempilhar um elemento a pilha estava vazia?

 

Alternativas

 Alternativa 1 – Retorna NULL.

 Alternativa 2 – Deveria lançar uma exceção de pilha vazia.

 Alternativa 3 – Retorna o elemento que foi removido da pilha.

 Alternativa 4 – Remove o elemento da pilha sem retornar qualquer valor.

 Alternativa 5 – Aumenta o tamanho da pilha para 1 e insere o elemento desempilhado.

 

QUESTÃO 4

Filas são amplamente empregadas como estruturas de dados, embora sua dinâmica apresente complexidades adicionais em comparação com pilhas. O princípio fundamental subjacente a todas as filas é o FIFO (First In, First Out), que, traduzido, significa que o primeiro elemento a ser inserido na fila é também o primeiro a ser retirado dela. Assim sendo, análise o trecho de código a seguir contendo a estrutura de dados da fila:

 

typedef struct {

int itens[MAX]; // MAX é o tamanho máximo da fila

int frente, tras;

} Fila;

Fonte: Elaborado pelo professor, 2024.

 

Assinale a alternativa que contenha o trecho de código que faça a implementação correta da função em C para verificar se uma fila está vazia.

 

Alternativas

 Alternativa 1 – int fila_vazia(Fila *f) { if (f->frente == f->tras) return 1; else return 0; }

 Alternativa 2 – int fila_vazia(Fila *f) { if (f->frente == -1 && f->tras == -1) return 1; else return 0; }

 Alternativa 3 – int fila_vazia(Fila *f) { if (f->frente == 0 && f->tras == 0) return 1; else return 0; }

 Alternativa 4 – int fila_vazia(Fila *f) { if (f->frente == -1 || f->tras == -1) return 1; else return 0; }

 Alternativa 5 – int fila_vazia(Fila *f) { if (f->frente == NULL && f->tras == NULL) return 1; else return 0; }

 

QUESTÃO 5

Os grafos permitem modelar de forma matemática problemas reais de logística, custos, eficiência dentre muitos outros. Considerando o grafo ilustrado abaixo.

 

Assinale a alternativa em que é apresentada a descrição em vértices (V) e arestas (E) do grafo acima.

 

Alternativas

 Alternativa 1 – V = {1, 2, 3, 4, 5, 6 } e E = {(2, 4), (2, 3), (2, 5), (3, 6), (1, 5)}

 Alternativa 2 – V = { 2, 4, 1, 3, 6, 5 } e E = {(4, 2), (3, 1), (5, 2), (6, 3), (5, 3)}

 Alternativa 3 – V = {1, 2, 3, 4, 5, 6 } e E = {(4, 2), (3, 4), (5, 2), (6, 3), (5, 3)}

 Alternativa 4 – V = {1, 2, 3, 4, 5, 6 } e E = {(4, 2), (3, 1), (5, 1), (6, 2), (5, 3)}

 Alternativa 5 – V = { 2, 4, 1, 3, 6, 5 } e E = {(2, 3), (1, 4), (5, 2), (6, 3), (5, 3)}

 

QUESTÃO 6

Ao trabalharmos com vetores em linguagem de programação, temos duas opções de uso: estáticos e dinâmicos. Quando criamos um vetor estático, dizemos na sua declaração qual será o seu tamanho, mas em vetores dinâmicos o seu tamanho definido em tempo de execução do programa.

Fonte: Elaborado pelo professor, 2024.

 

Qual é a principal vantagem dos vetores dinâmicos em comparação com os vetores estáticos em linguagens de programação?

 

Alternativas

 Alternativa 1 – Vetores dinâmicos possuem tamanho fixo, o que facilita a alocação de memória.

 Alternativa 2 – Vetores dinâmicos são mais eficientes em termos de uso de memória e tempo de execução do que os vetores estáticos.

 Alternativa 3 – Vetores dinâmicos só podem armazenar um tipo específico de dados, enquanto os vetores estáticos podem armazenar uma variedade de tipos.

 Alternativa 4 – Vetores dinâmicos são estáticos em termos de tamanho, mas dinâmicos em termos de conteúdo, o que os torna mais previsíveis e seguros.

 Alternativa 5 – Vetores dinâmicos permitem redimensionamento durante a execução do programa, adaptando-se às necessidades de armazenamento de dados.

 

QUESTÃO 7

Em um programa que utiliza estrutura de dados em pilha para gerenciar o histórico de páginas visitadas em um navegador web, considere que essa pilha é implementada de forma estática com capacidade máxima para 10 elementos.

Fonte: Elaborado pelo professor, 2024.

 

Qual operação deve ser realizada quando um usuário acessa uma nova página?

 

Alternativas

 Alternativa 1 – IsEmpty: Verificar se a pilha está vazia.

 Alternativa 2 – Push: Adicionar a nova página no topo da pilha.

 Alternativa 3 – Top: Visualizar a página atual sem removê-la da pilha.

 Alternativa 4 – Pop: Remover a página mais recente do topo da pilha.

 Alternativa 5 – IsFull: Verificar se a pilha atingiu sua capacidade máxima.

 

QUESTÃO 8

O algoritmo de busca em profundidade, quando aplicado a grafos, tem a propriedade de investigar todo um caminho até encontrar um “nó folha”, ou até que não seja possível mais ir a fundo no grafo. É um algoritmo bastante utilizado em aplicações computacionais e utiliza uma pilha para controlar a ordem de visitação dos nós.

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.

 

Sabendo disso, realize uma busca em profundidade no grafo a seguir, tomando como início o nó 10.

 

Dessa forma, a ordem correta de visitação é:

 

Alternativas

 Alternativa 1 – 10, 30, 60, 20, 70, 50, 40

 Alternativa 2 – 10, 20, 40, 50, 70, 30, 60 

 Alternativa 3 – 10, 20, 30, 40, 50, 60, 70

 Alternativa 4 – 10, 20, 30, 60, 50, 40, 70

 Alternativa 5 – 10, 70, 20, 60, 50, 30, 40

 

QUESTÃO 9

As aplicações da busca em largura são diversas. Por exemplo, uma empresa do ramo logístico poderia mapear suas rotas em forma de grafos e, em seguida, aplicar algoritmos baseados em busca em largura para traçar rotas automaticamente. A implementação da busca em largura depende do uso de uma fila, para controlar a visitação dos nós.

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.

 

Sabendo disso, aplique a busca em largura no grafo abaixo, iniciando a partir do nó 10.

 

Dessa forma, podemos dizer que a ordem de visitação correta é:

 

Alternativas

 Alternativa 1 – 10, 30, 60, 20, 70, 50, 40.

 Alternativa 2 – 10, 20, 40, 50, 70, 30, 60.

 Alternativa 3 – 10, 20, 30, 40, 50, 60, 70. 

 Alternativa 4 – 10, 20, 30, 60, 50, 40, 70.

 Alternativa 5 – 10, 70, 20, 60, 50, 30, 40.

 

QUESTÃO 10

“Muitos problemas podem ser descritos por meio de grafos, nos quais a solução para o problema requer que realizemos uma busca pelo grafo. As buscas, em geral, partem de um nó inicial em direção a um nó alvo, fazendo com que tenhamos que percorrer toda uma sequência ordenada de nós e arestas. Além disso, o próprio caminho, em si, pode ser objeto da busca, isto é, às vezes a solução reside no caminho percorrido, e não em um nó alvo específico.”

 

OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.

 

Considerando tanto o algoritmo de busca em largura, quanto em profundidade, para que seja possível que tais algoritmos consigam navegar por todos os nós de um grafo, é imprescindível que o grafo seja:

 

Alternativas

 Alternativa 1 – Um dígrafo.

 Alternativa 2 – Orientado.

 Alternativa 3 – Conexo. (Gabarito Oficial)

 Alternativa 4 – Ponderado.

 Alternativa 5 – Um multigrafo.