ENADE — Algoritmos
e Estruturas de Dados

Considere o código C abaixo, que implementa uma pilha com vetor estático:

struct Pilha { int elementos[100]; int topo; };
void push(struct Pilha *p, int v) { p->elementos[p->topo++] = v; }
int  pop (struct Pilha *p)       { return p->elementos[--p->topo]; }
int main() {
    struct Pilha *p = (struct Pilha*) malloc(sizeof(struct Pilha));
    p->topo = 0;
    push(p,2); push(p,3); push(p,4);
    pop(p); push(p,2);
    int a = pop(p) + pop(p);  /* a = 2+3 = 5 */
    push(p, a);
    a += pop(p);              /* a = 5+5 = 10 */
    printf("%d\n", a);        /* imprime 10 */
    return 0;
}

Considere as afirmativas:
I. As operações push e pop têm complexidade O(1).
II. Substituindo int a = pop(p) + pop(p) por int a = pop(p); a += pop(p), o valor impresso seria o mesmo.
III. Como a pilha foi alocada com malloc, a chamada a free(p) ao final do main é opcional.

Considere a estrutura de lista simplesmente encadeada e a função recursiva abaixo:

struct ListaEncadeada {
    int dado;
    struct ListaEncadeada *proximo;
};
void mostrar(struct ListaEncadeada *lista) {
    if (lista == NULL) return;
    mostrar(lista->proximo);
    printf("%d\n", lista->dado);
}

a) Determine a complexidade de tempo da função mostrar em função do número N de elementos da lista, justificando sua resposta.
b) Reescreva mostrar de forma não-recursiva, utilizando uma estrutura de pilha auxiliar para obter a mesma saída (elementos em ordem inversa da lista).

Um comitê olímpico registra os recordes mundiais em uma estrutura de dados na ordem cronológica em que são estabelecidos. A principal operação de consulta é recuperar o recorde mais recente primeiro. Qual estrutura de dados é a mais adequada para implementar essa funcionalidade?

Uma biblioteca Java oferece as seguintes interfaces/classes para estruturas de dados:
Classe A — permite inserção e remoção nas duas extremidades;
Classe B — cada nó armazena uma referência apenas para o próximo elemento;
Classe C — remove elementos na ordem inversa à de inserção;
Classe D — remove sempre o elemento inserido há mais tempo.
Quais são, respectivamente, as estruturas que correspondem às classes A, B, C e D?

Um sistema hospitalar de triagem utiliza o código C abaixo para gerenciar uma fila com prioridade baseada na cor do cartão (A = amarelo, V = verde):

struct lista { int numero; char cor; struct lista *prox; };

void inserir_fim(struct lista **inicio, int num, char c) { /* insere no fim */ }

void inserir(struct lista **inicio, int num, char cor) {
    if (cor == 'V') inserir_fim(inicio, num, cor);
    else            inserir_prioridade(inicio, num, cor);
}

As chegadas são: 10-V, 11-V, 5-A, 12-V, 6-A. Após todas as inserções a fila deve ser: [5, 6, 10, 11, 12].
Implemente a função inserir_prioridade para pacientes amarelos, que devem ser inseridos após o último amarelo já na fila (antes dos verdes).

Considere as implementações em C a seguir. Qual delas provoca memory leak (vazamento de memória)?

/* A */ char *f(){ char *s=malloc(10); strcpy(s,"ok"); free(s); return NULL; }
/* B */ void g(){ float x; x=3.14; }
/* C */ int h(char *data){ char *s=malloc(60);
         if(strlen(data)>50){ return -1; } /* free(s) nunca chamado */
         strcpy(s,data); free(s); return 0; }
/* D */ char *k(){ char *s=malloc(20); return s; } /* chamador libera */
/* E */ void m(){ char *s=malloc(8); free(s); free(s); } /* double free */

Um controlador PID calcula: termo proporcional K_p·e(t), termo integral K_i·∑e(t) e termo derivativo K_d·Δe(t). Analise as afirmativas sobre as estruturas de dados adequadas para cada termo:
I. Para o termo integral, é necessária uma fila para armazenar o histórico completo de erros.
II. O termo proporcional é calculado diretamente como K_p·e(t), sem necessidade de estrutura de dados adicional.
III. Para o termo derivativo, uma pilha contendo as duas amostras de erro mais recentes é adequada.

Analise as afirmativas sobre Tipos Abstratos de Dados (TDA):
I. A especificação de um TDA deve incluir detalhes sobre a representação interna dos dados.
II. Em linguagens orientadas a objetos, um TDA pode ser implementado por meio de composição ou herança.
III. Se o TDA S pode ser substituído pelo TDA T em qualquer contexto, então S é subtipo de T.
IV. O encapsulamento fornecido por um TDA tem efeito positivo sobre a modularidade e a manutenibilidade do software.

Uma sequência de caracteres de DNA A,G,T,C,A,G,T,T é inserida, um a um, em uma Estrutura 1. Os elementos são retirados da Estrutura 1 e inseridos em uma Estrutura 2; obtendo-se a sequência T,T,G,A,C,T,G,A. Os elementos são retirados da Estrutura 2 obtendo-se novamente T,T,G,A,C,T,G,A. Quais são, respectivamente, as Estruturas 1, 2 e o tipo de leitura final?

Sobre uma pilha p inicialmente vazia, são executadas as seguintes operações na ordem indicada:
PUSH(p,10), PUSH(p,5), PUSH(p,3), PUSH(p,40), POP(p), PUSH(p,11), PUSH(p,4), PUSH(p,7), POP(p), POP(p).
Após essas operações, qual é o valor do elemento no topo e qual é a soma de todos os elementos restantes na pilha?

A figura mostra uma Árvore Binária de Pesquisa (ABP) com raiz 15: subárvore esquerda com raiz 10 (filhos 7 e 13; 13 tem filho direito 14) e subárvore direita com raiz 20 (filhos 17 e 25). Analise as afirmativas:
I. A ABP permite busca eficiente de forma análoga à busca binária em vetor ordenado.
II. A árvore está desbalanceada porque possui número ímpar de nós.
III. O percurso pós-ordem produz os elementos em ordem decrescente.
IV. A complexidade de busca nessa árvore é O(log n) no caso médio.

Considere a árvore AVL com raiz 13: filho esquerdo 10 (com filhos 5 e 11; 5 tem filhos 4 e 8) e filho direito 15 (com filho direito 16). Após inserir a chave 3 (filho esquerdo de 4), ocorre desbalanceamento. Qual das opções representa corretamente a árvore AVL após a rotação necessária?

Uma árvore binária de busca (ABB) é construída com a inserção das chaves na seguinte ordem: 27, 34, 40, 18, 23, 5, 25, 36, 10, 7, −2. Analise as afirmativas sobre a árvore resultante:
A) A árvore possui 5 níveis e 6 nós na subárvore esquerda da raiz principal.
B) O percurso pré-ordem produz: −2, 7, 10, 5, 25, 23, 18, 36, 40, 34, 27.
C) O percurso em-ordem produz: −2, 5, 7, 10, 18, 23, 25, 27, 34, 36, 40.
D) O percurso pré-ordem produz os elementos em ordem crescente.
E) Uma árvore binária de 10 níveis pode armazenar no máximo 1 023 nós.

O código C a seguir implementa as funções heapify e buildHeap para max-heap:

void heapify(int v[], int n, int i) {
    int maior = i, esq = 2*i+1, dir = 2*i+2;
    if (esq < n && v[esq] > v[maior]) maior = esq;
    if (dir < n && v[dir] > v[maior]) maior = dir;
    if (maior != i) { int t=v[i]; v[i]=v[maior]; v[maior]=t;
                      heapify(v, n, maior); }
}
void buildHeap(int v[], int n) {
    for (int i = n/2-1; i >= 0; i--) heapify(v, n, i);
}

Dado o vetor {2, 5, 8, 13, 21, 1, 3, 34}:
a) Execute buildHeap e mostre o vetor resultante (max-heap).
b) Determine a complexidade de tempo de heapify em função de n.

Considere uma Árvore AVL inicialmente com os elementos {21, 2, 9, 15, 27, 36, 50}.
a) Construa a ABB balanceada resultante justificando a posição de cada elemento.
b) Insira as chaves 9, 27 e 50 nessa ordem em uma AVL vazia e descreva as rotações necessárias após cada inserção desequilibrante.
c) Insira as chaves 9, 27, 50, 15, 2, 21, 36 em uma AVL vazia; identifique o tipo de rotação dupla gerada e mostre a árvore resultante.

Considere o pseudocódigo abaixo para o percurso pré-ordem iterativo com pilha:

ptr ← raiz
enquanto ptr ≠ λ faça
    escreve ptr.chave
    se ptr.dir ≠ λ então push(ptr.dir)
    se ptr.esq ≠ λ então push(ptr.esq)
    ptr ← pop()

Analise as afirmativas:
I. O algoritmo visita cada nó da árvore exatamente uma vez.
II. Quando a pilha está vazia, pop() retorna λ, encerrando o laço.
III. As operações push e pop têm complexidade O(1).
IV. A complexidade de tempo do algoritmo é O(n).

Sobre heaps binários usados como filas de prioridade para recuperação de informação, analise as afirmativas:
I. Um heap binário é uma Árvore Binária de Pesquisa (ABP); a complexidade de buildHeap é O(n log n).
II. Em um heap com n elementos armazenados em vetor, o pai do elemento na posição i está na posição 2i+1.
III. Extrair os m documentos de maior prioridade de um heap com n documentos custa O(m log n).
IV. Encontrar o elemento máximo em um max-heap custa O(1).

Em uma ABP são examinados os seguintes nós (em ordem) ao buscar a chave 287. Quais sequências são possíveis numa ABP válida?
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

Dado um vetor ordenado v[1..n] com n = 2^m−1 elementos, construa uma ABP perfeitamente balanceada a partir desse vetor sem comparações adicionais.
a) Defina a estrutura do nó em C (struct nodo).
b) Escreva a função recursiva CriaABP(v, i, j) que cria a ABP a partir do subvetor v[i..j], usando o elemento médio como raiz.

Considere a árvore binária com raiz 33: filho esquerdo 15 e filho direito 41; 41 tem filhos 38 (com filho esquerdo 34) e 47 (com filhos 43 e 49).
a) Liste os nós visitados em DFS (busca em profundidade) a partir do nó 41.
b) Liste o percurso pré-ordem completo da árvore.
c) Insira o valor 21 na árvore como filho direito de 15; depois remova 47 (substituindo pelo sucessor em-ordem) e insira 48.

Uma tabela hash T possui 9 posições (índices 0 a 8) com encadeamento exterior e função h(k) = k mod 9. São realizadas as inserções: insere(13,6); insere(46,7); insere(20,22); insere(28,25); insere(19,26); insere(17,9). Analise as afirmativas sobre o estado da tabela após todas as inserções:
I. No índice 1: (46,7)→(28,25)→(19,26)→NULO.
II. No índice 2: (20,22)→NULO; no índice 4: (13,6)→NULO; no índice 8: (17,9)→NULO.
III. Nenhuma posição permanece completamente vazia.
IV. Todas as inserções produzem colisão.

Uma tabela hash com 23 endereços utiliza h(x) = x mod 23 com encadeamento exterior. Insira as chaves na seguinte ordem: 44, 46, 49, 70, 27, 71, 90, 97, 95.
a) Identifique todos os pares de chaves que colidem (mesma posição na tabela).
b) Mostre o estado final da tabela indicando as listas em cada posição ocupada.

Pesquisa binária em vetor ordenado de n elementos:
a) Escreva o algoritmo de busca binária em pseudocódigo (versão iterativa), indicando claramente os índices extremos e o cálculo do meio.
b) Determine o número máximo de comparações em função de n e justifique usando análise de complexidade assintótica.

Um arquivo texto contém N cidades, uma por linha, em ordem alfabética. Um programa lê o arquivo sequencialmente, linha a linha, para buscar uma cidade pelo nome. Qual é a complexidade de tempo dessa busca no pior caso?

Considere o código C que define funcao1 (busca sequencial) e funcao2 (busca binária recursiva) em um vetor TAM=10: {1,3,5,7,9,11,13,15,17,19}. A chamada printf("%d - %d", funcao1(vetor,15), funcao2(vetor,15,0,TAM-1)) é executada. Analise:
I. O resultado impresso é 7 - 7 (índice do elemento 15 em ambas as funções).
II. Para esse vetor, funcao1 é mais eficiente que funcao2 no pior caso.
III. funcao2 é uma implementação iterativa.

O código de Insertion Sort abaixo contém dois erros lógicos (linhas 08 e 10). Qual das alternativas apresenta a correção correta?

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

Considere a implementação do Quicksort com partição de Lomuto (pivô = último elemento). Analise as afirmativas:
I. No pior caso, a profundidade da recursão é O(n), exigindo O(n) de espaço na pilha de chamadas.
II. O Quicksort é um algoritmo recursivo e estável.
III. A complexidade de tempo médio do Quicksort é O(n log n).
IV. Escolher sempre o primeiro elemento como pivô torna o Quicksort mais eficiente em vetores já ordenados.

Considere uma implementação de busca binária em Python com recursão em cauda. Analise as afirmativas sobre possíveis refatorações:
I. Trocar a ordem das linhas 10 e 12 no código não altera o resultado da função.
II. Substituir a chamada recursiva em cauda por um laço while True elimina a recursão em cauda mantendo o resultado.
III. Introduzir variáveis auxiliares remove a recursão em cauda da função.
IV. Reorganizar o código para conter uma única chamada recursiva ao final mantém o resultado para qualquer entrada.

Qual das implementações Java do MergeSort abaixo está correta?

/* A */ void sort(int[] a,int lo,int hi){ if(hi==lo) return;
         int mid=lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); }
/* B */ void sort(int[] a,int lo,int hi){ if(hi>lo) return;
         int mid=lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); }
/* C */ void sort(int[] a,int lo,int hi){ if(hi<=lo) return;
         int mid=lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid,hi); merge(a,lo,mid,hi); }
/* D */ void sort(int[] a,int lo,int hi){ if(hi>lo) return;
         int mid=lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); }
/* E */ void sort(int[] a,int lo,int hi){ if(hi<=lo) return;
         int mid=lo+(hi-lo)/2; sort(a,lo,mid); sort(a,mid+1,hi); merge(a,lo,mid,hi); }

Uma rede de varejo possui tabela X com N registros e precisa eliminar duplicatas. São propostos dois algoritmos:
Algoritmo A (busca sequencial): para cada registro, verifica todos os anteriores — O(N²).
Algoritmo B (quicksort + varredura): ordena a tabela e remove duplicatas consecutivas em O(N log N).
a) Quantas comparações no máximo realiza o Algoritmo A?
b) Quantas comparações na varredura pós-ordenação do Algoritmo B?
c) Identifique os parâmetros a, b, c, d da chamada recursiva do quicksort: particiona(X, a, b) e particiona(X, c, d).
d) Implemente a função particiona usando trocas.

Analise as afirmativas sobre algoritmos de ordenação:
I. O algoritmo de insertion sort tem complexidade de tempo O(n × log n) no pior caso.
II. Um algoritmo de ordenação é estável se não altera a posição relativa de elementos com chaves iguais.
III. A escolha do pivô influencia a eficiência do algoritmo quicksort.
IV. Os algoritmos bubble sort e insertion sort têm o mesmo número médio de comparações.

Um algoritmo de ordenação divide o problema de n elementos em duas metades recursivamente e combina as soluções. Sua relação de recorrência é T(n) = 2T(n/2) + Θ(n). Qual é a complexidade de tempo desse algoritmo?

Aplica-se busca binária a vetores ordenados de tamanho 50, 1 000 e 300. Qual é o número máximo de comparações para cada tamanho (usando ⌊log₂n⌋ + 1)?

Execute o Bubble Sort sobre V = {2, 0, 4, 3, 1}. Analise os rastreamentos abaixo, onde I e J são os índices externo e interno do algoritmo (J percorre comparando pares adjacentes):
I. I=0, J=1: após essa comparação V = {0, 2, 4, 3, 1}.
II. I=1, J=0: após a passagem I=1, V = {0, 2, 3, 1, 4}.
III. I=1, J=2: após essa comparação V = {0, 2, 1, 3, 4}.

O pseudocódigo da busca binária em V[0..9] está incompleto (linhas 6, 8 e 12 em branco). Qual sequência de instruções completa corretamente o algoritmo?

01 Função BuscaBin(V, n, x)
02   F ← n - 1
03   /* linha 06: inicializa C */
04   enquanto C ≤ F faça
05     M ← /* linha 08 */
06     se V[M] = x então retorna M
07     se V[M] < x então /* linha 12 */
08     senão F ← M - 1
09   retorna -1

Analise o custo computacional dos algoritmos a seguir, que calculam P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ··· + a₁x + a₀, com coeficientes armazenados em a[0..n] e x dado:

Algoritmo 1 (ingênuo):
soma = a[0]
Repita para i = 1 até n
  Se a[i] ≠ 0.0 então
    potência = x
    Repita para j = 2 até i
      potência = potência * x
    soma = soma + a[i] * potência
  Fim se
Imprima(soma)

Algoritmo 2 (Horner):
soma = a[n]
Repita para i = n-1 até 0 passo -1
  soma = soma * x + a[i]
Imprima(soma)

Avalie as asserções e a relação entre elas:
I. Os algoritmos possuem a mesma complexidade assintótica.
PORQUE
II. Para o melhor caso, ambos os algoritmos possuem complexidade O(n).

Qual o valor de retorno da função a seguir, caso n = 27?

int recursao (int n) {
    if (n <= 10) {
        return n * 2;
    }
    else {
        return recursao(recursao(n/3));
    }
}

A sequência de Fibonacci começa em 1, 1 e cada elemento subsequente é a soma dos dois anteriores. A função fib abaixo calcula o n-ésimo elemento:

unsigned int fib (unsigned int n)
{
    if (n < 2)
        return 1;
    return fib(n - 2) + fib (n - 1);
}

Avalie as afirmações:
I. A complexidade de tempo da função fib é exponencial no valor de n.
II. A complexidade de espaço da função fib é exponencial no valor de n.
III. É possível implementar uma versão iterativa de fib com complexidade de tempo linear e de espaço constante.

Considere a função recursiva F a seguir, que em sua execução chama a função G:

void F(int n) {
    if(n > 0) {
        for(int i = 0; i < n; i++) {
            G(i);
        }
        F(n/2);
    }
}

Avalie as afirmações:
I. A equação de recorrência que define a complexidade de F é a mesma do algoritmo mergesort.
II. O número de chamadas recursivas da função F é Θ(log n).
III. O número de vezes que a função G da linha 4 é chamada é O(n log n).

Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P. Avalie as asserções e a relação entre elas:
I. A descoberta do cientista implica P = NP.
PORQUE
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-Completos.

Na matemática, um produtório é definido como ∏ᵢ₌ₘⁿ xᵢ = xₘ × xₘ₊₁ × ··· × xₙ₋₁ × xₙ. Com base nessa equação, e considerando que xᵢ = i + 1/i (com i > 0), faça o que se pede:
a) Escreva uma função iterativa, em linguagem C, que receba os parâmetros de limite inferior m e superior n, calcule e retorne o resultado do produtório. (5,0 pontos)
b) Escreva uma função recursiva, em linguagem C, que receba os parâmetros de limite inferior m e superior n, calcule e retorne o resultado do produtório. (5,0 pontos)

O código a seguir define duas funções em linguagem funcional (Haskell) que manipulam listas de inteiros:

enade :: [Int] -> [Int]
enade [] = []
enade (cabeca:cauda) = auxiliar cabeca (enade cauda)
auxiliar :: Int -> [Int] -> [Int]
auxiliar x [] = [x]
auxiliar x (cabeca:cauda)
  | (x `mod` 2 == 0) = x:cabeca:cauda
  | otherwise = cabeca:auxiliar x cauda

Considerando o código apresentado, se a função enade for executada com a lista [1, 2, 3, 4, 5, 6, 7, 8], o resultado será

Vetores de tamanho dinâmico são muito utilizados para armazenar listas e tabelas hash. Uma técnica para implementá-los dobra o tamanho do vetor quando o número de itens ultrapassa o tamanho atual. Essa operação requer alocar memória para o dobro do tamanho e copiar todos os elementos para o novo vetor. Considere uma lista linear implementada com um vetor dinâmico, com vetor de tamanho inicial para comportar apenas 1 item e todos os itens com o mesmo tamanho.
Considerando uma sequência de n inserções no final dessa lista, o tempo médio por inserção e o tempo total gasto para executar todas as n operações são, respectivamente, da ordem de

No modo recursivo de representação, a descrição de um conceito faz referência ao próprio conceito. Julgue os itens abaixo, com relação à recursividade como paradigma de programação:
I. São elementos fundamentais de uma definição recursiva: o caso-base (base da recursão) e a reaplicação da definição.
II. O uso da recursão não é possível em linguagens com estruturas para orientação a objetos.
III. As linguagens de programação funcionais têm, na recursão, seu principal elemento de repetição.
IV. No que diz respeito ao poder computacional, as estruturas iterativas e recursivas são equivalentes.
V. Estruturas iterativas e recursivas não podem ser misturadas em um mesmo programa.
Estão certos apenas os itens

No famoso jogo da Torre de Hanói, é dada uma torre com discos de raios diferentes, empilhados por tamanho decrescente em um dos três pinos dados. O objetivo do jogo é transportar toda a torre para um dos outros pinos, de acordo com as regras: apenas um disco pode ser deslocado por vez, e em todo instante todos os discos precisam estar em um dos três pinos; além disso, em nenhum momento um disco pode ser colocado sobre um disco de raio menor que o dele; é claro que o terceiro pino pode ser usado como local temporário para os discos.
Imaginando que se tenha uma situação em que a torre inicial tenha um conjunto de 5 discos, qual o número mínimo de movimentações de discos que deverão ser realizadas para se atingir o objetivo do jogo?

Considere que, durante a análise de um problema de programação, tenha sido obtida a seguinte fórmula recursiva que descreve a solução para o problema:
C(i,j) = 0, se i=0 ou j=0; 1+C(i−1,j−1) se 0<i≤M, 0<j≤N e i=j; max{C(i,j−1), C(i−1,j)} se 0<i≤M, 0<j≤N e i≠j
Qual a complexidade da solução encontrada?

A análise de complexidade provê critérios para a classificação de problemas com base na computabilidade de suas soluções. Nesse contexto, julgue os itens a seguir:
I. É possível demonstrar que P ⊆ NP e NP ⊆ P.
II. É possível demonstrar que se P ≠ NP, então P ∩ NP-Completo = ∅.
III. Se um problema Q é NP-difícil e Q ∈ NP, então Q é NP-completo.
IV. O problema da satisfatibilidade de uma fórmula booleana F foi provado ser NP-difícil e NP-Completo.
V. Encontrar o caminho mais curto entre dois vértices dados em um grafo de N vértices e M arestas não é um problema da classe P.
Estão certos apenas os itens

Os números de Fibonacci constituem uma sequência na qual os dois primeiros elementos são 0 e 1 e os demais, a soma dos dois elementos imediatamente anteriores: fib(0)=0, fib(1)=1, fib(n)=fib(n−1)+fib(n−2) se n>1. A implementação abaixo em linguagem funcional não reutiliza resultados previamente computados:

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Considerando o programa acima, quantas chamadas são feitas à função fib para computar fib 5?

Os termos da sequência de Fibonacci são definidos por Fibonacci(0)=0, Fibonacci(1)=1, Fibonacci(n)=Fibonacci(n−1)+Fibonacci(n−2). Uma solução recursiva para o cálculo do i-ésimo termo é dada pela função a seguir:

funcao fibonacci(inteiro longo n)
   se((n=0) OU (n=1)) entao
       retorne n
   senao
       retorne fibonacci(n-1) + fibonacci(n-2)
   fim se
fim

Acerca da execução recursiva dessa função, assinale a opção incorreta.

Os números de Fibonacci correspondem a uma sequência infinita na qual os dois primeiros termos são 0 e 1. Cada termo da sequência, à exceção dos dois primeiros, é igual à soma dos dois anteriores, conforme a relação de recorrência: fₙ = fₙ₋₁ + fₙ₋₂
Desenvolva dois algoritmos, um iterativo e outro recursivo, que, dado um número natural n > 0, retorna o n-ésimo termo da sequência de Fibonacci. Apresente as vantagens e desvantagens de cada algoritmo. (valor: 10,0 pontos)

O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação. A classe P contém os problemas cujas soluções podem ser eficientemente obtidas (algoritmos de pior caso polinomial). A classe NP contém os problemas para os quais uma solução pode ser eficientemente verificada. Um problema é NP-completo se pertence à NP e todo problema em NP pode ser eficientemente transformado nesse problema.
Considerando as noções de complexidade computacional apresentadas acima, analise as afirmações:
I. Existem problemas na classe P que não estão na classe NP.
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P, então A está na classe P.
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
IV. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.
É correto apenas o que se afirma em

A busca primeiro em profundidade (DFS) é um algoritmo de exploração sistemática em grafos, em que as arestas são exploradas a partir do vértice v mais recentemente descoberto que ainda tem arestas inexploradas saindo dele. Quando todas as arestas de v são exploradas, a busca regressa para explorar as arestas que deixam o vértice a partir do qual v foi descoberto. O processo continua até que todos os vértices acessíveis a partir do vértice inicial sejam explorados.
Considere o grafo dirigido com vértices {p, q, r, s, t, u, w, x, y, z} e arestas dirigidas (q→s, q→t, q→w, s→p, p→w, w→s, t→x, t→y, x→z, z→x, y→q, r→u, r→y, u→y).
a) Mostre a sequência de vértices descobertos durante a execução de uma busca em profundidade com controle de estados repetidos, utilizando o vértice r como inicial. No caso de um vértice explorado ter mais de um vértice adjacente, utilize a ordem alfabética crescente como critério para priorizar a exploração. (valor: 7,0 pontos)
b) Faça uma representação da matriz de adjacências desse grafo, podendo os zeros ser omitidos nessa matriz. (valor: 3,0 pontos)

A figura exibe um grafo que representa um mapa rodoviário, com vértices como cidades (i, j, k, w e outros) e arestas como vias com pesos de tempo de deslocamento. Considerando que os tempos de ida e volta são iguais para qualquer via, avalie as afirmações acerca desse grafo:
I. Dado o vértice de origem i, o algoritmo de Dijkstra encontra o menor tempo de deslocamento entre a cidade i e as demais cidades do grafo.
II. Uma árvore geradora de custo mínimo gerada pelo algoritmo de Kruskal contém um caminho de custo mínimo cuja origem é i e cujo destino é k.
III. Se um caminho de custo mínimo entre os vértices i e k contém o vértice w, então o subcaminho de origem w e destino k deve também ser mínimo.

A teoria dos grafos estuda as relações entre elementos em um determinado conjunto. Um grafo G(V,E) é determinado por um conjunto não vazio de vértices (V) e um subconjunto de pares de vértices não ordenados, chamados arestas (E). A figura seguinte representa a possibilidade de voos de uma companhia aérea tal que V = {Porto Alegre, Curitiba, São Paulo, Rio de Janeiro e Brasília} e E = {{Curitiba, São Paulo}, {São Paulo, Rio de Janeiro}, {Porto Alegre, Rio de Janeiro}, {São Paulo, Brasília}}. Avalie as afirmações:
I. São Paulo é adjacente a Porto Alegre.
II. Porto Alegre possui valência igual a 2.
III. Rio de Janeiro é incidente em São Paulo e Porto Alegre.
IV. Curitiba possui comprimento igual a 2.

O algoritmo de Dijkstra para o problema do caminho mínimo em dígrafos com pesos utiliza uma fila de prioridades de vértices, na qual as prioridades são uma estimativa do custo final. A cada iteração, um vértice é retirado da fila e os arcos que começam nesse vértice são analisados. Considere o grafo a seguir com arcos: D→A(5), D→B(9), D→E(5), D→F(1), A→B(2), B→C(8), E→B(1), E→C(5), F→E(3), F→G(1), G→E(1). Deseja-se conhecer o custo de um caminho mínimo para cada vértice a partir do vértice D. Considere que −1 representa custo "infinito". Assinale a alternativa que representa a estimativa de custo após duas iterações do algoritmo.

Uma fazenda possui um único poço artesiano que deve abastecer n bebedouros para o gado. Deseja-se determinar um projeto de ligação entre esses n+1 pontos através de encanamentos com a menor extensão total. Um algoritmo proposto para a solução do problema executa os seguintes passos: (1) Crie n+1 conjuntos unitários, cada um contendo um dos pontos; (2) Crie um conjunto D contendo um registro para cada combinação possível de dois pontos distintos a serem ligados (campos cᵢ, cⱼ e d); (3) Enquanto D não estiver vazio faça: 3.1. Remova o registro de D com o menor valor de distância d; 3.2. Se os valores de cᵢ e cⱼ do registro removido pertencerem a conjuntos distintos de C, então: 3.2.1. Substitua estes dois conjuntos pela união entre eles; 3.2.2. Guarde o registro removido em um conjunto-solução.
Com base na descrição do problema e do algoritmo proposto, conclui-se que

Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos térmicos e químicos para ficar pronto. Cada uma das n etapas de tratamento é realizada uma única vez na mesma caldeira. Além do custo próprio de cada etapa do tratamento, existe o custo de se passar de uma etapa para outra (dependendo da sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la para evitar a reação entre os produtos químicos utilizados). Assuma que o processo de fabricação inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a sequência de tratamentos que possibilite fabricar o produto com o menor custo total. Nessa situação, conclui-se que

O gestor de um hotel precisa satisfazer a demanda de vários grupos de eventos pelo uso exclusivo de auditórios por uma semana utilizando o menor número possível de auditórios. A tabela apresenta os conflitos de demandas dos grupos de eventos para todos os dias na semana, em que o valor 1 em uma célula indica que um determinado grupo precisará usar um auditório no mesmo horário que outro grupo e o valor 0 indica que não há conflito entre os dois grupos:
G1–G2: 1, G1–G3: 1, G1–G4: 1, G1–G5: 1, G2–G3: 1, G2–G4: 1, G2–G5: 0, G3–G4: 0, G3–G5: 1, G4–G5: 0.
Nessa situação, o número mínimo de auditórios que satisfaz todas as demandas é de

Protocolos de roteamento de estado de enlace utilizam difusão por spanning tree para evitar a transmissão de pacotes redundantes na rede. Uma spanning tree de um grafo G=(N,E) é um grafo G'=(N,E') tal que E' é um subconjunto de E, G' é conexo, não possui ciclos e contém todos os nós originais em G. Se cada enlace tiver um custo associado e o custo de uma árvore for a soma dos custos dos enlaces, então uma árvore cujo custo seja o mínimo entre todas as spanning trees do grafo é denominada uma spanning tree mínima.
Considere uma rede composta por 6 roteadores (A, B, C, D, E e F) com os seguintes custos de enlace: A–B: 2, A–C: 2, B–C: 2, B–D: 3, C–D: 3, C–E: 1, C–F: 1, D–F: 2, E–F: 1.
Neste cenário, o custo da spanning tree mínima correspondente é, exatamente:

Suponha que uma empresa de transportes deseje calcular uma rota de Manaus para São Paulo utilizando a estratégia da busca gulosa, técnica de busca local que seleciona a melhor alternativa disponível a cada passo. Observe um grafo de conexão de cidades até o destino final e o quadro com estimativas de distância de São Paulo até as demais cidades do grafo: Manaus=2693km, Porto Velho=2464km, Macapá=2665km, Belém=2463km, Palmas=1489km, Cuiabá=1326km, Goiânia=809km, São Paulo=0km. Com base nessas informações, a solução encontrada a partir da utilização do algoritmo será

Deseja-se supervisionar as redes de comunicação de dados de um conjunto de empresas. Cada empresa tem a sua própria rede, que é independente das redes das outras empresas e é constituída de ramos de fibra óptica. Cada ramo conecta duas filiais distintas (ponto-a-ponto) da empresa. Há, no máximo, um ramo de fibra interligando diretamente um mesmo par de filiais. A tabela abaixo apresenta algumas informações acerca das redes dessas empresas: E1(9 filiais, 18 ramos), E2(10 filiais, 45 ramos), E3(14 filiais, 13 ramos), E4(8 filiais, 24 ramos). Com relação à situação apresentada, é correto deduzir que:
I. no caso da empresa E1, a falha de um ramo de rede certamente fará que, ao menos, uma filial não possa mais comunicar-se diretamente com todas as outras filiais da empresa.
II. na rede da empresa E2, a introdução de um novo ramo de rede certamente violará a informação de que há somente um par de fibras entre duas filiais.
III. no caso da empresa E3, a falha de um único ramo de rede certamente fará que, ao menos, uma filial não possa mais comunicar-se, direta ou indiretamente, com todas as outras filiais da empresa.
IV. na rede da empresa E4, todas as filiais da empresa comunicam-se entre si diretamente.

Considere o diagrama de Hasse apresentado abaixo, com os vértices Adriano (topo), Ronaldo (segundo nível), Emerson e José Roberto (terceiro nível, ambos ligados a Ronaldo), e Marcos (base, ligado a Emerson e José Roberto). Assinale a opção que apresenta uma lista ordenada, da esquerda para a direita, que preserva a ordem do diagrama.

Num grafo de rotas entre as cidades A e M, cada nó representa uma cidade e cada ramo uma rodovia com peso = distância em km. Os valores h (distância em linha reta de cada cidade até M) são fornecidos em uma tabela: A=44,72 B=20,00 C=33,54 D=25,00 E=30,67 F=22,36 G=14,14 H=10,00 I=11,18 J=5,00 K=40,00 L=20,00. Julgue os itens relativos a algoritmos de busca:
I. Utilizando-se o algoritmo A*, a rota entre A e M encontrada no problema acima é ACDFLM e o custo do caminho é 56,18.
II. Utilizando-se a busca gulosa, a rota encontrada no problema acima é ACDFLM.
III. Para utilizar algoritmos de busca heurística, deve-se definir uma heurística que superestime o custo da solução.
IV. O A* é um algoritmo ótimo e completo quando heurísticas admissíveis são utilizadas.
V. No simulated annealing, é possível haver movimentos para um estado com avaliação pior do que a do estado corrente, dependendo da temperatura do processo e da probabilidade de escolha.

Julgue os itens a seguir, relativos a métodos de busca com informação (busca heurística) e sem informação (busca cega), aplicados a problemas em que todas as ações têm o mesmo custo, o grafo de busca tem fator de ramificação finito e as ações não retornam a estados já visitados:
I. A primeira solução encontrada pela estratégia de busca em largura é a solução ótima.
II. A primeira solução encontrada pela estratégia de busca em profundidade é a solução ótima.
III. As estratégias de busca com informação usam funções heurísticas que, quando bem definidas, permitem melhorar a eficiência da busca.
IV. A estratégia de busca gulosa é eficiente porque expande apenas os nós que estão no caminho da solução.

Considere um jogo do tipo 8-puzzle, cujo objetivo é conduzir o tabuleiro esquematizado na figura abaixo para o seguinte estado final: [1 2 3 / 8 _ 4 / 7 6 5]. Em determinado instante do jogo, tem-se o estado E0: [3 4 6 / 5 8 _ / 2 1 7]. Os próximos estados possíveis são E1 (espaço move para cima), E2 (espaço move para esquerda) e E3 (espaço move para direita). Considere uma função heurística h embasada na soma das distâncias de Manhattan das peças em relação ao estado final desejado. Utilizando-se um algoritmo de busca gulosa pela melhor escolha que utiliza a função h, o próximo estado no desenvolvimento do jogo a partir do estado E0 tem de ser E3, porque dos três estados E1, E2 e E3 possíveis, o estado com menor soma das distâncias entre a posição atual das peças e a posição final é o estado E3. Assinale a opção correta a respeito dessas asserções.

Considere que G é um grafo qualquer e que V e E são os conjuntos de vértices e de arestas de G, respectivamente. Considere também que grau(v) é o grau de um vértice v pertencente ao conjunto V. Nesse contexto, analise as seguintes asserções:
Em G, a quantidade de vértices com grau ímpar é ímpar.
PORQUE
Para G, vale a identidade dada pela expressão ∑ᵥ∈V grau(v) = 2|E|.

Considere que a figura abaixo corresponde ao cenário de um jogo de computador. Esse cenário é dividido em 24 quadrados e a movimentação de um personagem entre cada quadrado tem custo 1, sendo permitida apenas na horizontal ou na vertical. Os quadrados marcados em preto correspondem a regiões para as quais os personagens não podem se mover. Nesse cenário, o algoritmo A* vai ser usado para determinar o caminho de custo mínimo pelo qual um personagem deve se mover desde o quadrado verde (linha 1, coluna 2) até o quadrado vermelho (linha 3, coluna 3). No A*, o custo f(x) de determinado nó x é computado somando-se o custo real g(x) ao custo da função heurística h(x), e a heurística utilizada é a distância de Manhattan (soma das distâncias horizontal e vertical de x até o objetivo). Desse modo, o custo f(x) do quadrado verde é igual a

O jogo Sudoku consiste em uma matriz 9×9 dividida em 9 sub-matrizes 3×3. A matrix está parcialmente preenchida com números de 1 a 9 e o objetivo é completar a matrix, de forma que cada linha, coluna e sub-matrix contenham todos os números de 1 a 9.
A partir dessas informações, escreva um algoritmo recursivo baseado em retrocesso (backtracking) para resolver o jogo. A matrix foi transformada em um vetor V de 81 posições, contendo zeros nas posições que faltam para serem preenchidas.
Considere que existem duas funções implementadas. A primeira função, NaoHaViolacao(x,i,V), retorna verdadeiro se a inserção do número x na posição i do vetor V não causa violação das restrições do jogo. A segunda função, Imprime(V), realiza a impressão do vetor V.
Considere, ainda, que o algoritmo deve imprimir o vetor V com a solução encontrada, se esta existir. (valor: 10,0 pontos)

/* chamada inicial: if (!Resolve(V, 0)) printf("Sem solução"); */
int Resolve(int V[], int i) {
    if (i == 81) { Imprime(V); return 1; }  /* todas as posições preenchidas */
    if (V[i] != 0) return Resolve(V, i + 1); /* posição já dada: segue adiante */
    for (int x = 1; x <= 9; x++) {
        if (NaoHaViolacao(x, i, V)) {
            V[i] = x;                /* escolhe */
            if (Resolve(V, i + 1))  /* explora */
                return 1;
            V[i] = 0;               /* desfaz (retrocesso) */
        }
    }
    return 0;                       /* nenhum x serve: volta */
}

As técnicas de projeto de algoritmos são essenciais para que os desenvolvedores possam implementar software de qualidade. Essas técnicas descrevem os princípios que devem ser adotados para se projetar soluções algorítmicas para um dado problema. Entre as principais técnicas, destacam-se os projetos de algoritmos por tentativa e erro, divisão e conquista, programação dinâmica e algoritmos gulosos.
Nesse contexto, faça o que se pede nos itens a seguir.
a) Descreva o que caracteriza o projeto de algoritmos por divisão e conquista. (valor: 6,0 pontos)
b) Apresente uma situação de uso da técnica de projeto de algoritmos por divisão e conquista. (valor: 4,0 pontos)

Um país utiliza moedas de 1, 5, 10, 25 e 50 centavos. Um programador desenvolveu o método a seguir, que implementa a estratégia gulosa para o problema do troco mínimo. Esse método recebe como parâmetro um valor inteiro, em centavos, e retorna um array no qual cada posição indica a quantidade de moedas de cada valor.

public static int[] troco(int valor){
    int[] moedas = new int[5];
    moedas[4] = valor / 50;
    valor = valor % 50;
    moedas[3] = valor / 25;
    valor = valor % 25;
    moedas[2] = valor / 10;
    valor = valor % 10;
    moedas[1] = valor / 5;
    valor = valor % 5;
    moedas[0] = valor;
    return(moedas);
}

Considerando o método apresentado, avalie as asserções a seguir e a relação proposta entre elas.
I. O método guloso encontra o menor número de moedas para o valor de entrada, considerando as moedas do país.
PORQUE
II. Métodos gulosos sempre encontram a solução global ótima.
A respeito dessas asserções, assinale a opção correta.

Dada uma sequência de caracteres S = s₁,s₂,…,sₙ, uma subsequência de S é dada pela remoção de zero ou mais caracteres de S. O problema da Subsequência Comum Mais Longa (LCS) pressupõe duas sequências de caracteres A = a₁,a₂,…,aₙ e B = b₁,b₂,…,bₘ, de comprimentos n e m, respectivamente.
A partir dessas informações, considere que Z = z₁,z₂,…,zₖ seja uma LCS das sequências A e B. Em relação ao problema da LCS, avalie as afirmações a seguir.
I. Se aₙ = bₘ, então zₖ = aₙ, zₖ = bₘ e Zₖ₋₁ é uma LCS de Aₙ₋₁ e Bₘ₋₁.
II. Se aₙ ≠ bₘ e zₖ ≠ aₙ, então Z é uma LCS de Aₙ₋₁ e B.
III. Seja lcs(i,j) o comprimento da LCS entre Aᵢ e Bⱼ. Para i,j > 0, se aᵢ ≠ bⱼ, então lcs(i,j) = min{lcs(i,j−1), lcs(i−1,j)}.
IV. Seja lcs(i,j) o comprimento da LCS entre Aᵢ e Bⱼ. Para i,j > 0, se aᵢ = bⱼ, então lcs(i,j) = lcs(i−1,j−1) + 1.
É correto apenas o que se afirma em

Os métodos de projeto e análise de algoritmos são necessários para o desenvolvimento de algoritmos eficientes, pois eles permitem que se resolva problemas computacionais, reduzindo complexidade e tempo de execução. Acerca desses métodos, assinale a opção incorreta.

O problema do escalonamento de intervalos tem como entrada um conjunto de intervalos numéricos (usualmente interpretados como início e fim de atividades), e o objetivo é escolher, desse conjunto, o maior número possível de intervalos disjuntos de dois a dois.
O problema do escalonamento de intervalos pode ser resolvido com o algoritmo descrito a seguir. O conjunto de intervalos dados inicialmente é R e o conjunto de intervalos escolhidos, A, começa vazio.

enquanto R não estiver vazio,
    seja x o intervalo de R com menor tempo de término, e que não tenha interseção com
    algum intervalo em A
    retire x de R e adicione ao conjunto A
retorne A

A respeito desse algoritmo, analise as seguintes asserções.
Para checar se o algoritmo está correto, basta verificar que o primeiro intervalo adicionado ao conjunto A necessariamente faz parte de uma solução ótima.
PORQUE
Pode-se mostrar, por indução no número máximo de intervalos calculados (ou seja, o número de vezes que o laço "enquanto" é executado), que embora possa haver soluções tão boas quanto A, nenhuma delas é estritamente melhor que A. O conjunto com um único intervalo é a base de indução.

Algoritmos criados para resolver um mesmo problema podem diferir de forma drástica quanto a sua eficiência. Para evitar este fato, são utilizadas técnicas algorítmicas, isto é, conjunto de técnicas que compreendem os métodos de codificação de algoritmos de forma a salientar sua complexidade, levando-se em conta a forma pela qual determinado algoritmo chega à solução desejada.
Considerando os diferentes paradigmas e técnicas de projeto de algoritmos, analise as afirmações abaixo.
I. A técnica de tentativa e erro (backtracking) efetua uma escolha ótima local, na esperança de obter uma solução ótima global.
II. A técnica de divisão e conquista pode ser dividida em três etapas: dividir a instância do problema em duas ou mais instâncias menores; resolver as instâncias menores recursivamente; obter a solução para as instâncias originais (maiores) por meio da combinação dessas soluções.
III. A técnica de programação dinâmica decompõe o processo em um número finito de subtarefas parciais que devem ser exploradas exaustivamente.
IV. O uso de heurísticas (ou algoritmos aproximados) é caracterizado pela ação de um procedimento chamar a si próprio, direta ou indiretamente.
É correto apenas o que se afirma em

Considere uma situação em que um professor que queira saber se existem alunos cursando, ao mesmo tempo, as disciplinas A e B, tenha implementado um programa que: (1) inicializa um array a de 30 posições que contém as matrículas dos alunos da disciplina A; (2) inicializa outro array b de 40 posições, que contém as matrículas dos alunos da disciplina B; (3) imprime a matrícula dos alunos que estão cursando as disciplinas A e B ao mesmo tempo.
Considere, ainda, que os arrays foram declarados e inicializados, não estão necessariamente ordenados, e seus índices variam entre 0 e n−1, sendo n o tamanho do array.

1. for ( i = 0 to 29 ) {
2.     for ( j = 0 to 39 ) {
3.
4.
5.
6.     }
7. }

Com base nessas informações, conclui-se que o trecho a ser incluído nas linhas 3, 4 e 5 do código acima, para que o programa funcione corretamente, é

A figura a seguir representa uma plantação de café com x colunas e y linhas. Nessa figura, as regiões com os cafeeiros plantados são as que estão com os espaços preenchidos, e as regiões com falhas de plantios são as que apresentam seus espaços vazios.
Considerando uma solução algorítmica para contar a quantidade de falhas de plantio do cafezal representado na figura, faça o que se pede nos itens a seguir.
a) Indique o tipo de estrutura de dados utilizada na solução, justificando a sua resposta. (valor: 4,0 pontos)
b) Escreva o algoritmo da solução em pseudocódigo ou em linguagem de programação. (valor: 6,0 pontos)

int contaFalhas(int y, int x, int cafezal[y][x]) {
    int falhas = 0;
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            if (cafezal[i][j] == 0)
                falhas++;
    return falhas;
}

Algumas linguagens de programação obedecem a uma ordem específica no que diz respeito à avaliação de operadores. A precedência dos operadores aritméticos, relacionais e booleanos é demonstrada na tabela a seguir, na qual os operadores ++ e −−, pré ou pós-fixados, incrementam ou decrementam a variável, como no exemplo: variável x com valor 0, resultado de ++x é igual a 1 e o de --x é igual a −1.
Considerando essas informações e sabendo que as variáveis a, b e c têm, em determinado momento, os valores 1, 2 e 0, respectivamente, assinale a opção em que o resultado da expressão apresentada corresponde ao da expressão -a * ++b - --c.

