Questões Resolvidas do POSCOMP 2002 (Parte 1)

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

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

Índice

• Questão 21
• Questão 22
• Questão 23
• Questão 24
• Questões 25 e 26
• Questão 27
• Questão 28
• Questão 29

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.

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

Agora, vamos simplicar a expressão

$$\begin{align*}S&=\overline{(\overline{a.b}).(\overline{a.b})}\\&=\overline{(\overline{a.b})}\\&=a.b\end{align*}$$

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)=\begin{cases}1&\mbox{se }x\neq y\\0&\mbox{caso contrário}\end{cases}$$

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

• (A) $x+\overline{y}z$
• (B) $\overline{xyz}+x\overline{y}z$
• (C) $\overline{x}y+x\overline{y}$
• (D) $xy+\overline{y}z+\overline{z}$
• (E) $\overline{x}z+xy+\overline{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	$\overline{x}.y.\overline{z}$
0	1	1	1	$\overline{x}.y.z$
1	0	0	1	$x.\overline{y}.\overline{z}$
1	0	1	1	$x.\overline{y}.z$
1	1	0	0	-
1	1	1	0	-

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

$$\begin{align*}f(x,y,z)&=\overline{x}.y.\overline{z}+\overline{x}.y.z+x.\overline{y}.\overline{z}+x.\overline{y}.z\\&=\overline{x}.y.(\overline{z}+z)+x.\overline{y}.(\overline{z}+z)\\&=\overline{x}.y+x.\overline{y}\\\end{align*}$$

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

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.

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, ..., $i^2$, ... for armazenada nessa tabela segundo a função $f(x)=x\operatorname{mod} 4$, 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) = 1 \operatorname{mod} 4 = 1$;
• Para o valor 4, temos $f(4) = 4 \operatorname{mod} 4 = 0$;
• Para o valor 9, temos $f(9) = 9 \operatorname{mod} 4 = 1$;
• Para o valor 16, temos $f(16) = 16 \operatorname{mod} 4 = 0$;
• Para o valor 25, temos $f(25) = 25 \operatorname{mod} 4 = 1$;
• Para o valor 36, temos $f(36) = 36 \operatorname{mod} 4 = 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

$$x\operatorname{mod} a = x - a\times\left\lfloor\frac{x}{a}\right\rfloor,\,a,x\in\mathbb{Z}$$

No nosso caso, $x = i^2$. Substituindo na fórmula anterior, temos

$$\begin{align*}x\operatorname{mod} 4 &= i^2\operatorname{mod} 4\\&= i^2 - 4\times\left\lfloor\frac{i^2}{4}\right\rfloor\end{align*}$$

Quando $i^2$ é par, temos que $i=2k$, logo

$$\begin{align*}i^2\operatorname{mod} 4&=(2k)^2 - 4\times\left\lfloor\frac{(2k)^2}{4}\right\rfloor\\&=4k^2 - 4\times\left\lfloor\frac{4k^2}{4}\right\rfloor\\&=4k^2 - 4\times\lfloor k^2\rfloor\\&=0\end{align*}$$

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

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

$$\begin{align*}i^2\operatorname{mod} 4&=(2k+1)^2 - 4\times\left\lfloor\frac{(2k+1)^2}{4}\right\rfloor\\&=4k^2 + 4k + 1 - 4\times\left\lfloor\frac{4k^2 + 4k + 1}{4}\right\rfloor\\&=4k^2 + 4k + 1 - 4\times\left\lfloor k^2+k+\frac{1}{4} \right\rfloor\\&=4k^2 + 4k + 1 - 4\times\left(k^2+k\right)\\&=1\end{align*}$$

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.