Teste Estrutura de Dados 1

UENF Universidade Estadual do Norte Fluminense Darcy Ribeiro Curso Ciência de Computação Data 16052024 Prova T1 Período 3 º Disciplina Estrutura de dados I Professor Fermín Alfredo Tang Turno Diurno Nome do Aluno Luiz Gabriel Licassali Beyruth Matrícula 20211100062 20 Pontos Explique o conceito de TAD Qual a vantagem de definir uma estrutura como TAD Porque motivo a definição do TAD é realizada em arquivos diferentes do programa de aplicação TAD tipo abstrato de dados é um conjunto de valores com seu comportamento definido por operações implementadas na forma de funções O TAD é usado para simplificar a descrição de algoritmos abstratos classificar e avaliar as estruturas de dados e descrever formalmente certos tipos de sistemas Vantagens Encapsulamento ao ocultarmos a implementação fornecemos um conjunto de operações possíveis para o TAD Isso é tudo o que o usuário precisa saber para fazer uso do TAD O usuário não precisa de nenhum conhecimento técnico sobre como a implementação trabalha para usálo tornando o seu uso muito mais fácil Segurança o usuário não tem acesso direto aos dados Isso evita que ele manipule os dados de uma maneira imprópria Flexibilidade podemos alterar o TAD sem alterar as aplicações que o utilizam De fato podemos ter diferentes implementações de um TAD desde que todos respeitem a mesma interface Assim podemos usar a implementação mais eficiente para determinada situação Reutilização a implementação do TAD é feita em um módulo diferente do programa do usuário Separar a definição e a implementação de um TAD em arquivos diferentes melhora a modularidade a reutilização a testabilidade e a colaboração em equipe Isso promove um design de software mais limpo robusto e fácil de manter 20 Pontos Considerando que a fila F0 foi criada e contém os seguintes elementos Qual seria o conteúdo da filas F1 e F2 após o seguinte código ser executado F1 createqueue F2 createqueue enquanto não emptyqueueF0 fazer xdequeueF0 se x mod 2 0 então enqueue F1 x se não enqueue F2 x fimfazer 20 Pontos Usando as operações básicas de pilhas escreva um algoritmo para a função copystack que copia o conteúdo de uma pilha PX em outra pilha P0 preservando a ordem dos dados em PX Considere Considere que os dados da pilha P0 devem ser preservados Considere que os dados da pilha P0 não devem ser preservados Ilustre com um exemplo em cada caso 4 20 Ponto Usando as operações básicas de listas encadeadas escreva um algoritmo combine duas listas ordenadas L1 e L2 em uma única lista ordenada L3 Considere i Que as listas L1 e L2 devem ser preservadas ii Que as listas L1 e L2 não devem ser preservadas Ilustre com um exemplo em cada caso 5 20 Ponto Dada uma lista duplamente encadeada onde cada nó possui dois ponteiros seguinte e anterior denotados como sgte e ant conforme a Figura 1a Escreva as operações necessárias para inserir o novo nó apontado por q ver Figura 1b após o nó apontado por p ver Figura 1c Descreva as operações acessando os campos seguinte e anterior usando a notação psgte e qant Figura 1