Considere a realização de uma pesquisa com 1 000 pessoas para obtenção das seguintes informações: o valor da maior altura; o valor da menor altura; a média das alturas; quantas pessoas têm altura inferior à média das alturas.
Considere, ainda, que um programador foi selecionado para desenvolver um modelo de código que soluciona o problema automatizando a coleta das alturas e a geração das informações.
Com base nas informações apresentadas, desenvolva o código adequado para resolver o problema usando pseudocódigo ou uma linguagem de programação. (valor: 10,0 pontos)

algoritmo "pesquisa"
var altura[1000], menor, maior, total=0, media: real
var qtdmenor=0, ctpessoas: inteiro
inicio
leia altura[1]
menor = altura[1]
maior = altura[1]
total = altura[1]
para ctpessoas=2 até 1000 faça
    leia (altura[ctpessoas])
    total = total + altura[ctpessoas]
fimpara
media = total/1000
para ctpessoas=1 até 1000 faça
    se menor > altura[ctpessoas] então menor = altura[ctpessoas]
    se maior < altura[ctpessoas] então maior = altura[ctpessoas]
    se media > altura[ctpessoas] então qtdmenor = qtdmenor + 1
fimpara
escreva ("Maior = ", maior, " Menor= ", menor, " Média= ", media,
         " Quantidade de alturas menores que a média= ", qtdmenor)

Os proprietários de um teatro necessitam de uma ferramenta de software para reserva de lugares. O desenvolvedor contratado verificou que as poltronas disponíveis para reserva são referenciadas pelo número da fila (a partir do n.º 1) e pelo número da cadeira (a partir do n.º 1) em cada fila, em uma representação matricial em que as linhas e colunas da matriz correspondem, respectivamente, às filas e às colunas de cadeiras. Embora o contexto seja o da organização matricial — N filas de cadeiras (linhas), cada uma contendo M cadeiras (colunas) —, a solução a ser implementada utilizará uma estrutura linear unidimensional (vetor), sendo, portanto, necessária uma conversão entre o lugar referenciado (número f da fila, número c da cadeira) e a posição real na estrutura de armazenamento (posição p no vetor).
Na situação apresentada, considere que a referida matriz seja armazenada no vetor segundo sua sequência de linhas, da primeira para a última, e, em cada linha, da primeira coluna para a última, e que a primeira posição no vetor tenha índice 0. Nessa situação, a posição p da poltrona do teatro localizada à fila de número f e à coluna de número c, é igual a

 1 Algoritmo ENADE2008
 2 variaveis
 3     varA, varB, varC: inteiro
 4     varF : real
 5     varS : literal
 6     varL : logico
 7 inicio
 8     varS ← "1000"
 9     varA ← 4
10     varF ← 3.5
11     varC ← 0
12     varL ← VERDADEIRO
13     se((varC < varA) E varL OU (varS > varC)) entao
14         varB ← varF/varA
15     senao
16         varB ← varA/varC
17     fim se
18 fim algoritmo

O código acima

 1 Algoritmo MatrizENADE2008
 2 variaveis
 3     M[0..2][0..3], I, J, C : inteiro
 4 inicio
 5     C ← 0
 6     para I ← 0 ate 2 passo 1 faca
 7     inicio
 8         para J ← 0 ate 3 passo 1 faca
 9         inicio
10             C ← C + 1
11             M[I][J] ← C
12         fim para
13     fim para
14     para I ← 0 ate 2 passo 1 faca
15     inicio
16         para J ← 0 até 3 passo 1 faca
17         inicio
18             C ← M[2-I][3-J]
19             M[I][J] ← C
20         fim para
21     fim para
22 fim algoritmo

Considerando a execução do algoritmo apresentada acima, faça o que se pede a seguir.
A) Apresente os dados da matriz M ao término da execução da linha 12. (valor: 4,0 pontos)
B) Apresente os dados da matriz M ao término da execução da linha 19. (valor: 6,0 pontos)

Considerando a execução do algoritmo abaixo, responda ao que se pede nos itens a e b.

01 algoritmo Vetores
02 variaveis
03     vetA[1..10], vetB[1..10], i: inteiro
04 inicio
05     para i <- 1 ate 10 passo 1 faca
06         vetB[i] <- 0
07         se resto(i,2) = 0 entao
08             vetA[i] <- i
09         senão
10             vetA[i] <- 2 * i
11         fimse
12     fimpara
13     para i <- 1 ate 10 passo 1 faca
14         enquanto(vetA[i] > i)
15             vetB[i] <- vetA[i]
16             vetA[i] <- vetA[i] - 1
17         fimenquanto
18     fimpara
19 fimalgoritmo

a) Apresente os dados dos vetores vetA e vetB ao término da execução da linha 12. (valor: 5,0 pontos)
b) Apresente os dados dos vetores vetA e vetB ao término da execução da linha 19. (valor: 5,0 pontos)

Jogos de tabuleiro são atividades comuns de entretenimento na vida cotidiana das pessoas. No livro O Homem que Calculava, de Malba Tahan, há uma história na qual um rei deveria efetuar o pagamento pelos serviços de um de seus conselheiros, dando-lhe uma certa quantidade de grãos de trigo a ser calculada da seguinte forma: coloca-se 1 grão de trigo na primeira casa do tabuleiro, 2 na segunda casa, 4 na terceira casa, 8 na quarta casa e assim dobrando-se sucessivamente até a última casa.
Considerando o tabuleiro 4×4 ilustrado acima, contendo a indicação da ordem das casas, construa um único algoritmo que:
a) calcule, armazene em uma estrutura e escreva em ordem a quantidade de grãos de trigo em cada casa do tabuleiro; (valor: 8,0 pontos)
b) calcule, armazene em uma variável e escreva a quantidade total de grãos de trigo presentes no tabuleiro. (valor: 2,0 pontos)

inicio
  tipo Trigo = vetor [1..16] de inteiros;
  inteiro: TotalTrigo, Indice1;
  TotalTrigo <- 0;
  Para Indice1 de 0 até 15 passo 1 faça
      Trigo[Indice1 + 1] <- pot(2, Indice1);
      TotalTrigo <- TotalTrigo + Trigo[Indice1 + 1];
  Fim para;
  Para Indice1 de 1 até 16 passo 1 faça
      Escreva("Quantidade de grãos de trigo na casa ", Indice1, " = ", Trigo[Indice1]);
  Fim para;
  Escreva("Total de grãos de trigo no tabuleiro = ", TotalTrigo);
Fim.