1

ALGORITMOS E
PROGRAMAÇÃO II
Prof. Me. Filipe Costa Fernandes
 2
PROF. ME. FILIPE COSTA FERNANDES

ALGORITMOS E PROGRAMAÇÃO II

1° edição

Ipatinga, MG
Editora Prominas
2025
 3

Diretor Geral: Prof. Esp. Valdir Henrique Valério

Diretor Executivo: Prof. Dr. William José Ferreira

Ger. do Núcleo de Educação a Distância: Profª. Esp. Cristiane Lelis dos Santos

Coord. Pedag. da Equipe Multidisciplinar: Profª. Esp. Cristiane Lelis dos Santos

Revisão Gramatical e Ortográfica: Profª. Elislaine Santos

Revisão Técnica: Prof. Dr. Maicon Melo Alves

Revisão/Diagramação/Estruturação: Bruna Luiza Mendes

Lorena Oliveira Silva Portugal

Design: Bárbara Carla Amorim O. Silva

Élen Cristina Teixeira Oliveira

Cristiano Soares Andrade

Guilherme Carmo

© 2025, Editora Prominas.

Este livro ou parte dele não podem ser reproduzidos por qualquer meio sem Autorização es-
crita do Editor.

Ficha catalográfica elaborada pela bibliotecária Melina Lacerda Vaz CRB – 6/2920.
 4

FILIPE COSTA FERNANDES

Mestre em Modelagem Matemática e

Computacional pelo CEFET-MG (2009);
Especialização em Redes de Computa-
dores e E-Commerce - Faculdades Inte-
gradas de Caratinga (2007); Bacharel em
Ciência da Computação - Faculdades In-
tegradas de Caratinga (2003). Atualmen-
te é Gerente de TI e Analista de Sistemas
Web na empresa Vale Telecom (Ipatin-
ga) onde é o principal responsável por
manter toda a estrutura de servidores e
versões de sistemas do SIGESIS Sistemas
de Gestão, Coordenador e professor dos
cursos de Bacharelado em Ciência da
Computação e Sistemas de Informação
na Faculdade Única de Ipatinga. Possui
experiência e atuação como Coordena-
dor e Professor de cursos superiores de
Tecnologia EaD e também tem experiên-
cia na área de Ciência da Computação e
Sistemas de Informação, atuando princi-
palmente nos seguintes temas: Coorde-
nação de Curso, Coordenação e Gestão
de Equipes, Análise e Desenvolvimento
Web (PHP, MySql, [Link], C#, Sql Server),
Desenvolvimento (Java, C#, C), Software
Livre, Estruturas de Dados, Inteligência Ar-
tificial e Pesquisa Operacional.
 5
LEGENDA DE

Ícones
Com o intuito de facilitar o seu estudo e uma melhor compreensão
do conteúdo aplicado ao longo do livro didático, você irá encontrar
ícones ao lado dos textos. Eles são para chamar a sua atenção para
determinado trecho do conteúdo, cada um com uma função específica,
mostradas a seguir:

FIQUE ATENTO
Trata-se dos conceitos, definições e informações importantes
nas quais você precisa ficar atento.

BUSQUE POR MAIS

São opções de links de vídeos, artigos, sites ou livros da biblioteca
virtual, relacionados ao conteúdo apresentado no livro.

VAMOS PENSAR?
Espaço para reflexão sobre questões citadas em cada unidade,
associando-os a suas ações.

FIXANDO O CONTEÚDO
Atividades de multipla escolha para ajudar na fixação dos
conteúdos abordados no livro.

GLOSSÁRIO
Apresentação dos significados de um determinado termo ou
palavras mostradas no decorrer do livro.
 6
SUMÁRIO
UNIDADE 1
TIPOS DE DADOS E TIPOS ABSTRATOS DE DADOS................................................................9
1. DADOS E TIPOS DE DADOS...................................................................................................................................10
2. TIPOS PRIMITIVOS DE DADOS.............................................................................................................................10
3. ARRAY UNIDIMENSIONAL E MULTIDIMENSIONAL...........................................................................................11
4. TIPOS ABSTRATOS DE DADOS (TAD)..............................................................................................................14
5. ESTRUTURAS DE TIPOS ABSTRATOS DE DADOS..........................................................................................14
FIXANDO O CONTEÚDO..................................................................................................................................17

UNIDADE 2
ESTUDO DE RECURSIVIDADE.................................................................................................22
1. INTRODUÇÃO À RECURSIVIDADE......................................................................................................................23
2. FORMAS DE IMPLEMENTAÇÃO DA RECURSIVIDADE..................................................................................24
FIXANDO O CONTEÚDO.................................................................................................................................28

UNIDADE 3
INTRODUÇÃO ÀS TÉCNICAS DE ANÁLISE DE ALGORITMOS............................................................32
1. INTRODUÇÃO AO PROJETO DE ANÁLISE DE ALGORITMOS......................................................................33
2. ANÁLISE DE ALGORITMOS....................................................................................................................................33
3. MEDIDA DE TEMPO DOS ALGORITMOS...........................................................................................................35
4. TÉCNICAS DE ANÁLISE DE ALGORITMOS.......................................................................................................38
FIXANDO O CONTEÚDO..................................................................................................................................41

UNIDADE 4
ESTRUTURAS DE DADOS ESTÁTICAS E DINÂMICAS NA MEMÓRIA PRINCIPAL................44
1. ESTRUTURAS DE DADOS LISTAS LINEARES.....................................................................................................45
1.1. Listas Lineares Estáticas..............................................................................................................................................45
1.2. Listas Lineares Dinâmicas.........................................................................................................................................48
2. ESTRUTURAS DE DADOS FILA..............................................................................................................................51
2.1. Filas Estáticas...................................................................................................................................................................51
2.2. Filas Dinâmicas.............................................................................................................................................................53
3. ESTRUTURAS DE DADOS PILHA.........................................................................................................................54
3.1. Pilhas Estáticas..............................................................................................................................................................55
3.2. Pilhas Dinâmicas..........................................................................................................................................................56
FIXANDO O CONTEÚDO.................................................................................................................................58
 7
UNIDADE 5
ALGORITMOS DE PESQUISA E ORDENAÇÃO EM MEMÓRIA PRINCIPAL.............................61
1. INTRODUÇÃO À PESQUISA..................................................................................................................................62
2. PESQUISA SEQUENCIAL.......................................................................................................................................62
3. PESQUISA BINÁRIA................................................................................................................................................64
4. ÁRVORE DE PESQUISA.........................................................................................................................................65
4.1. Árvore Binária de Pesquisa sem Balanceamento..........................................................................................66
4.2. Árvore Binária de Pesquisa com Balanceamento.........................................................................................69
5. INTRODUÇÃO À ORDENAÇÃO...........................................................................................................................74
6. ORDENAÇÃO POR SELEÇÃO...............................................................................................................................75
7. ORDENAÇÃO POR INSERÇÃO............................................................................................................................76
8. ORDENAÇÃO QUICKSORT..................................................................................................................................78
FIXANDO O CONTEÚDO.................................................................................................................................82

UNIDADE 6
ACESSO AOS ARQUIVOS DE DADOS....................................................................................90
1. INTRODUÇÃO AO USO DE ARQUIVOS..............................................................................................................91
2. FUNÇÕES DE ARQUIVOS.......................................................................................................................................91
2.1. Abertura de Arquivos: fopen().................................................................................................................................93
2.2. Fechamento de Arquivo: fclose()..........................................................................................................................94
3. MANIPULAÇÃO DE ARQUIVOS EM TEXTO VS BINÁRIO.............................................................................95
3.1. Leitura de Arquivo.........................................................................................................................................................96
3.2. Escrita em Arquivo.......................................................................................................................................................96
3.3. Manipulação de Arquivos Binários.......................................................................................................................97
4. MANIPULAÇÃO AVANÇADA DE ARQUIVOS.................................................................................................98
4.1. Movimentação do Ponteiro de Arquivo: fseek() e ftell().............................................................................98
4.2. Verificando Fim de Arquivo: feof()......................................................................................................................100
4.3. Tratamento de Erros em Arquivos: ferror().....................................................................................................102
FIXANDO O CONTEÚDO...............................................................................................................................104

GABARITO.........................................................................................................................108
REFERÊNCIAS BIBLIOGRÁFICAS.....................................................................................109
 8
UNIDADE 1
A unidade I trata sobre os tipos de dados e suas generalizações. Nesta
unidade veremos sobre Tipos de Dados e Tipos Abstratos de Dados, fazendo
uma definição teórico-práticas sobre os conceitos e utilização destes
CONFIRA NO LIVRO

elementos em linguagens de programação. Ainda na Unidade I veremos

algumas estruturas de Dados sobre Tipos de Dados mais comuns, como os
Array Uni e Multi dimensionais e as Estruturas.

UNIDADE 2
Na Unidade II fazemos um estudo sobre os processos de Recursividade,
identificando os que é e como tratar a recursividade. Veremos sobre
problemas recursivos e funções recursivas para tratamento de dados.

UNIDADE 3
A unidade III apresenta uma introdução às principais técnicas de Análise
de Algoritmos, demonstrando como identificar as estruturas e classes de
problemas e os algoritmos para resolvê-los. Ainda nesta unidade veremos
como realizar o estudo da medida de tempo dos algoritmos.

UNIDADE 4
A unidade IV apresenta as estruturas de dados mais comuns e utilizadas,
Lista, Pilhas e Filas. Nesta unidade iremos entender o funcionamento destas
estruturas, bem como a definição de códigos e a relação entre elas. Veremos
sobre estruturas Estáticas, que utilizam posições previamente definidas de
memória, e também estruturas Dinâmicas, que utilizam alocação dinâmica
de memória para proporcionar melhor flexibilidade no uso de memória e
tamanho das estruturas

UNIDADE 5
A unidade V apresenta estruturas de dados e seus algoritmos para pesquisa
e ordenação, fazendo uma introdução e conceitos fundamentais para
utilização das principais e mais utilizadas estruturas de dados para este
fim. Veremos nesta unidade sobre conceitos e definições de Pesquisa, seus
principais tipos a aplicações, bem como sobre as técnicas de ordenação,
conhecendo os principais algoritmos para esta finalidade

UNIDADE 6
Na unidade VI iremos tratar sobre persistência de dados com a utilização
de arquivos para salvar as informações e recuperação das mesmas.
Entenderemos o conceito e aplicação dos arquivos, suas funcionalidade e
principais funções para manipulação de arquivos para gravação e leitura
de dados.
 9

TIPOS DE DADOS E TIPOS

ABSTRATOS DE DADOS
 10
1. DADOS E TIPOS DE DADOS

Ao se pensar em algoritmos e programação de computadores é impossível não

pensar em Dados e Tipos de Dados. Os algoritmos representam sequencias lógicas e
bem definidas para se realizar determinada tarefa, e toda e qualquer tarefa que tenha
um mínimo de motivação ou sentido possui tratativas de dados.
Os dados são representações de qualquer tipo de informações que podemos
tratar e manipular em nossas tarefas. Eles correspondem à menor parte das informações
utilizadas nas tomadas de decisão em todas as tarefas realizadas e são considerados
os itens mais primitivos no processamento de informações, e por isso as categorias de
dados mais simples, são classificadas também como Tipos Primitivos de Dados.
Podemos pensar em um cadastro de usuários ou clientes de um estabelecimento.
Cada item separado que constitui este cadastro pode ser representado como um dado,
como por exemplo o nome do cliente, a data de nascimento do cliente, o CPF, o usuário
de login, a senha, a data do registro, dentre outros, os dados representam cada parte
de um todo da informação.
Ao se pensar em Computação ou Programação de Computadores, os dados são
representações de informações que podem ser utilizadas em um programa/algoritmo.
Estes dados são organizados/categorizados por tipos, que chamamos de Tipos de Dados
ou Tipos Primitivos de Dados, que determinam o conjunto de valores que os mesmos
podem assumir e até a diversificações das operações que podem ser utilizadas com
estes Dados e seus Tipos.
Os tipos de dados são extremamente importantes para qualquer linguagem de
programação, são eles que especificam os tipos de valores que as variáveis, constantes
e funções podem receber ou armazenar. Os tipos de dados também especificam
como que estes valores podem ser tratados e a álgebra relacional que os representa,
determinando todas as possíveis operações que podem ser realizadas sobre mesmos.
Existem várias linguagens de programação disponíveis no mercado e com relação
aos tipos de dados elas podem ser classificadas em tipadas ou não tipadas.
As linguagens tipadas são aquelas que exigem que os tipos de dados sejam
declarados explicitamente e requerem que todas as lógicas e formas de conversão
entre tipos sejam sempre observadas e tratadas.
As linguagens de programação não tipadas tratam os tipos de dados de forma
mais transparente para o programador, não obrigando que sejam declarados ou
observadas restrições sobre trocas de valores.
O correto entendimento e uso dos tipos de dados permitem que os programas
sejam mais eficientes e seguros, evitando problemas como estouro de memória ou erros
de tipo, onde valores inadequados são atribuídos a variáveis, gerando comportamento
indesejado ou resultados imprecisos.

2. TIPOS PRIMITIVOS DE DADOS

Os tipos primitivos de dados são aqueles tipos básicos declarados no escopo da

gramática da linguagem de programação, estes tipos estão diretamente disponíveis
e não requerem definição adicional, ou seja, são os tipos que usamos para declarar
 11
variáveis sem a necessidade de outras declarações. Eles formam a base para a
criação de variáveis e são muito utilizados em qualquer programa ou sistema. Na
linguagem de programação C, que é tipada, podemos diferenciar claramente os tipos
primitivos de dados e definir eficientemente o conjunto de valores que estes tipos de
dados representam. Os principais tipos primitivos de dados utilizados na linguagem de
programação C são: int, char, float e double.

FIQUE ATENTO
O tipo string ou texto não é representado como um tipo de dados primitivo na linguagem
C, este tipo de dados é definido pela união de vários tipos de dados char em uma única
variável, que chamamos de Array. Portanto, um string na linguagem de programação C
é definido como um Array de char.

NOME DO TIPO DESCRIÇÃO

Recebe números inteiros positivos ou negativos. Ex. 1; 2; 3; -4;

Int
-50; +100; etc.
Recebe caracteres únicos, ou seja, suporta somente uma
Char letra ou um número, sempre definido entre aspas simples.
Ex. ‘A’; ‘a’; ‘1’; etc.

Recebe números fracionários, com casas decimais, positivos

Float
ou negativos. Ex. 1.0; 2.0; 1.3; -5.4; etc.
É uma extensão do tipo float, permitindo valores maiores,
tecnicamente, é o dobro do tamanho do tipo float. Recebe
Double
números fracionários, com casas decimais, positivos ou
negativos. Ex. 1.0; 2.0; 1.3; -5.4; etc.
Quadro 1: Tipos de dados primitivos na linguagem C
Fonte: Fernandes, 2021

3. ARRAY UNIDIMENSIONAL E MULTIDIMENSIONAL

Os arrays, também chamados de Vetor (array unidimensional) e Matriz (array

multidimensional) são uma forma de armazenar mais de um elemento de um mesmo
tipo de dado em uma única variável. Ao invés de declarar várias variáveis separadas
para armazenar os dados, podemos utilizar array para armazenar todos estes dados
em um único local e com acesso facilitado através de índices.
É possível definir um array como um conjunto de posições de memória, variáveis,
do mesmo tipo, que é referenciado por um único nome. Este conjunto de elementos do
mesmo tipo pode armazenar tantos valores distintos quanto o seu tamanho (Fernandes,
2021).
Um item específico em um array pode ser acessado através do nome deste
 12
array e do índice associado ao mesmo. Em C, todos os arrays consistem em posições
contínuas na memória, ou seja, uma após a outra e sempre iniciam pelo índice 0 (zero).
Como vimos no início deste capítulo, os array também são chamados de Vetores
ou Matrizes. Os vetores são arrays de somente uma dimensão, enquanto as matrizes
são arrays de mais de uma dimensão. Para declarar um array devemos definir o tipo de
dados do mesmo, o seu nome e entre colchetes o tamanho, ou seja, a quantidade de
elementos distintos que desejamos para a nossa declaração.

Sintaxe:

tipo_de_dados nome [ tamanho ];

ex. int nota[10];

No exemplo acima, foi declarado um array com 10 posições de inteiros, ou seja,

é como se fossem 10 variáveis de inteiros, podendo armazenar 10 inteiros distintos ao
mesmo tempo, mas sendo todos eles referenciados por uma mesma variável com
acesso via índices. Para ter acesso a cada posição utilizamos o nome do array e o seu
índice entre colchetes. Então, nota[3] informa que estamos acessando o índice 3 do
array (vetor) nota, ou a posição 4 deste mesmo vetor, visto que a primeira posição é a
0(zero).

FIQUE ATENTO
Em C, os índices dos arrays sempre iniciam em 0 (zero). Portanto, int nota[10] corresponde
a nota[0], nota[1], nota[2], nota[3], ..., nota[8] e nota[9]. O mesmo se aplica para os arrays
uni e multidimensionais, os índices sempre iniciam em 0 (zero).

Ex.: Ler a nota de 3 alunos e calcular a média.

int i;
float nota[3], media,soma=0;
for (i=0; i<3; i++)
{
printf(“Digite a nota: ”);
scanf(“%f”,&nota[ i ]);
soma += nota[i];
}
media = soma / 3;
printf(“A média das notas é = %f”,media);

O exemplo acima faz a leitura das notas de três alunos e calcula e apresenta a
média destas notas. Neste código foi declarado um array chamado nota de tamanho
3, ou seja, com três posições que são os índices 0, 1 e 2. Dentro do laço de repetição for
podemos visualizar o comando scanf que faz a leitura do valor da nota, acessando o
array nota no índice i, que é controlado pelo laço, variando de 0 a 2. Estas notas são
somadas e por fim divididas por 3 para encontrar a média dos valores digitados.
Um array multidimensional, também chamado de matriz, é um array que consiste
 13
em uma estrutura de linhas e colunas (semelhante a uma tabela) (Fernandes, 2021).

int valores[3][4];

A declaração acima definiu um array chamado valores, que possui 3 linhas

e 4 colunas. Com isso temos: valores[0][0], valores[0][1], valores[0][2], e assim
sucessivamente, que são as definições de chamada de cada posição deste array. Neste
exemplo, as linhas vão de 0 a 2 (3 linhas) e as colunas vão de 0 e 3 (4 colunas).
O tipo de array multidimensional mais comumente utilizado é o array
bidimensional, que possui 2 dimensões, linha e coluna. Como vimos anteriormente
um array bidimensional é visualizado como uma tabela com linhas e colunas, o que o
torna ideal para representar dados como planilhas, mapas de imagem ou até matrizes
matemáticas usadas em álgebra linear.
A decisão de utilizar array uni ou multidimensional vai depender da necessidade
do projeto a ser tratado, por exemplo, para tratar uma lista de preços é mais interessante
que se utilize o array unidimensional, já para mapear uma imagem ou tratar pontos de
distância em um problema de roteamento de veículo é extremamente indicado que se
utilize o array multidimensional.
Os arrays multidimensionais podem ter duas ou mais dimensões para
representação dos dados. Para cada dimensão deve-se utilizar um colchete com a
representação do tamanho desta dimensão para a declaração, e no uso deste array
deve-se ter a mesma forma de apresentação colocando cada índice entre colchete
isoladamente. Por exemplo, um array de 4 dimensões pode ser declarado da seguinte
forma:

int modelo[3][5][2][4];

Neste array temos que a primeira dimensão tem tamanho 3, a segunda tem
tamanho 5, a terceira tem tamanho 2 e a última dimensão tem tamanho 4. Assim
como no array bidimensional, aqui temos que para cada dimensão temos todas as
outras, ou seja, no array modelo que declaramos temos 120 posições de memória para
armazenamento de valores do tipo de dados int (inteiro).

BUSQUE POR MAIS

Nos links abaixo é possível encontrar um conteúdo complementar sobre a utilização de
Arrays uni e multidimensionais na linguagem C. Assista aos vídeos e faça um comparativo
sobre o conteúdo aprendido até aqui no livro e o exposto nos links.

LINK 01. Disponível em: [Link] Acesso em: 16 jan. 2025.

 14

LINK 02. Disponível em: [Link] Acesso em: 16 jan. 2025.

4. TIPOS ABSTRATOS DE DADOS (TAD)

Uma vez que entendemos a teoria e as formas dos tipos primitivos de dados,
temos plena condições de entender o que são os Tipos Abstratos de Dados. Os tipos
abstratos de dados são uma forma especial de utilização dos tipos primitivos aplicados
para algum conceito ou finalidade específica onde os tipos primitivos individualmente
não são suficientes para atender às necessidades do projeto ou situação.
Os Tipos Abstratos de Dados são uma forma de encapsular dados e as operações
permitidas sobre eles, escondendo os detalhes de implementação e focando na
interface de uso. Diferente dos tipos primitivos, que são definidos pela linguagem, um
tipo abstrato de dados é uma construção que combina estrutura de dados com as
operações que podem ser realizadas sobre essa estrutura (Ziviani, 2005).
Contudo, um tipo abstrato de dados pode ser visto com uma combinação de Tipos
Primitivos e suas operações, definindo novos comportamentos e operações para serem
realizados por uma determinada aplicação ou projeto específico. Um exemplo clássico
de tipo abstrato de dados é a lista linear, que pode ser implementada de diferentes
formas, como uma lista encadeada ou um array. O usuário da lista, no entanto, não
precisa saber qual implementação está sendo utilizada. O importante é que ele possa
adicionar, remover e acessar elementos da lista por meio de funções ou operações
predefinidas.
Ainda seguindo o exemplo de aplicação de uma lista linear, o Tipo Abstrato de
Dados Lista Linear é uma combinação de Tipos Primitivos, ajustados adequadamente
para permitir o melhor aproveitamento das informações e tratativas de dados para a
lista. Neste contexto pode-se ainda definir as principais operações sobre listas lineares,
tais como: criar uma lista vazia; inserir um elemento na lista; pesquisar por um elemento
na lista; remover um elemento da lista; dentro outras que podem ser necessárias para
cada projeto em específico.

5. ESTRUTURAS DE TIPOS ABSTRATOS DE DADOS

As estruturas de dados são implementações com uso de Tipos de Dados

Primitivos para proporcionar uma melhor organização e estruturação dos mesmos e
consequentemente permitir a criação e estruturação dos Tipos Abstratos de Dados.
Estas estruturas organizam e armazenam os dados de maneira a facilitar o uso e
proporcionar facilidades nas operações de Inserção, Busca, Remoção, dentre outras.
 15
As estruturas de dados mais comuns e utilizadas são as Listas Lineares, as Filas, as
Pilhas e as Árvores Binárias de Pesquisa. É preciso um capítulo específico para tratar de
cada uma destas estruturas de dados, mas falaremos aqui um pouco sobre cada uma
delas.
As listas são estruturas de dados para armazenamento e recuperação de
informações, elas podem ser estáticas ou dinâmicas. Listas estáticas, implementadas
como arrays, têm tamanho fixo, enquanto listas dinâmicas, como listas encadeadas,
podem crescer ou diminuir conforme necessário com a utilização de alocação
dinâmica de memória, usando ponteiros ou estruturas auto referenciadas dependendo
da linguagem de programação utilizada. As listas dinâmicas são uma ferramenta
poderosa para armazenar sequências de dados que podem mudar de tamanho
durante a execução do programa.
As Filas e Pilhas são generalizações das Listas, onde implementam formas
específicas e regras bem definidas para acesso aos elementos (inserções e retiradas).
Uma Fila é uma estrutura em que as inserções são realizadas em um extremo e as
retiradas em outro. Esta estrutura também é conhecida com a sigla, do inglês, FIFO,
First-in, First-out, ou seja, o primeiro a chegar é o primeiro a sair, como em uma fila
tradicional, quem chega primeiro é atendido primeiro.
Uma Pilha é uma estrutura em que as inserções e retiradas são realizadas no
mesmo lugar. Esta estrutura também é conhecida com a sigla, do inglês, LIFO, Last-in,
First-out, ou seja, o ultimo que chega é o primeiro a ser atendido, pense no exemplo de
uma pilha de pratos em um restaurante, os clientes retiram os pratos do topo da pilha
e quando chega um prato novo ele é inserido no mesmo lugar, no topo da pilha.
Estas estruturas são bastante utilizadas e cada uma tem uma função importante
na construção de modelos computacionais de software. Atividades do dia a dia
podem ser tratadas com estas estruturas, tais como: Uma lista de telefones, uma fila
de impressão, uma pilha de processos ou arquivos para serem tratados, dentre várias
outras.
As árvores binárias são estruturas hierárquica onde os dados são organizados
em nós, com um nó raiz e subnós que formam subárvores. As árvores são usadas
para representar dados que têm uma relação hierárquica, como sistemas de arquivos
ou organizações de empresa. Mas também podem ser utilizadas para armazenar e
recuperar informações, como uma lista telefônica por exemplo. Os seus conceitos de
aplicação são amplos e podem ser implementados de acordo com a necessidade do
projeto a seu tratado.
O Algoritmo 1 apresenta uma proposta de Tipo Abstrato de Dados, TAD, para uma
Lista Linear com apontadores. Neste algoritmo identificar facilmente todos os elementos
constituintes de uma lista linear e ainda as suas definições de Tipos Abstratos. Como
vimos anteriormente nesta unidade, os TADs são generalizações dos tipos primitivos,
estruturados de forma a apresentar a representatividade da Estrutura de Dados em
questão, no caso do nosso exemplo, uma lista linear. Note que a estrutura principal da
lista será declarada pelo TAD TipoLista. Este por sua vez contem TADs Apontadores para
o Primeiro e o Último elemento da lista.
O TAD TipoApontador é uma estrutura de dados de ligação que permite a
declaração de outros TADs para a criação da Lista Linear, ele é um apontador de
memória para o TipoCelula, que é a estrutura Célula que contém os elementos da Lista.
Na célula temos o Item que recebe os itens que serão tratados/armazenados na lista e
um Apontador para o Próximo elemento da lista, permitindo assim a sua ligação.
 16
typedef int TipoChave;

typedef struct {
int Chave;
/* outros componentes */
} TipoItem;

typedef struct TipoCelula *TipoApontador;

typedef struct TipoCelula {

TipoItem Item;
TipoApontador Prox;
} TipoCelula;

typedef struct {
TipoApontador Primeiro, Ultimo;
} TipoLista;

Algoritmo 1: Tipo Abstrato de Dados Lista

Fonte: Ziviani, 2005

Essas estruturas são extremamente importantes no projeto de algoritmos pois

podem reduzir o tempo de busca ou inserção e até mesmo otimizar a utilização e
organização dos dados na tratativa das informações.

VAMOS PENSAR?
Imagine que você está desenvolvendo um sistema de gerenciamento de compras em
um supermercado. Que tipos de dados ou tipos abstratos de dados seriam os mais
adequados para representar as compras de um cliente? Pense na flexibilidade das
operações que você precisaria (inserir novos itens, excluir itens, ordenar por preço, etc.).
Para estes casos precisaremos pensar em Estruturas de Dados mais elaboradas, tais
como uma TAD Lista ou Fila, utilizando Arrays ou estruturas de alocação dinâmica de
memória.
 17
FIXANDO O CONTEÚDO
1. Analisando as expressões abaixo:

A = (2+2)*3
B = 2+2*3

Após a execução das expressões, quais serão os resultados de A e B:

A) A = 8 e B = 12
B) A = 12 e B = 12
C) A=4eB=8
D) A = 12 e B = 8
E) A = 12 e B = 4

