Questões sobre Algoritmos

Com relação à programação, algoritmos e estrutura de dados, julgue os itens seguintes.

No método de hashing, por meio de acesso sequencial, são utilizados tabelas e mapas para recuperar informações de endereço de arquivos de forma rápida e eficiente.

• C. Certo
• E. Errado

Com relação à programação, algoritmos e estrutura de dados, julgue os itens seguintes.

Na implementação de um deque sequencial, é necessário ter, em cada extremidade, uma variável de ponteiro externa, por meio da qual as inserções e retiradas sejam efetuadas.

• C. Certo
• E. Errado

Com relação à programação, algoritmos e estrutura de dados, julgue os itens seguintes.

Pesquisa realizada em árvore para procurar uma chave pode ser feita por meio de operação de busca, caso a chave esteja na raiz, ou em função do número de níveis que a árvore possua, caso a chave não esteja na raiz.

• C. Certo
• E. Errado

O procedimento troca de r arestas (r-exchange) é uma das heurísticas de maior sucesso em obter uma solução aproximadamente ótima para o problema do caixeiro-viajante com n vértices. Em relação a esse procedimento, considere as afirmativas a seguir.

I - A partir de um ciclo Hamiltoniano H, o procedimento retira r arestas de H, produzindo r caminhos desconexos e os reconecta usando arestas diferentes daquelas retiradas, produzindo uma nova rota H’.

II - De um ciclo Hamiltoniano H é produzido um novo ciclo H’, o qual difere de H em exatamente r arestas, as demais (n-r) arestas coincidem.

III - Caso o custo de H’, produzido a partir da troca de r arestas de um ciclo Hamiltoniano H, seja maior que o custo de H, então H é substituído por H’, senão um novo conjunto de r arestas de H é selecionado para troca.

IV - O processo de troca de r arestas é repetido até que nenhuma melhora adicional seja alcançada.

V - O procedimento r-exchange termina em um ótimo global, chamado de r-ótimo ou r-opt.

São corretas APENAS as afirmativas

• A. I e II.
• B. III e IV.
• C. I, IV e V.
• D. II, III, IV e V.
• E. I, II, III e V.

• A. do primeiro vizinho com melhora (first improvement) com ordem fixa para avaliar os vizinhos.
• B. do primeiro vizinho com melhora (first improvement) com ordem aleatória para avaliar os vizinhos.
• C. C) do melhor vizinho (best improvement) que escolhe o vizinho com melhora máxima em g.
• D. por melhora aleatória (random improvement) que escolhe aleatoriamente um vizinho entre os vizinhos com melhora.
• E. por pior melhora (least improvement) que escolhe o vizinho de melhora mínima em g.

Existem algoritmos de busca local estocástica em que a função passo está implementada em dois estágios. No primeiro estágio, uma solução vizinha s’ da solução candidata corrente s é selecionada uniformemente e depois é aceita, ou não, de acordo com a função de probabilidade: p(T,s,s’) = 1, se f(s’)  f(s); ou p(T,s,s’) = exp( (f(s)-f(s’))/T ), caso contrário, onde T é um parâmetro denominado temperatura e f é a função avaliação. Quanto ao emprego desse critério, conhecido como condição de Metropolis, tem-se que

• A. quando T diminui, a aceitação fica mais rigorosa, ou seja, uma solução s’ com função avaliação pior que s tem pouca chance de ser aceita como nova solução candidata.
• B. à medida que T aumenta, menos chance tem uma solução pior que a solução candidata corrente em ser aceita como nova solução candidata.
• C. existe a possibilidade de uma solução selecionada s’ que melhora a função avaliação ser rejeitada.
• D. o algoritmo Simulated Annealing usa o critério de Metropolis que é parametrizado por um valor fixo de T
• E. são exemplos de algoritmos de busca local estocástica que utilizam esse critério Simulated Annealing, Melhoria Iterativa Probabilística e Busca Tabu.

Considere o algoritmo em que é feita uma passagem de argumentos por referência, em que V[] é um vetor de inteiros e X e Y são valores inteiros.

Com respeito ao algoritmo acima, assinale a opção correta.

• A.

  A função recursiva f1 retorna a quantidade de valores zero que existem desde a posição X até a posição Y do vetor V.

• B.

  A chamada f1(vet,8,1) leva a uma execução infinita, qualquer que seja o vetor vet passado como parâmetro.

• C.

  Considere vet um vetor que contenha os valores [1,2,3,4,5,6,7,8,9,10] e a chamada da função f1(vet,1,5). A alteração da linha 5 para retorne 1 + f1(V,X+1,Y+1) não alteraria o resultado da execução da função.

• D.

  Considerando as características da função f1, não é possível implementá-la sem o uso de recursividade.

• E.

  A garantia de que a função recursiva não será infinitamente executada está implementada exclusivamente no trecho do algoritmo que compreende da linha 10 à linha 14.

Tradutores de linguagem são programas que traduzem os programas-fonte escritos em linguagem de alto nível para código de máquina. Com relação a tradutores, assinale a opção correta.

• A.

  Compiladores são projetados para um tipo específico de hardware e de sistema operacional.

• B.

  A interpretação nada mais é do que uma compilação cruzada.

• C.

  Toda linguagem orientada a objetos pura é compilada.

• D.

  Java é uma linguagem fundamentalmente interpretada.

• E.

  A linguagem Delphi pode ser tanto interpretada quanto compilada.

Se, e somente se, todas as colunas de uma tabela tiverem apenas valores atômicos, isto é, se cada coluna só puder ter um valor para cada linha na tabela.

Trata-se da definição da

• A.

  1FN.

• B.

  2FN.

• C.

  3FN.

• D.

  FNBC.

• E.

  5FN.

A respeito dos conceitos de linguagens de programação, julgue os itens a seguir.

As estruturas de repetição são utilizadas para se executar determinado trecho de um programa certo número de vezes, de acordo com uma condição lógica. Na estrutura de repetição enquanto (while), a condição lógica é testada antes da execução dos trechos do programa, ao passo que, na estrutura para (for), o conjunto de comandos declarados após o for será realizado uma vez antes de se realizar o teste da condição.

• C. Certo
• E. Errado