Pensamento computacional e resolução de problemas

Uma busca encontra um valor-alvo em uma coleção (geralmente uma array 数组) e retorna sua posição, ou "não encontrado".

Busca linear

Uma busca linear 线性查找 percorre do início ao fim, comparando cada elemento com o alvo:

FOR i ← 1 TO n
    IF A[i] = target THEN
        RETURN i
    ENDIF
NEXT i
RETURN -1   // not found

Nenhuma preparação é necessária, então funciona em qualquer lista. Pior caso O($n$) (alvo no final ou ausente); melhor caso 1 comparação. Use-a em dados não ordenados ou listas pequenas. (O retorno -1 é um valor sentinela — uma posição impossível que significa "não encontrado"; quem chama testa IF result = -1.)

A versão do exame. O Paper 3 pede para completar uma busca linear escrita com uma flag e um loop WHILE, e o Paper 4 pede para escrever uma função que retorne o índice ou uma contagem. Ambos parecem assim:

FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index, Count : INTEGER
    Count ← 0
    FOR Index ← 1 TO 100
        IF Data[Index] = Target THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count          // how many times Target occurs; 0 means not found
ENDFUNCTION

Para parar na primeira correspondência, use um loop WHILE Index <= 100 AND NOT Found que define Found ← TRUE e lembra o índice. As marcas são pelo loop sobre todo elemento, a comparação e o que é retornado quando o valor está ausente.

Busca binária

Uma busca binária 二分查找 precisa dos dados ordenados. Olhe para o elemento do meio; se for o alvo, pronto; se o alvo for menor, busque na metade esquerda, senão na direita — dividindo o intervalo pela metade cada vez:

low ← 1
high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN
        RETURN mid
    ENDIF
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
RETURN -1

Pior caso O($\log_{2} n$) — para um milhão de itens, cerca de 20 comparações. Muito mais rápida que a busca linear em arrays grandes ordenados, mas você deve ordenar primeiro (um custo único O($n \log n$)), vale a pena se buscar muitas vezes.

"Enuncie a condição necessária para uma busca binária." Os dados devem estar em ordem (ordenados, ascendentes ou descendentes, na chave sendo buscada). "Descreva como realizar uma busca binária" (três marcas): (1) encontre o item meio da lista (ou do intervalo atual) e compare-o com o alvo; (2) se corresponder, a busca termina; se o alvo for menor, repita na metade inferior, se maior, na metade superior; (3) continue dividindo pela metade o intervalo até que o item seja encontrado ou o intervalo esteja vazio, o que significa que não está presente.

A versão do exame, com os limites e uma flag, é a que você deve reproduzir quando solicitado a completar o algoritmo:

DECLARE Lower, Upper, Mid : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
    Mid ← (Lower + Upper) DIV 2
    IF Names[Mid] = Target THEN
        Found ← TRUE
    ELSE
        IF Names[Mid] < Target THEN
            Lower ← Mid + 1
        ELSE
            Upper ← Mid - 1
        ENDIF
    ENDIF
ENDWHILE
IF Found THEN
    OUTPUT Mid
ELSE
    OUTPUT "Not found"
ENDIF

"Explique como o desempenho varia com o número de itens." Cada comparação reduz à metade o número de itens restantes, então o número máximo de comparações é aproximadamente $\log_{2} n$: dobrar o tamanho da lista adiciona apenas uma comparação a mais. Isso é O($\log n$). "Compare busca linear e busca binária": uma busca linear precisa de até $n$ comparações (O($n$)) e, em média, metade disso, mas funciona em dados não ordenados; uma busca binária precisa no máximo de $\log_{2} n$ (O($\log n$)) e é muito mais rápida para listas grandes, mas os dados devem estar previamente ordenados e deve permitir acesso direto ao item do meio (um array, não uma lista ligada). Para $1000$ itens: $1000$ contra $10$ comparações.

*Um catálogo de cartões: registros ordenados são o que tornam a busca binária possível — reduza pela metade, olhe, reduza novamente