2. Leia as afirmativas abaixo e marque a alternativa CORRETA.

I - Um algoritmo é uma sequência lógica de instruções para realizar uma determinada

tarefa.
II - Os algoritmos não representam necessariamente programas de computador, e sim
os passos necessários para se realizar uma tarefa.
III - Diferentes algoritmos podem realizar a mesma tarefa usando um conjunto
diferenciado de instruções em mais ou menos tempo, espaço ou esforço do que outros.

A) I e III são verdadeiros

B) Apenas II é verdadeira
C) II e III são verdadeiros
D) I e II são verdadeiros
E) Todas são verdadeiras

3. Sobre dados e tipos abstratos de dados, analise as afirmativas abaixo e marque a

alternativa correta

I – Dados e Tipos Abstratos de Dados são a mesma coisa e podem ser utilizados para
representação de informações com tipos primitivos nos algoritmos.
II - Os dados são representações de qualquer tipo de informações que podemos tratar
e manipular em nossas tarefas.
III – Tipo Abstrato de Dados é uma representação simbólica de um tipo primitivo de
dados em linguagens de programação que não implementam tipos de dados.

A) I e III são verdadeiros

B) Apenas II é verdadeira
C) II e III são verdadeiros
D) I e II são verdadeiros
E) Todas são verdadeiras
 18
4. Avalie as seguintes linhas de código na linguagem C e assinale a alternativa correta.

Linha 01: int A, B;

Linha 02: float C, D;
Linha 03: A = 10; B = 20;
Linha 04: C = 40;
Linha 05: D = 15.32;
Linha 06: C = A; printf(“%.2f”,C);

A) A atribuição realizada na Linha 04 não é permitida pois o valor inteiro 40 não pode ser
atribuído à variável float C.
B) A atribuição realizada na Linha 06 não é permitida pois o valor de A não é do mesmo
tipo que C.
C) O comando de saída vai enviar para o dispositivo padrão de saída o número 10.00.
D) O comando de saída vai enviar para o dispositivo padrão de saída o número 40.00.
E) Não podemos ter mais de uma instrução por linha de código como apresentado nas
Linhas 03 e 06.

5. Vetores e Matrizes são estruturas de dados muito simples que podem nos ajudar
muito quando temos muitas variáveis do mesmo tipo em um algoritmo. Imagine o
seguinte problema: você precisa criar um algoritmo que lê o nome e as 4 notas de
500 alunos, calcular a média de cada aluno e informar quais foram aprovados e quais
foram reprovados. Para este tipo de problema podemos utilizar estruturas de dados
tipo Vetor ou Matriz.

Considerando este contexto, avalie as seguintes asserções e a relação proposta entre

elas, e marque a opção correta.

I – Os vetores são estruturas que armazenam dados do mesmo tipo em posições

sequenciais de memória onde que podemos acessar cada tipo através de um índice,
esta estrutura é muito diferente da estrutura Matriz.
PORQUE
II – A estrutura Matriz armazena uma quantidade maior de elementos e estes podem
ser distribuídos por entre os índices e os diversos tipos de dados existentes dentro da
mesma estrutura.

A) As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

B) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
C) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E) As asserções I e II são proposições falsas.

6. Dado um algoritmo com um array global de tamanho 10, chamado vetor, e todas
as declarações e inicializações necessárias para o seu correto funcionamento. Dado
ainda que este algoritmo tem duas funções, funcaoAlgo1 e funcaoAlgo2 (apresentadas
abaixo), e que estas funções foram declaradas e assinadas no programa. Dado
um programa principal que faz a leitura de valores para o vetor e chama a função
funcaoAlgo1, analise a descrição apresentada e os trechos de códigos abaixo e marque
 19
a alternativa CORRETA.

void funcaoAlgo1()
{
for (i=0;i<9;i++)
{
for (j=i+1; j<10;j++)
{
if (vetor[j]<vetor[i])
funcaoAlgo2 (i,j);
}
}
}

void funcaoAlgo2(int x, int y)

{
int aux;
aux = vetor[x];
vetor[x] = vetor[y];
vetor[y] = aux;
}

A) Este cenário apresenta uma situação em que vários blocos de códigos escritos e
agrupados dentro de um programa principal com todas as suas declarações, mas
não realiza nenhuma atividade relevante, não fazendo movimentação de dados e nem
utilização de memória.
B) Este cenário apresenta uma estrutura que utiliza um vetor de inteiros, duas funções
auxiliares e dentro do programa principal preenche o vetor e invoca as funções
auxiliares, chamando primeiro a primeira função e depois a segunda função. As funções
embaralham os valores do vetor.
C) Este cenário demonstra a utilização de uma estrutura complexa para a realização
de tarefas simples de tratamento de entrada e saída de dados inteiros em estrutura
do tipo vetor. As funções demonstradas fazem uma demonstração de entrada, saída e
movimentação dos valores no vetor.
D) Este cenário apresenta uma estrutura que utiliza um vetor de inteiros, duas funções
auxiliares e dentro do programa principal faz a leitura dos valores neste vetor de inteiro
e invoca as funções auxiliares para realizar a ordenação de forma crescente nos valores
armazenados no vetor.
E) Este cenário não é relevante e apresenta uma estrutura falha e com erros, ao se codificar
toda a definição apresentada será necessário modificar algumas funcionalidades e
redefinir algumas informações para evitar erros de compilação e execução do programa.

7. Um Tipo Abstrato de Dados é uma estrutura de dados que define o conjunto de

operações permitidas, sem especificar a implementação interna. Sobre TADs, considere
as seguintes afirmações:

I. Um TAD deve encapsular os dados, permitindo acesso somente através de operações

específicas.
 20
II. A implementação de um TAD pode ser feita com diferentes estruturas de dados, desde
que as operações definidas sejam mantidas.
III. Um TAD define a forma de armazenamento interno dos dados.

Está correto o que se afirma em:

A) I, apenas.
B) I e II, apenas.
C) II e III, apenas.
D) I e III, apenas.
E) I, II e III.

8. Em C, a palavra-chave struct permite definir um Tipo Abstrato de Dados (TAD)

que agrupa diferentes tipos de dados em uma única estrutura. Considere a seguinte
definição de estrutura que representa um ponto no espaço 2D:

struct Ponto {
float x;
float y;
};

float calcularDistancia(struct Ponto a, struct Ponto b) {

return (b.x - a.x) + (b.y - a.y);
}

Agora, considere o seguinte código:

int main() {
struct Ponto p1, p2;

p1.x = 2.0;
p1.y = 3.0;

p2.x = 5.0;
p2.y = 7.0;

float distancia = calcularDistancia(p1, p2);

return 0;
}

O programa acima visa calcular a "distância" entre dois pontos p1 e p2. No entanto, o
cálculo da distância está incorreto. Qual das alternativas abaixo corrige o erro de lógica
no cálculo da distância entre os pontos?

A) Alterar a função calcularDistancia() para retornar ((b.x - a.x) * (b.x - a.x)) + ((b.y - a.y)
* (b.y - a.y)).
B) Alterar a função calcularDistancia() para retornar b.x + b.y - a.x - a.y.
C) Alterar a função calcularDistancia() para retornar (b.x + b.y) - (a.x + a.y).
 21
D) Alterar a função calcularDistancia() para retornar (b.x - a.x) + (b.y - a.y), pois o código
já está correto.
E) Alterar a função calcularDistancia() para retornar (b.x - a.x) * (b.y - a.y).
 22

ESTUDO DE RECURSIVIDADE
 23
1. INTRODUÇÃO À RECURSIVIDADE

A Recursividade é uma técnica na qual uma função chama a si mesma para

resolver problemas ou subproblemas menores de um problema maior. Esta abordagem
é baseada no princípio da divisão e conquista, onde um problema é repetidamente
dividido em partes menores até que cada uma dessas partes se torne simples o
suficiente para ser resolvida diretamente.
A recursividade é uma técnica matemática extremamente importante na
computação e tratativa de problemas que tenha características recursivas em suas
formulações. Em problemas que envolvem estruturas como árvores ou grafos, ou onde
a decomposição repetida é necessária, a recursividade oferece uma maneira natural e
clara de modelar a solução para estes problemas.
Esta técnica matemática é muito útil em situações onde a solução do problema
pode ser expressa em termos recursivos de soluções de subproblemas de tamanho
menor. Ao usar recursividade, um problema complexo pode ser descrito de forma mais
concisa e intuitiva. Por exemplo, na matemática, uma definição recursiva de um número
fatorial (n!) diz que o fatorial de n é n * (n-1)!, e o caso base é 0! = 1. O mesmo raciocínio
pode ser aplicado a algoritmos de programação.
Com isso podemos ter uma noção mais ampla sobre o que é a recursividade ao
entender o problema matemático do Fatorial. O Fatorial de um número é a multiplicação
deste número por todos os seus antecessores até 1, ou seja, o fatorial de 5, que é
representado por 5! é a multiplicação de 5 por todos os seus antecessores, sendo igual
a 5 x 4 x 3 x 2 x 1, que é igual a 120.
Analisando este cenário, temos que o fatorial de 4, 4!, é igual a 4 x 3 x 2 x 1, com
isso podemos concluir que o fatorial de 5 é igual a 5 vezes o fatorial de 4, sendo 5! =
5 x 4!. Note que cada parte da solução de fatorial de um número é o fatorial de outro
número, então o fatorial é um problema matemático recursivo por natureza, ou seja, um
problema que pode ser divido em partes menores para a solução do mesmo, em que
cada parte pode representar o todo de algum outro problema.
No entanto, embora seja poderosa, a recursividade deve ser usada com cuidado.
Um dos maiores perigos da recursividade é a possibilidade de loops infinitos ou estouro
de pilha, quando a função recursiva continua chamando a si mesma indefinidamente
ou excede a capacidade de memória da pilha de execução do sistema. Para evitar
esses problemas, é necessário definir claramente as condições parada ou caso base,
que determinam quando a função recursiva deve parar.

FIQUE ATENTO
A condição de parada, ou caso base, é um dos pontos mais importante a se observar ao
definir funções recursivas para resolução de problemas. Se a condição de parada for mal
definida ou não existir, o processamento poderá ser indeterminado e ocasionar resultado
imprecisos, estouro de pilha (memória) ou loop infinitos.
 24
O Quadro 1 apresenta uma relação de vantagens e desvantagens do uso de
recursividade que devem ser sempre observados e levado em consideração na tratativa
de problemas computacionais e na escolha dos algoritmos para resolvê-los.

VANTAGENS DESVANTAGENS
Simplicidade na representação de Uso de memória. Cada chamada recursiva
problemas complexos. Para certos consome memória, pois o sistema precisa
problemas, a recursividade permite uma armazenar o estado atual da função na pilha
solução natural e intuitiva, onde seria mais de chamadas até que a função recursiva
difícil encontrar uma solução iterativa retorne. Para problemas de grande escala,
equivalente. Problemas envolvendo isso pode levar a estouro da pilha e falhas de
árvores, grafos ou algoritmos de busca em execução.
profundidade são exemplos disso.

Divisão e Conquista. A recursividade Desempenho. Em alguns casos, a recursão

facilita a aplicação da técnica de divisão pode resultar em múltiplas chamadas
e conquista, onde um problema é redundantes. Por exemplo, em certos
decomposto em subproblemas menores, problemas como o cálculo da sequência
resolvidos recursivamente, e suas soluções de Fibonacci, uma abordagem recursiva
são combinadas para resolver o problema direta faz chamadas repetidas para calcular
original. Exemplos clássicos incluem o os mesmos valores múltiplas vezes, o que
algoritmo Quicksort e a busca binária. compromete o desempenho.

Menor necessidade de estruturas de Compreensão e depuração. Embora a

controle. Enquanto a solução iterativa de um recursividade possa simplificar o código,
problema pode requerer estruturas como ela também pode torná-lo mais difícil de
loops e pilhas adicionais para controlar o entender e depurar, especialmente para
fluxo do programa, a recursividade embute programadores menos experientes. Quando
esses controles no próprio fluxo da execução o número de chamadas recursivas é grande,
da função, simplificando o código. rastrear a execução e o estado do programa
se torna mais complicado.
Quadro 1: Quadro comparativo de Vantagens e Desvantagens da Recursividade
Fonte: Elaborado pelo autor (2024).

2. FORMAS DE IMPLEMENTAÇÃO DA RECURSIVIDADE

A recursividade, ou funções recursivas, podem ser classificadas em dois

tipos principais: recursividade direta e recursividade indireta, cada uma com suas
características e usos apropriados que podem ser aplicadas de acordo com a
necessidade do problema a ser tratado. Como vimos anteriormente, cada tipo de
problema tem suas características e a forma mais indicada e correta de seus tratamentos
é seguindo suas características principais, tornando assim mais fácil e eficiente a sua
solução, por isso o correto entendimento das técnicas de projetos de algoritmos, como
a recursividade, por exemplo, é muito importante para a escolha das melhores técnicas
de solução (Ziviani, 2012).
A recursividade direta ocorre quando uma função chama a si mesma diretamente.
Este é o tipo mais simples e comum de recursividade, utilizado em problemas como
cálculo de fatorial, algoritmos de ordenação, árvores e pesquisas binárias (Cormen,
1990).
 25
A implementação de uma função recursiva direta envolve três componentes
principais:

1. Caso base: a condição que determina quando a função deve parar de se chamar.
Sem um caso base bem definido, a recursividade resultará em um loop infinito.
2. Passo recursivo: a parte da função onde o problema é decomposto e a função se
chama novamente para resolver uma versão menor do problema original.
3. Combinatória de resultados: após a resolução dos subproblemas, os resultados
parciais são combinados para produzir a solução final.

Por exemplo, ao calcular o fatorial de um número N, o caso base é a condição que

irá resultar na parada das chamadas recursivas do procedimento/função, ou seja, a
condição que não envolve realizar outra chamada recursiva. No caso do fatorial, o caso
base poderia ser definido com resultado igual a 1 para N valendo 0 ou 1.
O passo recursivo do fatorial envolve chamar a função com o valor de N-1
repetidamente até encontrar o caso base. E a combinação de resultados é a aplicação
da fórmula base do fatorial para resolver o problema tratado. Vejamos a segui um
algoritmo simples para cálculo do fatorial de um número.

1 int fatorial(int N)
2 {
3 if (n<1)
4 return 1;
5 else
6 return N * fatorial(N-1)
7 }

Exemplo 1: Algoritmo recursivo para o fatorial

Fonte: próprio autor

Neste algoritmo recursivo para cálculo do fatorial de um número temos uma

função que recebe um parâmetro do tipo inteiro e retorno um valor do tipo inteiro, como
podemos observar na linha 1. O nome da função é fatorial e o número a ser calculado o
fatorial está na variável N que é passada por parâmetro para a função.
Nas tratativas apresentadas nas linhas 3 e 4 temos o caso base, onde será
retornado para a chamada recursiva o valor 1 caso o número recebido pela função
seja menor que 1. Na linha 6 temos a definição do passo recursivo e a combinação dos
resultados em uma única chamada, onde o passo recursivo envolve chamar a função
fatorial recursivamente enviando como parâmetro o valor de N-1 em cada passo, e a
combinação dos resultados envolver a aplicação da fórmula do fatorial onde o valor
atual de N é multiplicado pelo resultado do fatorial de N-1.
Vamos a um entendimento mais visual deste processo. Como vimos anteriormente,
o fatorial de um número é a multiplicação deste número por todos os seus antecessores
até 1. Então o fatorial de 5, escrito como 5!, é 5 x 4 x 3 x 2 x 1, e consequentemente o fatorial
de 4 é 4! que é igual a 4 x 3 x 2 x 1, com isso conseguimos concluir que o fatorial de 5
pode ser descrito recursivamente com sendo 5 x 4!, ou seja, 5 x (5-1)!. E isso acontece
 26
com qualquer número que desejarmos calcular o fatorial.
Tomando a definição anterior como base para todo o entendimento do
fatorial, podemos observar que ao chamar uma função que calcula o fatorial de 5, se
multiplicarmos este valor pelo resultado do cálculo do fatorial de 5-1, ou seja, 4!, vamos
obter o valor do fatorial de 5. A figura 1 ilustra este procedimento.

Figura 1: Exemplo do cálculo do fatorial de 5

Fonte: Elaborado pelo autor (2024).

Como podemos observar na figura 1, em chamadas recursivas o resultado vem

sendo construído do final para o início, ou seja, as chamadas recursivas são empilhadas
e no retorno eles serão desempilhados e construindo o resultado. Neste caso, ao chamar
a função recursiva fatorial e enviar o valor 5 como parâmetro desta função na linha 6
do nosso algoritmo do fatorial, ela retorna o valor de 5 multiplicado pelo valor do fatorial
de 5-1. Veja na figura 1 este passo onde temos 5 x 4!.
Como ainda não temos o valor do fatorial de 4, o processo da recursividade irá
empilhar o valor de 5 e aguardar o cálculo do fatorial de 4 para realizar a multiplicação.
Este passo se repete até o caso base, que é o valor de N ser igual a 1, onde será retornado
o valor 1 para multiplicar com 2 (da chamada recursiva anterior). E esse resultado
será multiplicado por 3, e o resultado por 4 e finalmente o valor do fatorial de 4 será
multiplicado por 5, resultando no valor 120 que é o fatorial de 5.
As funções recursivas são excelentes tratativas para problemas de natureza
recursiva pois agregam praticidade, facilidade e eficiência na resolução destes
problemas.

FIQUE ATENTO
Quase todos os problemas que tem natureza recursiva podem ser tratados facilmente
por algoritmos recursivos, como é o caso do fatorial, das árvores binárias e vários outros.
Mas existem alguns problemas de natureza recursiva que não geram bons resultados ao
serem tratados por algoritmos recursivos, como é o caso do algoritmo de Fibonacci. Estas
tratativas são extremamente ineficientes pois podem gerar retrabalho de ter que calcular
os mesmos valores várias vezes na tratativa e isso deixa o procedimento recursivo caro
computacionalmente.
 27
VAMOS PENSAR?
Uma árvore binária também é uma estrutura recursiva, onde cada parte de uma
árvore (subárvore) pode ser vista como uma árvore por si só. Com isso a aplicação de
recursividade é uma ótima solução para este problema. Pense em um algoritmo recursivo
onde a chamada para os elementos de uma árvore sempre escolhem a subárvore
esquerda ou à subárvore direita para continuar um procedimento de caminhamento em
árvore, por exemplo.

A recursividade indireta é um procedimento onde uma função A chama outra

função B, que por sua vez chama a função A novamente. Esta forma de recursividade é
menos comum de acontecer, mas aparece em casos onde o controle de fluxo depende
de mais de uma funcionalidade em separado e que pelo padrão de desacoplamento
precisam ficar separados, ou seja, o controle do fluxo do programa é distribuído entre
várias funções distintas (Cormen, 1990).
A recursividade indireta requer atenção especial ao definir os casos base, pois a
interação entre as funções pode tornar difícil identificar a condição de parada.

BUSQUE POR MAIS

Existem alguns outros tipos particulares de recursividade, eles são um pouco menos
comuns e menos utilizados que os citados, mas são igualmente importantes para nosso
conhecimento e para processos de programação. Nos links a seguir podemos conhecer
um pouco mais sobre estes tipos.

LINK 01. Disponível em: [Link] Acesso em 16 jan. 2025.

LINK 02. Disponível em: [Link] Acesso em 16 jan. 2025.

LINK 03. Disponível em: [Link] Acesso em 16 jan. 2025.

 28
FIXANDO O CONTEÚDO
1. A recursividade é uma técnica utilizada em programação onde uma função chama
a si mesma para resolver subproblemas menores de um problema maior. Considere a
seguinte implementação em C de uma função recursiva que calcula o fatorial de um
número inteiro positivo n:

int fatorial(int n) {
if (n == 0) {
return 1;
} else {
return n * fatorial(n - 1);
}
}

Sobre o código acima, assinale a alternativa correta:

A) A função fatorial entrará em laço de repetição infinito se n for negativo.
B) A função fatorial não retornará o valor correto se n for maior que 10.
C) A função fatorial utiliza a técnica de divisão e conquista para resolver o problema.
D) A função fatorial possui um caso base que garante a terminação da recursão.
E) A função fatorial não pode ser implementada iterativamente.

2. Algumas funções matemáticas podem ser estabelecidas de tal forma que as suas
definições utilizem, de modo recorrente, a própria função que se está definindo. Um
exemplo clássico disso é a recursividade, que é uma ideia inteligente que desempenha
um papel central na programação funcional como o mecanismo de programação na
qual a chamada é feita direta ou indiretamente por ela mesma para realizar o cálculo
necessário.
Fonte: Aprendendo a Programar Programando na Linguagem C de Jaime Evaristo (Terceira Edição).

Analise o trecho do código em C abaixo, aplicando a recursividade com a utilização do

conceito de um número fatorial.

long int FatRec(int n)

{
if ((n== 0) || (n== 1))
return (1);

else
return (n * FatRec(n - 1));
}

Qual seria o resultado exibido para o usuário usando o comando “printf” se ativarmos a
função acima passando o valor de n = 8?
 29
A) 5040
B) 40320
C) 362880
D) 40480
E) 36860

3. Sobre recursividade, analise as afirmativas abaixo e marque a alternativa correta.

I – A recursividade é uma técnica matemática extremamente importante na computação

e tratativa de problemas que tenha características recursivas em suas formulações.
II – Uma árvore binária também é uma estrutura recursiva, onde cada parte de uma
árvore (subárvore) pode ser vista como uma árvore por si só.
III – A recursividade direta ocorre quando uma função chama a si mesma diretamente.
Este é o tipo mais simples e comum de recursividade.

É correto o que se afirma em:

A) I, apenas.
B) II, apenas.
C) I e III, apenas.
D) II e III, apenas.
E) I, II e III.

4. A recursividade é uma técnica fundamental em algoritmos, onde uma função chama

a si mesma para resolver um problema maior dividindo-o em subproblemas menores.
Considere o seguinte código em C, que calcula o fatorial de um número:

int fatorial(int n) {
if (n == 0)
return 1;
else
return n * fatorial(n - 1);
}

Sobre esse código e o conceito de recursividade, analise as seguintes afirmações:

I. A função utiliza recursividade para resolver o problema, pois chama a si mesma para
calcular o fatorial de n.
II. O caso base está corretamente definido na condição n == 0, o que impede um loop
infinito.
III. A função pode causar estouro de pilha se for chamada com valores muito grandes
de n.

Está correto o que se afirma em:

A) I, apenas.
B) I e II, apenas.
C) II e III, apenas.
D) I, II e III.
E) Nenhuma das alternativas anteriores.
 30
5. A recursividade é frequentemente usada em problemas que podem ser decompostos
em subproblemas menores, como o cálculo do fatorial. Entretanto, um dos maiores
desafios ao utilizar recursividade é a definição do caso base, que garante que a recursão
seja interrompida em algum ponto. Sobre o uso de recursão no cálculo do fatorial,
assinale a alternativa correta:

A) A recursão sempre resulta em um loop infinito, independentemente da definição do

caso base.
B) O caso base para a função fatorial define a condição de parada da recursão, evitando
loops infinitos.
C) O cálculo do fatorial não pode ser implementado usando recursão, apenas iteração.
D) A função recursiva fatorial não precisa de um caso base, pois ela se resolve
automaticamente.
E) A recursividade só é eficiente para pequenos valores de n, sendo proibida para valores
maiores.

6. Sobre recursividade, analise as afirmativas abaixo e marque a alternativa correta.

I – A implementação de uma função recursiva direta envolve três componentes

principais: Caso base, Passo recursivo e Combinatória de resultados
II – Recursividade é uma técnica computacional para definição de tipos de dados e
tipos abstratos de dados
III – Em todos os casos de recursividade a estrutura do algoritmo será apresentada da
mesma forma, obtendo assim sempre a mesma chama da função base.

É correto o que se afirma em:

A) I, apenas.
B) II, apenas.
C) I e III, apenas.
D) II e III, apenas.
E) I, II e III.

7. Considerando o contexto da recursividade direta e indireta, avalie as seguintes

asserções e a relação proposta entre elas, e marque a opção correta.

I – A recursividade direta ocorre quando uma função chama a si mesma diretamente,

sendo amplamente utilizada em problemas como cálculo de fatorial e algoritmos de
ordenação.
PORQUE
II – A recursividade indireta é aquela em que uma função chama outra função, que por
sua vez chama a função original novamente, o que dificulta a implementação de casos
base, tornando-a menos comum.

A) As asserções I e II são proposições verdadeiras, e a II é uma justificativa da I.

B) As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa da I.
C) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
D) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
E) As asserções I e II são proposições falsas.
 31
8. Sobre a recursividade e seu uso em algoritmos, considere as seguintes afirmações:

I - Funções recursivas precisam ter um caso base claramente definido para evitar loops
infinitos.
II - A recursividade indireta é caracterizada por uma função chamar outra função, que
por sua vez chama a função original novamente.
III - Em todos os problemas que podem ser modelados recursivamente, a recursividade
é sempre mais eficiente do que uma solução iterativa.

Está correto o que se afirma em:

A) I e II, apenas.
B) I e III, apenas.
C) II e III, apenas.
D) I, II e III.
E) I, apenas.
 32

INTRODUÇÃO ÀS TÉCNICAS DE
ANÁLISE DE ALGORITMOS
 33
1. INTRODUÇÃO AO PROJETO DE ANÁLISE DE ALGORITMOS

Um algoritmo é uma sequência finita de instruções bem definidas, estruturas e

sem ambiguidade para ser resolver alguma determinada tarefa. Na computação a
busca por algoritmos eficazes para resolução de problemas é uma busca incansável
dos programadores, analistas e cientistas, pois a eficiência de um algoritmo pode ter
um impacto significativo no desempenho geral de um sistema (SERPA, 2021).
O projeto de algoritmos envolve o processo de criação de soluções que são corretas
e que também devem ser eficientes ao mesmo tempo. Esta é a principal preocupação
do projeto e análise de algoritmos, criar, determinar, analisar quais algoritmos são mais
eficientes para determinados problemas.
E quando falamos de eficiência, não estamos falando somente de funcionar
corretamente, mas também de ter boa utilização de recursos, ou seja, memórias,
processamento e tempo. Com isso surge a área de análise de algoritmos, que é uma
área da computação dedicada ao estudo da eficiência dos algoritmos e classes de
problemas (Ziviani, 2012).
Segundo (Ziviani, 2012) o projeto de algoritmos é fortemente influenciado pelo
estudo de seus comportamentos e depois que um problema é analisado e decisões
de projeto são finalizadas, é necessário entender todas as opções para utilização e
aplicação destes algoritmos, analisando os casos e considerando aspectos de tempo
de execução e espaço utilizados, ou seja, processamento e memória.
Como citado anteriormente, a análise de algoritmos é a área da ciência da
computação dedicada a todo o processo de entendimentos dos comportamentos
e aplicações dos algoritmos com foco principal no que chamamos de eficiência dos
algoritmos. Neste processo três situações principais merecem destaque e atenção:

• Tempo de execução: quantas operações o algoritmo executa à medida que o

tamanho da entrada aumenta.
• Uso de memória: quanta memória o algoritmo requer durante sua execução.
• Complexidade computacional: uma medida de como o uso de tempo e memória
cresce com o tamanho da entrada.

O processo de análise de algoritmos é muito importante no apoio às tomadas

de decisão dentro do desenvolvimento de software e na escolha das representações
algorítmicas para resolução de problemas ou mesmo o desenvolvimento completo
de um software ou aplicativo. Este processo permite aos profissionais da área tomar
decisões sobre qual algoritmo usar para o tipo de problema que estiver resolvendo
ou para o qual sua aplicação se propõe a solucionar, levando em consideração as
limitações de hardware e a natureza do problema em questão (Cormen, 1990).

2. ANÁLISE DE ALGORITMOS

A análise de algoritmos pode ser realizada de várias maneiras, mas duas delas
são mais comumente conhecidas, embora somente uma delas é mais amplamente
utiliza e mais confiável. Neste sentido podemos destacar a análise empírica e a análise
 34
teórica.
A análise empírica envolve a execução real do algoritmo em diferentes entradas
e a medição de seu desempenho em termos de tempo e espaço de execução. Embora
esse método forneça resultados práticos e concretos, ele está sujeito a limitações,
como as condições do ambiente de execução, o hardware utilizado e a natureza
específica das entradas testadas. Assim, ele pode não fornecer uma visão geral sobre o
comportamento do algoritmo para entradas muito grandes ou desconhecidas (Ziviani,
2012).
Este tipo de análise entrega pouca eficiência em termos de resultados, pois
estamos sujeitos aso desempenho da máquina e dos softwares instalados na mesma.
Se existir uma requisição extra para memória ou processamento no momento da análise
todo o resultado poderá ser comprometido por esta requisição de recursos não previsto
no projeto do algoritmo.
A análise teórica busca entender o comportamento do algoritmo
independentemente do hardware ou das entradas específicas, examinando como o
tempo de execução e o uso de memória escalam com o tamanho da entrada. A análise
teórica utiliza notações matemáticas para expressar a complexidade dos algoritmos,
sendo a mais comum a notação Big O (Ziviani, 2012).
Este tipo de análise é mais preciso em seus resultados e não está relacionado com
a execução ou recursos de máquina, ela utiliza modelos matemáticos para analisar
e determinar a complexidade computacional de um determinado algoritmo ou uma
classe de algoritmos da mesma família entregando resultados mais precisos.
A análise de complexidade de tempo leva em consideração a quantidade de
tempo, ou seja, o número de operações que o algoritmo requer para executar com uma
entrada de tamanho N, sendo N definido como a medida do tamanho da entrada.
Utilizamos a notação O(N) para sinalizar a ordem da que complexidade
computacional de um problema de tamanho N., portanto uma análise de algoritmo
com resultado de complexidade igual à O(N) quer dizer que este algoritmo realiza um
número linear de operações em relação ao tamanho da entrada N e que o mesmo irá
crescer ou diminuir linearmente de acordo com o tamanho da entrada, ou seja, e n
dobra, o número de operações também dobra.
Da mesma forma podemos identificar que um algoritmo de complexidade O(N²)
realiza um número quadrático de operações, o que significa que se o tamanho da
entrada N dobra, o número de operações quadruplica.
Por outro lado, a análise de complexidade de espaço trata da quantidade de
memória necessária para a execução do algoritmo, levando em consideração todas
as variáveis, estruturas, declarações e operações utilizando memória no algoritmo
analisado.
A notação Big O é uma forma matemática de descrever a eficiência de um
algoritmo em termos de tempo de execução ou uso de memória, definindo assim a
ordem de complexidade matemática dos algoritmos e expressando a relação entre o
tamanho da entrada e o número de operações executadas.
Esta notação classifica os algoritmos de acordo com sua ordem de crescimento,
ou seja, como o tempo de execução ou o uso de memória crescem à medida que o
tamanho da entrada aumenta. Definindo resultados de acordo com um padrão de
tamanho de entrada para os algoritmos.
Alguns exemplos de complexidades mais comuns são O(1), O(n), O(log n), O(n log
n) e )(n2) (Ziviani, 2012).
 35
• O(1): Complexidade constante – o tempo de execução não depende do tamanho
da entrada. Exemplo: acesso direto a um elemento em um array. Esta complexidade
é aplicada quando temos acesso direto, sempre indo objetivamente ao elemento
desejado.
• O(n): Complexidade linear – o tempo de execução cresce proporcionalmente ao
tamanho da entrada. Exemplo: percorrer todos os elementos de uma lista. Esta
complexidade é aplicada a algoritmos que sempre tem custo igual ao tamanho
do problema.
• O(log n): Complexidade logarítmica – o tempo de execução cresce de forma
lenta conforme o tamanho da entrada aumenta. Exemplo: busca binária. Esta
complexidade é aplicada a algoritmos que, geralmente, partem o problema ao
meio, descartam uma parte e continuam a execução com a outra.
• O(n log n): Complexidade linear-logarítmica – combina características lineares
e logarítmicas. Exemplo: algoritmos eficientes de ordenação como Merge Sort e
Quick Sort. Esta complexidade é aplicada a algoritmos que, geralmente, partem
o problema ao meio e tratam todas as partes para depois juntar os resultados.
• O(n²): Complexidade quadrática – o tempo de execução cresce de forma
quadrática em relação ao tamanho da entrada. Exemplo: algoritmos simples
de ordenação como Bubble Sort. Esta complexidade, geralmente, é aplicada a
algoritmos que precisam comparar as estruturas de seus conjuntos, como é o
caso de algoritmos de ordenação, que precisam comparar os valores de um
conjunto para ordená-los.

A notação Big O permite aos programadores prever o comportamento de

algoritmos quando lidam com grandes volumes de dados, ajudando na escolha de
algoritmos mais eficientes para diferentes cenários.

3. MEDIDA DE TEMPO DOS ALGORITMOS

Uma das métricas mais importantes e eficientes para avaliar os algoritmos é pela
medida de tempo de execução dos algoritmos. Esta medida de tempo é na verdade
uma definição teórica matemática para analisar a complexidade computacional dos
algoritmos, pois a medida do tempo real de execução de um algoritmo depende de
fatores externos como a velocidade do processador e as condições de uso de memória
e do sistema.
Essa medida de tempo teórica foca em quantas operações o algoritmo realiza
para uma entrada de tamanho N. Essa medida é importante para compreender a
escalabilidade do algoritmo, especialmente em sistemas que processam grandes
volumes de dados.
A medida de tempo de um algoritmo é a formulação matemática do número de
operações primitivas realizadas durante a sua execução. Essas operações são ações
que são executadas em tempo constante, como somas, multiplicações ou comparações
entre dois números. O objetivo da medida matemática de tempo é contar o número
total de operações primitivas realizadas pelo algoritmo como uma função do tamanho
da entrada.
 36
Como dito, ao analisar o tempo de um algoritmo verificamos a quantidade de
operações primitivas que este algoritmo executa. Por exemplo, para verificar qual é o
maior valor em um conjunto de valores é preciso comparar todos os valores existentes no
conjunto, portanto, um algoritmo eficiente para esta operação deverá obter o primeiro
valor e comparar com todos os outros do conjunto, sempre atualizando o maior valor
quando encontrar, ou seja, obtemos o primeiro valor e comparamos com o segundo,
ficando com o maior, depois comparamos este maior com o terceiro, também ficando
com o maior, e repetimos esta operação com todos os demais valores do conjunto.
No final desta operação de comparações realizamos N-1 comparações no conjunto
para encontrar o maior valor existente no mesmo. Por definição matemática e lógica, é
impossível encontrar o maior valor de um conjunto desordenado sem comparar todos
os valores, e com isso chegamos à conclusão que a melhor situação para encontrar
o maior valor de um conjunto é realizando N-1 comparações. Com isso, temo que no
melhor caso, ou seja, a melhor situação possível, este algoritmo para encontrar o menor
valor de um conjunto tem medida de tempo igual a N-1.
Agora vamos a outra situação de exemplo, imagina que você precisa encontrar
o nome em uma lista de nome já preenchida. Supondo que esta lista de nome está
desordenada e tomando por base que a medida de tempo leva em consideração a
quantidade de operações primitivas realizadas, então cada comparação entre nomes
irá somar uma operação na medida de tempo.
Um bom algoritmo para encontrar um nome em um conjunto de nomes poderia
obter o primeiro nome do conjunto e verificar se é o nome procurado, se for encontrado
o nome, finaliza o algoritmo. Se não for encontrado o nome, passa para o próximo nome
e repita a operação, ou seja, compara se é o nome procurado. Faça isso até encontrar
o nome procurado ou atingir o final do conjunto e não encontrar o nome.
Para esta busca por um elemento em um conjunto, tempo algumas situações a
observar: (1) O nome procurado pode ser o primeiro do conjunto; (2) O nome procurado
pode ser o último ou não existir no conjunto. Caso o nome procurado seja o primeiro do
conjunto, está é a melhor situação possível, pois vamos encontrar e finalizar o algoritmo
no tempo mais rápido possível. Caso o nome não exista, esta é a pior situação pois
além de procurar em todos os elementos, não encontramos o nome procurado.
Com isso podemos notar que a análise de tempo de um algoritmo é geralmente
dividida em três cenários, onde nós temos o melhor caso de comportamento do
algoritmo, o pior caso de comportamento do algoritmo e também podemos fazer
uma média de caso obtendo um caso médio destas análises. Todas estas situações
dependem da forma do problema e como está disposta a entrada dos dados para
serem tratados, nos fornecendo assim o Melhor Caso, o Pior Caso e o Caso Médio.
• Melhor Caso: é a melhor situação possível para a execução do algoritmo. Onde o
algoritmo realiza o menor número possível de operações.
• Pior Caso: é a pior situação possível para a execução do algoritmo. Onde o
algoritmo realiza o maior número de operações possíveis. Este é o cenário mais
comum na análise de algoritmos, pois fornece uma garantia de desempenho no
pior cenário.
• Caso Médio: como o nome sugere, é a análise para o desempenho médio do
algoritmo, calculando a média do tempo de execução esperado em várias
entradas diferentes. Esta análise pode ser difícil de realizar, pois depende da
distribuição das entradas, mas um resultado fácil, rápido e eficiente pode ser
obtido realizando a média do tempo obtidos entre o Melhor Caso e o Pior Caso.
 37
Para exemplificar melhor este processo, como já vimos anteriormente, no algoritmo
de busca sequencial (aquele para encontrar um nome entre um conjunto de nomes),
o melhor caso ocorre quando o nome procurado é o primeiro da lista, enquanto o pior
caso ocorre quando o nome não está presente ou está no final da lista.
Já em um algoritmo de busca binária, onde os elementos do conjunto devem
estar ordenados para este algoritmo funcionar corretamente, o tempo de execução é
logarítmico no pior caso, pois o número de elementos a serem verificados é reduzido
pela metade a cada iteração.

FIQUE ATENTO
A análise de caso na medida de tempo de algoritmos está relacionada com o tipo do
problema e com a forma como a entrada do problema é apresentada, ou seja, se está
ordenada ou desordenada, por exemplo.

BUSQUE POR MAIS

Pesquise sobre as notações assintóticas mais avançadas, como Θ (Theta) e Ω (Ômega),
que oferecem uma análise mais precisa do comportamento dos algoritmos em diferentes
cenários de entrada.

LINK 01. Disponível em: [Link] Acesso em: 16 jan. 2025.

LINK 02. Disponível em: [Link] Acesso em: 16 jan. 2025.

LINK 03. Disponível em: [Link] Acesso em: 16 jan. 2025.

 38
VAMOS PENSAR?
Considere o problema de ordenação. Se você usar o algoritmo quicksort em um vetor de
números já ordenados, como ele se comportaria em termos de complexidade de tempo?
Isso pode ser importante ao escolher o algoritmo certo dependendo das características
do seu conjunto de dados. Dependendo do tamanho ou da forma como a entrada está
apresentada, a escolha do algoritmo pode mudar.

4. TÉCNICAS DE ANÁLISE DE ALGORITMOS

Para analisar os algoritmos ou classes de problemas, podemos utilizar várias

técnicas distintas de análise de desempenho de algoritmos. Cada uma destas técnicas
fornece informações e formas diferentes sobre o comportamento de um algoritmo
em termos de tempo de execução e uso de recursos (processamento e memória)
(Szwarcfiter, 2015).
As principais técnicas para análise de desempenho de algoritmos são Análise
de Caso, Análise Recursiva ou análise de recorrência, análise amortizada, análise
probabilística e análise experimental. A seguir veremos sobre cada uma delas.
A análise de caso, como já vimos anteriormente nesta mesma unidade, é uma
abordagem comum que foca em avaliar o desempenho de um algoritmo em diferentes
situações de acordo com o tamanho e a forma da entrada de dados para tratamento.
As três opções de casos mais comuns desta análise são:
• Melhor caso: descreve o cenário em que o algoritmo executa o menor número
possível de operações. Geralmente, esse cenário não é o mais útil para uma análise
rigorosa, pois o melhor caso pode ocorrer raramente na prática. Um exemplo de
melhor caso seria uma busca em um array onde o elemento desejado está na
primeira posição. Nesse caso, a busca linear seria concluída em apenas uma
operação, ou O(1).
• Caso médio: é a análise mais representativa, pois tenta modelar o comportamento
típico do algoritmo para entradas aleatórias ou distribuídas uniformemente. O
cálculo do caso médio requer um entendimento profundo da distribuição de
entradas possíveis, mas podemos obter resultados satisfatórios obtendo a média
aritmética simples entre o Melhor Caso e o Pior Caso. Um exemplo clássico é o
algoritmo Quicksort, onde o tempo médio de execução é O(n log n), considerando
uma distribuição uniforme dos pivôs durante a ordenação.
• Pior caso: esta análise avalia o desempenho do algoritmo no cenário mais
desfavorável, o que garante que o tempo de execução não ultrapassará um certo
limite, mesmo nas piores situações. É a medida mais usada, pois oferece uma
garantia de desempenho. Um exemplo de pior caso ocorre na busca binária, onde
o elemento procurado pode estar no final da pesquisa, resultando em O(log n)
operações. Já no caso do Quicksort, o pior caso ocorre quando o pivô escolhido é
sempre o maior ou o menor elemento do array, resultando em O(n²).

A técnica de análise de algoritmos por recorrência é utilizada para analisar

 39
problemas ou algoritmos de natureza recursivos. Este tipo de problema ou algoritmo
tem o seu tempo de execução dependente do tempo de execução de subproblemas
menores e que estão na pilha das chamadas recursivas do problema. As equações de
recorrência descrevem a relação entre o tempo de execução do problema original e
seus subproblemas (Ziviani, 2012).
Exemplos clássicos de recorrência podem ser citados dos algoritmos de Ordenação
e da Pesquisa. Também podemos encontrar estes algoritmos para resolução de alguns
problemas de natureza recursiva, como é o caso do cálculo o Fatorial de um número ou
da sequência Fibonacci (apesar de não recomendado para esta última).
Para resolver equações de recorrência, técnicas como o método da substituição,
o método da árvore de recorrência e o método mestre são amplamente utilizadas.

BUSQUE POR MAIS

Para conhecer um pouco mais sobre os métodos de resolução de
equações de recorrência, amplie seus conhecimentos pesquisando
resoluções no YouTube. O vídeo a seguir mostra como usar indução
para provar a classe de custo de uma equação de recorrência. Mostra
também como usar troca de variáveis para resolver equações. Disponível
em: [Link] Acesso em: 16 jan. 2024.

A análise probabilística é usada quando os dados de entrada de um algoritmo

podem ser modelados probabilisticamente ou quando o comportamento do algoritmo
depende de eventos aleatórios. Nessa técnica de análise, o tempo de execução é
tomado como uma variável aleatória, e o objetivo é calcular o tempo esperado de
execução ou o desempenho médio. Note que, como estamos tratando de informações
probabilísticas, as tomadas de decisão são sempre em função das escolhas e não se
pode afirmar com exatidão os resultados que serão encontrados.
Algoritmos probabilísticos, como o algoritmo de hashing (também conhecido
com tabelas hash) ou o Quicksort (algoritmo de ordenação) com pivôs aleatórios, são
exemplos clássicos. No caso do Quicksort, o pivô pode ser escolhido aleatoriamente,
o que torna a análise do caso médio mais complexa, mas garante que, em média, o
tempo de execução seja O(n log n).
A mesma situação ocorre na aplicação dos algoritmos de hashing, onde a
escolha aleatória de funções de hash impacta a distribuição de elementos nos campos
de valores do hash. A análise probabilística ajuda a desejar que, em média, a inserção,
busca e remoção de elementos no hash ocorram em tempo O(1).
A análise experimental, também conhecida como benchmarking, consiste em
executar o algoritmo em diferentes entradas e situações, e medir seu desempenho
real de execução em um ambiente controlado. Embora a análise teórica (modelos
matemáticos apresentados anteriormente) forneça uma boa estimativa de como
um algoritmo deve se comportar, a análise experimental fornece dados reais sobre o
desempenho em um ambiente específico de hardware e software.
Portanto, esta análise pode ser muito útil para algoritmos complexos ou aqueles
cujo desempenho depende de muitos fatores externos, como cache, arquitetura do
processador, memória ou otimizações do compilador. Esta é uma análise prática,
 40
determinada em tempo real de execução dos algoritmos e permite medir o tempo de
execução real, o uso de memória, o consumo de processamento, o comportamento
de cache, paralelismo e outros elementos que possam impactar no desempenho da
máquina e na execução do algoritmo.
No entanto, a análise experimental tem suas limitações, já que os resultados
dependem fortemente do ambiente de execução, e esses resultados podem não ser
facilmente controlados para outros sistemas ou dispositivos. A situação atual do sistema
ou do uso de hardware pode variar a cada momento e isso pode impactar ou interferir
nos resultados obtidos nesta análise.
Essa abordagem é frequentemente usada em conjunto com a análise teórica para
verificar se o desempenho observado está de acordo com as previsões teóricas. Além
disso, os experimentos permitem identificar gargalos e oportunidades de otimização no
código que podem não ser evidentes durante a análise teórica.

FIQUE ATENTO
A análise de tempo de execução de um algoritmo depende fortemente do tipo de entrada
e do tamanho da entrada. Portanto, sempre defina claramente o modelo de entrada ao
fazer qualquer análise de complexidade.
 41
FIXANDO O CONTEÚDO
1. (ENADE 2017) Considere a função recursiva F a seguir, que em sua execução chama a
função G:

Com base nos conceitos de teoria da complexidade, avalie as afirmações a seguir.

I - A equação de recorrência que define a complexidade da função F é chamada de

recorrência funcional por que está na função F.
II - O número de chamadas recursivas da função F é O(log n).
III - O número de vezes que a função G da linha 4 é chamada é O(n log n).

É correto o que se afirma em:

A) I, apenas.
B) II e III, apenas.
C) I e III, apenas.
D) II, apenas.
E) I, II e III.

2. (Ano: 2015 - Banca: CETRO - Prova: CETRO - AMAZUL - Engenheiro Mecatrônico

– 2015) A análise de algoritmos é uma disciplina da computação e engenharia, pois
procura prever o comportamento de um algoritmo antes que ele seja efetivamente
implementado e colocado “em produção”. A corretude é um dos aspectos importantes
na análise de um algoritmo, sobre a qual é correto afirmar que:

A) mede o desempenho de um algoritmo de acordo com determinado critério.

B) é influenciada pelo tamanho e configuração da entrada.
C) as análises são realizadas levando-se em consideração o pior caso, o caso médio e
o melhor caso.
D) o algoritmo deve fornecer uma resposta correta para qualquer entrada.
E) analisa vários laços de uma vez só.

3. Considere as seguintes complexidades de algoritmos: O(1), O(n), O(log n), O(n log n)
e O(n²)
Qual das alternativas a seguir melhor descreve o comportamento de um algoritmo com
complexidade O(log n)?
 42
A) O tempo de execução é constante, independentemente do tamanho da entrada.
B) O tempo de execução cresce proporcionalmente ao tamanho da entrada.
C) O tempo de execução cresce lentamente à medida que o tamanho da entrada
aumenta, dividindo o problema ao meio a cada etapa.
D) O tempo de execução é linear, mas com uma componente logarítmica, combinando
dois tipos de crescimento.
E) O tempo de execução cresce de maneira quadrática conforme o tamanho da entrada
aumenta.

