Questões de Ciência da Computação do ano 2006

Uma das tarefas mais importantes no desenvolvimento de aplicações é a análise e a avaliação da eficiência computacional dessas soluções, isto é, a comparação entre os diferentes algoritmos que podem ser utilizados para a solução de um mesmo problema. No que se refere aos algoritmos e técnicas e aos seus desempenhos, julgue os itens que se seguem.

Considere o algoritmo de busca em profundidade em um grafo G, partindo de um vértice v 0 G. Nesse algoritmo, a busca se inicia pelo vértice v, listando todos os vértices adjacentes. Em seguida, escolhe-se um dos vértices adjacentes para continuar a busca, novamente listando os vértices adjacentes, e assim por diante.

Uma das tarefas mais importantes no desenvolvimento de aplicações é a análise e a avaliação da eficiência computacional dessas soluções, isto é, a comparação entre os diferentes algoritmos que podem ser utilizados para a solução de um mesmo problema. No que se refere aos algoritmos e técnicas e aos seus desempenhos, julgue os itens que se seguem.

Os algoritmos de ordenação têm como função colocar os elementos de uma dada seqüência em uma certa ordem, a qual pode ser parcial ou total. Considerando-se os algoritmos de ordenação, é correto afirmar que o desempenho médio do algoritmo quick-sort é de ordem O(n log n), em que n representa o número de elementos a serem ordenados. Porém, no pior caso, o desempenho do quick-sort é semelhante ao desempenho do algoritmo de bolha (bublesort).

Acerca dos bancos de dados relacionais, julgue os seguintes itens.

Na operação de junção natural, se A₁, A₂, ..., An são atributos nas relações R e S, então uma tupla r de R e uma tupla s de S são combinadas se elas têm os mesmos valores em cada atributo A₁, A₂, ..., An. O resultado da operação é uma tupla com os atributos das relações R e S, que tem os valores de r nos atributos da relação R e os valores de s nos atributos da relação S.

A função apresentada a seguir calcula o exponencial de um numero n elevado ao expoente x, para n e x inteiros e n >= 0.

Sabendo que o código abaixo é parte de um programa pascal, analise a função Z abaixo e responda qual o valor de retorno desta função quando o X = 4.