Resposta: Um TAD define um conjunto de dados e as operações possíveis sobre eles, sem expor como são implementados internamente. A interface é o contrato (assinaturas e comportamento das funções); a implementação é como os dados são representados e as funções codificadas. Exemplo: PilhaEnc — o usuário chama push/pop sem saber que internamente usa lista encadeada.

Resposta: Listas encadeadas crescem e diminuem em tempo de execução; cada nodo é alocado individualmente no heap com malloc, pois o tamanho total não é conhecido em tempo de compilação. Sem alocação dinâmica, seria necessário um vetor com tamanho máximo fixo, desperdiçando memória ou limitando o TAD.
Memory leak: se o programador não chamar free para cada nodo removido, a memória permanece ocupada até o fim do processo — pode esgotar a memória em programas de longa duração.

Resposta: O(n) significa que o tempo de execução cresce linearmente com o tamanho n da entrada: dobrar n dobra o tempo (aproximadamente).
O(1) em lista encadeada: inserirInicio — apenas atualiza o ponteiro ini, independente do tamanho.
O(n): busca por valor ou inserção no fim sem ponteiro fim — exige percorrer todos os nodos.

Resposta: Uma lista contígua armazena os elementos em um vetor, com posições consecutivas de memória. Permite acesso direto ao k-ésimo elemento em O(1) via índice.
Inserir no início é O(n) porque é necessário deslocar todos os elementos uma posição à direita para abrir espaço. Além disso, o tamanho máximo deve ser definido na declaração (sem crescimento dinâmico).

Resposta: Nodo: struct com dois campos — dado (conteúdo, ex: Produto) e prox (ponteiro para o próximo; NULL no último).
Descritor (ListaEnc): struct que representa a lista como um todo; contém apenas ini, ponteiro para o primeiro nodo (NULL se vazia).
Os nodos são alocados dinamicamente no heap; o descritor pode estar na pilha ou no heap.

Resposta: A função precisa atualizar ini do descritor para apontar para o novo nodo. Se recebesse por valor (ListaEnc lista), receberia uma cópia do descritor: a alteração de lista.ini ficaria nessa cópia local e seria descartada ao retornar — a lista original não seria modificada.
Com ListaEnc *lista, lista->ini = novo modifica o descritor original.

Resposta: (1) Verificar se a lista está vazia (lista->ini == NULL); se sim, retornar.
(2) Guardar: Nodo *tmp = lista->ini;
(3) Avançar o início: lista->ini = lista->ini->prox;
(4) Liberar: free(tmp);
Guardar tmp antes de atualizar ini é essencial; caso contrário o ponteiro para o nodo é perdido e a memória vaza.

Resposta: Em uma lista duplamente encadeada, cada nodo possui dois ponteiros: prox (para o seguinte) e ant (para o anterior).
Vantagem: percurso nos dois sentidos e remoção de um nodo em O(1) sem ponteiro externo anterior — basta acessar nodo->ant diretamente, sem varredura adicional.

Resposta: Seja alvo o nodo a remover, com vizinhos alvo->ant e alvo->prox:
(1) alvo->ant->prox = alvo->prox; — o anterior aponta para o próximo de alvo.
(2) alvo->prox->ant = alvo->ant; — o próximo aponta de volta para o anterior de alvo.
(3) free(alvo);
Tratar bordas: se alvo é o primeiro, ajustar ini do descritor; se é o último, ajustar fim.

Resposta: Em uma lista circular, o prox do último nodo aponta de volta para o primeiro (em vez de NULL), formando um ciclo.
Para detectar o fim da varredura sem NULL, compara-se o nodo atual com o nodo inicial (sentinela): a varredura termina quando atual == primeiro (ao retornar ao ponto de partida).
Aplicação: buffers circulares, escalonamento round-robin.

Resposta: O Insertion Sort mantém um segmento ordenado no início do vetor. A cada passo i (de 1 a n−1): guarda chave = vetor[i] e desloca para a direita os elementos do segmento ordenado que sejam maiores que chave, depois insere chave na posição correta.
Melhor caso O(n): vetor já ordenado — nenhum deslocamento é feito.
Pior caso O(n²): vetor em ordem decrescente — cada inserção desloca todos os elementos anteriores.