4. Um algoritmo percorre todos os elementos de uma lista de tamanho n uma única vez,
e para cada elemento realiza uma operação de busca binária em um array ordenado
de tamanho n. Qual das alternativas a seguir representa corretamente a complexidade
desse algoritmo?

A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)
E) O(n²)

5. (Concurso: Tribunal de Contas da União (TCU) Banca: Cespe/UnB Ano: 2015) Assinale
a alternativa que corresponde a um algoritmo de ordenação com complexidade O(n
log n):

A) Bubble Sort.
B) Quick Sort.
C) Insertion Sort.
D) Selection Sort.
E) Counting Sort.

6. A análise de desempenho de algoritmos pode ser realizada de diversas formas,

considerando diferentes técnicas para medir o tempo de execução e o uso de recursos.
Dentre as técnicas de análise mencionadas, qual das opções abaixo melhor descreve
a análise de pior caso?

A) O desempenho médio do algoritmo em situações comuns e entradas aleatórias.

B) A quantidade mínima de operações que o algoritmo realizará, independentemente
das entradas.
C) O comportamento do algoritmo em cenários menos favoráveis, garantindo que o
tempo de execução não ultrapassará certo limite.
D) A execução prática de um algoritmo em um ambiente controlado para medir seu
desempenho real.
E) A análise de problemas que envolvem chamadas recursivas e o tempo de execução
de subproblemas menores.

7. Considerando as técnicas de análise de desempenho de algoritmos apresentadas,

qual das seguintes afirmações sobre a análise de caso é correta?
 43
A) O melhor caso descreve o comportamento do algoritmo nas situações mais
desfavoráveis e com as entradas mais complexas.
B) A análise do caso médio geralmente envolve a média entre o melhor caso e o pior
caso, fornecendo uma estimativa do desempenho em cenários típicos.
C) A análise de pior caso foca em medir o número máximo de operações,
independentemente da entrada de dados.
D) O caso médio é uma abordagem teórica que analisa o desempenho do algoritmo
em condições ideais de execução.
E) A análise do pior caso é a menos utilizada, pois pode resultar em estimativas de
tempo muito conservadoras.

8. Em relação às técnicas de análise de algoritmos, qual das alternativas abaixo melhor

descreve a análise experimental?

A) A análise experimental usa modelos matemáticos para prever o comportamento de

algoritmos em diferentes cenários.
B) A análise experimental permite medir o desempenho real do algoritmo em diferentes
ambientes de execução, como tempo de execução e uso de memória.
C) A análise experimental é baseada na resolução de equações de recorrência para
entender o tempo de execução de subproblemas.
D) A análise experimental se foca apenas em determinar o melhor e pior caso para
diferentes entradas de dados.
E) A análise experimental ignora a execução prática e depende apenas de simulações
teóricas para medir o desempenho.
 44

ESTRUTURAS DE DADOS ESTÁTICAS E

DINÂMICAS NA MEMÓRIA PRINCIPAL
 45
Seria muito difícil pensar em desenvolvimento de software, algoritmos e programas
eficientes sem utilizar os conceitos fundamentais das estruturas de dados.
As estruturas de dados são definições de algoritmos com características
específicas e um conjunto de regras para uma determinada aplicação em projetos
de software. Existem vários tipos de estruturas de dados diferentes e estes são obtidos
relacionando o conceito de funcionalidade com as estruturas de tipos abstratos de
dados. (Ziviani, 2012).
Tais estruturas são muito importantes no desenvolvimento de algoritmos e
programas funcionais, pois são proporcionam melhor organização e armazenamento
de dados na memória de forma que facilitem o acesso e manipulação destes dados. As
estruturas de dados podem ser classificadas como estáticas ou dinâmicas, dependendo
de como a memória é alocada para elas.
Nas estruturas de dados estáticas a memória é alocada de forma fixa durante o
tempo de execução, ou seja, o espaço de memória reservado para essa estrutura não
muda durante a execução do programa. Estas memórias são definidas em forma de
variáveis simples ou do tipo array dentro dos programas e não podem sofrer alteração
em tamanho ou quantidade na execução do mesmo.
Nas estruturas de dados dinâmicas, ou contrário das estruturas estáticas, a
memória é alocada dinamicamente de acordo com a necessidade de uso e liberada
conforme necessário durante a execução do programa, permitindo maior flexibilidade
no gerenciamento desta memória. Estas memórias são definidas inicialmente como
um ponteiro ou estruturas de dados auto referenciadas, e no decorrer da utilização
da programação podem ser alocadas mais unidades de memória para a aplicação
ou podem ser liberadas algumas unidades de memórias, permitindo o tamanho de
sua utilização crescer ou diminuir dinamicamente de acordo com sua utilização ou
necessidade.

1. ESTRUTURAS DE DADOS LISTAS LINEARES

Uma lista linear é uma estrutura de dados para armazenamento de elementos em

uma sequência estática ou dinâmica, dependendo do tipo de alocação de memória que
é definido para esta lista. A lista é uma estrutura que, como o nome sugere, armazena
os elementos listados um após o outro, se comportando como uma sequência de
elementos (Ziviani, 2012).
As listas podem ser estáticas, com tamanho definidos no momento de sua
criação e não podem sofre alteração de tamanho no decorrer do uso do programa, ou
dinâmicas, declaradas para utilização com alocação dinâmica de memória, podemos
crescer ou diminuir de tamanho de acordo com a necessidade em tempo real de
utilização do programa (Cormem, 2013).

1.1. Listas Lineares Estáticas

As listas lineares estáticas são implementadas usando arrays (vetores), onde a

memória é alocada em tempo de projeto, ou seja, fixa no código do programa, com
um tamanho predefinido inicialmente. Essas listas são muito úteis quando o tamanho
da estrutura de dados é conhecido previamente e temos a certeza que não irá mudar
 46
durante a execução do programa.
Para este tipo de implementação podemos listar algumas vantagens e algumas
desvantagens em sua utilização. Mas o mais importante a observar é a questão de que
a lista estática não poderá sofre alteração de tamanho em tempo real de execução do
programa.

Vantagens na utilização das listas estáticas

• Acesso direto aos itens: como a lista estática é implementada por Array do tipo
Vetor, o acesso a qualquer elemento da lista é feito em tempo constante, O(1), pois
os elementos estão armazenados de forma contígua na memória, ou seja, estes
elemento estão alocados um após o outro e são referenciados por um índice do
vetor.
• Facilidade de implementação: arrays são simples e fáceis de implementar e
utilizar em diversas linguagens de programação. Estas estruturas são facilmente
definidas e por sua característica de acesso aos elementos por um índice, torna
a inserção e acesso aos itens mais fácil.

Desvantagens na utilização das listas estáticas

• Tamanho da lista fixo: um dos maiores problemas das listas estáticas é que
seu tamanho é definido no momento da declaração. Se o tamanho for definido
de forma errada, a lista não poderá armazenar todos os dados necessários ou
armazenará muito mais memória do que o necessário, ou seja, poderá faltar ou
sobre posições de memória para os elementos.
• Inserções e remoções custosas: inserir ou remover elementos no meio da lista
exige a movimentação de vários elementos para reorganizar as suas posições
dentro da estrutura, resultando em tempo O(n).

VAMOS PENSAR?
Vimos que a Inserção ou Remoção de um elemento no meio (ou em outras posições
internas) da lista estática pode ser muito custoso do ponto de vista computacional. Isso
acontece por que ao remover um elemento em uma posição interna da lista, para não
deixar aquela posição de memória vazia, temos que deslocar todos os elementos na
sequência. O mesmo acontece para inserir um elemento no meio da lista, teremos que
deslocar todos os elementos na sequência para abrir espaço para o novo inserido. Agora
pense na situação de ter uma lista com uma grande quantidade de elementos, o custo
computacional para deslocamento destes elementos pode ser muito alto.

A Figura 1 apresenta um exemplo de uma estrutura para uma lista linear estática,
utilizando Array do tipo vetor e identificação para todos os elementos da lista. Esta Figura
apresenta um exemplo para uma lista de Tamanho 8 (muito pequena, mas ideal para o
nosso exemplo), que contém apenas 4 itens inseridos na mesma.
Note que ainda temos mais 4 posições desta lista que estão sem utilização, mas
que já foram declaradas inicialmente, ou seja, é uma memória (um recurso) que está
 47
alocado para a estrutura e que não está em uso no momento.
Veja também que cada posição do Array é definida por um índice, que no nosso
exemplo pensando na linguagem C, inicia com o índice 0 (zero). Para ter acesso a algum
item da lista, basta utilizar o nome da lista seguido do seu índice correspondente.

Figura 1: Exemplo de Lista Linear Estática

Fonte: Elaborado pelo autor (2024).

A seguir, na Figura 2, veremos um exemplo de código para a lista linear estática.

Proposto no livro Projeto de Algoritmos com Implementação e C e Pascal (Ziviani, 2005),
este algoritmo é uma demonstração simples e eficiente do uso de recursos e estruturas
de dados para a utilização de lista linear estática.

Figura 2: Algoritmo Estrutura de Dados Lista Estática

Fonte: Ziviani (2005)

Veja no algoritmo de Estrutura de Dados Lista Estática apresentado na Figura 2

que temos um Tipo Abstrato de Dados (TAD) TipoLista, que é a definição principal da
nossa lista estática. O Tipolista contém três elementos, Item, Primeiro e Último.
O item é do tipo abstrato de dados TipoItem e contém todas as informações
da nossa lista. Se a minha lista for de alunos em uma disciplina, no TipoItem devo
implementar todos os tipos de dados para as informações destes alunos, por exemplo.
O primeiro e o último são do tipo int, que por sua vez representa a forma como os
itens da lista serão acessados, que no caso do nosso modelo é um tipo primitivo int, pois
se trata de índice simples para o array do tipo vetor.
 48
BUSQUE POR MAIS
No site oficial do Livro Projeto de Algoritmos com Implementação e C e
Pascal (Ziviani, 2005), podemos encontrar diversas informações sobre
as estruturas de dados, inclusive sobre Lista Estáticas e Dinâmicas. Entre
no link e veja, no capítulo 3, uma proposta de algoritmo completo para a
utilização das Estruturas de Dados apresentadas. Disponível em: https://
[Link]/bsdB. Acesso em: 16 jan. 2025.

1.2. Listas Lineares Dinâmicas

As listas lineares dinâmicas são implementadas utilizando ponteiros ou estruturas

auto referenciadas. Este tipo de declaração não requer a definição do tamanho no
ato da escrita do código e pode sofre alteração de criação ou remoção de elementos
(posições de memória) com o programa sendo executado, em tempo real de operação.
O uso de ponteiros, como na linguagem C, permite a locação dinâmica de
memória e gera mais flexibilidade para o uso das estruturas de dados dinâmicas. Através
das funcionalidades para alocar e liberar espaço de memória é possível, facilmente,
abrir (alocar memória para uso) novos espaços ou deletar (liberar memória alocada)
espaços de memória alocados.
Assim como nas listas estáticas, as listas dinâmicas também apresentam
algumas vantagens e desvantagens para sua escolha de utilização.
As principais vantagens no uso das listas dinâmicas são o tamanho flexível e a
facilidade de inserção e remoção. O tamanho da lista pode crescer ou diminuir facilmente
conforme necessário durante a execução do programa, sem desperdício de memória.
Também, inserir ou remover elementos da lista pode ser feito em tempo constante
de O(1) (desde que o local de inserção ou remoção já seja conhecido previamente),
pois o acesso e deslocamento de elemento está associado a tratativas de ligação e
desconexão de ponteiro ou estruturas auto referenciadas.
Com isso temos uma outra vantagem no uso deste tipo estrutura que é a
otimização de recursos, neste caso, memória. Uma vez que estamos alocando memória
dinamicamente não corremos o risco de mais ou menos espaço que o necessário.
Mantendo sempre o tamanho real utilizado para a estrutura.
Como já citado anteriormente, a vantagem para remoção ou inserção de
elementos na lista é um dos principais motivadores para sua utilização, uma vez que
estamos tratando com ponteiro basta refazer a estrutura de apontamentos dos mesmo
para eliminar o elemento deletado ou para alocar espaço em memória para novas
inserções.
A desvantagem do uso de estruturas dinâmicas é que sua implementação e
gestão de uso são um pouco mais complexas que da estrutura estática e o acesso aos
elementos devem seguir a forma de funcionamento da alocação de ponteiros, no caso
da linguagem C, ou seja, não podemos mais fazer acesso direto a um elemento através
de um índice, uma vez que tempos que percorrer o ponteiro em busca deste elemento.
Um exemplo comum de implementação de uma lista linear dinâmica é a lista
encadeada. Uma estrutura de lista encadeada consiste em uma sequência de nós,
onde cada nó contém um elemento de dados e um ponteiro para o próximo nó da
 49
sequência. Existem vários tipos de aplicações para as listas encadeadas, tais como:
a) Lista simplesmente encadeada, onde cada elemento aponta para o próximo
elemento na sequência.
b) Lista duplamente encadeada, onde cada elemento possui dois apontadores,
uma para o próximo elemento e outro para o elemento anterior a ele, podendo se
deslocar tanto para um lado como para outro.
c) Lista circular, possui a mesma ideia da lista duplamente encadeada com um
diferencial de que o primeiro elemento também aponta para o último e o último
também aponta para o primeiro, formando assim um círculo, onde podemos
percorrer todos os elementos de forma sequencial no mesmo sentido.

A Figura 3 apresenta um exemplo de uma estrutura para uma lista linear dinâmica,
utilizando o conceito de ponteiros, baseado na linguagem C e identificação para todos
os elementos da lista. Esta Figura apresenta um exemplo para uma lista dinâmica com
4 (quatro) elementos (muito pequena, mas ideal para o nosso exemplo).
Note que a utilização de memória para esta lista foi otimizada, uma vez que temos
alocação de memória para somente os itens necessários para a lista. Neste modelo,
somente a estrutura principal da lista é declara, e com o poder do uso de ponteiros
é possível alocar dinamicamente novos elementos na memória para a utilização de
novos itens para a lista.
Veja também que temos um apontamento para o primeiro elemento da lista e
para o último na estrutura principal e cada item tem um ponteiro para o próximo item.
Nesta estrutura, para acessar os elementos da lista é preciso iniciar no primeiro e seguir
a estrutura sempre passando para o próximo para ter acesso aos demais itens da lista.
Uma vez com o apontamento ao elemento desejado todas as operações são realizadas
com movimentação dos ponteiros correspondentes.

Figura 3: Exemplo de Lista Dinâmica

Fonte: Elaborado pelo autor (2024).

A seguir, na Figura 4, veremos um exemplo de código para a lista dinâmica.

Proposto no livro Projeto de Algoritmos com Implementação e C e Pascal (Ziviani, 2005),
este algoritmo é uma demonstração simples e eficiente do uso de recursos e estruturas
de dados para a utilização da lista dinâmica.
 50

Figura 4: Algoritmos Estrutura de Dados Lista Dinâmica

Fonte: Ziviani (2005)

Veja no algoritmo da Figura 4 que temos uma proposta para uma Estrutura de
Dados Lista Dinâmica, neste algoritmo temos um Tipo Abstrato de Dados (TAD) TipoLista,
que é a definição principal da nossa lista dinâmica. O Tipolista contém dois elementos,
Primeiro e Último.
O Primeiro e o Último são do tipo abstrato de dados TipoApontador, que por
sua vez é um tipo abstrato de dados que representa um ponteiro para o TipoCelula,
que é a estrutura principal de armazenamento da nossa lista (é quem irá guardar as
informações dos elementos da lista). Portanto os itens Primeiro e Ultimo são utilizados
na lista dinâmica para fazer apontamento para o primeiro elemento da lista e para o
último elemento da lista, respectivamente.
A célula da lista é composta por um item e por um apontador para o próximo
elemento da lista, ou seja, para a próxima célula. O Item é um tipo abstrato de dados
TipoItem, que deve conter todas as informações do item armazenado na lista. Por
exemplo, se estivermos tratando de uma lista de alunos de uma escola, onde desejamos
armazenar o número de matrícula, o nome, o curso matriculado e o telefone do aluno,
todas estas informações devem estar no tipo abstrato de dados TipoItem, conforme
ilustrado na Figura 5.

Figura 5: Exemplo de Código para o TipoItem da Lista Dinâmica

Fonte: Elaborado pelo autor (2024)

O Prox dentro da estrutura TipoCelula, como dito, é o responsável por fazer

a ligação entre uma célula da lista e a seguinte, como ilustrado na Figura 3, com o
nome de ‘próximo’. Veja nesta figura que está operação é representada por uma seta
ligando uma célula da lista a outra. E na prática é exatamente isso que acontece, o
 51
TipoApontador é um ponteiro para uma célula e permite que possamos manter o
controle destas ligações.

FIQUE ATENTO
Citamos que o uso de memória é um ponto forte nas listas dinâmicas, mas fique atento,
pois a lista dinâmica é mais eficiente na gestão da memória de alocação, mas cada
alocação de memória custa mais que na lista estática pelo fato de usar mais itens em
sua estrutura.

2. ESTRUTURAS DE DADOS FILA

Uma fila é uma estrutura de dados linear, semelhante às listas e com as mesmas
características de definição e implementação, onde os elementos são inseridos em
uma extremidade, chamada final da fila, e removidos na outra extremidade, chamada
início da fila, ou também podemos tratar como Frente e Trás.
Essa estrutura segue o princípio de definições FIFO (First In, First Out – primeiro
a entrar, primeiro a sair), ou seja, o primeiro que chega é o primeiro que saí. Podemos
fazer uma analogia a uma fila real, pense em uma fila de banco ou no caixa do super-
mercado, o conceito aqui é o mesmo, temos uma lista (que neste caso chamamos de
fila) onde o primeiro que chega nesta lista será o primeiro a ser atendido.
Ainda no exemplo do banco ou supermercado, também podemos pensar em es-
pecificações para cada tratativa, como temos no mundo real, as filas prioritárias ou os
clientes com prioridade. Para esta tratativa temos as filas com prioridades, que é uma
teoria dos projetos de algoritmos para tratar estas questões específicas.

2.1. Filas Estáticas

As filas estáticas são implementadas como arrays, do tipo vetor unidimensional,

da mesma forma que vimos sobre as listas. Assim como nas listas estáticas, o tamanho
da fila é fixo, e a memória é alocada em código, em tempo de projeto, não podendo
sofrer alterações futuras (a não ser que modifique o código e recompile todo o projeto).
A Figura 6 apresenta um exemplo de uma estrutura para uma fila estática, uti-
lizando Array do tipo vetor e identificação para todos os elementos da fila. Esta figura
apresenta um exemplo para uma fila de Tamanho 8 (muito pequena, mas ideal para o
nosso exemplo), que contém apenas 4 itens inseridos na mesma.
Note que ainda temos mais 4 posições desta fila que estão sem utilização, mas
que já foram declaradas inicialmente, ou seja, é uma memória (um recurso) que está
alocado para a estrutura e que não está em uso no momento.
Veja também que cada posição do Array é definida por um índice, que no nosso
exemplo pensando na linguagem C, inicia com o índice 0 (zero). Para ter acesso a al-
gum item da fila, basta utilizar o nome da fila seguido do seu índice correspondente.
A fila tem os indicadores de início e fim, que representam o primeiro elemento e o
último elemento respectivamente desta fila. Quando um novo elemento for inserido na
 52
fila ele deverá ser inserido no final da mesma, ou seja, após o último elemento. Quanto
um elemento for retirado da fila, deverá ser retirado a primeiro elemento e o desloca-
mento de todos os demais deverá ser realizado para reorganizar os elementos da fila,
pois o segundo para a ser o primeiro, o terceiro passa a ser o segundo e assim sucessi-
vamente até o ultimo, todos ganham uma posição.

Figura 6: Exemplo de Fila estática

Fonte: Elaborado pelo autor (2024).

Para este tipo de implementação podemos listar algumas vantagens e algumas

desvantagens em sua utilização. Mas o mais importante a observar é a questão de que
a fila estática não poderá sofre alteração de tamanho em tempo real de execução do
programa.

Vantagens na utilização das filas estáticas:

• Acesso direto aos itens: Como a fila estática é implementada por Array do tipo
Vetor, o acesso a qualquer elemento da fila é feito em tempo constante, O(1), pois
os elementos estão armazenados de forma contígua na memória, ou seja, estes
elementos estão alocados um após o outro e são referenciados por um índice do
vetor.
• Facilidade de implementação: Arrays são simples e fáceis de implementar e uti-
lizar em diversas linguagens de programação. Estas estruturas são facilmente
definidas e por sua característica de acesso aos elementos por um índice, torna
a inserção e acesso aos itens da fila mais fácil

Desvantagens na utilização das filas estáticas:

• Tamanho da fila fixo: Um dos maiores problemas das filas estáticas é que seu
tamanho é definido no momento da declaração. Se o tamanho for definido de
forma errada, a fila não poderá armazenar todos os dados necessários ou arma-
zenará muito mais memória do que o necessário, ou seja, poderá faltar ou sobrar
posições de memória para os elementos.
• Remoções custosas: Embora a inserção pode ser simples e direta, a remoção de
elementos exige a movimentação de todos os demais elementos para reorgani-
zar as suas posições dentro da estrutura, resultando em tempo O(n).

Além das variantes de filas com prioridades que já citamos anteriormente, uma
outra variante comum de fila estática é a fila circular, onde o array é tratado de forma
circular, ou seja, sempre ao atingir o final da fila passa-se para o início e a varredura
continua. Neste caso os índices de início e final são ajustados conforme os elementos
são inseridos e removidos na fila.
 53
2.2. Filas Dinâmicas

Como já vimos nas seções anteriores, as estruturas estáticas são aquelas decla-
radas em código, com tamanho fixo e utilizando Array, e as estruturas dinâmicas são
aquelas definidas com ponteiros ou com estruturas auto referencias para alocação
dinâmica de memória em tempo real de execução do programa.
Neste sentido, as Filas Dinâmicas têm as mesmas características e definições que
a sua versão estática, porém com implementação utilizando ponteiros para alocações
dinâmica de memória. Com isso, sua representação é uma estrutura de Células que
contem itens e apontadores para o próximo elemento da fila.

Vantagens na utilização das filas dinâmicas

• Tamanho flexível: a fila pode crescer e diminuir dinamicamente conforme neces-

sário, sem o risco de ficar cheia.
• Inserção e remoção eficientes: inserções no final da fila e remoções no início da
fila podem ser feitas em tempo constante, O(1).

Desvantagens na utilização das filas dinâmicas

• Maior uso de memória: apesar de ter melhor gestão da memória utilizada, cada
nó na lista encadeada requer memória extra para armazenar os ponteiros.
• Acesso sequencial: assim como nas listas encadeadas, o acesso a elementos no
meio da fila (em casos específicos com esta necessidade) é menos eficiente, pois
é necessário percorrer a fila desde o início.

Na prática, as filas dinâmicas são muito utilizadas em sistemas de gerenciamen-

to de tarefas, como filas de impressão, onde o número de tarefas pode variar e uma
ordem de processamento FIFO é importante.
A figura 7 apresenta um esboço da estrutura de uma fila dinâmica. Nesta figura
temos dois elementos principais que fazem parte da fila, um apontador para a frente da
fila, ou seja, o primeiro item que chegou nesta fila, e um apontador para a parte de trás
da fila, ou seja, o último item que chegou na fila. Cada item da fila tem um apontador
para o próximo, permitindo assim que os elementos se interliguem e que seja possível o
acesso a cada um deles.

Figura 7: Exemplo de Fila Dinâmica

Fonte: Elaborado pelo autor (2024)

Neste exemplo, para inserir um novo item na fila basta alocar uma célula que seja
apontada pelo elemento ‘próximo’ do item trás da fila e inserir o novo item nesta nova
célula. E para remover um item da fila, basta apontar o elemento ‘frente’ para o segun-
do da fila e apagar a memória do primeiro que será liberado.
 54
A seguir, na Figura 8, temos um exemplo de código para a fila dinâmica. Propos-
to no livro Projeto de Algoritmos com Implementação e C e Pascal (Ziviani, 2005), este
algoritmo é uma demonstração simples e eficiente do uso de recursos e estruturas de
dados para a utilização da fila dinâmica.

Figura 8: Algoritmos Estrutura de Dados Fila Dinâmica

Fonte: Ziviani (2005)

A estrutura principal da fila é o tipo abstrato de dados TipoFila. Nesta estrutura

temos dois apontadores, Frente e Trás, que apontam para o início e o final da fila, res-
pectivamente. TipoApontador é um ponteiro para uma célula da fila.
O TipoCelula define a célula da fila, é onde será armazenado cada item da fila. Es-
tas células contém um elemento Item, que é responsável por armazenar todas as infor-
mações do item proposto na fila, por exemplo, se for uma fila de pessoas em um banco,
no item teremos todas as informações necessárias para tratar cada pessoa desta fila.
E também um item Prox, que é um apontador para a próxima célula da fila, permitindo
a sua ligação, elemento por elemento.

3. ESTRUTURAS DE DADOS PILHA

Uma pilha, como o próprio nome sugere é uma estrutura de dados linear onde
os elementos são inseridos e acessados sumulando uma pilha de item, tendo acesso a
somente uma extremidade da estrutura.
Pense em uma pilha de pratos, cada prato está sobre o outro e o acesso,
normalmente, é somente no topo (na parte de cima da pilha). Quando for retirar um
prato dessa pilha o mesmo deverá ser removido do topo dessa pilha e o mesmo ocorre
na inserção de um novo prato, este deve ser inserido também no topo da pilha.
Note que o primeiro prato inserido na pilha ficará embaixo de todos e será o último
a ser removido, e o prato mais recentemente inserido será o primeiro a ser removido.
A este tipo de estrutura de dados damos o nome de estrutura LIFO (Last In, First Out -
último a entrar, primeiro a sair), ou seja, o último elemento que é inserido é o primeiro a
ser removido.
A pilha é uma estrutura de dados muito semelhante à lista linear, porém com
 55
esta particularidade de acesso para inserção e remoção dos elementos. Assim como
nas filas, as pilhas também têm uma definição de estrutura muito similar, sofrendo
alterações somente em algumas nomenclaturas e nas funções de inserção e remoção.
As pilhas são muito utilizadas em estruturas especializadas da computação, mas
podemos obter um exemplo simples e prático do nosso dia a dia no uso de computadores
analisando o recurso de desfazer (CTRL+Z) da maioria dos softwares. O recurso desfazer
é um exemplo claro de uso da pilha, cada ação realizada no computador é inserida na
pilha de ações e quando o desfazer é acionado a última ação é removida da pilha e sua
função é desfeita no software em questão.

3.1. Pilhas Estáticas

As pilhas estáticas, assim como nas listas e filas estáticas, são implementadas
com arrays do tipo vetor. O tamanho da pilha é fixo, e a memória é alocada diretamente
no código, em tempo de projeto, antes da compilação (ou execução). Um índice é usado
para identificar o topo da pilha, onde as inserções e remoções ocorrem, seguindo a
regra padrão para pilha.

Vantagens na utilização das pilhas estáticas:

• Simples de implementar: Pilhas estáticas, por usarem arrays do tipo vetor, são
fáceis de implementar e gerenciar.
• Acesso rápido: Inserções e remoções no topo da pilha ocorrem, diretamente, em
tempo constante O(1).

Desvantagens das pilhas estáticas:

• Tamanho fixo: Assim como outras estruturas estáticas, o tamanho da pilha

precisa ser definido antecipadamente. Se a pilha atingir seu limite, não será
possível inserir novos elementos.
• Desperdício de memória: Se o tamanho da pilha for superestimado, a memória
alocada pode ser desperdiçada.

A figura 9 ilustra a estrutura de uma pilha estática utilizando vetor. Nesta figura
temos duas visualizações diferentes da mesma estrutura, somente para ilustrar que a
forma como representamos simbolicamente as estruturas é somente para nosso visual
e entendimento, pois internamente na memória será sempre da mesma forma.
Podemos observar na figura 9 (A) uma estrutura de pilha desenhada na horizontal,
mas que possui todos os elementos necessários para a sua definição e funcionalidade.
O elemento Primeiro ou Fundo é a definição da base da pilha, onde está o seu início ou
o primeiro item inserido na mesma. Já o elemento Último ou Topo é a definição do topo
da pilha, o local de todo o seu acesso, onde iremos inserir ou remover itens.
A figura 9 (B) representa a mesma estrutura, porém desenhada de forma vertical
para simbolizar visualmente os itens que ficam um sobre os outros em uma pilha real,
mas na verdade ambas (A) e (B) são e representam a mesma estrutura.
 56

Figura 9: Exemplo de Pilha Estática

Fonte: Elaborado pelo autor (2024).

3.2. Pilhas Dinâmicas

As pilhas dinâmicas são implementadas usando listas encadeadas com ponteiros

ou estruturas uto referenciadas, e permitem a alocação dinâmica de memória, o que
significa que a pilha pode crescer e diminuir conforme necessário, sem a limitação de
um tamanho fixo.

Vantagens na utilização das pilhas dinâmicas:

• Tamanho flexível: a pilha pode crescer ou diminuir de acordo com a necessidade

do programa, sem limitação de tamanho predefinido. Isso evita desperdício
de memória e garante que o programa possa lidar com qualquer número de
elementos, desde que haja memória suficiente disponível.
• Inserção e remoção eficientes: assim como nas pilhas estáticas, a inserção e
remoção ocorrem no topo da pilha, em tempo constante, O(1), tornando essas
operações muito eficientes.
• Uso eficiente de memória: a memória é alocada conforme necessário, evitando
o desperdício de espaço, pois cada item é criado dinamicamente quando um
novo elemento é adicionado à pilha e a memória é liberada a cada elemento
removido da mesma.

Desvantagens na utilização das pilhas dinâmicas:

• Maior uso de memória por elemento: cada item em uma pilha dinâmica exige
espaço adicional para armazenar o ponteiro para o próximo item e manter a
ligação entre eles. Portanto, o consumo de memória total pode ser maior do que
em uma pilha estática.
• Complexidade de implementação: comparada com as pilhas estáticas, as pilhas
dinâmicas são um pouco mais complexas de implementar, pois é necessário
gerenciar explicitamente a alocação e liberação de memória.
 57
Conforme citado anteriormente, as Pilhas Dinâmicas são amplamente utilizadas
em situações onde o tamanho da pilha não pode ser previsto previamente, como no
recurso de desfazer de vários softwares, na avaliação de expressões matemáticas ou
na resolução de problemas com chamadas recursivas.

Figura 10: Algoritmos Estrutura de Dados Pilha Dinâmica

Fonte: Ziviani (2005)

A figura 10 apresenta um exemplo de código para a pilha dinâmica. Proposto

no livro Projeto de Algoritmos com Implementação e C e Pascal (Ziviani, 2005), este
algoritmo é uma demonstração simples e eficiente do uso de recursos e estruturas de
dados para a utilização da pilha dinâmica.
Na estrutura principal deste exemplo temos a declaração do elemento
Fundo, Topo e Tamanho. O elemento Fundo é um apontador para o item que estiver no
fundo da pilha, o elemento Topo é um apontador para o elemento que estiver no topo
da pilha e o elemento tamanho é uma variável auxiliar para servir de contador de itens
e informar de forma rápida e direta o tamanho atual da pilha.
Note que todas as demais informações contidas na estrutura deste algoritmo são
muito similares aos algoritmos já apresentados para as Listas e Filas Dinâmicas.
 58
FIXANDO O CONTEÚDO
1. (Ano: 2009. Banca: COSEAC. Órgão: Dataprev. Cargo: Analista de Tecnologia da
Informação – desenvolvimento de Sistemas) Sobre listas encadeadas dinâmicas, é
INCORRETO afirmar que:

A) os dados são armazenados dinamicamente;

B) são acessadas pelo primeiro nodo da lista;
C) o final da lista faz uma referência para null;
D) possuem tamanho fixo;
E) pilha e filas são versões limitadas de listas encadeadas.

2. (Ano: 2019. Banca: CCV-UFC. Órgão: UFC. Cargo: Técnico de Tecnologia da

Informação) Um dos exemplos de estrutura de dados é a lista encadeada dinâmica
simples. Com relação a esse tipo de lista, é correto afirmar:

A) Possui a característica de que o último elemento da lista possui um ponteiro para o

primeiro elemento da lista.
B) É necessário definir o seu tamanho no momento da sua criação, pois se trata de uma
estrutura de dados estática.
C) Quando essa estrutura é utilizada, os elementos da lista sempre estarão armazenados
sequencialmente na memória física.
D) Na inserção de um novo elemento, é necessário realizar a atualização dos ponteiros
dos elementos envolvidos, não sendo necessário realizar o deslocamento físico dos
elementos.
E) Na recuperação de qualquer elemento da lista, não é necessário percorrer os outros
elementos. Desta forma, o elemento buscado é acessado diretamente na posição onde
se encontra.

3. (Enade 2011) No desenvolvimento de um software que analisa bases de DNA,

representadas pelas letras A, C, G, T, utilizou-se as estruturas de dados: pilha e fila.
Considere que, se uma sequência representa uma pilha, o topo é o elemento mais à
esquerda; e se uma sequência representa uma fila, a sua frente é o elemento mais à
esquerda. Analise o seguinte cenário: “a sequência inicial ficou armazenada na primeira
estrutura de dados na seguinte ordem: (A,G,T,C,A,G,T,T). Cada elemento foi retirado da
primeira estrutura de dados e inserido na segunda estrutura de dados, e a sequência
ficou armazenada na seguinte ordem: (T,T,G,A,C,T,G,A). Finalmente, cada elemento foi
retirado da segunda estrutura de dados e inserido na terceira estrutura de dados e a
sequência ficou armazenada na seguinte ordem: (T,T,G,A,C,T,G,A)”.

Qual a única sequência de estruturas de dados apresentadas a seguir pode ter sido
usada no cenário descrito acima?
A) Fila - Pilha - Fila.
B) Fila - Fila - Pilha.
C) Fila - Pilha - Pilha.
D) Pilha - Fila - Pilha.
 59
E) Pilha - Pilha - Pilha.

4. (Ano: 2015 Banca: IESES Órgão: IFC-SC Prova: IESES - 2015 - IFC-SC - Informática -
Arquitetura de Computadores/Estrutura de Dados/Sistemas Operacionais) Uma lista
linear é um conjunto de informações de qualquer tipo, organizadas sequencialmente.
A organização sequencial estabelece uma relação de ordem, decorrendo daí a
possibilidade de identificar qualquer elemento da lista: o primeiro ou último ou qual
elemento precede ou sucede qualquer outro. Partindo dessa organização, as operações
básicas em listas lineares são:

A) Inserção e inclusão.
B) Busca, inserção e remoção.
C) Busca e arquivamento.
D) Inserção, remoção e arquivamento
E) Pesquisa e Ordenação

5. (Ano: 2010 Banca: Escola de Administração Fazendária – ESAF Prova: ESAF - CVM -
Analista - Área Sistemas – 2010) Uma fila é um tipo de lista linear em que:

A) as inserções são realizadas em um extremo e as remoções no outro extremo.

B) as inserções e remoções são realizadas em um mesmo extremo.
C) podem ser realizadas apenas inserções.
D) a inserção de um elemento requer a remoção de outro elemento.
E) a ordem de saída não corresponde à ordem de entrada dos elementos.

6. Em uma fila implementada de forma estática utilizando um vetor de tamanho fixo,

considere as operações enqueue (inserção de elemento) e dequeue (remoção de
elemento). Sabendo que a fila está inicialmente vazia e o vetor possui capacidade para
armazenar até 5 elementos, o diagrama a seguir representa as operações realizadas
na fila:

Operação 1: Enqueue(10)
Operação 2: Enqueue(20)
Operação 3: Enqueue(30)
Operação 4: Dequeue()
Operação 5: Enqueue(40)
Operação 6: Enqueue(50)

Com base nas operações realizadas, qual é o estado final da fila após todas as
operações?

A) [10, 20, 30, 40]

B) [20, 30, 40, 50]
C) [30, 40, 10, 20]
D) [40, 10, 20, 30]
E) [10, 20, 40, 30]
 60
7. Considere uma pilha implementada dinamicamente usando ponteiros, onde as
operações push (inserção) e pop (remoção) são realizadas. Considerando que a pilha
está inicialmente vazia, após a execução das operações abaixo, qual será a sequência
de elementos presentes na pilha?

Operação 1: Push(5)
Operação 2: Push(10)
Operação 3: Pop()
Operação 4: Push(15)
Operação 5: Pop()

A) 15.
B) 5, 10.
C) 10, 15.
D) 15, 10.
E) 5.

8. Considere as estruturas de dados pilha e fila e as seguintes afirmações sobre elas:

I – Uma pilha opera segundo o princípio FIFO (First In, First Out), ou seja, o primeiro
elemento a ser inserido é o primeiro a ser removido.
II – Uma fila é uma estrutura de dados que segue o princípio LIFO (Last In, First Out), ou
seja, o último elemento a ser inserido é o primeiro a ser removido.
III – Ambas as estruturas, pilha e fila, podem ser implementadas de forma dinâmica ou
estática.

Com base nas afirmações acima, assinale a alternativa correta:

A) Apenas I está correta.
B) Apenas III está correta.
C) I e II estão corretas.
D) II e III estão corretas.
E) I, II e III estão corretas.
 61

ALGORITMOS DE PESQUISA
E ORDENAÇÃO EM MEMÓRIA
PRINCIPAL
 62
Os algoritmos de pesquisa e ordenação são essenciais em qualquer sistema
que manipula dados, seja na memória principal (para pequenos volumes de dados)
ou em dispositivos de armazenamento externo (para grandes volumes de dados), os
algoritmos de pesquisa e ordenação são amplamente utilizados.
Pesquisa, como o nome sugere, são algoritmos para buscar informações, para
procurar algum dado ou conjunto deles. Ordenação, também com nome muito
sugestivo, são algoritmos para organizar dados, ordenar itens de acordo com algum
critério, seja ascendente ou descendentemente.
Esses algoritmos são usados para encontrar rapidamente um item em uma
coleção de dados (pesquisa) ou para organizar esses dados em uma ordem específica
(ordenação). A escolha correta do tipo de algoritmo a ser utilizada pode ter um impacto
significativo no desempenho do sistema que os utilize. Existem vários tipos de algoritmos
para pesquisa e para ordenação e iremos estudar alguns deles nesta unidade para
entender seus funcionamentos e poder escolher mais adequadamente qual aplicar em
cada situação. Exploraremos diferentes técnicas de pesquisa e ordenação, discutindo
suas características, vantagens e desvantagens, com foco em suas implementações
na memória principal.

1. INTRODUÇÃO À PESQUISA

O conceito de pesquisa em algoritmos e estruturas de dados refere-se ao processo

de encontrar um determinado elemento em uma coleção de dados. Dependendo da
estrutura de dados em uso e da natureza dos dados, diferentes algoritmos de pesquisa
podem ser aplicados. Existem alguns tipos diferentes de pesquisa e técnicas para se
encontrar ou recuperar informações, os dois tipos mais conhecidos de algoritmos de
pesquisa são a Pesquisa Sequencial e a Pesquisa Binária:

1. Pesquisa Sequencial: um método simples de busca onde cada elemento é

verificado, um de cada vez, até que o elemento desejado seja encontrado ou
todos os elementos tenham sido verificados.
2. Pesquisa Binária: um método mais eficiente que deve ser aplicado quando os
dados estão organizados de forma ordenada, dividindo repetidamente o espaço
de pesquisa pela metade.

2. PESQUISA SEQUENCIAL

A pesquisa sequencial, ou pesquisa linear, é o método mais simples e tradicional

de pesquisa conhecido. Ele consiste em percorrer cada elemento de um conjunto de
dados, um por um, até que o elemento desejado seja encontrado ou até que todos os
elementos tenham sido verificados.
Fazendo uma análise de casos na execução do algoritmo de pesquisa sequencial,
podemos observar que o melhor caso é quando o elemento pesquisado é o primeiro
verificado na lista – O(1) – e consequentemente, podemos observar que o pior caso é
 63
quando o elemento pesquisado é o último ou não está presente – O(n) – no conjunto,
necessitando percorrer todos os elementos deste conjunto para chegar neste ponto.
Neste sentido, podemos destacar alguns pontos de vantagens e desvantagens
no uso dos algoritmos de pesquisa sequencial.

Vantagens:

• Simplicidade: o algoritmo é fácil de implementar e não requer que os dados

estejam ordenados.
• Aplicabilidade geral: pode ser usado em qualquer tipo de estrutura de dados,
incluindo arrays e listas encadeadas.

Desvantagens:

• Ineficiente para grandes conjuntos de dados: o tempo de execução no pior caso

O(n) significa que, para grandes volumes de dados, a pesquisa sequencial pode
se tornar lenta.

A pesquisa sequencial é útil em cenários onde os dados são pequenos ou não

ordenados, ou quando a busca precisa ser realizada em uma lista que está mudando
constantemente e manter os dados ordenados seria caro computacionalmente.

Figura 11: Exemplo de conjunto de dados para pesquisa sequencial

Fonte: próprio autor

A figura 11 ilustra um conjunto de dados que trataremos como exemplo para

demonstração de funcionamento do algoritmo de pesquisa sequencial. Os números
0, 1, 2, 3, até 10 na parte de cima da imagem representam os índices do vetor utilizado.
As letras a, b, c, até j dentro dos quadros representam as chaves de valores para o
conjunto de dados. O fato dos itens estarem ordenados é simplesmente para facilitar
nossa análise, mas eles não precisam estar dispostos desta forma.
Deixamos o índice zero em branco para facilitar o entendimento da posição
dos itens dentro do vetor. Em uma abordagem específica dos algoritmos de pesquisa
sequencial, podemos utilizar este campo como auxiliar de pesquisa, tomando por
definição que toda pesquisa sempre retornará um sucesso, podemos iniciar o algoritmo
colocando o item a pesquisar neste campo e pesquisar o conjunto de trás para frente.
O algoritmo de pesquisa sequencial inicia pesquisando o item desejado na
primeira posição do conjunto, neste caso o item ‘a’ no índice 1. Se este for igual ao item
pesquisado, retorno as informações necessárias e finaliza o algoritmo. Se não, passa o
segundo item e repete o procedimento até encontrar o item desejado ou atingir o final
do conjunto.
 64
3. PESQUISA BINÁRIA

A pesquisa binária é um algoritmo um pouco mais eficiente que a pesquisa se-

quência pois a cada passo ela descarta praticamente metade do conjunto de dados,
mas só pode ser aplicado em dados ordenados. Esse algoritmo segue o princípio do
"dividir para conquistar", onde repetidamente divide o espaço de pesquisa pela metade
até encontrar o elemento desejado ou determinar que ele não está presente.
A ideia do funcionamento do algoritmo de pesquisa binária é, uma vez com o
conjunto todo ordenador, pesquise pelo elemento que está no meio do conjunto de
dados. Se o valor do elemento for igual ao elemento no meio do conjunto, pesquisa
realizada com sucesso. Se o valor do elemento pesquisado for menor que o elemento
do meio, a busca continua na metade inferior. Se o valor do elemento for maior que o
elemento do meio, continua na metade superior. Esse processo se repete até que o ele-
mento seja encontrado ou a lista acabe e nenhum elemento encontrado. O tempo de
execução no pior caso é O(log n), onde n é o número de elementos.

Figura 12: Exemplo de Pesquisa Binária

Fonte: próprio autor

A figura 12 apresenta um exemplo de pesquisa binária sendo realizado em um

conjunto de 10 elementos representados por letras, que é executado em 9 passos para
pesquisar pela chave ‘g’, no caso desse exemplo.
Note que o conjunto deve estar totalmente ordenado para que as técnicas da
pesquisa binária tenham efeito. No primeiro quadro da figura 12 podemos ver a repre-
sentação do conjunto de dados e a indicação de qual é a chave da pesquisa. A chave
da pesquisa é o item que desejamos encontrar, por exemplo, se uma pesquisa de clien-
tes for utilizar o cpf para encontrar um cliente, então este deverá ser a chave; se uma
pesquisa por alunos for utilizar a matrícula para encontrar um aluno, então está deverá
ser a chave.
No terceiro quadro da figura 12 está acontecendo o passo de identificação do ele-
mento central do conjunto, realizando uma operação de média matemática simples,
somando a posição do primeiro elemento com a do último elemento e dividindo por
dois, para encontrar o elemento que está no meio do conjunto, com isso foi identificado
que o elemento que está no meio do conjunto é o que está na posição 5 do conjunto/
 65
vetor.
Então, no quarto quadro da figura 12 o elemento que está na posição 5 é compa-
rado com o elemento alvo da nossa pesquisa:

(a) ‘e’ é igual a ‘g’? Neste caso não, então nada a se fazer.
(b) ‘e’ é maior que ‘g’? Também não, então nada a se fazer
(c) ‘e’ é menor que ‘g’? Sim. Então, como ‘g’ é maior, vamos descartar a metade menor
e repetir o procedimento com a metade maior para procurar por ‘g’.

Com isso, no quadro 4 a metade menor é descartada e o algoritmo continua

com a segunda metade, onde que no quadro 5 é recalculado a novo elemento do meio
usando a mesma fórmula matemática já conhecida. Neste quadro chegamos no ele-
mento ‘h’, que é maior que ‘g’, então vamos descartar a metade maior e continuar o
algoritmo com a metade menor.
Este procedimento de comparar e descartar se repete até que o elemento procu-
rado seja encontrado, resultado em uma busca com sucesso, ou que acabe o conjunto
e o elemento não seja encontrado, resultando em uma busca sem sucesso.
A seguir apresentamos algumas vantagens e desvantagens na utilização de al-
goritmos de pesquisa binária:

Vantagens:

• Muito eficiente: a pesquisa binária é extremamente rápida, especialmente para

grandes conjuntos de dados, devido à redução exponencial do espaço de busca
a cada iteração.
• Adequado para grandes volumes de dados: em dados ordenados, a pesqui-
sa binária pode encontrar um elemento com muito menos comparações que a
pesquisa sequencial.

Desvantagens:

• Necessidade de dados ordenados: a pesquisa binária só pode ser usada se os

dados estiverem previamente ordenados. Manter os dados ordenados pode ser
um desafio em algumas aplicações.
• Mais complexa de implementar: embora o conceito de dividir e conquistar seja
simples, a implementação de uma pesquisa binária exige cuidado com índices e
a recursividade.

4. ÁRVORE DE PESQUISA

Uma árvore de pesquisa é uma estrutura de dados hierárquica onde os elementos

são organizados de forma que cada nó tenha um valor maior ou menor que seus filhos,
dependendo da sua posição. Essa estrutura é amplamente utilizada em pesquisas
rápidas e eficientes, pois permite a execução de operações de busca, inserção e
remoção de forma ordenada.
A figura 13 apresenta um modelo de estruturas de dados para árvore binária. Note
 66
que esta estrutura apresenta um ‘No’ que contém o registro (Reg) e o apontadores para
subárvores esquerda (Esq) e direita (Dir).

Figura 13: Algoritmo Estrutura de Dados Árvore Binária

Fonte: Ziviani(2005)

4.1. Árvore Binária de Pesquisa sem Balanceamento

A árvore binária de pesquisa é uma árvore binária em que, para cada nó todos os
nós da subárvore à esquerda contêm valores menores que o valor do nó e todos os nós
da subárvore à direita contêm valores maiores que o valor do nó.

Figura 14: Árvore Binária de Pesquisa

Fonte: Elaborado pelo autor (2024).

A figura 14 ilustra este modelo apresentando uma árvore binária de pesquisa após
a inserção de alguns números. Note que para cada nó da árvore todos os nós internos
à esquerda são menores e todos os nós internos à direita são maiores que o nó raiz.
Chamamos estes nós de pais e filho, ou seja, no exemplo apresentado os nós 3 e 7 são
filhos do nó 5 que por sua vez é o nó pai destes dois.
Para inserir um elemento da árvore devemos percorrer a mesma em busca de
um nó vazio, onde será possível realizar a inserção do mesmo. Por exemplo, para inserir
o valor 8 na árvore apresentada, vamos comparar o valor com o nó raiz, que é 5. Como
8 é maior que 5, então caminha na subárvore da direita e com isso encontra o nó 7,
como também é maior que o nó 7, caminha na subárvore direita e encontra um nó
vazio, então o item 8 será inserido neste ponto.
Para remover um elemento da árvore o procedimento não é tão simples quando
a inserção e requer alguns cuidados a serem tomados. Se o nó a ser removido não
possui filhos ou possui no máximo um filho, a operação é simples e o nó a ser removido
será substituído pelo seu nó filho.
 67
Se o nó possuir dois filhos, este só deverá ser substituído pelo maior registro da
subárvore esquerda ou pelo menor registro da subárvore direita.
A figura 15 ilustra os passos para remoção de um nó em uma árvore binária de
pesquisa. Neste exemplo para remover o nó 5 da árvore, primeiro constatamos que o
mesmo possui dois filhos, então vamos utilizar o passo a passo descrito anteriormente
para a remoção deste nó.
Primeiro identificamos que o nó 5 pode ser substituído pelo nó 4 ou pelo nó 6, ou
seja, o maior da subárvore esquerda (4) ou o menor da subárvore direita (6). No nosso
exemplo foi escolhido o nó 4 para assumir o lugar do nó 5. Então o nó 4 passa a ocupar
o lugar do nó a ser removido e a sua estrutura é removida, como podemos ver na figura
15 (C).

Figura 15: Exemplo de Remoção do nó 5 da árvore binária

Fonte: Elaborado pelo autor (2024).

Vantagens na utilização de árvore binária de pesquisa:

• Pesquisa rápida: no melhor caso, a profundidade da árvore será logarítmica em

relação ao número de nós, resultando em um tempo de pesquisa de O(log n).
• Inserção e remoção eficientes: a inserção e remoção de elementos também
podem ser realizadas em tempo O(log n), no melhor caso.

Desvantagens na utilização de árvore binária de pesquisa:

• Desbalanceamento: uma árvore binária de pesquisa sem balanceamento

pode se tornar desbalanceada, especialmente se os dados forem inseridos em
uma ordem já ordenada. Neste caso, a árvore pode degenerar para uma lista,
resultando em uma eficiência de O(n) para pesquisa, inserção e remoção, no pior
caso.

Árvores binárias de pesquisa são muito utilizadas em sistemas onde a busca

eficiente é fundamental, como em bancos de dados ou sistemas de gerenciamento
de informações. Neste caso após construída pode ser necessário encontrar algum
elemento ou percorrer todos os elementos da árvore.
Existem três algoritmos eficientes para pesquisar em uma árvore ou para percorrer
todos os elementos da mesma. Estes algoritmos são conhecidos como algoritmos de
caminhamento em árvores e são chamados de ‘caminhamento central’, ‘caminhamento
pré ordem’ e ‘caminhamento pós ordem’. O nome do algoritmo está relacionado com a
posição em que o elemento da árvore é consultado.
Uma árvore binária de pesquisa é uma estrutura de dados naturalmente
recursiva, ou seja, para cada parte da estrutura ela pode se confundir com o todo. Com
 68
isso podemos implementar facilmente algoritmos recursivos para tratamento desta
estrutura de dados.

Figura 16: Algoritmos de Caminhamento em Árvore

Fonte: Ziviani (2005)

A figura 16 apresenta os três algoritmos para caminhamento em árvores. Note

que os algoritmos são muito parecidos e, como já dito anteriormente, o que muda é
somente a ordem de visitação dos itens da árvore.
O algoritmo Central, que apresenta a funcionalidade do caminhamento central
em árvores binárias, primeiro verifica se um nó vazio foi atingido como critério de
parada da chamada recursiva. O próximo passo é caminhar na subárvore esquerda
de forma recursiva para continuar o fluxo do algoritmo nesta subárvore. Após a retorno
desta chamada recursiva é item do nó da árvore é acessado, neste caso o algoritmo
escreve na tela o valor do item encontrado. Então o procedimento central é chamado
recursivamente novamente com a subárvore direita, para também continuar o fluxo
nesta subárvore.

Figura 17: Exemplo do caminhamento Central

Fonte: Elaborado pelo autor (2024)

A figura 17 ilustra o resultado obtido após a aplicação do caminhamento central

na árvore do nosso exemplo. Este algoritmo visita o nó raiz e chama recursivamente
a subárvore esquerda. Nesta chamada recursiva chega-se ao nó 3, que por sua vez
também tem uma chamada recursiva para a subárvore esquerda, chegando assim ao
nó 2, onde a chamada recursiva da subárvore esquerda encontra o nó 1.
No nó 1 a chamada da subárvore esquerda irá retornar pois é encontrado um
vazio (NULL) então está chamada recursiva é encerrada e o nó 1 será impresso na tela.
Na sequência é feita uma chamada recursiva para a direita do nó 1, que também retorna
com um vazio e que por sua vez retorna para o nó 2, onde este é impresso na tela.
Este procedimento de chamadas recursivas é executado até todas as chamadas
recursivas forem encerradas e todos os nós impressos na tela. Note que o caminhamento
central de uma árvore binária de pesquisa visita e usa os itens da árvore em ordem
crescente.
 69
A figura 18 apresenta o resultado do caminhamento Pré ordem e Pós ordem na
mesma árvore do nosso exemplo anterior.

Figura 18: Exemplo dos caminhamentos Pré e Pós

Fonte: Elaborado pelo autor (2024).

4.2. Árvore Binária de Pesquisa com Balanceamento

Uma árvore binária de pesquisa com balanceamento, ou simplesmente árvore

balanceada, é uma árvore binária de pesquisa que aplica técnicas de balanceamento
para garantir que a árvore permaneça com um certo equilíbrio entre a distribuição das
chaves, mantendo a complexidade logarítmica em relação ao número de nós, evitando
o desbalanceamento que pode ocorrer nas árvores binárias de pesquisa comuns.
O balanceamento de árvores está relacionado à altura das subárvores
pertencentes à mesmo, quando existem subárvores com caminhos muito compridos e
desproporcionais comparados com outros, está árvore está desbalanceada, também
conhecida como árvore degenerada.
Quando existe um equilíbrio entre a quantidade de nós nas subárvores de uma
árvore binária, está é dita estar balanceada. A Figura 19 ilustra uma comparação entre
uma árvore binária não balanceada (degenerada) e uma árvore binária balanceada
com os mesmos elementos.

Figura 19: Comparação entre Árvore Binária Degenerada e Árvore Binária Balanceada
Fonte: Neto (2024)
 70
Antes de entender sobre balanceamentos de árvores, precisamos conhecer
alguns conceitos sobre definições de árvores de pesquisa. O nó raiz é o nó principal de
uma árvore, ou seja, o primeiro. O nó folha é o último nó de uma árvore, ou seja, aquele
que não tem filhos (ou subárvores). A altura de uma árvore é o caminho mais longo
entre a raiz e todas as folhas.
Quando estamos analisando uma determinada subárvore, o nó principal desta
subárvore é dito ser o nó raiz desta subárvore, pois, neste caso, estamos analisando
somente esta parte isolada da árvore.
Existem várias técnicas de balanceamento, sendo as mais conhecidas as árvores
AVL e as árvores rubro-negras (Red-Black Tree). Uma árvore AVL é uma árvore binária
de pesquisa balanceada onde a diferença de altura entre as subárvores de qualquer nó
é no máximo 1. Quando uma inserção ou remoção de nó desbalanceia a árvore, ocorre
uma rotação para restaurar o balanceamento. A árvore rubro-negra é uma variação
da árvore binária balanceada, com a propriedade adicional de que cada nó é colorido
(marcado) de vermelho ou preto. A árvore mantém certas regras de coloração que
garantem que o caminho mais longo da raiz até qualquer folha seja no máximo o dobro
do caminho mais curto.
Neste livro trataremos em detalhes todos os conceitos da árvore binária com
balanceamento AVL.
A principal vantagem no balanceamento de árvores está relacionada ao conceito
de eficiência, pois as árvores balanceadas garantem que as operações de busca,
inserção e remoção sejam realizadas em tempo O(log n), independentemente da
ordem de inserção dos dados.
Por outro lado, a principal desvantagem no uso de árvore binária com
balanceamento é que estas são mais complexas de implementar devido às operações
adicionais necessárias para manter o balanceamento após cada inserção ou remoção.
Essas árvores são amplamente utilizadas em algoritmos que requerem garantias
de desempenho eficiente, como na implementação de estruturas de dados para bases
de dados, compiladores e sistemas de arquivos (Cormem, 1990).
Em uma árvore binária completamente balanceada os nós externos aparecem
em no máximo dois níveis diferentes, isso é importante para minimizar o tempo médio
de pesquisa pois uma distribuição mais uniforme das chaves permite que cada chave
seja igualmente provável de ser encontrada. Por outro lado, o custo computacional
para manter esta árvore completamente balanceada após cada inserção ou remoção
pode ser muito alto (Ziviani, 2012).
Para minimizar este impacto de custo em manter a árvore completamente
balanceada, algumas heurísticas foram propostas para este fim. Adelson-Velskii e
Landis propuseram em 1962 uma heurística baseada em movimentação de chaves
para o problema de balanceamento em árvore e deram o nome de AVL.
A heurística AVL consistem em manter a altura da subárvore em no máximo 1
nível de diferença, permitindo assim uma certa tolerância e minimizando o custo
computacional no balanceamento.
Uma AVL é uma árvore de pesquisa equilibrada, onde a altura de cada nó difere
em no máximo 1 nível. Para controlar esta situação na estrutura da árvore é adicionado
um campo chamado de Fator de Balanceamento (FB). O fator de balanceamento será
responsável por controlar a diferença entre a altura dos nós da direita (maiores) e dos
nós da esquerda (menores) da árvore, determinando assim a necessidade ou não de
balanceamento.
 71
O fator de balanceamento é obtido calculando a altura da subárvore direita (hD)
subtraído da altura da subárvore esquerda (hE). A figura 20 ilustra um exemplo de uma
árvore AVL com o cálculo do fator de balanceamento para cada nó. Note que o FB do nó
raiz é igual a 0 (zero) pois a altura da sua subárvore direita é igual a 3 e a altura da sua
subárvore esquerda é igual a 3, então 3-3 = 0.
Vamos analisar também os filhos do nó raiz. O nó 4 tem FB igual a -1, pois hD = 1 e
hE = 2, então 1 – 2 = -1. E o nó 6 tem FB igual a +1, pois hD = 2 e hE = 1, então 2 – 1 = +1.

Figura 20: Exemplo de uma árvore AVL

Fonte: Elaborado pelo autor (2024).

O fator de balanceamento (FB) de um nó é o indicador de balanceamento de

uma árvore AVL. Se o FB for igual a 0 (zero) o nó está totalmente balanceado. Se o FB for
igual a -1, o nó está parcialmente desbalanceado para a esquerda. Se o FB for igual a
+1, o nó está parcialmente desbalanceado para a direita. Uma heurística AVL aceita nós
parcialmente desbalanceados com FB até + ou – 1.
Se o FB de um nó for igual a +2 ou -2, este nó está desbalanceado e necessidade
de balanceamento. Para realizar o balanceamento em uma árvore AVL utiliza-se o
conceito de rotação de nós. Quando um nó está desbalanceado é feita uma espécie de
rotação entre este nó e o seu filho, trocando os dois de lugar.
Existem dois tipos de rotação para balanceamento de árvore AVL, a rotação
simples e a rotação dupla. O FB que irá determinar se a árvore está desbalanceada e
qual tipo de rotação deve ser aplicado.
Quando um nó está desbalanceado é por que seu FB é igual a 2 (positivo ou
negativo). Neste caso deve-se verificar o sinal do FB, se for positivo a árvore está
desbalanceada para a direita, e se for negativo a árvore está desbalanceada para a
esquerda. Então deve-se verificar o FB do filho que está na subárvore desbalanceada.
Se o FB do nó filho tiver o mesmo sinal que o FB do nó pai, ou seja, se os dois forem
positivos ou os dois forem negativos, aplica-se a rotação simples. Se o FB do nó filho
tiver sinal diferente do FB do nó pai, ou seja, se um for positivo e o outro for negativo,
aplica-se a rotação dupla.
A figura 21 ilustra uma situação de exemplo de rotação simples em árvore AVL.
Nesta figura temos uma árvore com as chaves 4, 8, 9, 10 e 15. Uma árvore que está
balanceada de acordo com as regras da AVL.
Ao inserir a chave 12 nesta árvore (da mesma forma que inserimos em uma árvore
binária tradicional), percebemos que a árvore ficará desbalanceada no nó 8, que terá
FB igual a 2. Verificando o FB do filho à direita, percebemos que também tem FB positivo,
 72
igual a 1. Neste caso, o procedimento é simples com rotação simples para a esquerda.
Como já vimos anteriormente, a rotação consiste em trocar o nó desbalanceado
com seu filho do lado desbalanceado, ou seja, precisamos trocar o 8 com o 10, mantendo
as mesmas características de uma árvore binária (maiores para a direita e menores
para a esquerda).
Para fazer esta rotação, podemos seguir o seguinte algoritmo: O filho deve apontar
para o pai, e o pai deverá apontar para quem o filho estava apontando. Ou seja, O nó
10 deverá apontar para o nó 8, e para isso o nó 10 deixará de apontar para o nó 9.
Consequentemente o nó 8 irá apontar para o nó 9. Veja como fica este procedimento
na figura 21, onde o nó 10 assume o lugar do nó 8 e a árvore é rearranjada com esta
rotação.

Figura 21 AVL: Rotação Simples

Fonte: Elaborado pelo autor (2024).

A figura 22 ilustra a situação de exemplo de rotação dupla em árvore AVL. Na

rotação dupla, como o nome sugere, devemos realizar a rotação simples com o filho
do nó desbalanceado e depois outra rotação simples com o nó desbalanceado. Este
passo é importante para manter a característica base da árvore binária de pesquisa,
uma vez que somente a aplicação da rotação simples não será suficiente para esta
operação.
Neste caso, temos um exemplo onde existem inseridos na árvore as chaves 2, 4, 6,
8 e 10. Ao inserir a chave 5 nesta árvore, podemos notar que o nó 8 ficará desbalanceado
com valor de FB igual a -2, ou seja, desbalanceada para a esquerda. Ao analisar o filho
da esquerda, percebemos que o mesmo (nó 4) está desbalanceado para a direita, com
FB igual a 1. Então, com o desbalanceamento e sendo o nó filho com sinal diferente do
nó pai, temos a necessidade de uma rotação dupla para balanceamento da árvore.
A rotação dupla consiste em realizar uma rotação simples no nó filho
desbalanceado e na sequência uma rotação simples no nó pai desbalanceado. Com
isso, veja na figura 22 que houve uma rotação simples envolvendo os nós 4 e 6, e
posteriormente outra rotação simples envolvendo os nós 8 e 6. Ao final das operações
a árvore está balanceada de acordo com os critérios da árvore AVL.
 73

Figura 22: AVL: Rotação Dupla

Fonte: Elaborado pelo autor (2024).

Veremos agora um exemplo mais completo e com mais detalhes do uso de uma
árvore AVL, iremos inserir os valores 30, 40, 15, 20, 10 e 5, nesta ordem, na árvore AVL. A
figura 23 ilustra este procedimento.
O primeiro valor a ser inserido será a chave 30. Como a árvore está vazia a chave
30 será inserida e terá FB igual a 0 (zero). Na sequência será inserida a chave 40. A
chave 40 é maior que a chave 30, então ela irá para a subárvore direita, e será inserida
neste ponto. O fator de balanceamento será recalculado para os nós com as chaves
envolvidas no caminho, e com isso o FB do nó com a chave 40 será igual a 0 e o FB do
nó com a chave 30 será igual a -1, como ilustrado na figura 23-A.
Na sequência a chave a ser inserida é a de valor 15. Sendo 15 menor que 30, ele vai
para a subárvore esquerda e novamente o FB dos nós é recalculado. Podemos visualizar
está situação na figura 23-B.
Nas figuras 23-C e 23-D podemos visualizar a inserção das chaves 20 e 10,
respectivamente, na árvore AVL do nosso exemplo. Após estas inserções, a figura 23-E e
23-F mostram a inserção da chave 5 e o novo cálculo do fator de balanceamento dos
nós envolvidos. Podemos perceber que com esta inserção houve o desbalanceamento
da árvore, onde notamos o FB do nó raiz 30 com valor igual a -30. Este valor nos indica
que está árvore está desbalanceada para a esquerda.
Ao analisar o FB do nó filho à esquerda do nó raiz 30, podemos notar que estes
fatores de balanceamento têm o mesmo sinal, ou seja, ambos são negativos. Com isso
chegamos à conclusão de que teremos aqui um procedimento de rotação simples.
As figuras 23-G, 23-H e 23-I ilustram a movimentação dos nós no procedimento
de rotação simples na árvore. O nó filho 15 deverá trocar de lugar com o nó pai 30, e
para isso o nó 15 deverá apontar para o no 30 e o nó 30 deverá apontar para o filho do
nó 15 e assim redesenhando a árvore.
Podemos entender sobre esta movimentação uma explicação simples e direta: o
filho aponta para o pai e o pai aponta para quem o filho apontava. Ou seja, o 15 apontou
para o 30, mas para isso ele teve que soltar o 20, então o 30 para a apontar para o 20.
 74

Figura 23: Exemplo de inserção de valores na AVL

Fonte: Elaborado pelo autor (2024).

BUSQUE POR MAIS

Veja um pouco mais sobre os conceitos e aplicação da árvore AVL nos links abaixo

A tradução do artigo “Inserção, rotação e fator de balanceamento da

árvore AVL explicados” está disponível no link seguir: [Link]
bsif. Acesso em: 16 jan. 2025.

O artigo “Árvores Balanceadas (AVL)” leva em torno de 10min de

leitura e pode conter informações importantes para o seu processo de
aprendizagem. Disponível em: [Link] Acesso em: 16 jan.
2025.

5. INTRODUÇÃO À ORDENAÇÃO

A ordenação é o processo de organizar uma sequência de dados em uma

determinada ordem, geralmente crescente ou decrescente. Ordenar dados facilita o
uso de algoritmos de pesquisa eficientes, como a pesquisa binária, além de ser um
pré-requisito para muitas outras operações de processamento de dados ou mesmo de
recuperação e apresentação das informações.
Existem vários algoritmos de ordenação com diferentes formas de funcionamento
e níveis de complexidade, desde os mais simples, como a ordenação por seleção e
 75
ordenação por inserção, até algoritmos mais avançados, como shellsort e quicksort.
Nesta unidade vamos trabalhar um pouco sobre os conceitos de ordenação e
faremos uma introdução a três destes quatro algoritmos que citamos, seleção, inserção
e quicksort.

6. ORDENAÇÃO POR SELEÇÃO

A ordenação por seleção é um algoritmo simples de ordenação que opera

selecionando repetidamente o menor (ou maior, dependendo da ordem desejada)
elemento da parte não ordenada da lista e trocando-o com o primeiro elemento da
parte não ordenada.
O algoritmo percorre o conjunto de dados (array ou lista) em busca do menor
elemento e o coloca na primeira posição. Em seguida, repete o processo para a segunda
posição, e assim por diante, até que toda a lista esteja ordenada.
No pior e no melhor caso, a complexidade de tempo é O(n²), tornando-o
inadequado para grandes conjuntos de dados. Sua principal vantagem é por causa de
sua simplicidade, sendo um algoritmo intuitivo e fácil de implementar. Por outro lado,
sua principal desvantagem é que por ser simples e com complexidade quadrática, ele
se torna ineficiente para grandes volumes de dados.
A figura 24 apresenta um algoritmo de ordenação por seleção proposto por Ziviani
(2005). Neste algoritmo é utilizada uma variável Min que recebe o índice do menor valor
do conjunto para realizar a operação de substituição do algoritmo. Note também que
o primeiro índice do conjunto, de valor 0(zero) não é utilizado para armazenamento de
dados ou poderia ser utilizado para armazenar este índice.

Figura 24: Algoritmo Ordenação por Seleção

Fonte: Ziviani (2005)

A figura 25 ilustra o funcionamento do algoritmo com uma sequência de imagens

demonstrando as trocas de valores para obter a ordenação desejada. Este exemplo
inicia com um conjunto de valores 5, 4, 2, 6, 1 e 3, nesta ordem, e tem como objetivo,
utilizando a técnica de ordenação por seleção, ordenar estes números.
 76

Figura 25: Exemplo de ordenação com Seleção

Fonte: Elaborado pelo autor (2024).

O primeiro passo do algoritmo é destacar a primeira posição do conjunto e a

partir daí selecionar o menor valor entre todos do conjunto para trocar com o primeiro,
como podemos observar na sequência das figuras 25-A até 25-H. Neste ponto o menor
valor está na primeira posição do conjunto, então passa-se para a segunda posição
e repete a operação, encontre o menor elemento entre os restantes e troque com o
elemento da segunda posição, repita esta operação até percorrer todas as posições do
conjunto, onde o mesmo estará completamente ordenado, como ilustrado nos passos
seguintes das figuras 25-I até 25-L.

7. ORDENAÇÃO POR INSERÇÃO

A ordenação por inserção é outro algoritmo simples, mas eficaz para listas
pequenas ou quase ordenadas. Podemos pensar que é o método preferido dos jogadores
de cartas, pois se assemelha muito com a forma como a maioria dos jogadores organiza
as cartas na mão ao recebe-las. Este procedimento é basicamente uma troca sucessiva
de cartas, colocando cada uma em seu devido lugar e pode ser descrito assim: Pega-
se uma carta de cada vez e a coloca na posição correta dentro da mão já ordenada,
sendo que a cada passo, as cartas da esquerda estão completamente ordenadas.
O algoritmo começa pela segunda posição e compara o valor com o primeiro. Se
o valor for menor, ele é inserido na posição correta (trocando os dois de lugar), movendo
os outros elementos para a direita. Esse processo é repetido até que todos os elementos
estejam ordenados. Ou seja, a partir do segundo elemento do conjunto, compare este
elemento com todos os anteriores a ele, sempre trocando quando for necessário.
A complexidade no pior caso é O(n²), mas no melhor caso (quando os dados já
estão quase ordenados), pode atingir O(n). A principal vantagem deste método é que
ele é simples e eficiente para pequenas listas, sendo fácil de implementar e funciona
bem quando o conjunto de dados é pequeno ou quase ordenado.
Uma outra característica é que ele é dito ser um método de ordenação estável, ou
 77
seja, ele mantém elementos com valores iguais na mesma posição inicial do conjunto.
Como desvantagem podemos citar que o algoritmo de ordenação por inserção
é ineficiente para grandes quantidades de dados, ou seja, quando tem muitos valores
para ordenar. Assim como a ordenação por seleção, a ordenação por inserção tem
uma complexidade quadrática, o que a torna impraticável para conjuntos de dados
grandes.
A figura 26 apresenta um algoritmo de ordenação por inserção proposto por
Ziviani(2005). Este algoritmo funciona com trocas sucessivas de chaves, sempre
comparando um valor com todos os seus anteriores e trocando estes valores de lugar
até que se encontre a posição correta. No final da execução todas as chaves estão em
seu devido lugar e o conjunto está completamente ordenado.

Figura 26: Algoritmo Ordenação por Inserção

Fonte: Ziviani (2005).

A figura 27 apresenta um modelo de exemplo de ordenação com o algoritmo de

Inserção.

Figura 27: Exemplo de ordenação com Inserção

Fonte: Próprio autor

Na figura 27 do nosso exemplo, temos um conjunto inicialmente preenchido com

as chaves 5, 4, 2, 6, 1 e 3, nesta ordem. O algoritmo inicia na segunda posição, neste
caso a chave 4 e compara com todas as chaves à sua esquerda, neste caso a chave
5. Como a chave 4 é menor que a chave 5, então os dois valores são trocados de lugar,
 78
como podemos ver nas figuras 27-A, 27-B e 27-C.
Na sequência, o algoritmo passa para a segunda posição ainda não ordenada,
neste caso a chave 2. A chave 2 é comparada com a anterior, chave 5, sendo menor, os
dois valores são trocados e então a chave 2 é comparada com a seguinte anteriormente,
neste caso a chave 4. Como também é menor, a chave 2 é trocada com a chave 4,
finalizando assim o segundo passo do algoritmo, como podemos verificar nas figuras
27-D e 27-E.
Estes passos são repetidos com as demais chaves até inserir a última chave na
sua posição ordenada. Veja as figuras 27-F até o final da sequência.

VAMOS PENSAR?
Vimos na unidade que o método de ordenação por inserção é estável. Esta característica
é definida pela capacidade do algoritmo de não trocar chaves iguais de posição, por
exemplo, se em um conjunto temos duas chaves de valor igual a 5, no final da ordenação
a chave que inicialmente estava antes, continuará antes da outra no conjunto. Esta
operação pode ser útil em alguns casos específicos em que a ordem de aparição inicial é
importante, como por exemplo em ordem de chegadas. Você consegue imaginar outras
situações reais de aplicação onde está funcionalidade é importante? Também pesquise
na internet sobre estas situações.

8. ORDENAÇÃO QUICKSORT

O Quicksort é um dos algoritmos de ordenação mais eficientes e amplamente

utilizados, especialmente em grandes volumes de dados. Ele segue o paradigma de
dividir e conquistar, dividindo recursivamente o conjunto em subconjuntos menores e
ordenando esses subconjuntos para depois juntar em um conjunto final completamente
ordenado.
O algoritmo de ordenação quicksort escolhe um pivô (geralmente um elemento
em posição mais centralizada no conjunto) e divide este conjunto em dois subconjuntos:
um contendo todos os elementos menores que o pivô e outro com todos os elementos
maiores que o pivô.
Em seguida, o algoritmo aplica recursivamente a mesma abordagem para os dois
subconjuntos separados anteriormente. Quando todos os subconjuntos atingem um
tamanho de 1 ou 2 elementos, o processo de ordenação é concluído e todo o conjunto
está completamente ordenado.

BUSQUE POR MAIS

Busque mais informações sobre a ordenação por quicksort e também sobre o paradigma
de desenvolvimento Dividir para Conquistar. Veja os links abaixo e também pesquise por
mais na internet:
 79

LINK 01: Ordenação Rápida - Quick Sort. Disponível em: [Link]

bs4F. Acesso em: 16 jan. 2025.

LINK 02: Visão geral do quicksort. Disponível em: [Link]

Acesso em 16 jan. 2025.

LINK 03: Estrutura de Dados e Algoritmos. Disponível em: [Link]

bs4j. Acesso em: 16 jan. 2025.

LINK 04: Algoritmo de dividir para conquistar: significado explicado e com

exemplos. Disponível em: [Link] Acesso em: 16 jan. 2025.

LINK 05: Divisão e conquista. Disponível em: [Link] Acesso

em 16: jan. 2025.

