Prova AB1: Estruturas de Dados - Teoria e Prática em C

1 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 1 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 2 10 Listas encadeadas Uma lista duplamente encadeada tem como característica ser formada por elementos que a se concatenam de forma circular de tal maneira que ao chegar ao final da lista o próximo elemento volta a ser o primeiro b 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 c 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 d 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 e 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 3 10 Pilhas e Filas Sobre as estruturas de dados lineares analise as proposições abaixo a Uma pilha é uma lista com acesso restrito a apenas uma das extremidades tanto para inserir quanto para remover b Uma fila é uma lista com acesso restrito a ambas as extremidades uma apenas para inserção e a outra apenas para remoção c Devido a sua característica dinâmica uma lista não pode ser implementada em um vetor d 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 a 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 2 4 10 Listas Pilhas e Filas Referente a estruturas de dados é CORRETO afirmar a 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ó b Por convenção o ponteiro de link do último nó de uma lista é inicializado em 0 zero c O tamanho quantidade de elementos de uma lista encadeada deve ser definido na hora da criação d Pilhas filas e árvores são consideradas também estruturas de dados lineares baseadas em listas encadeadas e Uma pilha usa método de inserção FIFO 5 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 a 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 b As pilhas conhecidas como estruturas FIFO firstin firstout possuem duas principais operações denominadas push e pop a primeira insere um elemento na estrutura a segunda remove um elemento da estrutura c A estrutura de dados Nó utilizada para definir listas encadeadas deve conter pelo menos um valor e uma ligação ao próximo nó d 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 e 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 6 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 3 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 7 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 8 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 i O procedimento para criar as pilhas inicializar ii As funções vaziaA e vaziaB iii 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 9 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 1 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 1 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 Precisamos estruturar nosso dados para atender a diferentes requisitos de processamento e organização do código Com as estruturas de dados é possível abstrair diversas operações e relacionamentos o que facilita a resolução de problemas complexos Sendo assim o maior problema na estruturação dos dados é a escolha de uma estrutura inadequada Nas estruturas homogênas todos os dados são do mesmo tipo o que não ocorre nas heterogêneas Nas estruturas estáticas há uma quantidade máxima de dados suportados como exemplo os vetores Já nas estruturas dinâmicas podemos expandir a quantidade de dados lista ligada Por fim temos as estruturas lineares eg vetores e não lineares eg árvores essas últimas são marcadas por possuirem relacionamentos hierárquico 2 10 Listas encadeadas Uma lista duplamente encadeada tem como característica ser formada por elementos que a se concatenam de forma circular de tal maneira que ao chegar ao final da lista o próximo elemento volta a ser o primeiro Errado Esta é a lista circular b 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 Errado Esta é a lista unicamente encadeada c 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 Errado Esta é a lista unicamente encadeada com ordenação d 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 Correto e 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 Errado Este é o vetor 2 3 10 Pilhas e Filas Sobre as estruturas de dados lineares analise as proposições abaixo a Uma pilha é uma lista com acesso restrito a apenas uma das extremidades tanto para inserir quanto para remover Correto b Uma fila é uma lista com acesso restrito a ambas as extremidades uma apenas para inserção e a outra apenas para remoção Correto c Devido a sua característica dinâmica uma lista não pode ser implementada em um vetor Errado É possível implementar uma lista em um vetor d 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 Correto Estão corretas a 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 4 10 Listas Pilhas e Filas Referente a estruturas de dados é CORRETO afirmar a 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ó Correto b Por convenção o ponteiro de link do último nó de uma lista é inicializado em 0 zeroErrado o ponteiro é inicializado com Vazio c O tamanho quantidade de elementos de uma lista encadeada deve ser definido na hora da criação Errado Se implementada com ponteiros a lista encadeada não possui restrição de tamanho d Pilhas filas e árvores são consideradas também estruturas de dados lineares baseadas em listas encadeadas Errado Árvores não é linear e Uma pilha usa método de inserção FIFO Errado Pilha utiliza LIFO 5 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 a 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 Errado esta é a pilha b As pilhas conhecidas como estruturas FIFO firstin firstout possuem duas principais operações denominadas push e pop a primeira insere um elemento na estrutura a segunda remove um elemento da estrutura Errado Pilha é uma estrutura LIFOlastin firstout c A estrutura de dados Nó utilizada para definir listas encadeadas deve conter pelo menos um valor e uma ligação ao próximo nó Correto d 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 Errado Homogêno siginifica que todos os elementos são do mesmo tipo e 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 Errado Os elementos 3 aparecem em ordem linear 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 6 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 Se definirmos que a fila está cheia quando o apontador para o fim estiver na posição anterior ao inicio não há dificuldade para diferenciar fila cheia da vazia 1 Criafila int filatamanho int inicio0 fim0 2 Inicio fim 3 Inicio fim1 tamanho 4 Se inicio fim 1 tamanho Fim fim 1 tamanho Filafim valor 5 Se inicio fim Se fim 0 Fim tamanho 1 Senao Fim fim 1 7 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 4 a b c d e f g SantoAntônio SantaFilomena SantoAntônio SantoAntônio Santoagostinho SantoAntônio Santoagostinho SantoAntônio Santoagostinho SantoAntônio SantaCatarina Santoagostinho SantoAntônio SantaCatarina 5 h i j k l Santoagostinho SantoAntônio SantaCatarina SantoExpedito Santoagostinho SantoAntônio SantaCatarina Santoagostinho SantoAntônio SantaCatarina SantaCatarina Santoagostinho SantoAntônio SantaCatarina SantaCatarina Santoagostinho SantoAntônio SantaCatarina SantaCatarina SantaGenoveva 6 m n 8 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 i O procedimento para criar as pilhas inicializar Criarpilhas Int vetortamanho Int topoA tamanho Int topoB 1 ii As funções vaziaA e vaziaB vaziaA retorna topoA tamanho vaizaB rotorna topoB 1 iii Os procedimentos empilhaA empilhaB desempilhaA e desempilhaB empilhaAvalor se topoA 1 topoB topoA pilhatopoA valor empilhaBvalor se topoB1 topoA Santoagostinho SantoAntônio SantaCatarina SantaCatarina Santoagostinho SantoAntônio SantaCatarina SantaCatarina SantaCatarina 7 topoB pilhatopoB valor desempilhaA se não vaizaA valor pilhatopoA topoA rotorna valor desempilhaB se não vaziaB valor pilhatopoB topoB retorna valor OBSERVAÇÃO para a questão 9 abaixo é necessário implementar os procedimentos elencados e apresentar o código em C 9 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