Resposta: O Shell Sort aplica Insertion Sort com gap (intervalo) decrescente em vez de intervalo 1. Nos primeiros passos, elementos distantes são comparados e trocados, eliminando inversões grandes rapidamente. À medida que o gap diminui até 1, o vetor já está quase ordenado, e o Insertion Sort final opera próximo do seu melhor caso O(n).
Resultado: muito mais eficiente que Insertion Sort puro para vetores grandes, pois reduz o número total de deslocamentos.

Resposta: LIFO (Last In, First Out): o último inserido é o primeiro removido.
Operações: inicializaPilha (topo=NULL), estaVaziaPilha, push (insere no topo), pop (remove e retorna o topo).
Push e pop ocorrem no início da lista interna: ambas são O(1). Operar no fim exigiria percorrer toda a lista (O(n)) para chegar ao último nodo.

Resposta (exemplos válidos): Pilha de chamadas: cada chamada de função empilha o contexto local (parâmetros, variáveis, endereço de retorno); return desempilha, restaurando o contexto anterior.
Histórico de desfazer (undo): cada ação é empilhada; Ctrl+Z desempilha e reverte a última ação.
Avaliação de expressões: calculadoras e compiladores usam pilha para converter e avaliar expressões aritméticas.

Resposta: FIFO (First In, First Out): o primeiro a entrar é o primeiro a sair.
enqueue (inserção) ocorre no fim; dequeue (remoção) ocorre no início.
O ponteiro fim torna o enqueue O(1): sem ele, seria preciso percorrer toda a lista para chegar ao último nodo (O(n)) a cada inserção. Com ini e fim, ambas as operações são O(1).

Resposta: Um deque (double-ended queue) permite inserção e remoção em ambas as extremidades. Operações: inserir/remover no início e inserir/remover no fim.
Generaliza a pilha: operando apenas em uma extremidade (início) obtém-se LIFO.
Generaliza a fila: inserindo em um lado e removendo no outro obtém-se FIFO.
Uma lista duplamente encadeada é a implementação natural para deques (O(1) em todas as extremidades).

Resposta: Raiz: nodo sem pai; é o ponto de entrada da árvore.
Folha: nodo sem filhos (esq == NULL && dir == NULL).
Nível: distância em arestas até a raiz; raiz tem nível 0.
Altura: nível máximo atingido na árvore (comprimento do caminho mais longo da raiz a uma folha).
Árvore com apenas a raiz: altura 0. Árvore vazia: altura −1 (convenção).

Resposta: Pré-ordem: raiz → esquerda → direita. O nodo é processado antes dos filhos. Usado para copiar/serializar a árvore.
In-ordem: esquerda → raiz → direita. Em uma ABP, produz os elementos em ordem crescente.
Pós-ordem: esquerda → direita → raiz. O nodo é processado depois dos filhos. Usado para destruir a árvore liberando memória (filhos antes do pai).

Resposta: Propriedade: para todo nodo, todos os valores na subárvore esquerda têm chave menor e todos na direita têm chave maior (recursivamente).
In-ordem crescente: ao imprimir esquerda (menores) antes da raiz e depois direita (maiores), e aplicar isso recursivamente, os nodos são impressos do menor para o maior — exatamente o que a propriedade da ABP garante.

Resposta: Caso 1 — folha: sem filhos. Ajustar ponteiro do pai para NULL e liberar.
Caso 2 — um filho: o pai passa a apontar diretamente para o único filho do nodo removido.
Caso 3 — dois filhos: substituir o dado pelo sucessor in-ordem (menor nodo da subárvore direita — obtido descendo sempre à esquerda até o NULL) e remover esse sucessor recursivamente (que é sempre caso 1 ou 2).

Critérios: inicializar maior com o primeiro elemento (0,4); percorrer do segundo em diante (0,4); comparar preco e atualizar (0,5); retornar maior (0,2).

Produto maiorPreco(const ListaEnc *lista) {
    Nodo *atual = lista->ini;
    Produto maior = atual->dado;     /* inicia com o primeiro */
    atual = atual->prox;
    while (atual != NULL) {
        if (atual->dado.preco > maior.preco)
            maior = atual->dado;
        atual = atual->prox;
    }
    return maior;
}