LINK 06: Mergeshort. Disponível em: [Link] Acesso em: 16

jan. 2025.
 80

Figura 28: Algoritmo Ordenação Quick Sort

Fonte: Ziviani (2005).

A figura 28 apresenta o algoritmo de ordenação quicksort proposto em

Ziviani(2005), este algoritmo envolve a chamada recursiva do procedimento ‘Ordena’
para realizar o controle dos índices e a partição do conjunto através do procedimento
auxiliar ‘Particao’.
A complexidade média do Quicksort é O(n log n), embora no pior caso (quando a
lista está já ordenada ou quase ordenada) a complexidade seja O(n²). Entretanto, com
a escolha adequada do pivô, o algoritmo pode manter a complexidade média de O(n
log n).
O algoritmo quicksort é muito rápido na prática para conjuntos de dados grandes,
geralmente superando outros algoritmos como a ordenação por inserção e seleção.

Figura 29: Exemplo de ordenação com Quick sort

Fonte: Próprio autor
 81
A figura 29 ilustra o funcionamento do método de ordenação quicksort para um
conjunto de dados. Este conjunto está inicialmente com os valores 6, 5, 9, 7, 2, 10, 4, 8, 3 e
1, nesta ordem.
Basicamente o funcionamento do quicksort consiste em escolher um pivô mediano
no conjunto e passar todos os valores menores que o pivô para a sua esquerda e todos
os valores maiores que o pivô para a sua direita. Então, o método usa um apontador de
posição esquerda e um apontador de posição direita, que percorrem o conjunto nestes
sentidos para verificar valores maiores ou menores, respectivamente e procede com a
troca destes valores.
Vamos acompanhar a sequência de imagens na figura 29 para entender este
procedimento de escolha de pivô e troca de chaves/valores. A escolha do pivô pode
seguir alguma heurística específica ou usar a técnica simples de pegar o elemento do
meio do conjunto. A nossa abordagem escolhe o elemento do meio do conjunto.
Veja na figura 29-A a demonstração do conjunto inicial e a definição do primeiro
pivô no procedimento. O pivô é obtido encontrado o elemento central do conjunto
através de média aritmética simples das posições do conjunto. Neste caso foi definido
que o elemento de valor 2 será o pivô. Com isso, o algoritmo irá percorrer da esquerda
para a direita em busca de um valor maior que o pivô, e ao mesmo tempo, irá percorrer
da direita para a esquerda em busca de um valor menor que o pivô. Quando encontrar
estes valores, troca-os de lugar.
Podemos observar na figura 29-B que no primeiro teste realizado foi encontrado à
esquerda o valor 6 que é maior que o pivô 2 e à direita o valor 1 que é menor que o pivô
2. Neste caso o item 6 é trocado com o item 1, como podemos observar na figura 29-C.
Após a troca o algoritmo continua realizando a mesma operação com os demais
elementos do conjunto até que o indicador de posição esquerdo cruze com o indicador
de posição direito, ou seja, quando o indicador esquerdo for maior que o indicador
direito. Neste momento o conjunto é particionado, e a ordenação será repetida com
cada uma destas partes.
Observe nas figuras 29-C, 29-D e 29-E que o indicador de posição esquerdo
encontra o valor 5 que é maior que o pivô 2 e o indicador de posição direito encontrar o
próprio valor 2 como menor ou igual e então realiza a troca destes valores. Os indicadores
de posição continuam percorrendo o conjunto e se cruzam entre as posições 2 e 3,
e é neste ponto que o conjunto será particionado. Então o algoritmo será reiniciado
recursivamente uma vez com a primeira metade e outra vez com a segunda metade.
As figuras 29-G até 29-L ilustram a continuidade do procedimento com o restante
do conjunto de dados. Estas mesmas operações descritas acima serão aplicadas
novamente e novamente até que cada parte dos subconjuntos tenha menos de três
elementos, momento em que todos o conjunto estará completamente ordenado.

FIQUE ATENTO
O processo de partição do algoritmo quicksort não parte fisicamente o conjunto de dados,
está partição é lógica, utilizando variáveis para indicar os limites esquerdo e direito de
cada parte dentro das chamadas recursivas do algoritmo.
 82
FIXANDO O CONTEÚDO
1. (Enade 2017) O algoritmo a seguir recebe um vetor v de números inteiros e rearranja
este vetor de tal forma que seus elementos, ao final, estejam ordenados de forma
crescente.

01 void ordena(int *v, int n)

02 {
03 int i, j, chave;
04 for(i = 1; i < n; i++)
05 {
06 chave = v[i];
07 j = i - 1;
08 while(j >= 0 && v[j] < chave)
09 {
10 v[j-1] = v[j];
11 j = j - 1;
12 }
13 v[j+1] = chave;
14 }
15 }

Considerando que neste algoritmo há erros de lógica que devem ser corrigidos para
que os elementos sejam ordenados de forma crescente, assinale a opção correta no
que se refere às correções adequadas.

A) A linha 04 deve ser corrigida da seguinte forma: for(i = 1; i < n - 1; i++)e a linha 13, do
seguinte modo: v[j - 1] = chave;.
B) A linha deve ser corrigida da seguinte forma: for(i = 1; i < n - 1; i++) e a linha 07, do
seguinte modo: j = i + 1;.
C) A linha 07 deve ser corrigida da seguinte forma: j = i + 1 e a linha 08, do seguinte
modo: while(j >= 0 && v[j] > chave).
D) A linha 08 deve ser corrigida da seguinte forma: while(j >= 0 && v[j] > chave) e a linha
10, do seguinte modo: v[j + 1] = v[j];.
E) A linha 10 deve ser corrigida da seguinte forma: v[j + 1] = v[j]; e a linha 13 do seguinte
modo v[j - 1] = chave;

2. (Enade 2011) Suponha que se queira pesquisar a chave 287 em uma árvore binária de
pesquisa com chaves entre 1 e 1000. Durante uma pesquisa como essa, uma sequência
de chaves é examinada. Cada sequência abaixo é uma suposta sequência de chaves
examinadas em uma busca da chave 287.

I – 7, 342, 199, 201, 310, 258, 287

II – 110, 132, 133, 156, 289, 288, 287
III – 252, 266, 271, 294, 295, 289, 287
IV – 715, 112, 530, 249, 406, 234, 287
 83
É válido apenas o que se apresenta em

A) I.
B) III.
C) I e II.
D) II e IV.
E) III e IV.

3. (Enade 2014) A figura a seguir apresenta uma árvore binária de pesquisa, que mantém
a seguinte propriedade fundamental: o valor associado à raiz é sempre menor do que o
valor de todos os nós da subárvore à direita e sempre maior do que o valor de todos os
nós da subárvore à esquerda.

Em relação à árvore apresentada na figura, avalie as afirmações a seguir

I – A árvore possui a vantagem de realizar a busca de elementos de forma eficiente,

como a busca binária em um vetor.
II – A árvore está desbalanceada, pois a subárvore da esquerda possui um número de
nós maior do que a subárvore da direita.
III – Quando a árvore é percorrida utilizando o método de caminhamento pós-ordem, os
valores são encontrados em ordem decrescente
IV – O número de comparações realizadas em função do número n de elementos na
árvore em uma busca binária com sucesso é O(log n).

É correto apenas o que se afirma em

A) I e III.
B) I e IV.
C) II e III.
D) I, II e IV.
E) II, III e IV.

4. (Enade 2014) Uma pilha é uma estrutura de dados que armazena uma coleção de
itens de dados relacionados e que garante o seguinte funcionamento: o último elemento
a ser inserido é o primeiro a ser removido. É comum na literatura utilizar os nomes
push e pop para as operações de inserção e remoção de um elemento em uma pilha,
respectivamente. O seguinte trecho de código em linguagem C define uma estrutura
de dados pulha utilizando um vetor de inteiros, bem como algumas funções para sua
manipulação.
 84

O programa a seguir utiliza uma pilha

A esse respeito, avalie as afirmações a seguir.

I – A complexidade computacional de ambas funções push e pop é O(1).

II – O valor exibido pelo programa seria o mesmo caso a instrução a += pop(p); fosse
trocada por a += a;
III – Em relação ao vazamento de memória (memory leak), é opcional chamar a função
free(p), pois o vetor usado pela pilha é alocado estaticamente.

É correto o que se afirma em:

A) I, apenas.
B) III, apenas.
C) I e II, apenas.
D) II e III, apenas.
E) I, II e III.

5. (Enade 2017) Uma árvore AVL é um tipo de árvore binária balanceada na qual a
diferença entre as alturas de suas subárvores da esquerda e da direita não pode ser
 85
maior do que 1 para qualquer nó. Após a inserção de um nó em uma AVL, a raiz da
subárvore de nível mais baixo no qual o novo nó foi inserido é marcada. Se a altura de
seus filhos diferir em mais de uma unidade, é realizada uma rotação simples ou uma
rotação dupla para igualar suas alturas.
A seguir, é apresentada um exemplo de árvore AVL

Pelo exposto no texto acima, após a inserção de um nó com valor 3 na árvore AVL
exemplificada, é correto afirmar que ela ficará com a seguinte configuração:

A)

B)
 86
C)

D)

E)

6. (Enade 2021) O uso da estrutura de dados tipo Árvore Binária de Busca é uma técnica
fundamental de programação. Uma árvore binária é um conjunto finito de elementos
que está vazio ou é particionado em três subconjuntos, a saber: 1) raiz da árvore -
elemento inicial (único), 2) subárvore da esquerda - se vista isoladamente compõe
outra árvore e 3) subárvore da direita - se vista isoladamente compõe outra árvore. A
árvore pode não ter qualquer elemento (árvore vazia). A definição de árvore é recursiva
e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. Sendo “A” a
raiz de uma árvore binária e “B” a raiz de sua subárvore esquerda ou direita, é dito que
“A” é pai de “B” e que “B” é filho de “A”. Um elemento sem filhos é chamado de folha. A
altura da árvore é o número de elementos encontrados no caminho descendente mais
longo que liga a sua raiz até uma folha.

Uma Árvore de Busca Binária é uma árvore binária especializada, na qual a informação
que o elemento filho esquerdo possui é numericamente menor que a informação do
elemento pai. De forma análoga, a informação que o elemento filho direito possui é
 87
numericamente maior ou igual à informação do elemento pai. O objetivo de organizar
dados em Árvores Binárias de Busca é facilitar a tarefa de encontrar um determinado
elemento. O percurso completo de uma árvore binária consiste em visitar todos os
elementos desta árvore, segundo algum critério, a fim de processá-los. Três formas são
bem conhecidas para a realização deste percurso: 1) pré-ordem, 2) em-ordem e 3)
pós-ordem. A figura a seguir mostra um exemplo de árvore binária.

Considerando o texto e a figura apresentados e que a seguinte lista de elementos

numéricos: (27, 34, 40, 18, 23, 5, 25, 36, 10, 7, -2) seja totalmente transferida para uma
estrutura de Árvore Binária de Busca, inicialmente vazia, elemento a elemento, da
esquerda para a direita, assinale a alternativa correta.

A) A árvore resultante terá 5 níveis de altura, com 6 elementos à esquerda da raiz

principal (inicial) e 4 elementos à direita.
B) O percurso da árvore em Pré-ordem irá processar os elementos na seguinte ordem
(do primeiro ao último): -2, 7, 10, 5, 25, 23, 18, 36, 40, 34, 27.
C) O percurso da árvore em Em-ordem irá processar os elementos na seguinte ordem
(do primeiro ao último): -2, 5, 7, 10, 18, 23, 25, 27, 34, 36, 40.
D) O percurso da árvore em Pós-ordem irá processar os elementos na seguinte ordem
(do primeiro ao último): 27, 18, 5, -2, 10, 7, 23, 25, 34, 40, 36.
E) O número máximo de elementos que essa árvore poderá ter com 10 níveis será de
1024 elementos.

7. (Enade 2021) Existe um grande número de implementações para algoritmos de

ordenação. Um dos fatores a serem considerados, por exemplo, é o número máximo e
médio de comparações que são necessárias para ordenar um vetor com n elementos.
Diz também que um algoritmo de ordenação é estável se ele preserva a ordem de
elementos que são iguais. Isto é, se tais elementos aparecem na sequência ordenada
na mesma ordem em que estão na sequência inicial. Analise o algoritmo abaixo, onde
A é um vetor e “i, j, lo e hi” são índices do vetor:
 88

Com relação ao algoritmo apresentado, avalie as afirmações a seguir.

I – O algoritmo precisa de um espaço adicional O(n) para a pilha de recursão.

II – O algoritmo apresentado é um algoritmo de ordenação recursivo e estável.
III – O algoritmo precisa, em média, de O(n log n) comparações para ordenar n itens.
IV – O uso do primeiro elemento do vetor como “pivot” é mais eficiente que usar o último.

É correto apenas o que se afirma em

A) I e III.
B) II e IV.
C) III e IV.
D) I, II e III.
E) I, II e IV.

8. Uma empresa possui um sistema de registro de produtos que armazena informações

sobre os itens em um vetor. Cada produto tem um código de identificação único (número
inteiro), nome e preço. O vetor de produtos está atualmente desordenado, e a empresa
deseja ordená-los de acordo com o preço, de forma crescente, para facilitar a consulta
e o planejamento de compras.

Com base nesse cenário, analise as alternativas a seguir e marque a correta:

A) O algoritmo Seleção é a melhor escolha, pois sua complexidade de tempo O(n²) é

mais eficiente para grandes listas de produtos do que o algoritmo de Inserção, que
também possui a mesma complexidade, mas é mais lento na prática devido ao maior
número de trocas realizadas.
 89
B) O algoritmo Inserção é mais adequado para ordenar grandes listas de produtos
devido à sua complexidade O(n²). Sua eficiência é maior em listas pequenas ou quase
ordenadas, mas em listas grandes ele pode ser significativamente mais lento do que
outros algoritmos, como o QuickSort.
C) O algoritmo QuickSort é uma excelente opção para ordenar listas de produtos, pois,
em média, possui uma complexidade de tempo O(n log n). Embora o pior caso seja
O(n²), isso pode ser evitado com a escolha adequada do pivô, tornando-o mais eficiente
que os algoritmos Seleção e Inserção em listas grandes.
D) O algoritmo Seleção é a escolha ideal para ordenar listas de produtos, pois sempre
possui complexidade de tempo O(n²) e é extremamente eficiente em listas de qualquer
tamanho, já que o número de comparações é fixo e não depende da ordem dos dados.
E) O algoritmo Inserção é sempre a melhor opção para qualquer tamanho de lista
de produtos, uma vez que sua complexidade de tempo O(n²) garante desempenho
constante independentemente do tamanho da lista, sendo mais eficiente que os
algoritmos Seleção e QuickSort.
 90

ACESSO AOS ARQUIVOS DE DADOS

 91
Quando lidamos com grandes volumes de dados ou quando precisamos arma-
zenar informações de forma persistente, a manipulação de arquivos torna-se essen-
cial. Arquivos permitem que os dados sejam armazenados e acessados entre diferentes
execuções de um programa, o que é fundamental para muitas aplicações, como ban-
cos de dados, editores de texto, sistemas de gerenciamento de conteúdo, entre outros.
Em linguagens de programação como C, o acesso a arquivos é realizado de maneira
simples, mas com um grande poder e flexibilidade.

1. INTRODUÇÃO AO USO DE ARQUIVOS

Ao desenvolver sistema ou aplicações que precisam de persistir dados, o uso e

acesso a arquivos de dados muito importante, usual e prático.
Arquivo são documentos guardados na memória do computador, e que fica salvo
para acesso posterior. Estes arquivos podem ser simples e abertos, como arquivo de
texto do tipo TXT por exemplo, ou específicos e fechados, como arquivos binários, com
dados de leitura exclusivas para o software que criou, podendo ser de tipos específicos
destes softwares.
Em C, trabalhar com arquivos é uma habilidade fundamental para programadores
que desenvolvem sistemas que precisam gravar ou ler dados de forma duradoura.
Como citamos anteriormente, existem dois tipos principais de arquivos com os quais
podemos trabalhar, os arquivos texto e os arquivos binários.
Os arquivos de texto são arquivos que armazenam dados em formato facilmente
legível por nós. Um exemplo clássico são os arquivos .txt, onde o conteúdo pode ser
facilmente lido e editado em qualquer editor de texto. Dados como strings de texto,
números formatados e até mesmo expressões podem ser armazenados nesse formato.
As principais vantagens no uso deste tipo de arquivo é que são fáceis de leitura
e edição, e os dados podem ser compartilhados entre diferentes sistemas de forma
simples. E as principais desvantagens deste tipo de arquivo é que pode ser mais lento
para processar grandes volumes de dados e tende a ocupar mais espaço em disco
devido à necessidade de converter números e outros tipos de dados em texto.
Os arquivos binários, ao contrário dos arquivos de texto, são arquivos que
armazenam dados de forma compacta, utilizando a representação de símbolos
codificados (dados binários) no sistema. Esses arquivos são mais rápidos para serem
lidos e gravados.
A principal vantagem no uso deste tipo de arquivo é que é mais rápido para
processar e mais eficiente em termos de espaço. E a principal desvantagem é que não
são legíveis diretamente por nós, exigindo programas especializados para manipulação.

2. FUNÇÕES DE ARQUIVOS

A linguagem C fornece um conjunto robusto de funções que permitem a

manipulação de arquivos. Estas funções são fornecidas pela biblioteca padrão da
linguagem e nos ajudam a realizar operações essenciais, como abrir, ler, escrever e
fechar arquivos.
 92
Estas operações são extremamente importes para manipulação de arquivos. Ao
se trabalhar com um arquivo, seja ele texto ou binário, a primeira ação que deve ser
realizada é a de abertura. A abertura do arquivo consiste em localizar este arquivo em
disco e estabelecer uma conexão do programa com o mesmo. Quando o arquivo não
existe em disco, deve-se utilizar da operação de abertura para criar este arquivo Schildt
(1996).
Após a abertura do arquivo, as demais operações como escrita, leitura, pesquisa
e outras, podem ser utilizadas sobre o arquivo aberto de acordo com a necessidade de
uso.
De acordo com o que já citamos anteriormente, em C, um arquivo pode ser
qualquer coisa, desde um arquivo em disco até um terminal ou uma impressora. Para
isso precisamos criar o que chamamos de strema de arquivo, que nada mais é do que
a ligação de um arquivo a uma variável do tipo FILE do sistema, realizando assim uma
operação de abertura. Uma vez o arquivo aberto, informações podem ser trocadas
entre ele e o seu programa Schildt (1996).
O objetivo da utilização de arquivo é a persistência de dados, ou seja, gravar
informações em disco para não perde-las quando o programa finalizar ou a máquina
for desligada. Para trabalhar com arquivo primeiro devemos criar este arquivo e depois
ter um apontador para este arquivo em nosso programa.
O quadro 1 apresenta algumas das principais funções para manipulação de
arquivos.

NOME FUNÇÃO

fopen() Abre um arquivo

fclose() Fecha um arquivo

fputc() Escreve um caractere em um arquivo

fgetc() Lê um caractere de um arquivo

Posiciona o cursor do arquivo em um byte específico

fseek()
dentro do mesmo
Escreve em um arquivo, funciona como o printf() para
fprintf()
o console.
Lê de um arquivo, funciona como o scanf() para o
fscanf()
console

feof() Retorna Verdadeiro se o fim do arquivo foi encontrado

ferror() Retorna Verdadeiro se ocorrer um erro

rewind() Desloca o cursor para o início do arquivo

remove() Apaga um arquivo

fflush() Libera o buffer

Quadro 1: Funções para manipulação de arquivo

Fonte: Schildt (1996)
 93
2.1. Abertura de Arquivos: fopen()

A função mais básica, e a primeira que deve ser utilizada, para trabalhar com
arquivos é fopen(), que é usada para abrir um arquivo existente ou criar um novo
arquivo, caso ele não exista. O modo de abertura do arquivo é um parâmetro essencial
e determina como o arquivo será manipulado.
Um ponteiro de arquivo é uma variável em seu programa que contém informações
sobre o arquivo que está tratando, tais como, Nome, Status e posição atual do arquivo. Um
ponteiro de arquivo deve ser um variável ponteiro do tipo FILE (sim, tudo em maiúsculo).
Para declarar um variável ponteiro do tipo FILE, use a seguinte sintaxe:

FILE *fp;

Onde FILE é o tipo de dados de arquivos, responsável por armazena o apontamento

para o arquivo e fp é o nome da variável que será utilizada como referência para o
arquivo que será aberto.
Para utilizar um arquivo, o mesmo deve ser criado e aberto na variável referência
do tipo Ponteiro de FILE. A função utilizada para abrir um arquivo é a fopen(), que retorna
um ponteiro para o arquivo aberto e tem a seguinte sintaxe:

FILE *fopen(const char* NomeArquivo, const char* ModoDeAbertura);

O modo de abertura de um arquivo é o que irá determinar como este arquivo será
criado e/ou aberto pelo sistema. Os diferentes modos de abertura de arquivos em C
são listados na Quadro 2.

MODO Significado

r Abre um arquivo texto para leitura

w Cria um arquivo texto para escrita

a Anexa a um arquivo texto

rb Abre um arquivo binário para leitura

wb Cria um arquivo binário para leitura

ab Anexa a um arquivo binário

r+ Abre um arquivo texto para Leitura e Escrita

w+ Cria um arquivo texto para Leitura e Escrita

a+ Anexa ou Cria um arquivo texto para Leitura e Escrita

r+b Abre um arquivo binário para Leitura e Escrita

w+b Cria um arquivo binário para Leitura e Escrita

a+b Anexa ou Cria um arquivo binário para Leitura e Escrita

Quadro 2: Modos de abertura de arquivo em C
Fonte: Schildt (1996).
 94
Como já vimos anteriormente, a função fopen() possui a seguinte sintaxe:

FILE *fopen(const char *nome_arquivo, const char *modo);

• FILE: é o tipo de dados de ponteiro para arquivo, este tipo de dados é utilizado para
declarar variáveis do tipo arquivo para receber ponteiros de abertura destes.
• nome_arquivo: O nome do arquivo a ser aberto (ou criado, se necessário).
• modo: O modo de abertura que determina a forma como o arquivo será aberto
(aberto ou criado) e as permissões de acesso ao arquivo.

Exemplo de abertura de arquivo:

FILE *arquivo = fopen(“[Link]”, “r”);

if (arquivo == NULL) {
printf(“Erro ao abrir o arquivo.\n”);
return 1;
}

O exemplo apresentado acima demonstra a abertura de um arquivo texto de

nome [Link] e as principais tratativas nesta operação. O trecho que código FILE
*arquivo, declara a variável arquivo como um ponteiro para o tipo FILE, que é o tipo de
dados para manipulação de arquivos.
Neste exemplo o arquivo [Link] será aberto para somente leitura (modo
“r”). Se a função fopen não consegui abrir o arquivo ela retorna um NULL, e é isso que
estamos verificando no condicional logo abaixo da abertura do arquivo, se for retornado
NULL emitimos uma mensagem de erro e finalizamos a execução do programa com o
comando return 1.

2.2. Fechamento de Arquivo: fclose()

Após concluir as operações em um arquivo, é importante fechar o arquivo para

liberar os recursos alocados pelo sistema para a operação de I/O (entrada e saída).
Esta operação é importante para liberar a memória utilizada e para não correr risco de
tratativa ou manipulação desnecessária ou equivocada com o arquivo em questão. A
função usada para fechamento de arquivo é a fclose(). Esta função recebe um ponteiro
para arquivo e fecha a conexão com o mesmo.

Sintaxe:
int fclose(FILE *arquivo);

Exemplo:

fclose(arquivo); //fecha o arquivo aberto na variável ‘arquivo’

 95
3. MANIPULAÇÃO DE ARQUIVOS EM TEXTO VS BINÁRIO

Uma das principais distinções ao manipular arquivos em C é a diferença entre

trabalhar com arquivos de texto e arquivos binários. Ambos têm usos específicos e
exigem diferentes técnicas de leitura e escrita.
Arquivos de texto são fáceis de ler e escrever, pois os dados são armazenados
como caracteres legíveis. Isso significa que você pode abrir o arquivo com um editor
de texto (como o Notepad no Windows ou o Vim no Linux) e visualizar o conteúdo
diretamente. Esses arquivos podem armazenar strings, números formatados e até
caracteres especiais como quebras de linha (\n).
Arquivos binários são mais eficientes para armazenar dados, pois não há
conversão para um formato de texto. Eles são ideais para armazenar dados como
números inteiros, números de ponto flutuante, estruturas complexas, etc. Como esses
arquivos não são legíveis diretamente por humanos, eles devem ser manipulados com
as funções fread() e fwrite().
Usamos a função fread() para ler dados binários diretamente de um arquivo
para a memória. Usamos a função fwrite() para escrever dados binários diretamente
no arquivo.

Exemplo de Leitura e Escrita em Arquivo Binário:

#include <stdio.h>

int main() {
// Escreve em arquivo binário
FILE *arquivo = fopen(“[Link]”, “wb”);
if (arquivo == NULL) {
printf(“Erro ao abrir o arquivo.\n”);
return 1;
}

int dados[] = {10, 20, 30, 40, 50};

fwrite(dados, sizeof(int), 5, arquivo);
fclose(arquivo);
}

Ao trabalhar com arquivos, a escolha entre arquivos de texto ou binários é

crucial, pois pode influenciar a eficiência do programa. Algumas situações devem ser
consideradas ao escolher o tipo de tratativas para cada caso.
Os arquivos texto são ideais quando os dados precisam ser legíveis por humanos
ou quando o formato do arquivo é um padrão amplamente adotado, como CSV ou
arquivos de configuração. Contudo, arquivos de texto podem ser mais lentos para
processar, já que os dados precisam ser convertidos de texto para tipos de dados
adequados durante a leitura.
Os arquivos binários são mais rápidos para processar, pois os dados são
armazenados no formato nativo da máquina. No entanto, não podem ser lidos
facilmente por humanos, o que pode tornar a depuração mais difícil, além de não serem
 96
portáveis entre diferentes sistemas (se houver diferença na forma como os dados são
armazenados e lidos).
Se precisarmos manipular grandes volumes de dados estruturados (como registros
de banco de dados ou matrizes de números), o formato binário é mais eficiente. Por
outro lado, para configurações simples ou quando você precisa garantir que o arquivo
seja facilmente editável e legível, o formato de texto é a escolha mais adequada.

3.1. Leitura de Arquivo

Existem várias funções para ler dados de arquivos utilizando a linguagem C. As

funções mais comuns incluem fgetc(), fgets e fread().

fgetc(): Lê um único caractere do arquivo.

Sintaxe:
int fgetc(FILE *arquivo);

fgets(): Lê uma linha de texto do arquivo e armazena em um buffer.

Sintaxe:
char *fgets(char *buffer, int tamanho, FILE *arquivo);

Exemplo de leitura de informações em um arquivo

char linha[100];
if (fgets(linha, sizeof(linha), arquivo) != NULL) {
printf("%s", linha);
}

fread(): Lê um bloco de dados binários de um arquivo para um buffer. A função fread()

é usada principalmente para arquivos binários.
Sintaxe:
size_t fread(void *buffer, size_t tamanho, size_t quantidade, FILE *arquivo);

FIQUE ATENTO
Para utilizar qualquer função de operações com arquivo o mesmo deve estar aberto
e deve-se observar o modo de abertura utilizado, verificando a compatibilidade da
operação realizada com o modo de abertura.

3.2. Escrita em Arquivo

Para escrever dados em um arquivo, usamos as funções fputc(), fputs(), fprintf()

e fwrite().
fputc(): Escreve um único caractere no arquivo.
Sintaxe:
int fputc(int caractere, FILE *arquivo);
 97
fputs(): Escreve uma string (sequência de caracteres) no arquivo.
Sintaxe:
int fputs(const char *str, FILE *arquivo);

fwrite(): Escreve um bloco de dados binários no arquivo.

Sintaxe:
size_t fwrite(const void *buffer, size_t tamanho, size_t quantidade, FILE *arquivo);

Exemplo de escrita em arquivo:

FILE *arquivo = fopen(“[Link]”, “w”);
if (arquivo == NULL) {
printf(“Erro ao abrir o arquivo.\n”);
return 1;
}
fputs(“Texto gravado no arquivo.\n”, arquivo);
fclose(arquivo);

3.3. Manipulação de Arquivos Binários

Os arquivos binários armazenam dados de forma compacta, utilizando os valores

nativos dos tipos de dados. A leitura e escrita de arquivos binários são feitas com fread()
e fwrite(), como já apresentados anteriormente, veremos um pouco mais sobre estas
funções.
As operações de entrada e saída em arquivos binários funcionam basicamente da
mesma forma que tratamos os arquivos texto comuns, mudando somente o modo de
abertura e algumas funções ou parâmetros de funções para realizar estas operações.
Quando usamos fread(), lemos blocos de dados binários diretamente da memória. Por
exemplo, para ler um vetor de inteiros, podemos fazer o seguinte:

int numeros[10];
FILE *arquivo = fopen(“[Link]”, “rb”);
if (arquivo == NULL) {
printf(“Erro ao abrir o arquivo.\n”);
return 1;
}
fread(numeros, sizeof(int), 10, arquivo);
fclose(arquivo);

Seguindo a mesma lógica de processamento, a escrita de Arquivos Binários: Da

mesma forma, usamos fwrite() para escrever dados binários no arquivo. Por exemplo:
 98
int numeros[] = {1, 2, 3, 4, 5};
FILE *arquivo = fopen("[Link]", "wb");
if (arquivo == NULL) {
printf("Erro ao abrir o arquivo.\n");
return 1;
}
fwrite(numeros, sizeof(int), 5, arquivo);
fclose(arquivo);

4. MANIPULAÇÃO AVANÇADA DE ARQUIVOS

Além das operações básicas de leitura e escrita, o C também permite realizar

operações mais avançadas para manipular o ponteiro de leitura/escrita e verificar o
estado do arquivo.

4.1. Movimentação do Ponteiro de Arquivo: fseek() e ftell()

fseek(): Permite mover o ponteiro de leitura/escrita dentro do arquivo. Isso é útil quando
precisamos ler ou escrever em posições específicas do arquivo.
Sintaxe:
int fseek(FILE *arquivo, long deslocamento, int origem);

Onde que:
deslocamento: É número de bytes a mover o ponteiro.
origem: É a posição de referência para o deslocamento.

ftell(): A função ftell() retorna à posição atual do ponteiro de leitura/escrita dentro do

arquivo, ou seja, ela informa quantos bytes foram lidos ou escritos desde o início do ar-
quivo. Essa função é útil para saber em que parte do arquivo o programa está no mo-
mento.
Sintaxe:
long ftell(FILE *arquivo);

O valor retornado por ftell() representa a posição do ponteiro no arquivo, e isso

pode ser útil em operações em que o programa precisa se mover para diferentes par-
tes do arquivo ou precisa registrar onde as operações de leitura ou escrita estão ocor-
rendo.
 99
Exemplo:
FILE *arquivo = fopen(“[Link]”, “r”);
if (arquivo == NULL) {
printf(“Erro ao abrir o arquivo.\n”);
return 1;
}
fseek(arquivo, 0, SEEK_END); // Vai para o final do arquivo
long tamanho = ftell(arquivo); // Retorna a posição atual (tamanho do arquivo)
printf(“O tamanho do arquivo é: %ld bytes\n”, tamanho);

fclose(arquivo);

BUSQUE POR MAIS

Existem diversos comandos, funções e parâmetros para manipulação
de arquivos na linguagem C, cada um com uma especificação,
funcionalidade e aplicação em situações específicas e importantes
para tratamento de informações em arquivos. Veja os links abaixo e
também busque por mais informações na internet sobre tratamento e
manipulação de arquivos na linguagem C. Disponível em: [Link]
ink/bdMg. Acesso em: 16 jan. 2025.

A figura 30 apresenta um exemplo de algoritmo para tratamento de arquivos, se

trata de um algoritmo simples com demonstração prática de algumas funções para
leitura e escrita em arquivo.
Este algoritmo abre um arquivo chamado [Link] e escreve neste ar-
quivo diversos nomes informados pelo usuário. Esta leitura no teclado e escrita no ar-
quivo se dará até que o usuário informe o valor 0(zero) no lugar de algum nome. É um
exemplo simples e que ilustra a utilização das funções fopen(), fprintf() e fclose().

Figura 30: Exemplo de algoritmo para tratamento

de arquivo
Fonte: Elaborado pelo autor (2024).
 100
4.2. Verificando Fim de Arquivo: feof()

A função feof() é usada para verificar se o ponteiro de leitura chegou ao fim do

arquivo – eof: end of file. Ela retorna um valor diferente de zero quando o fim do arquivo
foi atingido e zero quando ainda existem dados a serem lidos. Ou seja, ela retorna ver-
dadeiro quando o final do arquivo foi atingido e falso quando ainda não foi atingido o
final do arquivo.

Sintaxe:
int feof(FILE *arquivo);

Essa função é frequentemente usada em loops de leitura de arquivos, para ga-

rantir que o programa saiba quando parar de ler. Veja a seguir um exemplo de utiliza-
ção da função feof().

Exemplo:

FILE *arquivo = fopen("[Link]", "r");

if (arquivo == NULL) {
printf("Erro ao abrir o arquivo.\n");
return 1;
}

char linha[100];
while (!feof(arquivo)) {
fgets(linha, sizeof(linha), arquivo);
printf("%s", linha);
}

fclose(arquivo);

O exemplo apresentado acima faz a abertura de um arquivo texto chamado da-

[Link] no modo de somente leitura. Este algoritmo percorre todo o arquivo lendo suas
linhas e escrevendo na tela os valores lidos. Este procedimento de leitura no arquivo de
dará enquanto o final do arquivo não for atingido, situação essa demonstrada na linha
while(!feof(arquivo)).
 101
#include<stdio.h>
#include<stdlib.h>

int main()
{
FILE *arq = fopen("[Link]","a+");
int valor,leitura,existeValor;

if (arq==NULL){
printf("\n\n\tFalha ao tentar abrir o arquivo.\n\n");
exit(1);
}

do {
rewind(arq);
existeValor = 0;
printf("Digite um numero para o arquivo (0 para sair): ");
scanf("%d",&valor);

if (valor==0){
printf("\n\n\tFinalizando o sistema.\n");
} else {
while (!feof(arq)) {
fscanf(arq,"%d",&leitura);
if (leitura==valor)
existeValor = 1;
}

if (!existeValor) {
fprintf(arq,"%d\n",valor);
printf("Sucesso: Valor %d inserido no arquivo.\n",valor);
} else {
printf("Falha: Valor %d ja existe no arquivo.\n",valor);
}

}
}while(valor!=0);

printf("\n\n");
printf("Numeros existentes no arquivo: \n");
rewind(arq);
while (!feof(arq)) {
fscanf(arq,"%d",&leitura);
if (!feof(arq))
printf("%d - ",leitura);
}

fclose(arq);
}
Figura 31: Exemplo de algoritmo para tratamento de arquivo
Fonte: Próprio autor
 102
4.3. Tratamento de Erros em Arquivos: ferror()

A função ferror() é usada para verificar se ocorreu um erro durante a operação

de leitura ou escrita no arquivo. Isso é útil para garantir que o arquivo foi manipulado
corretamente durante o processo de entrada e saída.

Sintaxe:
int ferror(FILE *arquivo);

Se um erro ocorrer, ferror() retornará um valor diferente de zero. Isso pode ser uti-
lizado para interromper operações ou relatar problemas na leitura ou escrita de dados.

Exemplo:

FILE *arquivo = fopen("[Link]", "r");

if (arquivo == NULL) {
printf("Erro ao abrir o arquivo.\n");
return 1;
}

char caractere;
while ((caractere = fgetc(arquivo)) != EOF) {
if (ferror(arquivo)) {
printf("Erro de leitura no arquivo.\n");
break;
}
putchar(caractere); // Exibe o caractere lido
}

fclose(arquivo);

BUSQUE POR MAIS

Pesquise sobre o uso de arquivos de banco de dados (como SQLite) em programação
em C. Isso pode ser interessante para você aprender como acessar e manipular dados
em arquivos de banco de dados relacionais.

FIQUE ATENTO
Sempre que possível, faça uso de arquivos binários para armazenar grandes volumes
de dados. Eles são mais eficientes em termos de velocidade de leitura/escrita do que os
arquivos de texto, especialmente quando o formato dos dados não é legível por humanos.
 103
VAMOS PENSAR?
Suponha que você esteja trabalhando em um sistema de gerenciamento de registros
de funcionários. Quais são os prós e contras de armazenar esses dados em um arquivo
binário, comparado a um arquivo de texto? Quais operações seriam mais rápidas em
cada caso?
 104
FIXANDO O CONTEÚDO
1. Na linguagem C, ao trabalhar com arquivos, um arquivo texto é tratado como uma
sequência de caracteres. Para escrever um texto simples em um arquivo, é necessário
abrir o arquivo no modo de escrita. Assinale a alternativa que representa corretamente
a função para abrir um arquivo no modo de escrita:

A) fopen(“[Link]”, “r”)
B) fopen(“[Link]”, “w”)
C) fopen(“[Link]”, “a”)
D) fopen(“[Link]”, “wb”)
E) fopen(“[Link]”, “rb”)

2. Em C, ao manipular arquivos binários, a leitura e escrita são feitas em blocos de dados

que podem ser diferentes de caracteres, como números inteiros ou estruturas. Para
escrever um número inteiro em um arquivo binário, a função correta é:

A) fprintf(arquivo, “%d”, numero)

B) fwrite(&numero, sizeof(int), 1, arquivo)
C) fputs(&numero, arquivo)
D) fwrite(&numero, sizeof(char), 1, arquivo)
E) fscanf(arquivo, “%d”, &numero)

3. Em relação à diferença entre arquivos texto e arquivos binários, marque a alternativa

correta:

A) Arquivos binários armazenam dados em formato legível, enquanto arquivos texto

armazenam dados de forma compacta e não legível.
B) Arquivos texto são mais eficientes para armazenar dados estruturados, enquanto
arquivos binários são mais indicados para dados simples.
C) Arquivos texto podem ser lidos por qualquer editor de texto, enquanto arquivos
binários não podem ser lidos diretamente por editores de texto convencionais.
D) Arquivos binários são usados exclusivamente para armazenar texto e arquivos texto
para armazenar dados numéricos.
E) Arquivos binários são usados para armazenar qualquer tipo de dado, mas arquivos
texto apenas armazenam caracteres e strings.

4. Considerando um arquivo binário que armazena uma estrutura Aluno, que possui os
campos nome (um array de 50 caracteres) e nota (um número inteiro), a função abaixo
está corretamente implementada para gravar um aluno no arquivo binário. Assinale a
alternativa correta:
 105
typedef struct {
char nome[50];
int nota;
} Aluno;

void gravarAluno(FILE *arquivo, Aluno aluno) {

fwrite(&aluno, sizeof(Aluno), 1, arquivo);
}

A) A função está incorreta porque não é possível escrever estruturas diretamente em

arquivos binários.
B) A função está correta, pois fwrite grava a estrutura no arquivo binário, respeitando
seu tamanho.
C) A função está incorreta, pois deve ser utilizado fprintf para gravar dados de tipos
compostos.
D) A função está incorreta, pois fwrite não pode ser usado para tipos estruturados.
E) A função está correta, mas somente se o arquivo for aberto em modo texto.

5. Na linguagem C, ao manipular arquivos, diferentes modos de abertura podem ser

usados para ler ou escrever dados. Assinale as alternativas corretas sobre os modos de
abertura de arquivos:

I – O modo “w” abre um arquivo para escrita, criando-o se ele não existir ou apagando
o conteúdo se ele já existir.
II – O modo “rb” abre um arquivo binário para leitura, e o arquivo deve existir.
III – O modo “wb” abre um arquivo binário para escrita, criando-o se necessário, mas
não apaga o conteúdo existente.
IV – O modo “a” abre um arquivo para escrita, criando-o se necessário e permitindo
adicionar dados ao final do arquivo.

A) Apenas as alternativas I e II estão corretas.

B) Apenas as alternativas II e IV estão corretas.
C) Apenas as alternativas I e III estão corretas.
D) As alternativas I, II e IV estão corretas.
E) As alternativas II, III e IV estão corretas.

6. Assinale as alternativas corretas sobre a leitura de arquivos em C:

I – A função fscanf é usada para ler dados de um arquivo texto de acordo com o formato
especificado, como %d para inteiros ou %s para strings.
II – A função fread é usada para ler dados binários de um arquivo, especificando o
tamanho do bloco e a quantidade a ser lida.
III – A função fgets é usada para ler uma linha de um arquivo texto, incluindo espaços,
até encontrar o caractere de nova linha ou o final do arquivo.
IV – A função fgets é usada para ler dados binários de um arquivo, o que não é adequado
para este tipo de arquivo.
 106
A) Apenas as alternativas I, II e III estão corretas.
B) Apenas as alternativas II e III estão corretas.
C) Apenas as alternativas I e IV estão corretas.
D) As alternativas I, II, III e IV estão corretas.
E) As alternativas I e III estão corretas.

7. Em relação à manipulação de arquivos em C, considere as afirmações a seguir:

I – Arquivos texto podem ser lidos e escritos como uma sequência de caracteres,
enquanto arquivos binários devem ser manipulados em blocos de dados inteiros.
II – Arquivos binários não podem ser lidos diretamente por editores de texto, ao contrário
dos arquivos texto, que são legíveis em qualquer editor de texto.
III – A função fwrite pode ser utilizada para gravar dados binários em um arquivo, seja
para tipos primitivos ou para estruturas de dados.
IV – Arquivos texto devem ser usados apenas para armazenar strings, enquanto arquivos
binários são apropriados para armazenar dados como números inteiros e floats.

A) Apenas as alternativas I, II e III estão corretas.

B) Apenas as alternativas II, III e IV estão corretas.
C) Apenas as alternativas I e II estão corretas.
D) As alternativas I, II, III e IV estão corretas.
E) As alternativas II e III estão corretas.

8. Considere o seguinte código em C que escreve dados em um arquivo binário. Assinale

as alternativas corretas sobre o comportamento do código:

typedef struct {
char nome[50];
int idade;
} Pessoa;

Pessoa p1 = {“Filipe”, 25};

FILE *arquivo = fopen(“[Link]”, “wb”);

fwrite(&p1, sizeof(Pessoa), 1, arquivo);
fclose(arquivo);

I – A função fwrite grava a estrutura Pessoa no arquivo binário, respeitando o tamanho

da estrutura.
II – O arquivo [Link] será criado, e os dados da estrutura Pessoa serão gravados
nele, sobrepondo quaisquer dados existentes.
III – Se o arquivo [Link] não existir, a função fopen com o modo “wb” criará o arquivo
automaticamente.
IV – O código não funcionará corretamente, pois a função fwrite não pode ser usada
para gravar tipos estruturados em arquivos binários.

A) Apenas as alternativas I e II estão corretas.

B) Apenas as alternativas I, II e III estão corretas.
 107
C) Apenas as alternativas I e III estão corretas.
D) Apenas as alternativas II e IV estão corretas.
E) As alternativas I, II, III e IV estão corretas.
 108

GABARITO

UNIDADE 1 UNIDADE 2
QUESTÃO 1 D QUESTÃO 1 D
QUESTÃO 2 E QUESTÃO 2 B
QUESTÃO 3 B QUESTÃO 3 E
QUESTÃO 4 C QUESTÃO 4 D
QUESTÃO 5 E QUESTÃO 5 B
QUESTÃO 6 D QUESTÃO 6 A
QUESTÃO 7 B QUESTÃO 7 B
QUESTÃO 8 A QUESTÃO 8 A

UNIDADE 3 UNIDADE 4
QUESTÃO 1 D QUESTÃO 1 D
QUESTÃO 2 D QUESTÃO 2 D
QUESTÃO 3 C QUESTÃO 3 A
QUESTÃO 4 D QUESTÃO 4 B
QUESTÃO 5 B QUESTÃO 5 A
QUESTÃO 6 C QUESTÃO 6 B
QUESTÃO 7 B QUESTÃO 7 E
QUESTÃO 8 B QUESTÃO 8 B

UNIDADE 5 UNIDADE 6
QUESTÃO 1 D QUESTÃO 1 B
QUESTÃO 2 C QUESTÃO 2 B
QUESTÃO 3 B QUESTÃO 3 C
QUESTÃO 4 C QUESTÃO 4 B
QUESTÃO 5 A QUESTÃO 5 D
QUESTÃO 6 C QUESTÃO 6 A
QUESTÃO 7 A QUESTÃO 7 A
QUESTÃO 8 C QUESTÃO 8 B
 109

REFERÊNCIAS BIBLIOGRÁFICAS
FERNANDES, Filipe Costa. Programação de Computadores I. 1º ed. Ipatinga: Faculdade
Única Editorial, 2021.

FORBELLONE, André Luiz Villar; EBERSPÄCHER, Henri Frederico. Lógica de programação: a

construção de algoritmos e estrutura de dados. 3 ed. São Paulo: Prentice Hall, 2005.
Disponível em: <[Link] Acesso
em 23 de junho de 2021>.

MIZRAHI, Victorine Viviane. Treinamento em linguagem C. 2 ed. São Paulo: Pearson Prentice
Hall, 2006. Disponível em: <[Link]
Acesso em 23 de junho de 2021>.

RIBEIRO, João Araujo. Introdução à programação e aos algoritmos / João Araujo Ribeiro.
- 1. ed. - Rio de Janeiro: LTC, 2019. Disponível em:< [Link]
[Link]/#/books/9788595022492/cfi/1!/4/2@100:0.00>. Acesso em 23 de junho de 2021>.

SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de dados e seus algoritmos. [Link].
[Reimpr.]. - Rio de Janeiro: LTC, 2015. Disponível em: <[Link]
[Link]/#/books/978-85-216-2995-5/cfi/6/2!/4/2/2@0:0>. Acesso em 23 de junho de
2021.

PEREIRA, F. Microcontroladores PIC: programação em C. 6a edição -São Paulo: Érica, 2007.

Disponível em: <[Link]
cfi/0!/4/2@100:0.00>. Acesso em 23 de junho de 2021>.

ZIVIANI, Nivio. Projeto de Algoritmos com implementação e Pascal e C. São Paulo: Pioneira
Thomson Learning, 2005.

EDELWEISS, N.; LIVI, M. A. C. Algoritmos e programação com exemplos em Pascal e C.

Porto Alegre: Bookman, 2014.

MANZANO, J. A. N. G. Programação de Computadores com C/C++. 1. ed. São Paulo: Editora

Érica, 2014. 120 p.

MANZANO, J. A. N. G.; OLIVEIRA, J. F. D. Algoritmos: Lógica para Desenvolvimento de

Programação de Computadores. 28. ed. São Paulo: Érica, 2016.

RIBEIRO, J. A. Introdução à programação e aos algoritmos. 1. ed. Rio de Janeiro: LTC, 2019.

SOFFNER, R. Algoritmos e programação em linguagem C. 1. ed. São Paulo: Saraiva, 2013.

200 p.
 110
RIBEIRO, João A. Introdução à Programação e aos Algoritmos. Rio de Janeiro: LTC, 2019.
E-book. [Link]. ISBN 9788521636410. Disponível em: [Link]
br/reader/books/9788521636410/. Acesso em: 21 nov. 2024.

SCHILDT, Hebert. C Completo e Total. 3ª ed. São Paulo: Makron Books, 1996

ZIVIANI, Nivio. Projeto de Algoritmos: com implementações em JAVA e C++. Porto Alegre:
+A Educação - Cengage Learning Brasil, 2012. E-book. [Link]. ISBN 9788522108213. Disponível
em: [Link] Acesso
em: 21 nov. 2024.

CORMEN, Thomas H.; LEISERSON, Charles E.; Ronald L. Rivest; et al. Algoritmos. 4th ed. Rio
de Janeiro: GEN LTC, 1990. E-book. [Link]. ISBN 9788595159914. Disponível em: https://
[Link]/reader/books/9788595159914/. Acesso em: 21 nov.
2024.

CORMEN, Thomas. Desmistificando Algoritmos. Rio de Janeiro: GEN LTC, 2013. E-book.
[Link]. ISBN 9788595153929. Disponível em: [Link]
reader/books/9788595153929/. Acesso em: 21 nov. 2024.

SERPA, Matheus S.; RODRIGUES, Thiago N.; ALVES, Ítalo C.; et al. Análise de Algoritmos.
Porto Alegre: SAGAH, 2021. E-book. [Link]. ISBN 9786556901862. Disponível em: https://
[Link]/reader/books/9786556901862/. Acesso em: 21 nov.
2024.

VETORAZZO, Adriana S.; SARAIVA, Mauício O.; BARRETO, Jeanine S.; et al. Estrutura de
dados. Porto Alegre: SAGAH, 2018. E-book. [Link]. ISBN 9788595023932. Disponível em:
[Link] Acesso em:
01 dez. 2024.

MANZANO, Jose Augusto Navarro G. Algoritmos Funcionais. Rio de Janeiro: Editora

Alta Books, 2020. E-book. p.1. ISBN 9786555202502. Disponível em: [Link]
[Link]/reader/books/9786555202502/. Acesso em: 01 dez. 2024.

BROOKSHEAR, J G. Ciência da computação. 11th ed. Porto Alegre: Bookman, 2013. E-book.
p.207. ISBN 9788582600313. Disponível em: [Link]
reader/books/9788582600313/. Acesso em: 01 dez. 2024.

GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. 7th ed.

Rio de Janeiro: LTC, 2016. E-book. p.i. ISBN 9788521633303. Disponível em: [Link]
[Link]/reader/books/9788521633303/. Acesso em: 01 dez. 2024.

NETO, Jose Antônio. Árvore Binária Balanceada (2024). Disponível em: [Link]
[Link]/slide/3652631/. Acesso em: 19 dez. 2024.
111