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

Analise o código abaixo:

O tipo de estrutura de dados a que ele se refere pode ser definido como um

• A. algoritmo de um grafo.
• B. algoritmo de pesquisa booleana.
• C. algoritmo vetor de lista encadeada.
• D. algoritmo vetor de lista ligada.
• E. array de vetores e vértices para formar uma busca simples.

O gráfico a seguir representa linhas resultantes de funções de n (número de entradas) por f(n) (número de passos e/ou tempo consumido na solução) para determinados algoritmos. Quando determinado algoritmo possui um grau de complexidade muito grande à medida que se aumenta o número de entradas, ou o tamanho da entrada em número de bits para representá-la, aumenta-se o tempo ou número de passos da solução de acordo com uma função matemática. Pela análise do gráfico e de acordo com as referências descritas em bibliografias do assunto referentes à complexidade de algoritmos, assinale a alternativa que indica a ordem das funções que representam e traduzem a complexidade de algoritmos em ordem crescente, isto é, da menor para a maior complexidade de algoritmos.

• A.

  log n, n, n * log n, n2, 2 n.

• B.

  log n, n * log n, n, 2 n; n2.

• C.

  n, log n, n * log n, 2 n; n2.

• D.

  n, n * log n, log n, n2, 2 n.

• E.

  n * log n, log n, n, 2 n; n2.

Considere a árvore binária não balanceada representada na figura a seguir e assinale a alternativa correspondente ao percorrimento/caminhamento em uma árvore binária conhecido na bibliografia clássica como pós-ordem ou ordem final. Considere a estrutura da árvore definida e o esboço do algoritmo de percorrimento conforme a seguinte descrição:

• A.

  20, 10, 5, 7, 30, 25, 36, 33, 40.

• B.

  20, 5, 10, 7, 25, 30, 36, 33, 40.

• C.

  5, 10, 7, 25, 30, 33, 36, 40, 20.

• D.

  5, 7, 10, 25, 33, 40, 36, 30, 20.

• E.

  5, 10, 7, 20, 25, 30, 33, 36, 40.

Seja T um texto e C, uma cadeia de caracteres, onde n e m correspondem ao tamanho de T e C, respectivamente. Sobre a busca de C em T, é correto afirmar que o algoritmo de:

• A.

  força bruta (ingênuo) tem o melhor desempenho, por utilizar funções hash.

• B.

  Knuth-Pratt-Morris, no pior caso, tem complexidade de tempo O(log n).

• C.

  Knuth-Pratt-Morris realiza comparações da direita para a esquerda.

• D.

  Rabin-Karp, no melhor caso, tem complexidade de tempo (mn²).

• E.

  Boyer-Moore utiliza as heurísticas do mau caractere e do bom sufixo.

Seja T um texto e C, uma cadeia de caracteres, onde n e m correspondem ao tamanho de T e C, respectivamente. Sobre a busca de C em T, é correto afirmar que o algoritmo de:

• A.

  força bruta (ingênuo) tem o melhor desempenho, por utilizar funções hash.

• B.

  Knuth-Pratt-Morris, no pior caso, tem complexidade de tempo O(log n).

• C.

  Knuth-Pratt-Morris realiza comparações da direita para a esquerda.

• D.

  Rabin-Karp, no melhor caso, tem complexidade de tempo  (mn²).

• E.

  Boyer-Moore utiliza as heurísticas do mau caractere e do bom sufixo.

Acerca dos conceitos fundamentais de lógica de programação e algoritmos, é incorreto afirmar que

• A. os denonimados fluxos seqüenciais em algoritmos determinam explicitamente os passos a serem seguidos, com a respectiva execução seqüencial.
• B. compreender o problema, selecionar um método de solução, descrever a solução passo a passo, validar o algoritmo, programá-lo e testá-lo, nesta seqüência, é uma proposta viável para analisar um problema.
• C. o controle de fluxo de programas corresponde à lógica do algoritmo que, por sua vez, canaliza a ação entre os procedimentos, na ordem necessária à realização da execução.
• D. rotinas de biblioteca, em linguagens de programação estruturada, correspondem a programas independentes (subprogramas externos), compilados e testados separadamente.
• E. por meio do desenvolvimento de algoritmos que tornem mais eficiente o uso de repetições (ou de fluxo repetitivo), consegue-se desenvolver programas que realizem atividades em escalas mais amplas.

Com relação aos sistemas de numeração e aritmética de complementos, assinale a opção correta.

• A.

  A soma dos números binários 00110 e 01111 é igual a 11101.

• B.

  A representação do número decimal –5 usando-se 4 bits e complemento dois é 1100.

• C.

  O número binário 0010111 é igual ao número decimal 25.

• D.

  O número binário 011110100011 é igual ao número hexadecimal 7A3.

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.

Considerando-se os algoritmos de busca em árvores, a busca em pré-ordem inicia-se pela raiz da árvore, seguindo para a subárvore à direita e, depois, a subárvore à esquerda, ambas em pré-ordem.

• C. Certo
• E. Errado

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.

• C. Certo
• E. Errado

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).

• C. Certo
• E. Errado