Questões de Concursos Algoritmos

Analise as seguintes afirmações relacionadas a noções básicas de programação:

I. A idéia básica do algoritmo de ordenação bubble sort é montar uma árvore com os dados a serem ordenados, percorrer esses dados pela última camada denominada folhas e, a cada passagem, comparar cada elemento da folha com o seu sucessor. Se os elementos não estão ordenados deve-se trocá-los de posição.

II. Na orientação a objetos, uma classe é uma abstração de software que pode representar algo real ou virtual. Uma classe é formada por um conjunto de propriedades (variáveis) e procedimentos (métodos).

III. Uma função é dita recursiva quando em seu código existe uma chamada a si própria, podendo utilizar os mesmos parâmetros de entrada (correndo o risco de provocar um ciclo infi nito) ou outros.

IV. Uma árvore binária é um conjunto finito de elementos que ou está vazio ou está dividido em 3 subconjuntos: um elemento chamado raiz da árvore e dois subconjuntos, cada um dos quais é, por si só, uma árvore binária, chamadas sub-árvore direita e sub-árvore esquerda. Indique a opção que contenha todas as afirmações verdadeiras.

O desenvolvimento de aplicações que dependem de alto desempenho normalmente envolve a utilização de mecanismos e algoritmos eficientes. Dependendo do volume de dados envolvidos, a escolha de um algoritmo ineficiente pode ter sérias implicações, tanto no que se refere ao tempo de resposta como na qualidade da resposta obtida. Acerca desse assunto, bem como sobre as técnicas de construção de algoritmos e estruturas de dados e conceitos básicos sobre estruturas de dados, julgue os itens de 81 a 92.

A complexidade de um algoritmo é de suma importância na ciência da computação. Os algoritmos que possuem solução em tempo polinomial são ditos pertencentes à classe P. Os algoritmos que não pertencem a essa classe são chamados de algoritmos intratáveis.

Dado programa abaixo

int func (int x1)

{

            int max,num;

            if (x1 = = 0) return(1);

            max = x1 - 1;

            num = func (max);

            return (x1 * num);

}

Podemos afirmar que o programa acima utiliza o conceito de

O desenvolvimento de aplicações que dependem de alto desempenho normalmente envolve a utilização de mecanismos e algoritmos eficientes. Dependendo do volume de dados envolvidos, a escolha de um algoritmo ineficiente pode ter sérias implicações, tanto no que se refere ao tempo de resposta como na qualidade da resposta obtida. Acerca desse assunto, bem como sobre as técnicas de construção de algoritmos e estruturas de dados e conceitos básicos sobre estruturas de dados, julgue os itens de 81 a 92.

A busca binária em uma lista contendo N elementos possui complexidade temporal O(log N). A busca binária só pode ser executada em uma lista que seja previamente ordenada. Como o custo de ordenação é da ordem O(log N), o custo total para ordenar e recuperar um elemento da lista é de O(log N) + O(log N) = O (log N).

Seja uma matriz Nx12 onde cada elemento da matriz é um número real e representa um índice mensal de inflação de um determinado país. Cada uma das N linhas da matriz representa um país e as 12 colunas representam os meses do ano. Deseja-se criar o método Java "public float[ ] calculeMaiorInflação(float[ ][ ] m)" que retorna o mês de maior inflação de cada um dos N países. O parâmetro do método "calculeMaiorInflação" é a matriz de inflações citada. Para a implementação desse método "calculeMaiorInflação", qual fragmento de código Java é o correto, no que se refere a sua lógica algorítmica?

Acerca de algoritmos, estruturas de dados e lógica de programação, julgue os itens subsequentes.

A árvore geradora mínima de um grafo conexo não direcionado construída com o algoritmo de Kruskal é única. Nessa árvore geradora mínima, a substituição de arestas de mesmo peso não afetará o custo total da árvore.

Julgue os próximos itens, acerca de características, funções, algoritmos e componentes de sistemas operacionais.

Um processador superescalar possui múltiplas unidades de execução, o que implica a necessidade de o sistema operacional resolver problemas complexos na seqüência de execução das instruções.

A análise da complexidade de algoritmos computacionais permite, entre outras coisas, calcular a escalabilidade do uso de determinado algoritmo em função da dimensão de um sistema em que o algoritmo é aplicado. Assim, freqüentemente a complexidade é expressa em termos da dimensão do sistema, usualmente anotada com n. Com relação a algoritmos de complexidade linear, polinomial, exponencial e logarítmica, julgue os itens a seguir.

Algoritmos com complexidade exponencial são menos escaláveis que algoritmos com complexidade logarítmica.

A Internet tem representado, nos últimos anos, um dos agentes de transformação da sociedade, alterando o modo de vida das pessoas e apresentando penetração cada vez maior nos mais diversos segmentos e classes sociais. Sua infra-estrutura tem exigido, por outro lado, progressivas adaptações, capazes de suportar as variadas e crescentes demandas que se apresentam. A respeito da Internet, julgue os itens seguintes.

Em um algoritmo de roteamento do tipo estado de enlace, consideram-se conhecidos a topologia da rede e todos os custos de enlaces, informações estas obtidas por meio de um broadcast realizado por cada nó com relação aos roteadores da rede.

Quanto a estruturas de dados e algoritmos básicos, julgue os itens seguintes.

Quando há necessidade de freqüentes varreduras seqüenciais de elementos uniformes e contíguos, as tabelas (arrays) apresentam características de desempenho melhores que as das listas encadeadas.

Acerca dos sistemas operacionais modernos, julgue os itens de 111 a 122.

O algoritmo para alocação dinâmica de memória (worst-fit) consiste em procurar o primeiro menor espaço disponível que seja suficiente para alocar a quantidade de memória necessária. Essa abordagem sempre obriga a procura por espaço em toda a estrutura, acarretando em degradação significativa de desempenho.

Os diversos sistemas operacionais existentes empregam algumas soluções comuns à questão do compartilhamento de recursos computacionais entre os usuários e aplicações. Com relação às estratégias, às estruturas e aos mecanismos dos sistemas operacionais, julgue os itens que se seguem.

Uma sessão crítica é o trecho de um programa que acessa um recurso crítico, ou seja, um recurso que não pode, em determinado intervalo de tempo, ser compartilhado por múltiplos processos.

Considerando os valores x = TRUE, y = FALSE e z = FALSE, em se tratando de lógica booleana, é correto afirmar que a instrução

NOT (NOT x) AND NOT (x OR z) retorna um valor TRUE.

Com relação a sistemas operacionais, julgue os seguintes itens.

Em alguns algoritmos de escalonamento de processos classificados como round robin with multilevel feedback, as prioridades dos processos são periodicamente calculadas e os processos são movidos entre listas que representam as prioridades. Há implementações desses algoritmos nas quais os processos podem influenciar as suas prioridades.

Ainda com relação a características, funções, algoritmos e componentes de sistemas operacionais, julgue os itens a seguir.

A técnica de compactação de memória é usada com freqüência na gestão de memória por ter um pequeno tempo de processamento.