Revisão Julho - Estrutura de Dados

--- title: Revisão Julho - Estrutura de Dados --- ![](https://letscode-academy.com/assets/logo_lc_png.png) ---------- <center> Avaliação de Retorno</center> <center> Estrutura de Dados</center> ---------- # Regras - A avaliação consite na escolha e resolução de 3 dos 4 exercícios disponíveis nessa lista; - O aluno estará aprovado se obter ao menos 50% da nota final; - O aluno pode consultar o material em sala, assim como material disponível na internet; - Entretanto, o aluno deve realizar a avaliação de maneira individual, sem consultas a outras pessoas; - A avaliação deve ser entregue até dia 04/jan/21, 23h50, via email para rychard.guedes@letscode.com.br; - O código deve estar comentado, contando positivamente na avaliação. # Exercícios ## Exercício 1 - Árvore de Decisão Vamos fazer um programa que utiliza uma árvore de decisão para auxiliar um diagnóstico médico. ### Passo 1 (35%) Construa uma árvore que represente a informação do diagrama abaixo. Cada nó contem uma pergunta, a respeito de um teste, e dois filhos direito e esquerdo correspondendo às respostas True e False respectivamente. Os nós folha contém o diagnóstico mais provável dados os resultados dos testes. ![](https://s3-sa-east-1.amazonaws.com/lcpi/74076101-fada-47e6-921b-d32aaba4d516.png) Figura extraída de: Albu, A. (2017). **From logical inference to decision trees in medical diagnosis**. 2017 E-Health and Bioengineering Conference (EHB), 65-68. ### Passo 2 (65%) Com a árvore construída o seu programa deverá ler um arquivo csv no formato abaixo onde cada coluna indica um teste e cada linha corresponde aos testes de um paciente. Para cada linha o programa deverá percorrer a árvore de acordo com os resultados dos testes informados até chegar a um nó folha e então imprimir o diagnóstico. Caso o paciente não tenha efetuado um teste necessário para o diagnóstico, o programa deve imprimir `Missing TestX` onde TestX é o teste faltante. Exemplo de entrada: ``` HBsAg ,anti-HDV,anti-HBc,anti-HBs,IgM anti-HBc positive,positive, , , negative,negative,positive, , ,positive, , , ``` Exemplo de saída: ``` Hepatitis B+D Unclear (possible resolved) Missing HBsAg ``` > Observação: os espaços no exemplo de entrada são apenas para facilitar a visualização. ---------- ## Exercício 2 - Lowest Common Ancestor Resolver o problema do Lowest Common Ancestor no [Hackerrank](https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem). ---------- ## Exercício 3 - Trajetos de Metrô Vamos fazer um programa que, dado um arquivo especificando a malha metroviária de uma cidade, possibilita definir o melhor caminho entre duas estações. O programa deverá ler um arquivo no formato abaixo e armazenar estas informações em um grafo. Por simplicidade, não vamos incluir todas as estações da malha metroviária, mas apenas conexões e outros pontos de interesse. ### Formato do arquivo de entrada Cada linha contem duas estações separadas por vírgula e um número indicando o "custo" entre duas estações. ``` Sé, República, 2 Sé, Paraíso, 10 Sé, Luz, 2 Luz, República, 1 Consolação, República, 2 Consolação, Paraíso, 3 Chacara Klabin, Santa Cruz, 1 Santa Cruz, Paraíso, 3 Chacara Klabin, Paraíso, 2 Eng. Goulart, Guarulhos CECAP, 5 Guarulhos CECAP, Guarulhos Aeroporto, 2 ``` ### Passo 1 (40%) Faça um programa que lê um arquivo no formato acima e carrega as informações em um grafo. ### Passo 2 (40%) Modifique o programa para que receba uma solicitação do usuário contendo duas estações A, B e indique um caminho (qualquer) para sair da estação A e chegar na estação B. Exemplo de entrada: ``` Luz, Chacara Klabin ``` Exemplo de saída: ``` Luz -> República -> Consolação -> Paraíso -> Chacara Klabin ``` ### Passo 3 (20%) Modifique o programa para que a resposta do passo 2 seja garantidamente o menor caminho. ---------- ## Exercício 4 - Famílias de Troia A Guerra de Troia pode ter sido um grande conflito bélico entre gregos e troianos, possivelmente ocorrido entre 1300 a.C. e 1200 a.C. (fim da Idade do Bronze no Mediterrâneo). Recentemente foram encontradas inscrições numa caverna a respeito de sobreviventes. Após um trabalho árduo, arqueólogos descobritam que as incrições descreviam relações de parentesco numa certa população. Cada item da inscrição indicavam duas pessoas que pertenciam a uma mesma família. Seu problema é determinar quantas famílias distintas existem. ### Entrada O arquivo de entrada consiste de M + 1 linhas. A primeira linha do arquivo de entrada contém um inteiro positivo N, que indica o número de elementos da comunidade, numerados de 1 a N. As demais M linhas do arquivo de entrada contêm, cada uma, dois inteiros. Cada inteiro identifica um elemento da comunidade. Cada linha indica que os dois indivíduos pertencem a uma mesma família. Exemplo de entrada: ``` 9 8 1 2 2 3 3 6 4 3 6 5 7 8 1 4 6 2 ``` ### Saída A saída deve conter apenas uma linha contendo um único inteiro, que é o número de famílias. Exemplo de saída: ``` 3 ``` Extraído de: [URI](https://www.urionlinejudge.com.br/judge/en/problems/view/2440)