Atividades sobre Programação usando grafos e árvores com gabarito — 9º ano (EF09CO01)

Quando recebi o código EF09CO01 no planejamento do 9º ano, confesso que a primeira reação foi de dúvida: como transformar grafos e árvores em uma aula que os alunos entendam de verdade? Eu já tinha visto esses conceitos em cursos de programação, mas traduzir aquilo para uma turma com pouca familiaridade com a área exigiu uma adaptação.

Foi aí que percebi que a maior parte do trabalho estava em conectar a teoria a situações que eles já vivem: uma rede de amigos, uma pasta de arquivos no computador, um mapa de rotas de ônibus. Com isso em mente, consegui planejar aulas e avaliações que fazem sentido para a turma.

O que a habilidade EF09CO01 pede, de verdade?

Na prática, a habilidade pede que o aluno saiba identificar quando grafos e árvores são a melhor forma de descrever um problema e, a partir disso, escrever uma solução que possa ser automatizada em uma linguagem de programação. Em outras palavras, não basta conhecer a definição: o estudante precisa escolher a estrutura adequada para cada situação e entender por que ela funciona.

Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.

Traduzindo para o dia a dia da sala: o aluno deve olhar para um problema, perceber se ele envolve relações entre elementos (grafo) ou uma organização em níveis, com um ponto de partida e ramificações (árvore), e então representar essa estrutura de forma que um programa consiga percorrê-la e tirar conclusões dela.

Como trabalhar EF09CO01 em sala?

Algumas ideias que funcionaram bem para mim, sem precisar de material caro:

• Mapa de amizades no papel: peça para os alunos desenharem círculos (pessoas) e linhas (amizades) e, depois, perguntarem quem é o vizinho de quem. Isso introduz vértices e arestas de forma concreta.
• Árvore de pastas da escola: mostre a organização de pastas do computador da sala e peça que desenhem a hierarquia no caderno, identificando a raiz e os ramos.
• Rota de ônibus da cidade: trabalhe um grafo de rotas, discutindo caminhos possíveis e a existência ou não de ciclos.
• Pseudocódigo antes do código: antes de programar, peça que descrevam em passos simples como percorrer uma árvore de pastas para encontrar um arquivo.

Esses exercícios preparam o terreno para a programação propriamente dita e ajudam a turma a ganhar confiança com a linguagem dos grafos.

Como avaliar essa habilidade?

Uma boa questão sobre esse código precisa cobrar mais do que decorar nomes. Ela deve pedir que o aluno escolha a estrutura adequada para um cenário, analise as propriedades de um grafo ou árvore e, quando possível, justifique a escolha.

Os erros mais comuns que vejo em avaliações desse tema são: tratar árvores e grafos como sinônimos; esquecer que árvores não têm ciclos; e cobrar apenas a definição de vértice e aresta sem nenhuma situação de aplicação. Quando a questão apresenta um contexto real, como uma rede social ou um sistema de arquivos, o aluno consegue mostrar o que realmente aprendeu.

Questões prontas de EF09CO01 (com gabarito comentado)

Abaixo estão seis questões reais do acervo alinhadas ao código, com o gabarito e a explicação de cada alternativa.

Questão 1: estrutura para relacionamentos entre objetos

Em programação, qual estrutura de dados é mais adequada para representar relacionamentos entre objetos?

• ❌ A) Lista encadeada — Listas encadeadas são menos eficazes para representar relacionamentos complexos.
• ❌ B) Matriz — Matrizes não são ideais para representar relacionamentos entre objetos.
• ❌ C) Conjunto — Conjuntos são usados para coletar elementos, sem relacionamentos diretos.
• ✅ D) Grafos — Grafos são a estrutura ideal para representar relacionamentos, conectando diversos nós.
• ❌ E) Array — Arrays têm estrutura fixa e não favorecem a representação de relacionamentos.

Dica de resolução: considere as estruturas de dados mais comuns em programação.

Questão 2: o que representam vértices e arestas

Em um grafo, o que representam os vértices e as arestas?

• ❌ A) Vértices são conexões, arestas são entidades — É o contrário: vértices são entidades, e arestas conectam essas entidades.
• ❌ B) Ambos são tipos de dados organizados — Enquanto são organizados, vértices e arestas têm funções distintas em um grafo.
• ❌ C) Vértices representam relações, arestas entidades — Na verdade, são as arestas que representam as relações, enquanto os vértices representam as entidades.
• ✅ D) Vértices são entidades, arestas são relações — Vértices são as entidades no grafo, e as arestas representam as relações entre elas.
• ❌ E) Ambos representam dados não estruturados — Vértices e arestas são representações de dados estruturados, organizados em um grafo.

Dica de resolução: defina os conceitos de vértices e arestas em grafos.

Questão 3: técnica para redes sociais

Qual técnica é mais adequada para representar as relações entre amigos em uma rede social?

• ❌ A) Listas encadeadas, por serem mais simples. — Listas encadeadas não representam bem as relações complexas de redes sociais.
• ❌ B) Matrizes, pela facilidade de acesso. — Matrizes não são eficientes para representar conexões dinâmicas.
• ✅ C) Grafos, por representar conexões entre usuários. — Grafos são ideais para representar relações e conexões em redes.
• ❌ D) Registros, que organizam dados de maneira sequencial. — Registros não são adequados para representar relações complexas.
• ❌ E) Árvores, que organizam dados hierarquicamente. — Árvores são úteis para hierarquias, mas não para conexões entre múltiplos nós.

Dica de resolução: pense nas representações gráficas de redes sociais.

Questão 4: lista de adjacência em uma plataforma de relações direcionadas

