Resolução de Exercicios

Caro aluno Nesta prova há alguma questão com enunciado inconsistente problemas nas alternativas ou demais erros que dificultaram a sua interpretação Não Sim Registreos abaixo Avaliação Semestre X 20241 20242 Bimestre X 1º 2º Disciplina Estrutura de Dados Código EGS23205 Professor a Leandro Augusto Ensina Turma T01N Período 2 Turno noturno X Prova Bimestral Prova Bimestral em 2ª Chamada Exame Exame em 2ª Chamada Acadêmicoa Nota CURSO Engenharia de Software Recomendações Institucionais O aluno que realizar a prova a lápis ou com caneta de cor diferente da preta ou azul não poderá solicitar revisão de prova Celulares e aparelhos eletrônicos deverão estar desligados e guardados Não será permitida a consulta a qualquer material ou a colegas salvo orientação do professor Questões objetivas rasuradas serão zeradas Responder a prova com caneta que apaga constituise de fraude e caso constatada será atribuída nota zero ao acadêmico além de outras providências cabíveis Na entrega da prova os dois últimos acadêmicos deverão assinar a ata em que serão descritas todas as ocorrências que extrapolarem aos procedimentos usuais durante a realização desta avaliação Recomendações do curso Não será permitido o uso de LÁPIS para responder às questões sejam discursivas ou objetivas O uso do lápis autoriza o docente a não proceder à correção Na correção das respostas discursivas o uso da norma padrão da Língua Portuguesa também será avaliado podendo o docente descontar pontos em caso de mau uso do vernáculo A leitura e adequada compreensão dos enunciados da prova é parte integrante do processo de avaliação Não cabe ao professor portanto fazêlo durante a aplicação da prova Questão 1 Valor 30 Determine se cada uma das seguintes sentenças é verdadeira V ou falsa F a Uma estrutura struct é um tipo de dado cujo formato é definido pelo programador b Assim como a struct alocase para uma union um espaço de memória para cada um de seus membros apesar de que apenas um deles deve ser acessado por vez c Os arquivos de cabeçalho h devem ser acompanhados de uma include guard composta pelas diretivas ifndef define endif d As variáveis alocadas dinamicamente são armazenadas em uma área de memória denominada de heap enquanto os dados usados por funções parâmetros variáveis locais endereços de retorno são armazenados na stack e A única diferença entre vetores arrays e listas dinâmicas é o fato de que os vetores possuem tamanho fixo enquanto as listas possuem tamanho variável em tempo de execução f Ponteiros permitem armazenar apenas endereços de memória alocados dinamicamente g Todo ponteiro deve ser inicializado apontar para algum endereço válido antes de ser acessado h Endereços alocados dinamicamente são liberados da memória logo após o término da função a qual requisitou a alocação dinâmica mesmo que o programador não libere explicitamente pela função free i Lista fila e pilha são estruturas de dados semelhantes porém com políticas de manipulação eg inserção e remoção diferentes j As estruturas de dados dinâmicas lista pilha fila limitamse apenas a armazenar tipos primitivos de dados como int char float e double Questão 2 Valor 10 Em relação a Tipo Abstrato de Dados TAD responda 1 Defina o conceito de TAD Valor 05 2 Qual a característica fundamental na sua utilização Valor 05 Questão 3 Valor 10 Em relação à lista linear em alocação sequencial é correto afirmar que a Para as estruturas do tipo pilha são necessários dois ponteiros início da pilha i e fim da pilha f Para a adição de um elemento movese o ponteiro i para a retirada movese o ponteiro f b O armazenamento sequencial de listas é empregado quando as estruturas ao longo do tempo sofrem muitas inserções e remoções acarretando a movimentação dos elementos da lista c Os nodos de uma lista simplesmente encadeada encontramse aleatoriamente dispostos na memória e são interligados por ponteiros que indicam a posição do próximo elemento da lista d Em uma lista sequencial o último nodo da lista aponta para o primeiro nodo da lista e Para as estruturas do tipo fila apenas um ponteiro precisa ser considerado o ponteiro topo pois as inserções e as remoções são executadas na mesma extremidade da lista Questão 4 Valor 10 Sobre listas analise as assertivas abaixo I Elementos podem ser inseridos em uma pilha a qualquer momento mas apenas o que foi inserido mais recentemente isto é o último pode ser removido a qualquer momento II Em uma fila os elementos podem ser inseridos a qualquer momento mas apenas o elemento que está a mais tempo na fila pode ser removido III Em uma fila os elementos são inseridos e removidos de acordo com o princípio o último que entra é o primeiro que sai Quais estão corretas a Apenas I b Apenas II c Apenas III d Apenas I e II e I II e III Questão 5 Valor 20 Escreva uma função que receba como parâmetro um vetor de inteiros com N valores determinando o maior elemento do vetor e o número de vezes que este elemento ocorreu Por exemplo para um vetor com os seguintes elementos 5 2 15 3 7 15 8 6 15 a função deve retornar via mudança dos valores dos argumentos o valor 15 e o número 3 indicando que o número 15 ocorreu 3 vezes Para isso considere o seguinte protótipo para a implementação void funcint vetor int tamanho int maior int numocorrencias Questão 6 Valor 20 Escreva uma função para determinar se uma expressão está ou não com os parênteses balanceados considerando as seguintes observações Utilize o protótipo de função abaixo para a implementação desta questão Utilize obrigatoriamente a estrutura de dados pilha para o desenvolvimento da solução A função isBalanceado deverá retornar 1 caso a expressão esteja com os parênteses balanceados ou 0 caso contrário int isBalanceadochar expressao Questão BÔNUS Valor 10 Escreva uma função que ordene uma lista de elementos Para isso considere a TAD lista disposta abaixo implementando a função ordenarLista 1 Determine se cada uma das seguintes sentenças é verdadeira V ou falsa F a V Uma estrutura struct é de fato um tipo de dado cujo formato é definido pelo programador b F Ao contrário de uma struct uma union aloca espaço de memória para todos os seus membros simultaneamente embora apenas um deles possa ser acessado por vez Justificativa Union Uma union aloca espaço para o maior membro e compartilha esse espaço entre todos os membros ao contrário da struct onde cada membro tem seu próprio espaço c V Os arquivos de cabeçalho h geralmente são acompanhados de um include guard que geralmente é composto pelas diretivas ifndef define e endif para evitar inclusões múltiplas d V As variáveis alocadas dinamicamente são armazenadas na área de memória chamada heap enquanto os dados usados por funções são armazenados na stack e F A diferença entre vetores arrays e listas dinâmicas vai além do tamanho fixo ou variável Listas dinâmicas geralmente permitem inserção e remoção eficientes em qualquer ponto enquanto vetores têm complexidade maior nesses casos Justificativa Diferenças entre vetores e listas dinâmicas Além do tamanho as listas dinâmicas oferecem operações de inserção e remoção eficientes em qualquer posição enquanto os vetores oferecem acesso aleatório eficiente f F Ponteiros podem armazenar endereços de memória de forma mais geral não apenas para alocações dinâmicas Justificativa Ponteiros Eles podem armazenar endereços de qualquer tipo de objeto ou variável não apenas endereços de memória alocados dinamicamente g V Todo ponteiro deve ser inicializado antes de ser acessado para evitar comportamento indefinido h F Endereços alocados dinamicamente não são liberados automaticamente após o término da função que os alocou É responsabilidade do programador liberar explicitamente a memória alocada usando a função free Justificativa Liberação de memória dinâmica A memória alocada dinamicamente não é liberada automaticamente após o término da função que a alocou o programador deve liberála explicitamente para evitar vazamentos de memória i V Lista fila e pilha são de fato estruturas de dados semelhantes mas diferem em suas políticas de manipulação como inserção e remoção j F Estruturas de dados dinâmicas não estão limitadas a armazenar apenas tipos primitivos de dados Elas podem armazenar tipos de dados complexos como structs classes e até mesmo outras estruturas de dados 2 Definição de TAD Tipo Abstrato de Dados Um Tipo Abstrato de Dados é uma abstração matemática que define um conjunto de valores e um conjunto de operações que podem ser realizadas sobre esses valores O foco principal é na interface ou seja nas operações que podem ser realizadas sem considerar a implementação interna dessas operações Isso permite que os detalhes de implementação sejam ocultados e que os usuários possam usar o tipo de dados sem se preocupar com sua implementação subjacente Característica fundamental na sua utilização A característica fundamental na utilização de um TAD é a encapsulação O TAD encapsula os dados e as operações em uma única unidade ocultando os detalhes de implementação dos usuários Isso promove a modularidade do código facilita a manutenção e promove a reutilização já que os usuários só precisam se preocupar com a interface fornecida pelo TAD não com os detalhes internos de sua implementação 3 R c Os nodos de uma lista simplesmente encadeada encontramse aleatoriamente dispostos na memória e são interligados por ponteiros que indicam a posição do próximo elemento da lista 4 R a Apenas I 5 R void funcint vetor int tamanho int maior int numocorrencias int elementoatual vetor0 int maxelemento elementoatual int countmaxelemento 1 for int i 1 i tamanho i elementoatual vetori if elementoatual maxelemento maxelemento elementoatual countmaxelemento 1 Zerar a contagem do novo elemento máximo else if elementoatual maxelemento Se for igual incrementar a contagem countmaxelemento maior maxelemento numocorrencias countmaxelemento 6 R typedef struct Pilha tipodado elementoTAMANHOPILHA define que o usuário quiser int topo Pilha void pilhainicializarPilha pilha pilhatopo 1 int pilhavaziaPilha pilha return pilhatopo 1 void pilhaempilharPilha pilha tipodado elemento if pilhatopo TAMANHOPILHA 1 pilhatopo pilhaelementopilhatopo elemento else printfPilha cheia tipodado pilhadesempilharPilha pilha if pilhavaziapilha return 0 else pilhatopo return pilhaelementopilhatopo 1 int isBalanceadochar expressao Pilha pilha pilhainicializarpilha for int i 0 expressaoi 0 i char c expressaoi if c c if c pilhaempilharpilha c else if pilhavaziapilha return 0 char topo pilhadesempilharpilha if topo c return 0 if pilhavaziapilha return 0 return 1 7 R Como não foi especificado nenhum algoritmo de ordenação foi utilizado o simples bubblesort void ordenarListaLista lista int i j for i 0 i listatamanho 1 i for j i 1 j listatamanho j if listainicioivalor listainiciojvalor No aux listainicioi listainicioi listainicioj listainicioj aux