Mais um backup de conteúdo. 📚🎓😁 O backup de conteúdo foi a forma que encontrei de documentar minha jornada de estudos e de ter a liberdade de revisitar alguns conteúdos que considero importantes. E claro, compartilhar conhecimento com outras pessoas interessadas. Pegue seu cafezinho e venha aprender junto comigo.
O que são Estruturas de Dados?
Em C, uma estrutura de dados é uma maneira de organizar e armazenar dados na memória do computador. Pense nelas como "recipientes" que podem conter diferentes tipos de dados (números, caracteres, outras estruturas) de forma estruturada.
Por que Estruturas de Dados são Importantes?
Organização: Permitem agrupar informações relacionadas, facilitando a manipulação e o acesso.
Eficiência: A escolha da estrutura de dados certa pode melhorar drasticamente o desempenho do seu programa, especialmente ao lidar com grandes quantidades de dados.
Reusabilidade: Estruturas de dados bem projetadas podem ser reutilizadas em diferentes partes do seu código ou até mesmo em outros projetos.
Tipos Básicos de Estruturas de Dados em C
Vamos começar com algumas das estruturas de dados mais comuns em C:
Arrays (Vetores):
Uma coleção ordenada de elementos do mesmo tipo.
Acesso rápido a elementos individuais por meio de um índice.
Tamanho fixo após a criação.
Structs (Registros):
Uma coleção de elementos de diferentes tipos (campos).
Cada campo tem um nome e um tipo.
Útil para representar objetos complexos.
Uniões:
Uma variável que pode armazenar diferentes tipos de dados, mas apenas um de cada vez.
Útil para economizar memória quando diferentes tipos de dados são usados alternadamente.
Ponteiros:
Variáveis que armazenam endereços de memória.
Fundamentais para construir estruturas de dados dinâmicas (que podem crescer ou diminuir durante a execução do programa).
Estruturas de Dados Dinâmicas em C
As estruturas de dados dinâmicas são mais flexíveis que as estáticas (como arrays). Elas usam alocação de memória dinâmica para crescer ou diminuir conforme necessário. Alguns exemplos importantes:
Listas Encadeadas:
Uma sequência de nós, onde cada nó contém dados e um ponteiro para o próximo nó.
Podem ser facilmente modificadas (inserção e remoção de elementos).
Pilhas (Stacks):
Uma estrutura LIFO (Last In, First Out - o último a entrar é o primeiro a sair).
Operações principais: push (empilhar) e pop (desempilhar).
Filas (Queues):
Uma estrutura FIFO (First In, First Out - o primeiro a entrar é o primeiro a sair).
Operações principais: enqueue (enfileirar) e dequeue (desenfileirar).
Árvores:
Uma estrutura hierárquica com um nó raiz e nós filhos.
Útil para representar relações hierárquicas e para busca eficiente.
Grafos:
Uma coleção de nós (vértices) conectados por arestas.
Útil para representar relações complexas entre objetos.
QUESTIONÁRIO
A alocação dinâmica na memória é um processo essencial em muitas linguagens de programação modernas. Imagine que você está organizando uma festa surpresa para um amigo, e você não sabe exatamente quantas pessoas vão comparecer. Você poderia reservar um espaço em um restaurante que tem capacidade para um número específico de convidados. No entanto, se mais pessoas aparecerem do que o esperado, você pode ficar sem espaço e alguns convidados terão que ficar de fora. Agora, considere a mesma situação, mas desta vez você reserva um salão de festas flexível, onde você pode adicionar mais mesas e cadeiras conforme necessário. Desta forma, você está permitindo que o espaço se adapte ao número de convidados que aparecem. Da mesma forma, a alocação dinâmica, possibilita uma utilização eficiente da memória, evitando desperdício e permitindo que os programas sejam mais flexíveis e adaptáveis.
Fonte: Elaborado pelo professor, 2024.
Com base no contexto apresentado, assinale a afirmativa correta.
Alternativa 2:
Permitir que os programas reservem espaço de memória conforme necessário durante a execução.
Pilhas são estruturas de dados lineares nas quais uma regra específica para inserção e remoção de dados deve ser respeitada. A regra é a seguinte: o primeiro elemento a entrar, terá a menor prioridade no momento de sair.
Em suma, o primeiro que entra, é o último que sai.
OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.
Dessa forma, analise o trecho de código abaixo, no qual apenas a função de inserção na pilha foi programada:
Com base no exposto, avalie as afirmações que se seguem:
I – Pode-se dizer que, ao inserir um novo elemento nessa pilha, o topo é incrementado em uma unidade.
II – A função push(), da forma como está implementada, poderia gerar erros semânticos caso a pilha esteja lotada, com mais de 10 elementos inseridos na pilha.
III – Da forma como foi implementada a struct tpilha, está faltando, obrigatoriamente, o campo “int ini;”.
De acordo com as afirmações acima, é possível dizer que está(ão) correta(s) a(s) afirmativa(s):
Alternativa 2:
I e II, apenas.
Os ponteiros são elementos fundamentais na linguagem C, conferindo-lhe uma notável flexibilidade e poder. Eles funcionam como variáveis especiais que armazenam endereços de memória de outras variáveis, permitindo acessá-las diretamente. Quando dizemos que um ponteiro "aponta" para uma variável, significa que ele detém o endereço dessa variável na memória. Essa capacidade de apontar para diferentes tipos de variáveis, como inteiros, ponto flutuante, duplos, entre outros, confere aos ponteiros uma versatilidade excepcional.
Fonte: Elaborado pelo professor, 2024.
Dado o contexto, qual a função do operador de referência (&) em estruturas de dados utilizando ponteiros em linguagem C?
Alternativa 1:
Retorna o endereço de memória da variável.
No trecho de código a seguir, foi iniciado o desenvolvimento de uma fila estática que é implementada com auxílio de uma struct contendo um campo “dados” (vetor), um campo “ini” que deverá armazenar o índice do primeiro elemento da fila e um campo “fim” que deverá armazenar o índice do último elemento da fila.
OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.
Observe:
Linha | Código |
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 | #define tamanho 5
struct tfila { int dados[tamanho]; int ini; int fim; };
struct tfila fila;
void remove() { int i; for (i = 0; i < tamanho; i++) { fila.dados[i] = fila.dados[i+1]; } fila.dados[fila.fim] = 0; fila.fim--; } |
Com base em seus conhecimentos sobre filas estáticas, tomando como referência o código-fonte acima, avalie:
I – A função definida entre as linhas 11 e 18 é do tipo void, por isso não retorna valor algum.
II – A função remove() realiza o deslocamento dos dados da fila em uma posição da direção do fim à direção do início da fila.
III – Podemos considerar que o início da fila será, nesse caso, a posição 0 do vetor de dados da struct tfila.
De acordo com as afirmações acima, é possível dizer que está(ão) correta(s) a(s) afirmativa(s):
Alternativa 5:
I, II e III.
Os conceitos de variáveis homogêneas e heterogêneas, vetores, matrizes e registros, listas, filas, etc, são os elementos básicos necessários para um processo lógico e estruturado de formação do conhecimento, também para construir estruturas de dados mais avançadas.
Fonte: Elaborado pelo professor, 2024.
Dado o contexto, qual a estrutura de dados é a mais adequada para armazenar informações de alunos, contendo nome, idade, sexo, curso e média final?
Alternativa 3:
Registro
Estruturas de dados complexas são feitas a partir de estruturas mais simples. Variáveis únicas, vetores, matrizes, registros, todas elas fazem parte das composições necessárias para se elaborar estruturas mais específicas e mais úteis na solução de determinadas situações problema. Em linguagem C, temos sintaxes bem definidas para a declaração dessas estruturas e suas respectivas e implementações em soluções algorítmicas.
OLIVEIRA, Pietro Martins de; PEREIRA, Rogério de Leon. Estruturas de Dados I. Maringá: Unicesumar, 2019.
A respeito de estruturas de dados homogêneas e heterogêneas, analise as afirmações que se seguem.
I – Podemos dizer que vetores são arranjos estruturais lineares e unidimensionais.
II – Os registros (structs) permitem que criemos novos tipos de dados compostos a partir de outros tipos de dados.
III – Pode-se dizer que matrizes são estruturas de dados multidimensionais, podendo ser combinadas com structs.
De acordo com as afirmações acima, é possível dizer que está(ão) correta(s) a(s) afirmativa(s):
Alternativa 5:
I, II e III.
Ponteiros desempenham um papel crucial quando uma variável precisa ser acessada em diferentes partes de um programa. Nesse contexto, é comum encontrar diversos ponteiros distribuídos por várias seções do código, cada um apontando para a variável que contém os dados necessários. Uma vantagem significativa dessa abordagem é que, se esses dados forem alterados, não há preocupação, pois todos os ponteiros no programa estão direcionados para o endereço onde os dados atualizados residem. Essa flexibilidade oferecida pelos ponteiros é fundamental para garantir a eficiência e a consistência na manipulação de dados em diferentes partes do código.
Considerando o uso de ponteiros em estruturas de dados, analise o seguinte código em C:
#include <stdio.h> int main() { int arr[5] = {1, 2, 3, 4, 5}; int *ptr = arr; printf("%d\n", *ptr + 2); printf("%d\n", *(ptr + 2)); printf("%d\n", ptr[2]); printf("%d\n", *ptr++); printf("%d\n", (*ptr)++); return 0; } |
Fonte: Elaborado pelo professor, 2024.
Dado o contexto e analisando o código, qual será a saída impressa ao executar este código?
Alternativa 1:
3, 3, 3, 1, 2
Listas, pilhas e filas são estruturas de dados, que nos permitem organizar e interagir com nossos dados e organizá-los de diferentes formas. Em C++ existem bibliotecas que nos permitem implementar esses tipos de estruturas, o que torna nosso trabalho mais simples do que se tivéssemos de criá-las manualmente.
GOULART, Gabriel. Listas, pilhas e filas em C++. Portal GSTI. Disponível em: https://www.portalgsti.com.br/2018/04/listas-pilhas-e-filas-em-c.html acesso em: 09/02/2022.
A partir dessas informações, avalie as asserções a seguir e a relação proposta entre elas:
I. Pilha é uma coleção de elementos, que segue a ordem LIFO. O que significa que o elemento que é inserido mais recentemente será removido primeiro. Uma pilha tem uma restrição de que a inserção e exclusão do elemento só pode ser feita a partir de apenas uma extremidade da pilha e chamamos essa posição de topo.
PORQUE
II. Fila é uma estrutura de dados que segue o princípio FIFO. Sendo que o elemento adicionado primeiro na fila será o que será removido primeiro. Os elementos são sempre adicionados na parte de trás e removidos da frente.
A respeito dessas asserções, assinale a opção correta.
Alternativa 2:
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
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?
Alternativa 3:
Organizar os dados em uma estrutura linear de acesso FIFO (First In, First Out).
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?
Alternativa 2:
Deveria lançar uma exceção de pilha vazia.
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?
Alternativa 2:
Push: Adicionar a nova página no topo da pilha.
"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:
Alternativa 3:
Conexo.
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 é:
Alternativa 2:
10, 20, 40, 50, 70, 30, 60
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; } |
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 é:
Alternativa 3:
10, 20, 30, 40, 50, 60, 70.
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?
Alternativa 5:
Vetores dinâmicos permitem redimensionamento durante a execução do programa, adaptando-se às necessidades de armazenamento de dados.