Inicializar com o primeiro (não com zero) garante que qualquer preço válido seja reconhecido.

Critérios: acumulador 0.0 (0,3); percorrer lista (0,4); testar cod % 2 != 0 (0,5); acumular preco (0,3).

float somarPrecosImpares(const ListaEnc *lista) {
    float soma = 0.0;
    Nodo *atual = lista->ini;
    while (atual != NULL) {
        if (atual->dado.cod % 2 != 0)
            soma += atual->dado.preco;
        atual = atual->prox;
    }
    return soma;
}

Critérios: remover consecutivos no início (0,6); percorrer com ant (0,5); não avançar ant ao remover (0,6); free correto (0,4); tratar lista vazia (0,4).

void removerMenoresQuePreco(ListaEnc *lista, float p) {
    while (lista->ini != NULL && lista->ini->dado.preco < p) {
        Nodo *tmp = lista->ini;
        lista->ini = lista->ini->prox;
        free(tmp);
    }
    if (lista->ini == NULL) return;

    Nodo *ant = lista->ini;
    while (ant->prox != NULL) {
        if (ant->prox->dado.preco < p) {
            Nodo *tmp = ant->prox;
            ant->prox = tmp->prox;
            free(tmp);
            /* NAO avanca ant */
        } else {
            ant = ant->prox;
        }
    }
}

Critérios: tratar b vazia (0,3); tratar a vazia (0,4); percorrer a ate o fim (0,5); ligar ao ini de b (0,3).

void concatenarListas(ListaEnc *a, const ListaEnc *b) {
    if (b->ini == NULL) return;
    if (a->ini == NULL) {
        a->ini = b->ini;
        return;
    }
    Nodo *atual = a->ini;
    while (atual->prox != NULL)
        atual = atual->prox;
    atual->prox = b->ini;
}

Nenhum nodo é criado: apenas o prox do último de a é atualizado para apontar para b->ini.

Critérios: ant=NULL inicial (0,4); guardar prox (0,5); inverter prox (0,5); avançar ant e atual (0,5); atualizar lista->ini (0,4); funciona para vazia/unitária (0,2).

void inverterLista(ListaEnc *lista) {
    Nodo *ant   = NULL;
    Nodo *atual = lista->ini;
    while (atual != NULL) {
        Nodo *prox  = atual->prox;  /* 1. guarda o proximo */
        atual->prox = ant;           /* 2. inverte ponteiro */
        ant   = atual;               /* 3. avanca ant       */
        atual = prox;                /* 4. avanca atual     */
    }
    lista->ini = ant;
}

[1,2,3] vira [3,2,1]. Cada passo inverte apenas um ponteiro; nenhum nodo é alocado.

Critérios: tratar lista vazia ou unitária (0,4); remover o primeiro atualizando ini (0,5); percorrer ate o último (0,5); ligar último ao antigo primeiro (0,4); prox do antigo primeiro = NULL (0,2).

void moverPrimeiroParaFim(ListaEnc *lista) {
    if (lista->ini == NULL) return;
    if (lista->ini->prox == NULL) return;  /* unitaria */

    Nodo *primeiro = lista->ini;
    lista->ini = primeiro->prox;   /* remove o primeiro */
    primeiro->prox = NULL;

    Nodo *atual = lista->ini;
    while (atual->prox != NULL)
        atual = atual->prox;
    atual->prox = primeiro;         /* liga ao fim */
}

Critérios: alocar nodo (0,3); tratar inserção antes do primeiro ou lista vazia (0,5); percorrer até ant->prox com cod ou NULL (0,5); inserir após ant (0,4); inserir no fim se não encontrado (0,3).

void inserirAntesDeCod(ListaEnc *lista, Produto p, int cod) {
    Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
    novo->dado = p;
    novo->prox = NULL;

    /* lista vazia ou o primeiro ja tem o cod */
    if (lista->ini == NULL || lista->ini->dado.cod == cod) {
        novo->prox = lista->ini;
        lista->ini = novo;
        return;
    }

    /* percorre: para quando ant->prox tem o cod ou chegou ao fim */
    Nodo *ant = lista->ini;
    while (ant->prox != NULL && ant->prox->dado.cod != cod)
        ant = ant->prox;

    /* insere apos ant (antes de ant->prox, seja ele o cod ou NULL) */
    novo->prox = ant->prox;
    ant->prox  = novo;
}

Se cod não existe, o while para com ant->prox == NULL e o novo é inserido no fim (novo->prox = NULL).

Critérios: dois acumuladores maior e segundo (0,5); atualizar ambos ao encontrar novo maior (0,7); atualizar apenas segundo quando entre segundo e maior (0,7); retornar segundo (0,3); -1.0 se não existir (0,3).

float segundoMaiorPreco(const ListaEnc *lista) {
    float maior   = -1.0;
    float segundo = -1.0;
    Nodo *atual = lista->ini;
    while (atual != NULL) {
        if (atual->dado.preco > maior) {
            segundo = maior;
            maior   = atual->dado.preco;
        } else if (atual->dado.preco < maior && atual->dado.preco > segundo) {
            segundo = atual->dado.preco;
        }
        atual = atual->prox;
    }
    return segundo;
}

Uma só passagem O(n). Retorna -1.0 se todos os preços forem iguais ou a lista tiver um único preço distinto.

Critérios: dequeue todos e achar maior (0,6); enqueue para temp (0,4); restaurar fila original (0,5).

Produto maiorPrecoFila(FilaEnc *fila) {
    FilaEnc temp;
    Produto v, maior;
    int n = 0;
    inicializaFila(&temp);
    while (!estaVaziaFila(fila)) {
        v = dequeue(fila);
        if (n == 0 || v.preco > maior.preco)
            maior = v;
        enqueue(&temp, v);
        n++;
    }
    while (!estaVaziaFila(&temp))
        enqueue(fila, dequeue(&temp));
    return maior;
}

Dequeue todos para temp (processando), depois enqueue de volta. A ordem é preservada pois temp também é FIFO.

Critérios: pop todos e achar maior (0,6); push para temp (0,4); restaurar via double-reversal (0,5).

Produto maiorPrecoPilha(PilhaEnc *pilha) {
    PilhaEnc temp;
    Produto v, maior;
    int n = 0;
    inicializaPilha(&temp);
    while (!estaVaziaPilha(pilha)) {
        v = pop(pilha);
        if (n == 0 || v.preco > maior.preco)
            maior = v;
        push(&temp, v);
        n++;
    }
    /* pop de temp e push de volta = duas reversoes = ordem original */
    while (!estaVaziaPilha(&temp))
        push(pilha, pop(&temp));
    return maior;
}

Pop da pilha inverte a ordem em temp. Pop de temp de volta para pilha inverte novamente: ordem restaurada.

Critérios: dequeue todos descartando o primeiro com cod (0,7); enqueue restantes para temp (0,4); restaurar fila (0,5).

void removerDaFilaPorCod(FilaEnc *fila, int cod) {
    FilaEnc temp;
    Produto v;
    int removido = 0;
    inicializaFila(&temp);
    while (!estaVaziaFila(fila)) {
        v = dequeue(fila);
        if (!removido && v.cod == cod) {
            removido = 1;            /* descarta este elemento */
        } else {
            enqueue(&temp, v);
        }
    }
    while (!estaVaziaFila(&temp))
        enqueue(fila, dequeue(&temp));
}

Critérios: pop todos descartando o primeiro com cod (0,7); push restantes em temp (0,4); restaurar via double-reversal (0,5).

void removerDaPilhaPorCod(PilhaEnc *pilha, int cod) {
    PilhaEnc temp;
    Produto v;
    int removido = 0;
    inicializaPilha(&temp);
    while (!estaVaziaPilha(pilha)) {
        v = pop(pilha);
        if (!removido && v.cod == cod) {
            removido = 1;            /* descarta o primeiro encontrado */
        } else {
            push(&temp, v);
        }
    }
    while (!estaVaziaPilha(&temp))
        push(pilha, pop(&temp));
}

O double-reversal (pop para temp, pop de volta para pilha) restaura a ordem original. A flag removido garante que apenas o primeiro com cod é descartado.

Critérios: inicializar pares e impares (0,3); dequeue todos (0,4); teste cod % 2 (0,5); enqueue na fila correta (0,4); ordem preservada em cada fila (0,4).

void separarParImpar(FilaEnc *fila, FilaEnc *pares, FilaEnc *impares) {
    Produto v;
    inicializaFila(pares);
    inicializaFila(impares);
    while (!estaVaziaFila(fila)) {
        v = dequeue(fila);
        if (v.cod % 2 == 0)
            enqueue(pares, v);
        else
            enqueue(impares, v);
    }
}

Critérios: acumulador 0.0 (0,2); dequeue para temp (0,4); testar cod impar (0,4); acumular preco (0,3); restaurar fila (0,5).

float somarPrecosImparesPreservando(FilaEnc *fila) {
    FilaEnc temp;
    Produto v;
    float soma = 0.0;
    inicializaFila(&temp);
    while (!estaVaziaFila(fila)) {
        v = dequeue(fila);
        if (v.cod % 2 != 0)
            soma += v.preco;
        enqueue(&temp, v);
    }
    while (!estaVaziaFila(&temp))
        enqueue(fila, dequeue(&temp));
    return soma;
}

Critérios: guardar elemento anterior (0,4); comparar cod com o anterior (0,5); detectar e sinalizar igualdade (0,4); dequeue para temp (0,3); restaurar fila (0,4).

int temConsecutivosIguais(FilaEnc *fila) {
    FilaEnc temp;
    Produto v, ant;
    int tem = 0, primeiro = 1;
    inicializaFila(&temp);
    while (!estaVaziaFila(fila)) {
        v = dequeue(fila);
        if (!primeiro && v.cod == ant.cod)
            tem = 1;
        ant     = v;
        primeiro = 0;
        enqueue(&temp, v);
    }
    while (!estaVaziaFila(&temp))
        enqueue(fila, dequeue(&temp));
    return tem;
}

Critérios: comparar cod par-a-par (0,6); detectar tamanhos diferentes (0,4); restaurar pilha via double-reversal (0,5); restaurar fila (0,4); retorno correto (0,3).

int mesmasElementos(PilhaEnc *pilha, FilaEnc *fila) {
    PilhaEnc tempP;
    FilaEnc  tempF;
    Produto vP, vF;
    int iguais = 1;
    inicializaPilha(&tempP);
    inicializaFila(&tempF);

    while (!estaVaziaPilha(pilha) && !estaVaziaFila(fila)) {
        vP = pop(pilha);
        vF = dequeue(fila);
        if (vP.cod != vF.cod) iguais = 0;
        push(&tempP, vP);
        enqueue(&tempF, vF);
    }
    /* se uma estrutura ainda tem elementos, tamanhos sao diferentes */
    if (!estaVaziaPilha(pilha) || !estaVaziaFila(fila)) iguais = 0;

    /* restaurar pilha (double-reversal) */
    while (!estaVaziaPilha(&tempP))
        push(pilha, pop(&tempP));
    /* restaurar fila */
    while (!estaVaziaFila(&tempF))
        enqueue(fila, dequeue(&tempF));

    return iguais;
}

Pop da pilha e dequeue da fila percorrem ambas na mesma ordem, permitindo comparação direta. O double-reversal da pilha restaura a ordem original.

Critérios: NULL retorna 1 (0,4); cod ímpar retorna 0 imediatamente (0,5); recursao nas duas subárvores (0,6).

int abpTodosPares(const NodoArv *raiz) {
    if (raiz == NULL) return 1;
    if (raiz->dado.cod % 2 != 0) return 0;
    if (abpTodosPares(raiz->esq) == 0) return 0;
    return abpTodosPares(raiz->dir);
}

NULL → 1 (vazio vacuamente satisfaz). Retorno antecipado ao encontrar o primeiro ímpar evita percurso desnecessário.

Critérios: NULL retorna 0 (0,4); somar recursivamente esq e dir (0,4); identificar exatamente um filho (0,7).