Bubble sort (Ordenação por bolha)

Um bubble sort 冒泡排序 percorre repetidamente o array, trocando pares adjacentes que estão fora de ordem, assim o maior "bolha" vai para o final a cada passada:

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            temp ← A[i]
            A[i] ← A[i + 1]
            A[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    NEXT i
    IF swapped = FALSE THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

Melhor caso O($n$) (já ordenado, com saída antecipada); médio/pior caso O($n^{2}$). Simples, mas lento para grandes $n$.

Insertion sort (Ordenação por inserção)

Um insertion sort 插入排序 constrói um prefixo ordenado da esquerda, inserindo cada novo elemento em seu lugar desviando os maiores para a direita:

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key
NEXT i

Melhor caso O($n$) (já ordenado); pior caso O($n^{2}$). Bom para arrays pequenos ou quase ordenados. Ordena in place 原地 e é estável 稳定 (mantém a ordem dos elementos iguais).

Rastreamento de uma ordenação

Uma tarefa comum é mostrar o array após cada passagem externa. Para [D, T, H, R] com insertion sort: passada 1 (chave T) sem mudança; passada 2 (chave H) → [D, H, T, R]; passada 3 (chave R) → [D, H, R, T].

Escrever uma ordenação do zero. "Escreva pseudocódigo para ordenar DataArray[1:1000] em ordem crescente" é respondido por um bubble sort completo com flag de saída antecipada, ou um insertion sort, declarado e recuado; ambos obtêm nota máxima se funcionarem para toda entrada:

DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO 1000 - Pass
        IF DataArray[Index] > DataArray[Index + 1] THEN
            Temp ← DataArray[Index]
            DataArray[Index] ← DataArray[Index + 1]
            DataArray[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000

Para ordem decrescente, altere > para <; para ordenar registros ou um array 2D por um campo, compare esse campo mas troque o registro inteiro (ou todas as colunas). Se perguntado a escrever um insertion sort "que realize a mesma tarefa" que um dado bubble sort, mantenha o mesmo nome de array e direção e reproduza o insertion sort acima invertendo a comparação se a ordem for decrescente.

"Descreva duas maneiras pelas quais o desempenho de uma ordenação é afetado pelos dados" (duas marcas). (1) O número de itens: uma ordenação $O(n^{2})$ leva quatro vezes mais tempo para o dobro de itens. (2) O quão perto os dados já estão de estar em ordem: um bubble sort com flag, ou um insertion sort, termina em uma única passada sobre dados já ordenados ($O(n)$) e realiza o máximo de trabalho em dados em ordem inversa; o número de trocas depende de quantos pares estão fora de ordem. (Também aceito: o intervalo ou número de valores duplicados, e se os itens são registros grandes que são caros de mover.) Bubble sort e insertion sort são ambos O($n^{2}$) nos casos pior e médio e O($n$) no melhor caso; quicksort e merge sort são O($n \log n$), que é por que são usados para grandes volumes de dados.

Os Abstract Data Types (ADTs) do Tema 10 aparecem dentro de muitos algoritmos: uma pilha 栈 impulsiona a travessia em profundidade e o desfazer; uma fila 队列 impulsiona a travessia em largura e a ordem de impressão; uma linked list 链表 permite que os dados cresçam e encolham.

ADTs podem ser construídos a partir de outros ADTs, não apenas de arrays: uma queue a partir de duas stacks; uma stack a partir de uma linked list (push = prepend um nó cabeça nó 节点); uma queue a partir de uma linked list com ponteiros de cabeça e cauda pointers 指针; uma binary tree 二叉树 a partir de nós com dois ponteiros de filho; um dictionary 字典 armazena pares chave→valor (muitas vezes em uma hash table). Camadas dessa forma separam responsabilidades — o algoritmo que usa o ADT não precisa saber como ele é construído.

Os ADTs que o exame pede para você descrever e implementar

Stack (último a entrar, primeiro a sair): os itens são adicionados (empilhados) e removidos (desempilhados) na mesma extremidade, o topo; um ponteiro TopOfStack guarda o índice do item no topo. Implementado com um array e aquele único ponteiro: push verifica se a stack não está cheia, incrementa o ponteiro e armazena o item; pop verifica se não está vazia, retorna o item no topo e decrementa o ponteiro.

FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
    IF TopOfStack = 9 THEN      // full (array 0 to 9)
        RETURN FALSE
    ENDIF
    TopOfStack ← TopOfStack + 1
    StackData[TopOfStack] ← Item
    RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
    IF TopOfStack = -1 THEN      // empty
        RETURN -1
    ENDIF
    TopOfStack ← TopOfStack - 1
    RETURN StackData[TopOfStack + 1]
ENDFUNCTION

Queue (primeiro a entrar, primeiro a sair): os itens entram na parte traseira (enfilam) e saem pela frente (desfilam); dois ponteiros e uma contagem. Em uma queue linear, o ponteiro da frente corre pelo array até que o espaço no início seja desperdiçado; uma circular queue 循环队列 faz ambas as ponteiros voltarem com MOD, reutilizando cada célula.

*Uma circular queue: os ponteiros traseiro e frontal avançam com MOD, reutilizando as primeiras células do array assim que seus itens saem

FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
    IF Count = 6 THEN      // full
        RETURN FALSE
    ENDIF
    Rear ← (Rear + 1) MOD 6
    QueueArray[Rear] ← Item
    Count ← Count + 1
    RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
    IF Count = 0 THEN      // empty
        RETURN ""
    ENDIF
    DECLARE Item : STRING
    Item ← QueueArray[Front]
    Front ← (Front + 1) MOD 6
    Count ← Count - 1
    RETURN Item
ENDFUNCTION

Linked list: uma sequência de nodes, cada um segurando um item de dados e um pointer para o próximo node; um start pointer dá o primeiro node e um ponteiro nulo (0 ou $-1$) encerra a lista. Em uma implementação com array, dois arrays paralelos seguram os dados e os ponteiros, e células não utilizadas são encadeadas em uma free list 空闲列表 para que uma inserção saiba onde colocar o novo node.

*Uma linked list em dois arrays: a ordem da lista está nos ponteiros, não nas posições; inserir um nome significa pegar uma célula da free list e religar dois ponteiros

FUNCTION FindInList(Target : STRING) RETURNS INTEGER   // index, or 0 if absent
    DECLARE Current : INTEGER
    Current ← Start
    WHILE Current <> 0
        IF Data[Current] = Target THEN
            RETURN Current
        ENDIF
        Current ← Pointer[Current]
    ENDWHILE
    RETURN 0
ENDFUNCTION

Para inserir em uma lista ordenada: pegue a primeira célula livre (NewNode ← FreeList, FreeList ← Pointer[FreeList]), armazene o item, depois percorra a lista com um ponteiro Previous e Current até Data[Current] > Item ou o fim; defina Pointer[NewNode] ← Current e Pointer[Previous] ← NewNode (ou Start ← NewNode se for o primeiro). Para excluir, religue o node anterior além do excluído e devolva a célula à free list.

Binary tree: um nó raiz, cada nó segurando dados, um left pointer para um subtree de valores menores e um right pointer para um subtree de valores maiores. Implementado como um array 2D (ou três arrays 1D) Tree[Index, 0..2] para left pointer, dados, right pointer, com um root pointer e um next-free pointer.

FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER   // index, or -1
    DECLARE Current : INTEGER
    Current ← Root
    WHILE Current <> -1
        IF Tree[Current, 1] = Target THEN
            RETURN Current
        ENDIF
        IF Target < Tree[Current, 1] THEN
            Current ← Tree[Current, 0]      // go left
        ELSE
            Current ← Tree[Current, 2]      // go right
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Para inserir: armazene o item no próximo nó livre com ambos os ponteiros $-1$; se a árvore estiver vazia, faça-a a root; caso contrário, percorra descendo da root, indo à esquerda ou à direita por comparação, até que o ponteiro que você seguiria fosse $-1$, e defina aquele ponteiro para o novo nó. Um ADT a partir de outro ADT: uma stack é uma linked list onde push e pop funcionam ambos no início; uma queue é uma linked list com um ponteiro de início e um de fim; uma queue pode ser feita a partir de duas stacks (push em uma, pop na outra, movendo tudo quando a segunda estiver vazia); os nós de uma binary tree são records ou objetos ligados por ponteiros, então é construído a partir de uma estrutura ligada de nós. Diga quais operações do novo ADT mapeiam para quais operações do antigo.

*Uma binary tree: cada nó tem até dois nós filhos

*Três travessias depth-first de uma binary tree: pre-order, in-order (ordem ordenada) e post-order

Complexidade temporal

Complexidade temporal 时间复杂度 é como o tempo de execução cresce com o tamanho de entrada $n$, escrito em notação Big-O 大O表示法 (o termo dominante): O(1) constante, O($\log n$) busca binária, O($n$) busca linear, O($n \log n$) boas ordenações, O($n^{2}$) bubble/insertion sort. Uma ordem menor é melhor em escala, mesmo se outro algoritmo for mais rápido para pequenos $n$.

Para tornar isso concreto: para ordenar um milhão de itens, uma ordenação $O(n \log n)$ termina em fração de segundo, enquanto uma ordenação $O(n^{2})$ pode levar minutos.

Exemplo resolvido. Uma lista ordenada contém $1000$ itens. Quantas comparações cada busca precisa no pior caso?

Uma busca linear verifica itens um de cada vez, então pode precisar de até $1000$ comparações — isso é $O(n)$. Uma busca binária reduz a lista pela metade a cada passo, então precisa no máximo de $\lceil \log_2 1000 \rceil = 10$ comparações — isso é $O(\log n)$. Dobrar a lista para $2000$ itens adiciona apenas uma comparação à busca binária, mas até mais $1000$ à busca linear — que é por que a ordem de crescimento, não a velocidade bruta, decide o vencedor em escala.

Descrevendo uma ordem. O(1): o tempo é constante, independente do número de itens (push em uma pilha, leitura de um elemento de array). O($\log n$): o tempo cresce com o logaritmo do número de itens, então dobrar os dados adiciona apenas uma etapa extra fixa (busca binária). O($n$): o tempo cresce proporcionalmente ao número de itens (busca linear, uma passagem por uma lista). O($n \log n$): um pouco pior que linear (classificações eficientes). O($n^{2}$): o tempo cresce com o quadrado do número de itens, então dobrar os dados quadruplica o tempo (bubble sort e insertion sort). "Declare a Big O de uma busca binária de Names[0:99]" é respondida $O(\log n)$, e "descreva seu significado" como acima; Big O mede como o tempo ou memória escala, não o tempo real.

*Como as ordens comuns de crescimento se comparam: uma ordem menor vence em escala

Complexidade de espaço

Complexidade de espaço 空间复杂度 é a memória extra necessária. Bubble sort e insertion sort usam O(1) extra (in-place); merge sort usa O($n$); recursão usa memória de pilha proporcional à sua profundidade. Frequentemente existe um compromisso entre tempo e memória.

Outros critérios

Simplicidade (mais fácil de codificar e manter), estabilidade e adaptabilidade (mais rápido em dados quase ordenados). O algoritmo correto depende dos dados e das restrições.

Algoritmos recursivos usam recursão 递归: a rotina chama-se a si mesma com uma versão menor do mesmo problema, até que um caso base 基本情形 termine a cadeia. Tem duas partes: o caso base (pequeno o suficiente para ser resolvido diretamente — sem ele a recursão nunca para) e o caso recursivo 递归情形 (reduzir a entrada e chamar-se a si mesma).

Fatorial 阶乘:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 OR n = 1 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    ENDIF
ENDFUNCTION

A recursão é natural para problemas autorreferenciais: árvores, divide-and-conquer 分治 (busca binária, merge sort) e dados aninhados. Quando não se adapta bem, um ciclo costuma ser mais limpo.

"Descreva o que significa recursão (duas marcas)." Uma função ou procedimento definido em termos de si mesmo: ela chama-se a si mesma dentro do seu próprio corpo, com uma versão menor do problema cada vez, até que um caso base seja alcançado. "Enuncie três características essenciais da recursão": (1) um caso base (condição de paragem) que retorna um valor sem uma chamada adicional; (2) um caso geral 一般情形 em que a rotina chama-se a si mesma; (3) cada chamada aproxima o problema do caso base (o parâmetro é reduzido), para que a recursão termine. Alguns esquemas adicionam: os valores são retornados conforme as chamadas desenrolam.

"Descreva quando o uso de recursão é benéfico e dê um exemplo." Quando o problema é naturalmente definido em termos de versões menores de si mesmo, de modo que a solução recursiva seja mais curta, clara e próxima da definição matemática do que um ciclo seria: um fatorial ou número de Fibonacci, uma busca binária, percorrer uma árvore binária, merge sort ou quicksort, e processar estruturas aninhadas como pastas dentro de pastas. É uma má escolha quando a profundidade é grande (a pilha pode transbordar) ou quando o mesmo sub-problema é calculado muitas vezes (Fibonacci ingênuo).

Rastreando uma chamada recursiva

Para Factorial(4): as chamadas descem até Factorial(1)=1, depois desenrolar multiplica de volta para cima: 2*1=2, 3*2=6, 4*6=24. Resultado final 24. Rastreie cada chamada pendente numa pilha.

Exemplo resolvido. A função abaixo é dada sem explicação. Rastreie Unknown(3, 5) e indique a sua saída e valor de retorno.

FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
    IF X < Y THEN
        OUTPUT X + Y
        RETURN Unknown(X + 1, Y - 1) + 1
    ELSE
        RETURN 0
    ENDIF
ENDFUNCTION

Chamada 1: $X = 3, Y = 5$: $3 < 5$, saída 8, chama Unknown(4, 4). Chamada 2: $4 < 4$ é falso, retorna 0. Desenrolamento: chamada 1 retorna $0 + 1 = 1$. Saída 8, valor de retorno 1. Escreva o rastro como uma tabela com uma linha por chamada (parâmetros, condição, saída, o que retorna) e faça os retornos da chamada mais profunda para cima: este é o desenrolamento que o gabarito procura.

Exemplo resolvido (Fibonacci). Fib(n) retorna n quando n < 2, caso contrário Fib(n - 1) + Fib(n - 2). Encontre Fib(5).

Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. Assim Fib(3) = 1 + 1 = 2, Fib(4) = 2 + 1 = 3, Fib(5) = 3 + 2 = 5. O caso base é alcançado muitas vezes (Fib(2) é calculado três vezes), razão pela qual esta versão é lenta: faz 15 chamadas para $n = 5$ e dobra aproximadamente as chamadas para cada aumento em $n$.

Convertendo recursão em iteração. Toda rotina recursiva pode ser reescrita com um ciclo, que usa menos memória e é mais rápida: mantenha um resultado acumulado e瞪ue do caso base para cima. Fatorial como um ciclo:

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    DECLARE Result, Count : INTEGER
    Result ← 1
    FOR Count ← 2 TO N
        Result ← Result * Count
    NEXT Count
    RETURN Result
ENDFUNCTION

Ao ser solicitado a alterar uma ordenação por inserção recursiva ou busca em uma iterativa, substitua a auto-chamada por um ciclo sobre o índice pelo qual a recursão estava avançando, e transforme o caso base na condição de saída do ciclo.

Riscos

• recursão infinita se o caso base for omitido — falha com transbordamento de pilha 栈溢出.
• alto uso de memória para recursão profunda.
• lento se repetir trabalho (Fibonacci ingênuo é exponencial — use um ciclo ou memoização 记忆化).

A recursão precisa de cada chamada ter sua própria cópia dos seus parâmetros 参数 e variáveis locais 局部变量. O compilador mantém estes na pilha de chamadas 调用栈. Para cada chamada, empilha um quadro de pilha 栈帧 contendo os parâmetros, as variáveis locais e o endereço de retorno 返回地址 (onde retomar no chamador). Quando a função retorna, o valor de retorno é passado, o quadro é removido e o controle retoma no endereço de retorno.

Porque cada chamada tem seu próprio quadro, chamadas recursivas não sobrepõem as variáveis umas das outras. A pilha pode crescer muito para recursão profunda, razão pela qual recursão muito profunda pode transbordá-la. Este é o mesmo mecanismo de chamada e retorno usado para chamadas ordinárias (não recursivas) — não há um "mecanismo de recursão" especial.

"Explique por que uma pilha é adequada para implementar recursão (três marcas)." Cada chamada recursiva deve salvar seu endereço de retorno, seus parâmetros e suas variáveis locais, e as chamadas são concluídas na ordem invertida àquela em que foram feitas (a última chamada feita é a primeira a terminar), o que é exatamente o comportamento último a entrar, primeiro a sair de uma pilha: cada nova chamada empilha um quadro, e cada retorno remove o quadro mais recente, restaurando o estado do chamador e dizendo-lhe onde continuar. Este é o trabalho do compilador quando traduz código recursivo: ele gera o empilhamento de um quadro de pilha em cada chamada e a remoção em cada retorno, e os quadros são desenrolados conforme os resultados voltam.

Uma questão de definição é avaliada contra wording fixo. Aprenda estas exatamente, e dê apenas uma resposta.

• Buscas: linear não precisa de ordem e O($n$); binária precisa de um array ordenado, divide ao meio a cada passo e é O($\log n$). Saiba ambos os algoritmos de cor, incluindo os limites e a flag.
• Ordenações: bubble com flag de troca, insertion com chave que desloca itens maiores para a direita; ambos O($n^{2}$) no pior caso, O($n$) em dados ordenados. O desempenho depende do número de itens e do quão ordenados eles estão.
• Implementações de TDA são gerenciamento de ponteiros: um ponteiro superior; front, rear e count com MOD; start, ponteiros e uma lista livre; raiz com ponteiros esquerdo e direito. Sempre verifique se está cheio e vazio.
• Big O trata de escalonamento: constante, logarítmica, linear, quadrada. Diga "dobrar os dados adiciona uma comparação" para uma busca binária.
• Recursão: caso base, caso geral, progresso em direção ao caso base; benéfico quando o problema é definido em termos de si mesmo; uma pilha guarda os endereços de retorno e variáveis porque as chamadas retornam em ordem inversa. Rastreie com uma tabela e desenrole da chamada mais profunda.

Erros comuns

• Usar uma busca binária em dados não ordenados, ou em uma lista ligada; e definir Lower ← Mid em vez de Mid + 1, o que loopa eternamente.
• Um loop interno de bubble sort que roda até o fim do array a cada passada, ou uma troca sem variável temporária.
• Um push ou enqueue que não testa para cheio, ou um pop ou dequeue que não testa para vazio.
• Mover o ponteiro frontal da fila sem MOD em uma fila circular, ou tratar front = rear como significando sempre vazio.
• Inserir em uma lista ligada deslocando o conteúdo do array; apenas os ponteiros mudam.
• Uma função recursiva sem caso base, ou cujas chamadas recursivas não tornam o problema menor.
• Rastrear uma chamada recursiva mas esquecer adicionar o trabalho pendente no caminho de volta para cima.
• Responder "por que uma pilha" com "porque é rápida"; a razão é a ordem último-entra-primeiro-sai dos retornos.