Questões de Concurso Público ARCE 2012 para Analista de Regulação - Analista de Sistemas

O método Quicksort é, essencialmente, uma aplicação do princípio “dividir para conquistar”. Para a ordenação, inicialmente o vetor é dividido em uma sublista da direita e uma da esquerda, de modo que todo elemento da sublista da esquerda seja menor que o da direita. Em seguida, ordenam-se, pelo mesmo processo, as duas sublistas de forma recursiva.

Para o cálculo da complexidade do Quicksort, leva-se em consideração o número de vezes que n (número de elementos do vetor) pode ser dividido por 10 que é O(log₁₀n), e em cada partição são feitas O(n) comparações.

No Quicksort, o pivô é responsável pelo número de partições em que o vetor é dividido. Como o pivô não pode ser um elemento que esteja repetido no vetor, o Quicksort não funciona quando há elementos repetidos.

Espalhamento ou hashing é o processo de transformação de uma chave em um endereço. O tempo gasto com buscas em uma tabela de espalhamento depende do tamanho da tabela, e aí reside sua grande vantagem: devem sempre ser usadas tabelas pequenas.

O índice gerado pela função hash é chamado endereço efetivo e o endereço verdadeiro do registro é chamado endereço primário. Quando duas ou mais chaves possuem o mesmo endereço efetivo, dizemos que houve dispersão, e essas chaves são chamadas de homônimas.

Uma empresa aérea quer fazer o controle de reservas de voos de forma automatizada. Há vários voos e cada um deles tem certo número de lugares disponíveis. Os usuários fazem a reserva por telefone, fornecendo seus nomes. As pilhas devem ser usadas para controlar a lista de passageiros de cada voo, ordenados pelo nome.

Vários usuários enviam dados para serem impressos numa única impressora. Como o controle das impressões poderia ser feito? Quem teria o direito de imprimir primeiro? Qual a ordem de impressão? As listas encadeadas devem ser usadas, colocando os arquivos ordenados pelo nome do usuário, usando a política LIFO – Last In Fisrt Out.

O comando “desfazer” (undo) de um editor de texto precisa ser implementado. A última ação do usuário é que será desfeita. Uma pilha deve ser usada para implementar o undo, mantendo no topo a última ação do usuário.

Uma empresa quer dar senhas de acesso diferenciadas para os seus funcionários de acordo com sua função e departamento. De acordo com a senha, o usuário poderá ter suas tarefas executadas em menor tempo no computador central, de forma prioritária. As árvores binárias devem ser usadas para geração das senhas e controle das prioridades de acesso.

O histórico de sites visitados pelos usuários do navegador Internet Explorer tem que ser organizado de forma que o site mais recentemente visitado fique no topo da lista. As filas devem ser usadas, de forma que o primeiro site visitado fique em seu topo.