Universidade Federal de Lavras
Programa de Pós-Graduação em Ciência da Computação
Prova Escrita do Processo de Seleção 2012/2
Nome:
Assinatura:
Data: 04/06/2012
Instruções
• Somente abra o Caderno de Provas após o aviso pelo Aplicador da Prova de inı́cio da prova escrita.
• Este Caderno de Prova contém 35 (trinta e cinco) questões objetivas, cada uma com 5 (cinco) alternativas, em que
apenas 1 (uma) é correta.
• Marque, à caneta (azul ou preta), somente uma alternativa em cada questão, no próprio Caderno de Provas.
• Anulam a questão: a marcação de mais de uma alternativa em uma mesma questão e/ou rasuras.
• Não haverá substituição do Caderno de Provas por erro de preenchimento.
• A interpretação faz parte da prova. Não serão permitidas perguntas ao Aplicador da Prova sobre as questões da Prova.
• Assine cada folha do Caderno de Provas.
• Tempo de prova: 3 horas, já incluı́do o tempo para o preenchimento para a marcação das respostas.
• Ao concluir a prova, permaneça em seu lugar e comunique ao Aplicador da Prova.
• Ao final da prova, o Caderno de Provas deverá ser entregue ao Aplicador da Prova.
√
Questão 1. Convertendo-se (4, 30◦ ) e (2 2, π/4) de coordenadas polares para coordenadas cartesianas, obtêm-se,
respectivamente:
√ √
a) (2, 2) e (2 2, 2 2)
√ √
√ √
b) ( 2, 2) e (2 2, 2 2)
√
c) (2 3, 2) e (2, 2) X
√ √
√
12
d) ( √
, 2 3) e (2 2, 2 2)
3
√ √
e) (2, 2) e (2 3, 2 3)
Questão 2.
R
du
=
u
a) u + C
b) u
c) 1/ ln u
e) u2 /2
d) ln |u| + C X
Questão 3. Considere a seguinte proposição: ”Este código não tem erros se e somente se ele retorna a saı́da esperada
para todos os valores de entrada”. Esta proposição é logicamente equivalente à:
I. Se este código está correto, então ele produz a saı́da esperada para todos os valores de entrada e se o programa produz
a resposta correta para todos os possı́veis valores de entrada então ele não tem erros.
II. Se este código não está correto, então ele produz a saı́da esperada para todos os valores de entrada e se o programa não
produz a resposta correta para todos os possı́veis valores de entrada então ele não tem erros.
III. Este código apresenta erros ou ele retorna a saı́da esperada para todos os valores de entrada, e, este código não retorna
a saı́da esperada para todos os valores de entrada ou ele não tem erros.
IV. Este código não apresenta erros ou ele retorna a saı́da esperada para todos os valores de entrada, e, este código retorna
a saı́da esperada para todos os valores de entrada ou ele não tem erros.
Estão corretas as afirmativas:
a) I e III. X
b) I e IV.
c) II e III.
d) II e IV.
e) Apenas I.
Questão 4. Dadas as quatro premissas abaixo, quais são as possı́veis conclusões que podemos extrair?
S1 Se eu tiro o dia de folga, chove ou neva.
S2 Eu tirei folga na terça ou na quinta.
S3 Fez sol na terça.
S4 Não nevou na quinta.
C1 Eu não tirei folga na terça.
C2 Eu tirei folga na quinta.
C3 Choveu na quinta.
C4 Choveu na terça.
a) C1 , C2 e C3 . X
b) C1 , C2 e C4 .
c) C1 , C3 e C4 .
d) C2 , C3 e C4 .
e) C1 , C2 , C3 e C4 .
Questão 5. Considere o seguinte argumento: ”Se eu for nadar, então eu ficarei no sol por muito tempo. Se eu ficar
no sol por muito tempo, então eu me queimarei. Por isso, se eu for nadar, eu me queimarei.”. Podemos dizer que o
argumento está:
a) Correto, por Modus Tollens.
b) Correto, por Modus Ponens.
c) Correto, por um silogismo hipotético. X
d) Incorreto, cometeu-se um erro reverso.
e) Incorreto, cometeu-se um erro oposto.
Assinatura:
Questão 6. Marcelino aposta 8 números, dentre 100 disponı́veis em uma loteria recém criada. Após todos os números
sorteados, ele verifica que todos os números sorteados são pares. Se ele tivesse essa informação antes do sorteio, sua
probabilidade de acerto seria:
a)
1
C(100,8)
b)
1
C(50,8)
X
c)
C(100,8)
C(50,8)
d) C(100, 8)
e) C(50, 8)
Questão 7. Analise as seguintes relações sobre o conjunto A = {1, 2, 3}: ANULADA
R = {(2, 1), (3, 1), (3, 3)}
S = {(1, 1), (2, 2)}
T = {(1, 2), (1, 3)}
U = {(2, 3), (3, 2)}
Podemos afirmar que:
a) Somente S é reflexiva.
b) Somente U é simétrica.
c) Nenhuma das relações é antissimétrica.
d) R ∪ S ∪ T é reflexiva e simétrica, mas não é transitiva.
e) S ∪ U não é reflexiva, mas é transitiva e simétrica.
Questão 8. Para todo número inteiro positivo i, considerando
i o conjunto de todas as cadeias de bits não vazias de
TA
S
∞
A
e
extensão não excedente a i , podemos afirmar que ∞
i
i=1 Ai são, respectivamente:
i=1
a) ∅ e ∅.
b) 0, 1 e todos os números binários.
c) Todos os números binários e 0, 1.X
d) Todos os números binários e ∅.
e) ∅ e todos os números binários.
Questão 9. Considere uma Máquina de Turing M e assuma que, de maneira extremamente simplificada, o conjunto
de todas possı́veis palavras de entrada é formado por {A, B, C}. Temos que M produz os seguintes resultados para
cada entrada:
• A: Aceita.
• B: Rejeita.
• C: Não para.
Baseando-se apenas em M , considere as afirmativas abaixo:
I. A linguagem formada por {A} é recursivamente enumerável.
II. A linguagem formada por {A,B} é decidı́vel.
III. A linguagem formada por {A,C} é reconhecı́vel.
IV. Se o resultado de M para C fosse “Aceita”, então poderı́amos dizer que a linguagem formada por {A,C} é recursiva.
V. Se o resultado de M para C fosse “Aceita”, então poderı́amos dizer que um problema de decisão representado pela
linguagem formada por {A,C} não pode ser resolvido por um algoritmo.
Em relação a estas afirmativas, temos que:
a) Apenas as afirmativas I, II e V são verdadeiras.
b) Apenas as afirmativas II e IV são verdadeiras.
c) Apenas as afirmativas III e V são verdadeiras.
d) Apenas as afirmativas I e IV são verdadeiras. X
e) Todas afirmativas são falsas.
Assinatura:
Questão 10. Com relação a linguagens formais, assinale a alternativa incorreta
a) Autômatos finitos e expressões regulares representam o mesmo conjunto de linguagens, chamado linguagens regulares.
b) A linguagem L = {0n 1n |n ≥ 0} pode ser reconhecida apenas por autômatos não-determinı́sticos. X
c) Uma gramática livre de contexto provê uma maneira de descrever linguagens através de regras recursivas chamadas
produções.
d) Linguagens livres de contexto são reconhecidas por autômatos de pilha.
e) O conjunto das linguagens reconhecidas por autômatos de pilha determinı́sticos é formado pelo subconjunto das linguagens
livres de contexto que possuem uma gramática não-ambı́gua.
Questão 11. Seja um alfabeto Σ. Considere as afirmações a seguir sobre redução polinomial ∝, determine se cada
uma é verdadeira ou falsa e escolha a alternativa correta.
I. Uma redução polinomial de uma linguagem L1 ⊂ Σ∗1 para uma linguagem L2 ⊂ Σ∗2 é uma função f : Σ∗1 → Σ∗2 que
satisfaz as condições: há um programa de máquina de Turing determinı́stica em tempo polinomial que computa f ;
(∀x ∈ Σ∗1 ) x ∈ L1 ⇔ f (x) ∈ L2 . Se há uma transformação polinomial de L1 para L2 , então, escreve-se L1 ∝ L2 .
II. (L1 ∝ L2 ∧ L2 ∈ P) ⇒ (L1 ∈
/ P).
III. (L1 ∝ L2 ∧ L1 ∈
/ P) ⇒ (L2 ∈ P).
IV. (L1 ∝ L2 ∧ L2 ∝ L3) ⇒ (L1 ∝ L3).
V. Se L1 ∝ L2 ∧ L2 ∝ L1 , então, pode-se afirmar que L1 e L2 (associadas a dois problemas de decisão Π1 e Π2 , respectivamente) são equivalentes.
a) I: verdadeira; II: falsa; III: falsa; IV: verdadeira. V. verdadeira. X
b) I: verdadeira; II: verdadeira; III: falsa; IV: falsa. V. falsa.
c) I: falsa; II: verdadeira; III: verdadeira; IV: falsa. V. verdadeira.
d) I: falsa; II: falsa; III: verdadeira; IV: verdadeira. V. falsa.
e) Todas são verdadeiras.
Questão 12. Considere as afirmações a seguir sobre redução polinomial ∝ e a teoria sobre NP-Completude, determine
se cada uma é verdadeira ou falsa e escolha a alternativa correta.
I. Considere a linguagem L. ((L ∈ NP) (∃L0 ∈ NP) (L0 ∝ L)) ⇒ (L ∈ NP-Completo).
II. Um problema de decisão Π ∈ NP-Completo se Π ∈ NP e existe uma redução polinomial Π0 ∝ Π em que Π0 ∈ NP.
III. Pode-se afirmar que, se algum problema na Classe NP puder ser resolvido em tempo polinomial, então, existe pelo
menos um problema em NP-Completo que pode ser resolvido em tempo polinomial.
IV. Pode-se afirmar que, se algum problema em NP é resolvido em tempo polinomial, então, todos os problemas em
NP-Completo também são resolvidos em tempo polinomial.
V. Considere que Π ∈ NP. Se for provado que P 6= NP, então, Π ∈ NP-P. De maneira similar, se fosse provado que Π ∈ P,
então, P = N P .
a) I: falsa; II: falsa; III: falsa; IV: falsa. V. verdadeira.
b) I: verdadeira; II: falsa; III: falsa; IV: verdadeira. V. verdadeira.
c) I: verdadeira; II: verdadeira; III: falsa; IV: falsa. V. falsa.
d) Todas são falsas. X
e) Todas são verdadeiras.
Assinatura:
Questão 13. Considere as afirmações a seguir, determine se cada uma é verdadeira ou falsa e escolha a alternativa
correta.
I. Para encontrar a árvore geradora mı́nima de um grafo G(V, A) com o algoritmo de Kruskal, obtém-se tempo O(|V |·lg |V |)
ao se utilizar as melhores heurı́sticas conhecidas em estruturas de dados para conjuntos disjuntos.
II. Para se resolver o problema do caminho mı́nimo em determinado vértice do grafo G(V, A) com o algoritmo de Dijkstra,
obtém-se tempo O((|A| + |V |) lg |V |) ao se utilizar uma heap de Fibonacci e tempo O(|A| + |V | lg |V |) ao se utilizar uma
heap mı́nima.
III. A complexidade do algoritmo de Floyd-Warshall é O(|V |2 ).
IV. Para se resolver o problema do caminho mı́nimo em determinado vértice do grafo G(V, A) com o algoritmo de Prim,
obtém-se tempo O(|A| · lg |V |) ao se utilizar uma heap mı́nima.
V. Para se percorrer todos os vértices de um grafo, pode-se utilizar a busca em profundidade ou a busca em largura e
ambas têm complexidade Θ(|A| + |V |).
a) Somente as afirmações I, II, IV e V são verdadeiras.
b) Somente a afirmação V é verdadeira. X
c) Somente as afirmações IV e V são verdadeiras.
d) Todas afirmações são verdadeiras.
e) Todas afirmações são falsas.
Questão 14. Conside uma constante c. Ao se resolver a recorrência T (n) = 2T (n/2) + cn · lg n, considerando-se que, se
n = 2, então, o tempo de execução é Θ(1), obtém-se, como limite superior de crescimento assintótico:
a) O(n · lg n)
b) O(n2 )
c) O(cn · lg n)
d) O(lg n)
e) O(n · (lg n)2 ) X
Questão 15. O grafo complementar Ḡ de um grafo simples G tem os mesmos vértices que G. Dois vértices são
adjacentes em Ḡ se e somente se eles não forem adjacentes em G. Se o grafo simples G tiver v vértices e e arestas,
quantas arestas tem o grafo Ḡ?
a) ve
2
b)v(v − 1) − e
c) v(v−1)
−e X
2
d)v(v − 1) − 2e
e) Nenhuma das respostas anteriores.
Questão 16. Considere o grafo G, ilustrado abaixo, e escolha a afirmativa correta.
a
b
c
d
O grafo G.
a) O vértice d é um vértice de corte.
b) A aresta associada a {d, e} é uma aresta de corte.
c) G não tem um ciclo euleriano. X
d) G não tem um caminho euleriano.
e) G não tem um ciclo hamiltoniano.
Assinatura:
e
Questão 17. Sobre Grafos Planares, qual das alternativas a seguir é incorreta?
O grafo H.
a) O grafo C5 é planar (Cn é o ciclo com n vértices, n ≥ 3).
b) O grafo K4 é planar (Kn é o grafo completo com n vértices).
c) O grafo bipartido completo K3,3 é planar. X
d) O grafo Q3 é planar (Qn é o grafo n-cubo).
e) O grafo H, ilustrado na figura acima, é planar.
Questão 18. Com relação à árvores de pesquisa, considere as afirmativas a seguir:
I. A ordem de complexidade de uma pesquisa com sucesso em uma árvore binária de pesquisa contendo n registros é O(1)
no melhor caso, O(n) no pior caso e O(log2 n) no caso médio.
II. O caminhamento conhecido como Pré-Ordem visita os nós de uma árvore binária de pesquisa em ordem crescente das
chaves de seus registros.
III. Árvore AVL é um tipo de árvore binária de pesquisa que mantém a árvore sempre balanceada após as operações de
inserção e exclusão.
IV. Árvore B é um tipo de árvore n-ária de pesquisa na qual cada nó possui n registros e n + 1 descendentes, exceto os nós
folha, que não possuem descendentes. É uma árvore balanceada, apropriada para ser usada em casos onde o número
de registros não cabe totalmente na memória principal do computador.
Assinale a alternativa correta.
a) Somente as afirmativas I e III são verdadeiras.
b) Somente a afirmativa II é falsa. X
c) Todas as afirmativas são verdadeiras.
d) Somente as afirmativas III e IV são verdadeiras.
e) As afirmativas II e IV são falsas.
Questão 19. Com relação ao processamento de cadeias de caracteres, marque a alternativa incorreta.
a) O problema de casamento de cadeias ou casamento de padrão consiste em encontrar as ocorrências de um determinado
padrão (substring) em um texto (string).
b) Algoritmos que efetuam um pré-processamento no padrão são, em geral, mais eficientes computacionalmente do que
aqueles que não o pré-processam.
c) Algoritmos que efetuam um pré-processamento no padrão e no texto conseguem uma complexidade de tempo e de espaço
menores do que aqueles que pré-processam apenas o padrão. X
d) A criação de arquivo invertido (ou lista invertida) é uma estratégia usada por algoritmos que pré-processam o padrão e
o texto.
e) Os seguintes são algoritmos conhecidos que efetuam o pré-processamento somente do padrão: Knuth-Morris-Pratt, BoyerMoore, Rabin-Karp.
Assinatura:
Questão 20. Com relação à ordenação externa (ou ordenação em memória secundária), temos que:
I. A ordenação externa envolve arquivos compostos por um número de registros que é maior do que a quantidade de
registros que podem ser armazenados na memória interna (principal) do computador.
II. O custo principal na ordenação externa está relacionado com o acesso à memória externa.
III. Nos métodos de intercalação balanceada de vários caminhos, inicialmente é realizada uma passada sobre o arquivo,
quebrando-o em blocos do tamanho da memória interna disponı́vel. Cada bloco é ordenado na memória interna e
gravado de volta na memória externa. Depois, os blocos ordenados são intercalados, fazendo várias passadas sobre o
arquivo. A cada passada são criados blocos ordenados cada vez maiores, até que todo o arquivo esteja ordenado.
IV. Os algoritmos para ordenação externa baseados em intercalação devem procurar reduzir o número de passadas sobre
o arquivo. Uma medida de complexidade de um algoritmo de ordenação por intercalação é o número de vezes que um
item é lido ou escrito na memória externa auxiliar.
V. O algoritmo de ordenação externa conhecido como Quicksort Externo ordena os registros de um arquivo sem a necessidade de memória externa auxiliar além da que é utilizada pelo arquivo original.
a) Apenas as afirmativas I e V são verdadeiras.
b) Apenas as afirmativas III, IV e V são verdadeiras.
c) Apenas a afirmativa IV é falsa.
d) Apenas a afirmativa V é falsa.
e) Todas afirmativas são verdadeiras.X
Questão 21. Com relação a linguagens de programação, considere as afirmações a seguir, determine se cada uma é
verdadeira ou falsa e escolha a alternativa correta.
I. O paradigma da programação funcional é baseado em funções matemáticas e composição de funções.
II. PROLOG é uma linguagem de programação cuja sintaxe é uma versão simplificada do cálculo de predicados e seu
método de inferência é uma forma restrita de Resolução.
III. O paradigma orientado a objeto surgiu em paralelo ao desenvolvimento de Smalltalk.
a) Somente a afirmativa I é verdadeira.
b) Somente a afirmativa II é verdadeira.
c) Somente as afirmativas I e III são verdadeiras.
d) Somente as afirmativas II e III são verdadeiras.
e) Todas as afirmativas são verdadeiras. X
Questão 22. Considere as afirmações a seguir, determine se cada uma é verdadeira ou falsa e escolha a alternativa
correta.
I. Ocultar dados dentro das classes e torná-los disponı́veis apenas por meio de métodos é uma técnica muito usada em
programas orientados a objetos e é chamada de sobrescrita de atributos.
II. Uma subclasse pode implementar novamente métodos que foram herdados de uma superclasse. Chamamos isso de
sobrecarga de métodos.
III. Em Java não existe Herança múltipla como em C++. A única maneira se se obter algo parecido é via interfaces.
a) Apenas a afirmativa I é falsa.
b) Apenas a afirmativa II é falsa.
c) Apenas a afirmativa III é falsa.
d) Apenas as afirmativas I e III são falsas.
e) Apenas as afirmativas I e II estão falsas. X
Assinatura:
Questão 23.O mecanismo de herança, no paradigma da programação orientada a objetos, é uma forma de reutilização
de software na qual uma nova classe é criada, absorvendo membros de uma classe existente e aprimorada com
capacidades novas ou modificadas. Considere as seguintes classes descritas na linguagem Java.
public class A
{
protected int v;
public A() {
v = 0;
}
public void m1() {
v += 10;
m2();
}
public void m2() {
v += 20;
}
public int getv() {
return v;
}
}
public class B extends A
{
public void m2() {
v += 30;
}
}
Se essas classes forem utilizadas a partir do programa a seguir,
public static final void main(String[] args) {
B obj = new B();
obj.m1();
obj.m2();
System.out.println(obj.getv());
}
a saı́da do código computacional acima será:
a) 30
b) 40
c) 50
d) 60
Questão 24. Das afirmações a seguir, sobre memória cache, quais são verdadeiras?
I. Numa estrutura totalmente associativa, um bloco de memória pode ser mapeado em qualquer slot do cache.
II. O campo tag do endereço é usado para identificar um bloco válido no cache, junto com o campo de ı́ndice.
III. Um cache de nı́vel 1 serve para reduzir a penalidade no caso de falta no nı́vel 2.
IV. O esquema de substituição LRU é o mais usado para a estrutura de mapeamento direto.
a) Somente as afirmações I, III e IV.
b) Somente as afirmações II, III e IV.
c) Somente afirmações I e II. X
d) Somente as afirmações I, II e III.
e) Somente as afirmações II e III.
Assinatura:
e) 70 X
Questão 25. Ao segmentar um processador utilizando a técnica de pipeling, obtém-se:
a) redução no número de ciclos necessários para executar um programa. X
b) redução no número de ciclos necessários para executar uma instrução.
c) redução no número de ciclos necessários para tratar uma interrupção.
d) redução no número de ciclos necessários para tratar uma exceção.
e) o circuito do processador fica mais simples.
Questão 26. Um registrador de deslocamento (shift register) é um componente importante para qual(quais) dos
dispositivos listados a seguir:
I. porta paralela.
II. porta serial (UART, ou universal asynchronous receiver/transmitter).
III. multiplicador sequencial.
IV. somador.
a) Somente I e II.
b) Somente II e IV.
c) Somente III e IV.
d) Somente I e III.
e) Somente II e III. X
Questão 27. Com relação ao acesso ao disco, considere as afirmações a seguir, determine se cada uma é verdadeira
ou falsa e escolha a alternativa correta.
I. O acesso a setores localizados em sequência em uma mesma trilha de um disco é mais rápido do que acessar o mesmo
número de setores em trilhas diferentes, devido ao menor número de deslocamentos do cabeçote e rotações no disco.
II. O escalonamento de operações de entrada e saı́da em um disco rı́gido pode ser utilizado para aumentar o desempenho.
Porém, algoritmos como o SSTF (Shortest Seek Time First) podem fazer com que requisições esperem indefinidamente.
III. Para minimizar o deslocamento do cabeçote, o algoritmo do elevador prioriza requisições de acesso a cilindros do disco
que estão mais próximos da posição atual do cabeçote.
a) Apenas a afirmativa I é verdadeira.
b) Apenas as afirmativas I e II são verdadeiras. X
c) Apenas a afirmativas II e III são verdadeiras.
d) Apenas a afirmativa III é verdadeira.
e) Todas afirmativas são verdadeiras.
Questão 28. Técnicas eficientes para o uso de memória, como memória virtual e caching, podem ser utilizadas porque:
a) o princı́pio da localidade pode ser aplicado. X
b) aumentou o espaço de armazenamento em RAM.
c) memórias dinâmicas são mais rápidas que memórias estáticas.
d) o thrashing não pode ocorrer em memórias modernas.
e) aumentou a velocidade de acesso para a memória RAM.
Questão 29. Qual dos seguintes mecanismos é o menos recomendado para se implementar regiões crı́ticas em sistemas
operacionais?
a) Espera ocupada. X
b) Variáveis de condição.
c) Monitores.
d) Semáforo.
e) Troca de mensagens.
Assinatura:
Questão 30. Qual das opções abaixo melhor caracteriza o protocolo IP?
a) Não orientado a conexão, sem suporte a QoS, sem mecanismo de retransmissão. X
b) Orientado a conexão, sem suporte a QoS, sem mecanismo de retransmissão.
c) Orientado a conexão, com suporte a QoS, com mecanismo de retransmissão.
d) Orientado a conexão, sem suporte a QoS, com mecanismo de retransmissão.
e) Não orientado a conexão, com suporte a QoS, sem mecanismo de retransmissão.
Questão 31. Considere as afirmações a seguir, determine se cada uma é verdadeira ou falsa e escolha a alternativa
correta.
I. O protocolo UDP é um protocolo da Camada de Transporte orientado a datagrama, enquanto que o TCP é um protocolo
da Camada de Transporte orientado a conexão.
II. Apesar de o protocolo IP ser orientado a datagrama, o protocolo UDP é necessário por fornecer multiplexação de um
endereço de rede em várias portas, permitindo que múltiplos processos sejam endereçados em um mesmo endereço de
rede.
III. O protocolo TCP utiliza o tamanho da janela deslizante de uma conexão para o controle de congestionamento.
a) Somente a afirmativa I é verdadeira.
b) Somente as afirmativas I e II são verdadeiras.
c) Somente as afirmativas I e III são verdadeiras.
d) Somente as afirmativas II e III são verdadeiras.
e) Todas as afirmativas são verdadeiras. X
Questão 32. Algoritmos de roteamento são o meio que um roteador utiliza para encaminhar mensagens na camada
de rede. Assinale a alternativa incorreta.
a) Nos algoritmos de roteamento estáticos as rotas são determinadas via tabelas definidas a priori e fixadas para o roteador,
em geral manualmente.
b) No roteamento por Vetor de Distância (Distance Vector), as tabelas de roteamento definidas pelos roteadores vizinhos
são repassadas periodicamente a cada roteador para obtenção de sua própria tabela.
c) No roteamento de Estado de Enlace (Link State), os valores dos enlaces são calculados pelo projetista da rede e os
roteadores atualizam suas tabelas por estes valores. X
d) Algoritmos de roteamento buscam estabelecer o caminho de menor custo entre dois hosts através do cálculo dos custos
acumulados mı́nimos entre os enlaces disponı́veis, dada a topologia da rede.
e) O OSPF é um exemplo de protocolo de roteamento baseado em Estado de Enlace e o BGP é um exemplo de protocolo
de roteamento baseado em Vetor de Distâncias.
Questão 33. Com relação a conceitos básicos de banco de dados, assinale a alternativa correta.
a) A principal vantagem da independência fı́sica de dados é permitir que caracterı́sticas da representação e organização dos
dados possam ser controladas por programas de aplicação.
b) O modelo de dados é uma combinação de três componentes: uma coleção de tipos de estruturas de dados, uma coleção de
operadores (ou regras de inferência) para manipulação dessas estruturas e regras de integridade definindo a consistência
dos dados. X
c) A linguagem SQL é uma linguagem inerentemente procedural ao passo que a álgebra relational é declarativa.
d) A propriedade de Isolamento de uma transação refere-se ao princı́pio “tudo ou nada”: ou todas operação de uma transação
são refletidas no banco de dados, ou nenhuma delas.
e) No contexto de transações, uma “leitura suja” ocorre quando dados corrompidos são lidos do disco.
Assinatura:
Questão 34. Com relação ao processamento de consultas em sistemas gerenciadores de banco de dados, considere as
afirmações a seguir, determine se cada uma é verdadeira ou falsa e escolha a alternativa correta.
I. Algoritmos de junção baseados em hashing são normalmente beneficiados (executam mais rápido) quando a distribuição
de dados não é uniforme.
II. Algoritmos de junção baseados em laços aninhados podem ser usados para implementar junções envolvendo qualquer
tipo de condição, por exemplo, condições usando os operadores como <, >, e 6= e, também, UDFs (user defined
functions).
III. O algoritmo de junção sort-merge produz como resultado uma relação ordenada pelas chaves primárias das duas relações.
IV. Operações de seleção são normalmente executadas primeiro em um plano de execução de consultas.
V. Considere uma operação de seleção sobre o atributo de uma determinada relação e um ı́ndice definido sobre este atributo.
Quanto menor for a quantidade de valores distintos deste atributo, maior é o benefı́cio de se usar o ı́ndice na execução
da operação.
a) Apenas as afirmativas I e III são verdadeiras.
b) Apenas as afirmativas I e V são verdadeiras.
c) Apenas as afirmativas II e III são verdadeiras.
d) Apenas as afirmativas II e IV são verdadeiras. X
e) Apenas as afirmativas IV e V são verdadeiras.
Questão 35. Considere as seguintes tabelas de um banco de dados contendo informações sobre alunos, disciplinas e
a vinculação estabelecida quando um aluno se matricula em uma disciplina:
Aluno (ID, Nome)
Disciplina (Nome Disciplina, Carga Horaria)
Matricula(ID, Nome Disciplina, Periodo)
Em cada tabela, os atributos sublinhados fazem parte da chave primária e não existem outras chaves (candidatas) além
da chave primária. Considere a seguinte consulta: “Liste o nome de cada aluno que tenha cursado pelo menos uma vez a
disciplina ’Banco de dados’ ”. Abaixo, encontram-se duas possı́veis especificações para esta consulta em SQL.
Q1: SELECT Nome
FROM Aluno
WHERE ID in (SELECT ID
FROM Matricula
WHERE Nome_Disciplina = ’Banco de Dados’)
Q2: SELECT Nome
FROM Aluno, Matricula
WHERE Aluno.ID = Matricula.ID AND Nome_Disciplina = ’Banco de Dados’
Analise as seguintes afirmativas a respetio de Q1 e Q2 e assinale a alternativa correta.
a) Tanto Q1 quanto Q2 produzem o resultado esperado para a consulta, mas Q1 irá, provavelmente, ser executada de maneira
mais eficiente.
b) Tanto Q1 quanto Q2 produzem o resultado esperado para a consulta, mas Q2 irá, provavelmente, ser executada de maneira
mais eficiente.
c) Apenas Q1 produz o resultado esperado para a consulta. X
d) Apenas Q2 produz o resultado esperado para a consulta.
e) Q1 e Q2 não produzem o resultado esperado para a consulta, mas este problema pode ser corrigido inserindo a palavrachave DISTINCT na cláusula SELECT das duas consultas.
Assinatura: