Prova AB1 Estrutura de Dados C - Teoria e Prática

Instruções Para prova teórica Para todas as questões de múltipla escolha justifique sua resposta indicando os erros encontrados Para prova prática Elaborar o projeto em C conforme solicitado na questão Exportar o projeto em arquivo ZIP ATENÇÃO Não é permitido c ópia de textocódigos de terceiros Caso comprovada a cópiaplágio receberá nota 00 zero Prova Teórica e Prática AB1 10 Conceitos Por que precisamos estruturar nossos dados Explique indicando vantagens e desvantagens e apresente exemplos dos seguintes conceitos de estruturas de dados Homogêneas x Heterogêneas estáticas x dinâmicas e linear x não linear 10 Listas encadeadas Uma lista duplamente encadeada tem como característica ser formada por elementos que se concatenam de forma circular de tal maneira que ao chegar ao final da lista o próximo elemento volta a ser o primeiro contêm além de um ou mais campos chave mais um campo de ponteiro o próximo que permite o acesso ao elemento que sucede o atual o próximo presente na mesma lista contêm além de um campo chave mais um campo de ponteiro o próximo que permite o acesso ao elemento que sucede o atual o próximo presente na mesma lista de tal forma que os campos chave estão ordenados ou seja a chave do próximo é sempre maior ou igual à chave do atual elemento contêm além de um ou mais campos chave dois outros campos de ponteiros próximo e anterior que permitem o acesso aos elementos adjacentes próximo e anterior presentes na mesma lista estão em posições adjacentes da memória permitindo o acesso sequencial ao próximo e ao anterior de cada elemento pelo simples uso de um índice 10 Pilhas e Filas Sobre as estruturas de dados lineares analise as proposições abaixo Uma pilha é uma lista com acesso restrito a apenas uma das extremidades tanto para inserir quanto para remover Uma fila é uma lista com acesso restrito a ambas as extremidades uma apenas para inserção e a outra apenas para remoção Devido a sua característica dinâmica uma lista não pode ser implementada em um vetor Uma fila é mais eficientemente implementada em uma lista simplesmente encadeada se as remoções são realizadas na cabeça da lista e as inserções na cauda da lista Estão corretas 1 2 3 e 4 b 1 2 e 3 apenas c 1 2 e 4 apenas d 1 3 e 4 apenas e 2 3 e 4 apenas 10 Listas Pilhas e Filas Referente a estruturas de dados é CORRETO afirmar Uma lista encadeada é uma coleção linear de objetos de uma classe autorreferenciada chamados de nós Pode ser acessada por meio de um ponteiro para o primeiro nó da lista Os nós subsequentes são acessados por meio do membro ponteiro de link armazenado em cada nó Por convenção o ponteiro de link do último nó de uma lista é inicializado em 0 zero O tamanho quantidade de elementos de uma lista encadeada deve ser definido na hora da criação Pilhas filas e árvores são consideradas também estruturas de dados lineares baseadas em listas encadeadas Uma pilha usa método de inserção FIFO 10 Estruturas de dados Três aspectos são fundamentais no que se refere a estruturas de dados a abstração a distinção entre estruturas estáticas e dinâmicas e o conceito de ponteiro A partir dessa informação assinale a opção correta Na estrutura do tipo fila as inserções e remoções são executadas por uma única extremidade da estrutura de modo que o último elemento a entrar na estrutura é o primeiro a ser removido As pilhas conhecidas como estruturas FIFO first in first out possuem duas principais operações denominadas push e pop a primeira insere um elemento na estrutura a segunda remove um elemento da estrutura A estrutura de dados Nó utilizada para definir listas encadeadas deve conter pelo menos um valor e uma ligação ao próximo nó A estrutura do tipo matriz é conhecida como um arranjo retangular chamado arranjo homogêneo ou matriz em que o termo homogêneo significa que todos os elementos do arranjo são de tipos diferentes Listas que podem ser classificadas como estrutura estática ou dinâmica consistem em uma coleção de elementos que aparecem em ordem combinatória OBSERVAÇÃO para as questões 6 a 8 abaixo considere implementar como apresentar um pseudocódigo eou uma explicação de como os procedimentos devem ser executados NÃO é necessário apresentar código em C 10 Fila Considere uma implementação de fila utilizando um vetor circular que utiliza apontadores índices para a frente e o final da fila frente aponta para a posição imediatamente anterior ao primeiro elemento da fila e final aponta para o último elemento inserido se existir conforme pode ser visto nas figuras abaixo Nesse sentido comente a dificuldade para se diferenciar fila cheia de fila vazia Apresente as ações pseudocódigo que deveriam ser realizadas para as funções 1 Criar Fila 2 Verificar fila vazia 3 Verificar Fila Cheia 4 Enfileirar e 5 Desenfileirar 10 Pilha Considere a estrutura de dados PILHA criada na variável STE Apresente o estado da pilha em desenho após a execução de cada comando apresentado abaixo 10 Pilha Duas pilhas A e B podem compartilhar o mesmo vetor como esquematizado na figura a seguir Nesse sentido apresente as ações pseudocódigo que deverão ser feitas para O procedimento para criar as pilhas inicializar As funções vaziaA e vaziaB Os procedimentos empilhaA empilhaB desempilhaA e desempilhaB OBSERVAÇÃO para a questão 9 abaixo é necessário implementar os procedimentos elencados e apresentar o código em C 20 Implementação de Fila ou Pilha Escolha o código de fila ou pilha presente no site da disciplina e faça as alterações necessárias para suportar uma fila ou pilha de Contatos Utilize o struct Contato definido no código de vetores 3 3