Uma plataforma brasileira de comunicação pretende representar as relações entre seus usuários. Nessa plataforma, seguir alguém não implica ser seguido por essa pessoa, portanto as relações são direcionadas. Há 10 mil usuários, mas cada usuário segue, em média, apenas 80 pessoas. O sistema precisa consultar com frequência a lista de pessoas seguidas por cada usuário e deve evitar reservar espaço para todas as possíveis combinações entre usuários.

Com base nas características dessa plataforma, qual estrutura de dados é mais adequada para representar as relações entre os usuários, considerando que elas são direcionadas, pouco numerosas em comparação com as combinações possíveis e que se deseja consultar os vizinhos de cada usuário?

• ❌ A) Uma árvore binária. — Uma árvore binária organiza dados em uma hierarquia em que cada nó pode ter até dois filhos. As relações da plataforma não formam necessariamente hierarquia nem limitam cada usuário a dois vínculos.
• ❌ B) Uma lista encadeada simples. — Uma lista encadeada simples organiza elementos em sequência, mas não associa naturalmente cada usuário ao conjunto de pessoas que ele segue. Usá-la isoladamente não representa adequadamente toda a rede de relações direcionadas.
• ❌ C) Uma matriz de adjacência. — A matriz representa relações direcionadas, mas reserva uma posição para cada par possível de usuários. Como há muitos usuários e poucas conexões em relação ao total de combinações, ela não atende ao critério de evitar desperdício de espaço.
• ✅ D) Uma lista de adjacência. — A lista de adjacência associa cada usuário à lista dos usuários que ele segue. Ela representa naturalmente relações direcionadas e, como cada usuário possui relativamente poucos relacionamentos, utiliza espaço proporcional ao número efetivo de conexões, sem reservar posições para todas as combinações possíveis. Além disso, permite consultar diretamente os vizinhos de cada usuário.
• ❌ E) Um registro de dados. — Um registro agrupa campos que descrevem uma entidade, como identificador e nome, mas não fornece por si só uma organização para representar os vários vínculos direcionados entre usuários.

Dica de resolução: considere as estruturas de dados mais comuns para relacionamentos.

Questão 5: hierarquia de pastas como aplicação de árvores

Em uma escola, os arquivos digitais são organizados no servidor por níveis. A pasta “Projetos” contém as pastas “Ciências” e “História”; dentro delas, há subpastas e arquivos específicos. Cada subpasta possui apenas uma pasta superior, exceto a pasta principal, e é possível percorrer a organização do nível mais amplo ao mais específico. Esse modelo é diferente de uma lista de tarefas, em que os itens ficam apenas em sequência; de uma tabela de notas, formada por linhas e colunas; de uma fila de atendimento, organizada pela ordem de chegada; e de um grafo de rotas, que pode apresentar ciclos entre os pontos.

Com base no texto, qual estrutura exemplifica uma aplicação do conceito de árvore na organização de dados?

• ✅ A) Uma hierarquia de pastas e arquivos — A hierarquia de pastas e arquivos apresenta uma estrutura em níveis, na qual cada elemento, exceto o principal, está ligado a um único elemento superior. Essa organização corresponde ao conceito de árvore, formado por uma raiz e por ramificações, como pastas, subpastas e arquivos.
• ❌ B) Uma fila de atendimento por chegada — Uma fila segue o princípio de que o primeiro elemento a entrar é o primeiro a sair, sem subdivisões em níveis ou ramificações.
• ❌ C) Uma sequência de tarefas pendentes — Esse modelo representa uma estrutura linear, na qual os itens são colocados em uma ordem única, sem ramificações hierárquicas.
• ❌ D) Uma tabela de notas escolares — Uma tabela organiza dados principalmente pela interseção entre linhas e colunas, e não por níveis hierárquicos com ramificações.
• ❌ E) Um grafo de rotas com ciclos — Um grafo com ciclos permite caminhos fechados e conexões variadas entre os pontos, enquanto uma árvore não possui ciclos e mantém uma organização hierárquica.

Dica de resolução: pense em como as árvores são usadas para organizar informações.

Questão 6: propriedade para ordenação topológica

Qual propriedade deve ter um grafo dirigido para que seja possível executar um algoritmo de ordenação topológica sobre seus vértices?

• ✅ A) Ser acíclico, sem ciclos dirigidos (DAG). — A ordenação topológica organiza os vértices de modo que as relações direcionadas sejam respeitadas. Isso só é possível quando o grafo não contém ciclos dirigidos.
• ❌ B) Deve ser um grafo completo para realizar a ordenação. — Ser completo significa haver uma aresta entre cada par de vértices. Essa propriedade não é necessária para a ordenação topológica.
• ❌ C) Ter todos os vértices com o mesmo número de conexões diretas. — A quantidade de conexões de cada vértice não determina se existe ordenação topológica; essa propriedade não é exigida pelo algoritmo.
• ❌ D) Ser um grafo não dirigido, pois facilita a ordenação. — A ordenação topológica considera a direção das arestas para representar relações de precedência. Um grafo não dirigido não fornece essas direções.
• ❌ E) Deve ter pelo menos um ciclo para a ordenação ser possível. — Um ciclo dirigido cria uma sequência de dependências que retorna ao vértice inicial; assim, não há uma ordenação topológica válida.

Dica de resolução: verifique qual condição permite ordenar vértices respeitando as direções das arestas.

Próximos passos

Se você quer ver todas as questões desta habilidade, acesse a consulta completa do código EF09CO01. Para montar sua própria prova em poucos minutos, use o gerador de provas do GeraProva, e, se ainda não tem conta, faça seu cadastro grátis.

Este conteúdo serve como apoio para o seu planejamento. Revise as questões antes de aplicá-las à sua turma e adapte o nível de dificuldade à realidade dos seus alunos. Bom trabalho em sala!