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

Para verificar a integridade de um backup armazenado no computador, pode-se utilizar um método criptográfico que, quando aplicado sobre uma informação, independente do seu tamanho, gera um resultado único e de tamanho fixo. Esse método criptográfico é denominado

• A. criptografia assimétrica.
• B. compressão binária.
• C. função elíptica.
• D. criptografia simétrica.
• E. função de hash.

No desenvolvimento de sistemas, a escolha de estruturas de dados em memória é especialmente relevante. Dentre outras classificações, é possível agrupar essas estruturas em lineares e não lineares, conforme a quantidade de sucessores e antecessores que os elementos da estrutura possam ter.

Assinale a opção que apresenta, respectivamente, estruturas de dados lineares e não lineares.

• A. Tabela de dispersão e fila.
• B. Estrutura de seleção e pilha.
• C. Pilha e estrutura de seleção.
• D. Pilha e árvore binária de busca.
• E. Fila e pilha.

As funções de hashes criptográficos devem possuir determinadas características para o seu funcionamento adequado.

Assinale a opção que indica uma delas.

• A. O valor de saída da função tenha tamanho variável.
• B. O valor de entrada da função tenha um tamanho fixo.
• C. O valor de entrada possa ser facilmente achado, dado o hash de saída.
• D. Os dois tipos de chaves assimétricas sejam utilizados.
• E. Os dois tipos de chaves assimétricas sejam utilizados.

A tabela a seguir deve ilustrar uma lista duplamente encadeada de cores, estruturada sobre os cinco elementos de um vetor.

Dado que a ordem correta das cores é Marrom-Verde-Azul- Vermelho-Amarelo, a coluna Cor, na tabela acima, deveria apresentar, de cima para baixo, os seguintes valores:

• A. Marrom-Vermelho-Amarelo-Azul-Verde;
• B. Azul-Marrom-Verde-Vermelho-Amarelo;
• C. Amarelo-Azul-Marrom-Vermelho-Verde;
• D. Azul-Vermelho-Amarelo-Verde-Marrom;
• E. Verde-Azul-Vermelho-Marrom-Amarelo.

João tem um arquivo que contém uma lista de nomes e endereços, com mais de 100.000 registros, e precisa implementar um mecanismo de busca por nome. João considerou três alternativas:

I. Árvore binária;

II. Tabela Hash;

III. Árvore B;

IV. Busca linear.

Depois de preparar os dados e testar cada algoritmo com nomes escolhidos aleatoriamente, João concluiu que, genericamente, a classificação desses métodos, do menor para o maior tempo de busca, é:

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

Um Programador da Defensoria Pública do Estado de São Paulo foi solicitado a propor uma solução para o problema: Há uma quantidade grande de dados classificáveis por chave e estes dados devem ser divididos em subconjuntos com base em alguma característica das chaves. Um método eficiente deve ser capaz de localizar em qual subconjunto deve-se colocar cada chave e depois estes subconjuntos bem menores devem ser gerenciados por algum método simples de busca para que se localize uma chave rapidamente. O Programador propôs como solução, corretamente, a implementação de

• A. Deques.
• B. Tabela e função hash.
• C. Pilhas.
• D. Fila duplamente encadeada.
• E. Árvore Binária de Busca.

Considerando a organização de arquivos diretos, é INCORRETO afirmar:

• A. Ao invés de um índice, é utilizada uma função (hashing) que calcula o endereço do registro a partir do valor da chave do registro.
• B. Quando há coincidência de chaves, ou seja, duas chaves gerando o mesmo endereço, este fato é denominado colisão.
• C. As colisões, caso ocorram, devem ser tratadas por algum método.
• D. São sempre previstos acessos seriais.
• E. O acesso aleatório é eficiente.

Quando se recebem mensagens assinadas digitalmente é possível verificar a Identificação Digital do signatário para determinar se não ocorreu nenhuma falsificação ou adulteração. No processo de assinatura digital, o que pode garantir a integridade da mensagem é o uso da

• A. chave pública.
• B. criptografia assimétrica.
• C. chave privada.
• D. criptografia simétrica.
• E. função de hash.

Considere uma estrutura de dados na forma de uma lista linear em que as operações referentes à inserção e remoção de elementos são realizadas na mesma extremidade dessa lista. O tipo específico dessa estrutura de dados e o nome usual da extremidade citada são, correta e respectivamente,

• A. pilha e topo.
• B. pilha e base.
• C. árvore e folha.
• D. grafo e folha.
• E. grafo e base.

Considere que a Manausprev armazena os nomes dos beneficiários de aposentadorias em uma Árvore Binária de Busca − ABB. Ao se armazenar, nesta ordem, os nomes Marcos, José, Carolina, Paula, Rui, Pedro e Maria, a ABB resultante

• A. é perfeitamente balanceada.
• B. tem altura 3, que corresponde à altura mínima para armazenar os 7 nomes.
• C. possui como folhas os nomes Rui e Maria.
• D. requer no máximo 3 comparações para localizar qualquer um dos 7 nomes.
• E. requer no máximo 4 comparações para localizar qualquer um dos 7 nomes.