int abpContarComUmFilho(const NodoArv *raiz) {
    int cont;
    if (raiz == NULL) return 0;
    cont = abpContarComUmFilho(raiz->esq)
         + abpContarComUmFilho(raiz->dir);
    if (raiz->esq == NULL && raiz->dir != NULL) cont++;
    if (raiz->esq != NULL && raiz->dir == NULL) cont++;
    return cont;
}

Folhas (sem filhos) e nodos com dois filhos não são contados.

Critérios: NULL retorna 0 (0,4); podar dir quando cod >= x (0,6); contar atual e explorar ambos quando cod < x (0,5).

int abpContarMenoresQue(const NodoArv *raiz, int x) {
    if (raiz == NULL) return 0;
    if (raiz->dado.cod >= x)
        return abpContarMenoresQue(raiz->esq, x);
    return 1
         + abpContarMenoresQue(raiz->esq, x)
         + abpContarMenoresQue(raiz->dir, x);
}

Quando cod >= x, toda a subárvore direita também é >= x (propriedade ABP) — podada.

Critérios: caso base dir==NULL retorna cod (0,6); descer sempre pela direita (0,6); ignorar subárvore esquerda (0,3).

int abpMaiorCod(const NodoArv *raiz) {
    if (raiz->dir == NULL)
        return raiz->dado.cod;
    return abpMaiorCod(raiz->dir);
}

O maior elemento está sempre no extremo direito da ABP. Complexidade O(h), não O(n).

Critérios: NULL retorna (0,3); explorar esq se cod > minCod (0,5); imprimir se no intervalo (0,4); explorar dir se cod < maxCod (0,5); ordem crescente (0,3).

void abpImprimirIntervalo(const NodoArv *raiz, int minCod, int maxCod) {
    if (raiz == NULL) return;
    if (raiz->dado.cod > minCod)
        abpImprimirIntervalo(raiz->esq, minCod, maxCod);
    if (raiz->dado.cod >= minCod && raiz->dado.cod <= maxCod)
        printf("%d - %s\n", raiz->dado.cod, raiz->dado.nome);
    if (raiz->dado.cod < maxCod)
        abpImprimirIntervalo(raiz->dir, minCod, maxCod);
}

In-ordem garante impressão crescente. Poda ambos os lados fora do intervalo. Exemplo: árvore 10→{5,20} com 5→{3,7}, [5,15]: imprime 5, 7, 10.

Critérios: NULL retorna 0 (0,4); podar esq quando cod <= x (0,6); contar atual e explorar ambos quando cod > x (0,5).

int abpContarMaioresQue(const NodoArv *raiz, int x) {
    if (raiz == NULL) return 0;
    if (raiz->dado.cod <= x)
        return abpContarMaioresQue(raiz->dir, x);
    return 1
         + abpContarMaioresQue(raiz->esq, x)
         + abpContarMaioresQue(raiz->dir, x);
}

Simétrico de abpContarMenoresQue: quando cod <= x, toda a subárvore esquerda também é <= x (podada).

Critérios: NULL retorna 0 (0,3); cod no intervalo retorna 1 imediatamente (0,5); descer só pela direita se cod < minCod (0,4); descer só pela esquerda se cod > maxCod (0,4).

int abpExisteNoIntervalo(const NodoArv *raiz, int minCod, int maxCod) {
    if (raiz == NULL) return 0;
    if (raiz->dado.cod >= minCod && raiz->dado.cod <= maxCod) return 1;
    if (raiz->dado.cod < minCod)        /* muito pequeno: busca na direita */
        return abpExisteNoIntervalo(raiz->dir, minCod, maxCod);
    return abpExisteNoIntervalo(raiz->esq, minCod, maxCod); /* muito grande */
}

Retorno antecipado ao encontrar o primeiro elemento no intervalo. Poda um lado por vez usando a propriedade da ABP: O(h) no melhor caso.

Critérios: NULL retorna 0 (0,4); soma cod atual (0,4); chamadas recursivas nas duas subárvores (0,4).

int abpSomaCods(const NodoArv *raiz) {
    if (raiz == NULL) return 0;
    return raiz->dado.cod
         + abpSomaCods(raiz->esq)
         + abpSomaCods(raiz->dir);
}

Percorre toda a árvore em O(n). Mesma estrutura de abpContarNodos, somando cod em vez de 1 por nodo.