Simulado 3 Concurso Professor De História

Para Baixar Pdf:

1-Sejam duas funções f(n) e g(n) que mapeiam números inteiros positivos em números
reais positivos.
Analise as afirmativas relativas às notações assintóticas de complexidade e assinale V
para as alternativas verdadeiras e F para as falsas.
( ) Diz-se que f(n) é Θ (g(n)) se existem constantes reais c1 > 0 e c2 > 0 e existe uma
constante inteira n0>=1 tal que c2* g(n)<=f(n) <=c1* g(n) para todo inteiro n>= n0.
( ) Diz-se que f(n) é Θ (g(n)) se, e somente se, f(n) é O(g(n)) e f(n) é Ω (g(n)).
A partir dessa análise, assinale a sequência CORRETA.
A) V V.
B) V F.
C) F F.
D) F V

2-Resolva a relação de recorrência a seguir e assinale a alternativa CORRETA.
T(n) = 8T(n/2) + n
A) T(n)=Θ(n3
).
B) T(n)=Θ(n).
C) T(n)=Θ(nlog n).
D) T(n)=Θ(n3
log n).

3-Resolva a seguinte relação de recorrência:
T(n) = 9T(n/3) + n2
O resultado será:
A) T(n)=Θ(n).
B) T(n)=Θ(n2
log n).
C) T(n)=Θ(n2
).
D) T(n)=Θ(nlog n)

4-Resolva a relação de recorrência a seguir:
T(n) = 2T(n/2) + n2
O resultado será:
A) T(n)=Θ(n3
log n).
B) T(n)=Θ(n).
C) T(n)=Θ(n2
log n).
D) T(n)=Θ(n2
).

5-Analise as afirmativas concernentes aos algoritmos de processamento de caracteres,
assinalando V para as afirmativas verdadeiras e F para as falsas.
( ) O algoritmo Boyer-Moore é mais eficiente quanto maior for o tamanho do padrão
de busca.
( ) Os algoritmos Shift-And e Knuth–Morris–Pratt (KMP) não tem necessidade de
retroceder para reler a entrada do texto.
A partir dessa análise, assinale a sequência CORRETA.
A) V F.
B) F F.
C) V V.
D) F V.

7-Analise as afirmativas que tratam dos algoritmos de processamento de caracteres,
assinalando V para as afirmativas verdadeiras e F para as falsas.
( ) O algoritmo Knuth–Morris–Pratt (KMP) é mais eficiente quando maior for o
tamanho do padrão de busca.
( ) O algoritmo de busca em autômatos não tem necessidade de retroceder para
reler a entrada do texto.
A partir dessa análise, assinale a sequência CORRETA.
A) V V.
B) F F.
C) V F.
D) F V.

8-Dados dois números quaisquer de n bits, assinale a alternativa que apresenta
CORRETAMENTE a complexidade para somá-los.
A) Ο(n).
B) Ο(1).
C) Ο(nlog n).
D) Ο(log n)

O formato de uma moldura de página da arquitetura (fictícia) k86 reserva os bits 0 a 23
para o endereço da moldura de página na memória física, usados para indexar a tabela
de páginas.
Admitindo um sistema de memória virtual paginada com tamanho de página de 2K bytes,
assinale a alternativa que apresenta qual a quantidade máxima CORRETA de memória
que um processo pode usar.
A) 32G bytes.
B) 16G bytes.
C) 16M bytes.
D) 32M bytes.

9-Considerando as funções f1 = log2 n e f2 = log10 n, assinale a alternativa CORRETA.
A) As funções são assintoticamente equivalentes.
B) A função f1 domina assintoticamente a função f2.
C) A função f2 domina assintoticamente a função f1.
D) As funções não são deriváveis.

10-Numere as estruturas de dados da COLUNA II com os algoritmos apresentados na
COLUNA I.
COLUNA I COLUNA II
1. Busca em largura. ( ) Pilha.
2. Busca em profundidade. ( ) Fila.
3. Caminho mínimo. ( ) Heap.
Assinale a alternativa que apresenta a sequência CORRETA.
A) 1 2 3.
B) 2 1 3.
C) 3 2 1.
D) 2 3 1.

Gabarito

1-B
2-A
3-D
4-B
5-C
6-B
7-A
8-C
9-C
10-A