Módulo 02
Estruturas Sequenciais
Exercícios de Estruturas Sequenciais
Cinco exercícios para revisar os principais conceitos do módulo: vetores, matrizes, inserção, remoção, busca, strings e lista sequencial. As questões combinam interpretação, rastreamento, complexidade e implementação.
Progresso da lista
0 / 5 concluídos
Revisão do Módulo 02
Exercícios
01
Fácil
Inserção em Vetor
Vetores · Inserção · Complexidade
Considere o vetor:
[ 10, 20, 30, 40, 50, _ , _ ]
Insira o valor 99 no índice 2.
- Mostre o vetor após a operação.
- Quantos elementos precisam ser deslocados?
- Qual é a complexidade dessa inserção no pior caso?
02
Médio
Índice Linear de uma Matriz
Matrizes · Row-major · Memória
Uma matriz possui 5 colunas e utiliza armazenamento row-major.
Determine o índice linear correspondente à posição
m[3][2].
Utilize a fórmula:
índice = linha × número_de_colunas + colunaEm seguida, explique por que o acesso a uma posição conhecida da matriz continua sendo O(1).
03
Médio
Busca Linear vs. Busca Binária
Busca · Rastreamento
Considere o vetor ordenado:
[ 3, 7, 12, 18, 25, 31, 39, 44, 52, 61, 73, 90 ]
O valor procurado é 73.
- Quantas comparações uma busca linear realiza?
- Execute a busca binária indicando os índices esquerda, direita e meio em cada passo.
- Qual algoritmo utiliza menos comparações nesse exemplo?
04
Médio
Strings Unicode e UTF-8
Strings · Caracteres
Considere:
C++17
#include <string>
std::string palavra = "DADOS";
std::size_t quantidade_de_bytes = palavra.size();- Qual é o resultado de
palavra.size()? - Quais bytes estão armazenados na
std::string? -
Explique por que, em UTF-8, não podemos assumir que
1 caractere = 1 byte.
05
Desafio
Lista Sequencial
TAD · C++17 · Desafio
Uma lista sequencial possui capacidade 10 e inicialmente contém:
[ 10, 20, 30, 40, 50, 60, _, _, _, _ ]
tamanho = 6Realize as operações na ordem:
- insira
99na posição 2; - remova o elemento da posição 4;
- busque o valor
60.
Mostre o estado final da lista e responda:
- qual será o novo valor de
tamanho? - qual é a complexidade da busca?
- por que as posições livres não fazem parte logicamente da lista, mesmo existindo fisicamente no array?
Confira depois de tentar
Gabarito
Orientação:
tente resolver os cinco exercícios antes de abrir as respostas.
Questão 01 — Inserção em Vetor
Resultado:
[ 10, 20, 99, 30, 40, 50, _ ]Os valores 30, 40 e 50 precisam avançar uma posição: 3 deslocamentos.
No pior caso, uma inserção em vetor exige deslocar uma quantidade proporcional a n elementos: O(n).
Questão 02 — Matriz
Índice linear:
3 × 5 + 2 = 17
Portanto, m[3][2] corresponde à posição linear
17.
O acesso é O(1) porque linha e coluna permitem calcular diretamente a posição, sem percorrer os elementos anteriores.
Questão 03 — Buscas
Na busca linear, 73 está no índice 10. Portanto são feitas 11 comparações.
Busca binária:
[0,11] meio = 5 → 31
[6,11] meio = 8 → 52
[9,11] meio = 10 → 73O valor é encontrado em 3 comparações.
Nesse exemplo, a busca binária é claramente mais eficiente.
Questão 04 — Strings
"DADOS" possui 5 caracteres e, por isso,
palavra.size() devolve 5.
std::string palavra → "DADOS"
palavra.size() → 5 bytes
Uma std::string armazena uma sequência de bytes. O significado desses
bytes depende da codificação adotada pelo programa, como UTF-8.
Em UTF-8, símbolos diferentes podem ocupar diferentes quantidades de bytes. Portanto a quantidade de bytes não é necessariamente igual à quantidade de caracteres percebidos no texto.
Questão 05 — Lista Sequencial
Estado inicial:
10 20 30 40 50 60Após inserir 99 na posição 2:
10 20 99 30 40 50 60Após remover a posição 4, que contém 40:
10 20 99 30 50 60O tamanho volta a ser 6.
Uma busca linear por 60 possui pior caso O(n).
As posições posteriores ao índice tamanho - 1 pertencem à
capacidade física, mas não à lista lógica. É a variável
tamanho que determina quais elementos fazem parte do TAD.
Fechamento