Ex 1:1- Um conjunto uma coleo de objetos distintos.2- Uma lista
um TAD representado por um conjunto de elementos ordenados onde o
mesmo elemento pode ocorrer mais de uma vez, sendo cada elemento um
item na lista. Na lista, os elementos podem ser removidos de
qualquer posio, independente da ordem de entrada.3- A pilha um TAD
no formato de uma lista, porm, na pilha, a ordem de sada dos
elementos regida pela regra de LIFO (last in first out), ou seja, o
ltimo a entrar na pilha o primeiro a sair.4- A fila um TAD no
formato de uma lista onde a ordem de sada dos elementos de FIFO
(first in first out), sendo assim, o primeiro a entrar o primeiro a
sair, assim como numa fila de pessoas.5- uma fila em que cada
elemento tem uma prioridade associada, que vai determinar a ordem
de sada deles, sendo o de maior prioridade o primeiro a sair e o de
menor prioridade, o ltimo.6- Um deque (Double-ended queue), como o
prprio nome diz, uma fila que ao contrrio da implementao de fila
comum, possui duas extremidades, uma no incio e outra no fim, sendo
possvel retirar elementos tanto do incio da fila como do fim.7- Um
dicionrio um mapeamento entre dois conjuntos de itens, um deles
contendo um valor e outro contendo uma chave pra esse valor, que
pode ser usada pra acessar o contedo dele.8- Uma rvore um grafo
onde cada par de ns est associado a apenas uma aresta e existe
apenas um caminho entre um vrtice e outro.9- Grafos so formados por
um conjunto no vazio de vrtices e um conjunto de arestas, onde cada
aresta liga um par de vrtices estabelecendo assim uma relao entre
eles, as arestas podem ser direcionadas ou no direcionadas, caso
seja direcionada, no caso, por exemplo, dos vrtices A e B, em que A
-> B, a condio vale pra A mas no vale pra B.10- uma estrutura de
dados bem definida que pode ser usada atravs de operaes especficas
para essa estrutura.
Ex 2:As possveis operaes em uma lista so insero, remoo, busca,
acesso e juno, as possveis implementaes de uma lista so: encadeada
e sequencial. Em listas no-ordenadas sequenciais, as operaes
possuem as seguintes complexidades: Busca = O(n), Insero = O(1),
Insero (numa posio especfica) = O(n - pos), Insero (numa referncia)
= O(n pos(ref)), Remoo(de uma posio) = O (n - pos), Remoo (de uma
referncia) = O(n pos(ref)), Junao = O(min(n , m)) e Acesso =
O(1).Em listas no-ordenadas encadeadas, possuem as seguintes
complexidades: Busca = O(n), Insero = O(1), Insero (numa posio
especfica) = O(pos), Insero (numa referncia) = O(1) Remoo(de uma
posio) = O(pos), Remoo (de uma referncia) = O(1), Junao = O(1) e
Acesso = O(pos).Em listas ordenadas sequenciais: Acesso = O(1),
Busca = O(log n(base 2)), Insero = O(n), Remoo(de uma posio) = O(n
- pos), Remoo (de uma referncia) = O(n pos(ref)) e Junao = O(n +
m).Em listas ordenadas encadeadas: Acesso = O(pos), Busca = O(n),
Insero = O(n), Remoo(de uma posio) = O(pos), Remoo (de uma
referncia) = O (1) e Junao = O(n + m).Ex 3:As possveis operaes com
uma pilha so criar, empilhar, desempilhar e mostrar o topo. As
possveis implementaes so esttica (com arranjos) e encadeada (com
alocao dinmica de memria). As operaes empilhar, desempilhar e
mostrar o topo possuem complexidade O(1) nas duas implementaes.Ex
4:As operaes usadas em filas so criar fila, enfileirar,
desenfileirar e mostrar o elemento da frente, assim como as pilhas,
podem ser implementadas de forma esttica (com arranjos) ou por
lista encadeada (alocao dinmica), e da mesma maneira, possuem
complexidade O(1) para as operaes enfileirar, desenfileirar e
mostrar o elemento da frente, independente da implementao.Ex 5:No
deque, as possveis operaes so criar, enfileirar na frente (push
front), enfileirar de trs (push back), desenfileirar na frente (pop
front), desenfileirar de trs (pop back), consultar elemento da
frente e consultar elemento de trs. Um deque pode ser implementado
por arranjo ou lista encadeada. Todas as suas operaes, com exceo de
criar, tem complexidade O(1).Ex 12:#include #include #define
TABLE_SIZE 100
struct Hash_table{ int value; int key;};
int hash_function(int val){return val % 10;}
void insert(Hash_table tab[], int val){int hash_key =
hash_function(val);tab[hash_key].value = val;}
void remove(Hash_table tab[], int key){tab[key].value =
NULL;}
void search(Hash_table.tab[], int val){ int flag = 0; for (int i
= 0; i < TABLE_SIZE; i++){ if (tab[i].value == val){ cout
