---
# System prepended metadata

title: Revisão Julho - Estrutura de Dados

---

---
title: Revisão Julho - Estrutura de Dados
---

![](https://letscode-academy.com/assets/logo_lc_png.png)

----------

<center> <font size="+4"><b> Avaliação de Retorno</b></font></center>

<center> <font size="+3"><b> Estrutura de Dados</b></font></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)
