DEPARTAMENTO DE CIÊNCIAS DE COMPUTAÇÃO SCC0202 – Algoritmos e Estruturas de Dados I 1ª lista de exercícios 1) Que é um Tipo Abstrato de Dados (T...

1) Um Tipo Abstrato de Dados (TAD) é uma estrutura de dados que define um conjunto de valores e as operações que podem ser realizadas sobre esses valores. A característica fundamental na sua utilização é que o usuário não precisa saber como os dados são armazenados ou como as operações são implementadas, apenas precisa saber como utilizá-las. 2) O programa A, construído de acordo com os princípios de TAD, possui uma interface bem definida e separada da implementação, o que permite que o usuário utilize as operações sem precisar conhecer a implementação. Já o programa B não possui essa separação, o que torna o uso das operações mais difícil e propenso a erros. 3) As vantagens de se programar com TADs incluem a facilidade de uso, a modularidade, a reutilização de código e a segurança, já que o usuário não precisa conhecer a implementação das operações. 4) Sistema de controle de empréstimos de uma biblioteca usando TAD: Dados: livros, usuários, empréstimos. Operações: cadastrar livro, cadastrar usuário, realizar empréstimo, devolver livro, consultar empréstimos. Organização: os dados podem ser organizados em listas encadeadas ou em tabelas hash. 5) Sistema de controle de reservas de um clube que aluga quadras poliesportivas usando TAD: Dados: quadras, reservas, usuários. Operações: cadastrar quadra, realizar reserva, cancelar reserva, consultar reservas. Organização: os dados podem ser organizados em listas encadeadas ou em tabelas hash. 6) Sistema de memória da programação de uma rádio: Dados: músicas, artistas, datas/horários de execução. Operações: cadastrar música, cadastrar artista, registrar execução, consultar execuções. Organização: os dados podem ser organizados em listas encadeadas ou em tabelas hash. 7) Uma pilha é uma estrutura de dados que permite a inserção e remoção de elementos apenas em uma extremidade, chamada topo. Ela segue o princípio LIFO (Last In, First Out), ou seja, o último elemento inserido é o primeiro a ser removido. 8) Alocação sequencial de memória para um conjunto de elementos significa que os elementos são armazenados em posições contíguas de memória, o que permite o acesso direto a qualquer elemento através de seu índice. 9) Alocação estática de memória para um conjunto de elementos significa que o tamanho do conjunto é fixo e definido em tempo de compilação. 10) Implementação sequencial e estática de uma pilha: Os dados são armazenados em um vetor de tamanho fixo. A pilha é representada por um índice que aponta para o topo da pilha. As operações de inserção e remoção são realizadas através do incremento e decremento desse índice. 11) Rotina para inverter a posição dos elementos de uma pilha P: Criar uma pilha auxiliar. Enquanto a pilha P não estiver vazia, remover o elemento do topo e inserir na pilha auxiliar. Depois, enquanto a pilha auxiliar não estiver vazia, remover o elemento do topo e inserir na pilha P. 12) Função para testar se uma pilha P1 tem mais elementos que uma pilha P2: Comparar o tamanho das pilhas P1 e P2. Se o tamanho de P1 for maior que o tamanho de P2, retornar verdadeiro. Caso contrário, retornar falso. 13) Função para testar se duas pilhas P1 e P2 são iguais: Comparar o tamanho das pilhas P1 e P2. Se forem diferentes, retornar falso. Em seguida, enquanto as pilhas não estiverem vazias, remover o elemento do topo de cada pilha e compará-los. Se forem diferentes, retornar falso. Caso contrário, retornar verdadeiro. 14) Uma estrutura do tipo fila é uma estrutura de dados que permite a inserção de elementos em uma extremidade, chamada fim, e a remoção de elementos na outra extremidade, chamada início. Ela segue o princípio FIFO (First In, First Out), ou seja, o primeiro elemento inserido é o primeiro a ser removido. 15) Uma fila pode ser utilizada em situações em que é necessário processar elementos na ordem em que foram inseridos, como em um sistema de impressão de documentos ou em um sistema de atendimento de chamados. 16) Implementação estática e sequencial de uma fila: Os dados são armazenados em um vetor de tamanho fixo. A fila é representada por dois índices, um que aponta para o início e outro que aponta para o fim. As operações de inserção e remoção são realizadas através do incremento e decremento desses índices. 17) Implementação de um TAD fila: Criar uma estrutura que contenha um vetor de elementos, um índice que aponte para o início da fila e um índice que aponte para o fim da fila. As operações de inserção e remoção são realizadas através do incremento e decremento desses índices. 18) Função para testar se uma fila F1 tem mais elementos do que uma fila F2: Comparar o tamanho das filas F1 e F2. Se o tamanho de F1 for maior que o tamanho de F2, retornar verdadeiro. Caso contrário, retornar falso. 19) Implementação de uma fila em um vetor circular: Os dados são armazenados em um vetor de tamanho fixo. A fila é representada por dois índices, um que aponta para o início da fila e outro que aponta para o fim da fila. Quando o índice do fim alcança o índice do início, a fila está cheia. Para contornar esse problema, é possível utilizar um vetor circular, em que o índice do fim é incrementado e, se necessário, volta para o início do vetor. 20) Implementação da funcionalidade de uma fila a partir de um TAD pilha: Criar duas pilhas, uma para inserção e outra para remoção. Para inserir um elemento na fila, inserir na pilha de inserção. Para remover um elemento da fila, se a pilha de remoção estiver vazia, transferir todos os elementos da pilha de inserção para a pilha de remoção e remover o elemento do topo da pilha de remoção. Se a pilha de remoção não estiver vazia, remover o elemento do topo da pilha de remoção. 21) Alocação sequencial utiliza posições contíguas de memória, enquanto alocação encadeada utiliza ponteiros para ligar os elementos. 22) As vantagens de se utilizar alocação encadeada incluem a flexibilidade no tamanho do conjunto de elementos e a facilidade de inserção e remoção de elementos em qualquer posição. As possíveis desvantagens incluem o consumo de memória adicional pelos ponteiros e a complexidade na implementação. 23) Pilha encadeada: Uma pilha encadeada é uma lista encadeada em que as operações de inserção e remoção são realizadas apenas no início da lista. A pilha é representada por um ponteiro que aponta para o início da lista. 24) Fila encadeada: Uma fila encadeada é uma lista encadeada em que as operações de inserção são realizadas no fim da lista e as operações de remoção são realizadas no início da lista. A fila é representada por dois ponteiros, um que aponta para o início da lista e outro que aponta para o fim da lista. 25) Alocação estática é definida em tempo de compilação, enquanto alocação dinâmica é definida em tempo de execução. 26) Implementação do TAD da lista encadeada e dinâmica: Criar uma estrutura que contenha um ponteiro para o início da lista. As operações de inserção e remoção são realizadas através da criação e remoção de nós da lista. 27) Sistema de cadastro de alunos de uma universidade: Dados: alunos, cursos, disciplinas. Operações: cadastrar aluno, cadastrar curso, cadastrar disciplina, matricular aluno em curso, matricular aluno em disciplina, consultar alunos matriculados em um curso, consultar alunos matriculados em uma disciplina. 28) Sistema de lista de compras para uma casa: Dados: itens de cozinha. Operações: adicionar item à lista, remover item da lista, consultar itens da lista. 29) As diferenças entre os dois sistemas anteriores incluem os dados e operações específicos de cada sistema. As vantagens de se usar TAD incluem a modularidade e a facilidade de manutenção do código. As desvantagens incluem a complexidade na implementação. 30) Problema melhor resolvido com uma representação estática e sequencial: armazenamento de dados que não precisam ser modificados com frequência, como uma lista de produtos em um supermercado. Problema melhor resolvido com uma representação dinâmica e encadeada: armazenamento de dados que precisam ser inseridos e removidos com frequência, como uma lista de tarefas em um aplicativo de organização pessoal. 31) Implementação de uma pilha sobre uma lista: Criar uma lista encadeada em que as operações de inserção e remoção são realizadas apenas no início da lista. A pilha é representada por um ponteiro que aponta para o início da lista. 32) Implementação de uma fila sobre uma lista: Criar uma lista encadeada em que as operações de inserção são realizadas no fim da lista e as operações de remoção são realizadas no início da lista. A fila é representada por dois ponteiros, um que aponta para o início da lista e outro que aponta para o fim da lista. 33) Uma pilha pode ser modelada sobre uma lista porque as operações de inserção e remoção são realizadas apenas no início da lista. Já uma pilha não pode ser manipulada como uma fila porque as operações de inserção e remoção são realizadas em extremidades diferentes da estrutura. 34) Uma lista linear é uma estrutura de dados em que os elementos são organizados em uma única dimensão. Exemplos incluem listas encadeadas e vetores. Já uma lista não linear é uma estrutura de dados em que os elementos são organizados em mais de uma dimensão. Exemplos incluem árvores e grafos. A nomenclatura se deve ao fato de que as listas lineares possuem uma ordem bem definida, enquanto as listas não lineares não possuem uma ordem fixa.