Questões Resolvidas do POSCOMP 2002 (Parte 1)

Por
| 

Nesta postagem, apresento a resolução de algumas questões do POSCOMP 2002. As questões são da parte de "Fundamentos" do exame.

Questões Resolvidas do POSCOMP 2002

Esta é a primeira parte das soluções, pois posteriormente eu pretendo fazer mais publicações.

Índice

Para mais questões resolvidas, acesse a página POSCOMP.

Questão 21

Assunto: arquitetura de computadores (índice).

Uma característica de uma arquitetura RISC é

  • (A) Uma arquitetura de alto risco pois o mercado de hardware evolui muito rapidamente
  • (B) Possui um grande conjunto de instruções complexas
  • (C) A arquitetura é constituída de milhares de processadores
  • (D) Possui um pequeno conjunto de instruções simples
  • (E) O processador é formado por válvulas e transistores

Resolução

A principal característica da arquitetura RISC é que os processadores possuem um conjunto reduzido de instruções simples, algo que permite mais velocidade e menor consumo de energia.

RISC significa Reduced Instruction Set Computer, isto é, Computador com um Conjunto Reduzido de Instruções. Portanto, a alternativa correta é a D.

Aliás, os principais pesquisadores por trás da arquitetura RISC receberam o Prêmio Turing 2017 por suas contribuições.

Questão 22

Assunto: circuitos digitais/lógica (índice).

Na Álgebra Booleana

  • (A) Os dígitos são octais, de 0 a 7
  • (B) Os dígitos são binários 0 e 1
  • (C) Há dez valores motivados pelos dez dedos do ser humano
  • (D) Os dígitos são alfanuméricos que podem ser representados por um byte
  • (E) Os dígitos são hexadecimais de 0 a 15

Resolução

Na Álgebra Booleana, trabalhamos com dois valores, que podem ser F ou V ou, respectivamente, 0 ou 1. Ou seja, os dígitos são binários.

Portanto, a alternativa correta é a B.

Questão 23

Assunto: circuitos digitais (índice).

Considere o circuito abaixo, implementado com duas portas NAND.

Circuito da questão 23 do POSCOMP 2002

Qual das seguintes portas equivale a este circuito?

  • (A) NOT
  • (B) OR
  • (C) AND
  • (D) XOR
  • (E) NOR

Resolução

A saída do circuito é representada a seguir

Resolução do circuito

Agora, vamos simplicar a expressão

S=¯(¯a.b).(¯a.b)=¯(¯a.b)=a.b

Ou seja, após as simplificações, concluímos que o circuito é equivalente a uma porta AND. Portanto, a alternativa correta é a C.

Questão 24

Assunto: circuitos digitais (índice).

Considere o projeto de um circuito digital que implementa uma função f com três variáveis de entrada e satisfazendo as seguintes propriedades:

f(x,y,z)={1se xy0caso contrário

Qual das seguintes expressões representa corretamente a função f?

  • (A) x+¯yz
  • (B) ¯xyz+x¯yz
  • (C) ¯xy+x¯y
  • (D) xy+¯yz+¯z
  • (E) ¯xz+xy+¯yz

Resolução

Primeiramente, vamos construir a tabela da verdade da função f e, em seguida, vamos utilizar a derivação de expressões por soma de produtos (SDP) para obter a expressão booleana de f.

x y z f(x,y,z) Termos da SDP
0 0 0 0 -
0 0 1 0 -
0 1 0 1 ¯x.y.¯z
0 1 1 1 ¯x.y.z
1 0 0 1 x.¯y.¯z
1 0 1 1 x.¯y.z
1 1 0 0 -
1 1 1 0 -

Agora, vamos somar os termos da última coluna e simplificar a expressão

f(x,y,z)=¯x.y.¯z+¯x.y.z+x.¯y.¯z+x.¯y.z=¯x.y.(¯z+z)+x.¯y.(¯z+z)=¯x.y+x.¯y

Portanto, alternativa correta é a C.

Questões 25 e 26

Assunto: linguagens formais e autômatos (índice).

As soluções dessas questões podem ser obtidas na postagem Questões do POSCOMP sobre Linguagens Formais e Autômatos #01.

Questão 27

Assunto: estruturas de dados (índice).

Suponha que T seja uma árvore AVL inicialmente vazia, e considere a inserção dos elementos 10, 20, 30, 5, 15, 2 em T, nesta ordem. Qual das sequências abaixo corresponde a um percurso de T em pré-ordem:

  • (A) 10, 5, 2, 20, 15, 30
  • (B) 20, 10, 5, 2, 15, 30
  • (C) 2, 5, 10, 15, 20, 30
  • (D) 30, 20, 15, 10, 5, 2
  • (E) 15, 10, 5, 2, 20, 30

Resolução

Primeiramente, vamos montar a árvore AVL fazendo as inserções conforme o enunciado apresenta. A imagem a seguir mostra a construção da árvore passo a passo (clique aqui para baixar a imagem):

Construção da árvore AVL da questão 27 do POSCOMP 2002
Construção da árvore AVL

Se preferir, você pode ver a construção passo a passo no seguinte vídeo: Construção da árvore AVL (YouTube). Tanto a imagem como o vídeo foram feitos utilizando um visualizador de estruturas de dados apresentado numa postagem anterior do blog.

Agora, basta realizar o percurso em pré-ordem (raiz-esquerda-direita). A sequência será 10, 5, 2, 20, 15, 30.

Percurso em pré-ordem na árvore AVL
Os números indicam a ordem das visitas aos nós da árvore AVL

Logo, a alternativa correta é a A.

Questão 28

Assunto: estruturas de dados (índice).

Considere uma tabela de espalhamento (tabela hash) com quatro posições numeradas 0, 1, 2 e 3. Se a sequência de quadrados perfeitos 1, 4, 9, ..., i2, ... for armazenada nessa tabela segundo a função f(x)=xmod4, como se dará a distribuição dos elementos pelas posições da tabela, à medida que o número de entradas cresce?

  • (A) Cada posição da tabela receberá aproximadamente o mesmo número de elementos
  • (B) Três posições da tabela receberão, cada uma, aproximadamente um terço dos elementos
  • (C) Uma única posição da tabela receberá todos os elementos, e as demais posições permanecerão vazias
  • (D) Todas as posições da tabela receberão elementos, mas as duas primeiras receberão, cada uma, o dobro das outras
  • (E) As duas primeiras posições da tabela receberão, cada uma, aproximadamente a metade dos elementos, e as demais posições permanecerão vazias

Resolução

É conveniente testar a função de hash com alguns valores para analisar o seu comportamento:

  • Para o valor 1, temos f(1)=1mod4=1;
  • Para o valor 4, temos f(4)=4mod4=0;
  • Para o valor 9, temos f(9)=9mod4=1;
  • Para o valor 16, temos f(16)=16mod4=0;
  • Para o valor 25, temos f(25)=25mod4=1;
  • Para o valor 36, temos f(36)=36mod4=0.

Só lembrando que mod é o operador para calcular o resto da divisão. Observe que a posição de inserção será 0 sempre que o número a ser inserido é par. Por outro lado, se o número é ímpar, então a posição de inserção será 1.

Outro ponto importante é que sempre que inserimos um número ímpar, o próximo valor a ser inserido será par e, quando inserimos um par, o próximo valor que vai ser inserido será ímpar, logo cada posição (0 ou 1) receberá aproximadamente o mesmo número de elementos.

Vamos tentar generalizar. O resto da divisão pode ser calculado da seguinte forma

xmoda=xa×xa,a,xZ

No nosso caso, x=i2. Substituindo na fórmula anterior, temos

xmod4=i2mod4=i24×i24

Quando i2 é par, temos que i=2k, logo

i2mod4=(2k)24×(2k)24=4k24×4k24=4k24×k2=0

Ou seja, se o valor a ser inserido for par, então a posição de inserção sempre será 0.

Se i2 é ímpar, então i=2k+1, portanto

i2mod4=(2k+1)24×(2k+1)24=4k2+4k+14×4k2+4k+14=4k2+4k+14×k2+k+14=4k2+4k+14×(k2+k)=1

Assim, se o valor a ser inserido for ímpar, então a posição de inserção sempre será 1.

Por fim, a alternativa correta é a E.

Questão 29

Assunto: complexidade de algoritmos (índice).

A questão 29 foi resolvida na postagem Questões do POSCOMP sobre Complexidade de Algoritmos #01.

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar