120-2008

MO640 - Questão para a prova oral
Número: 120
Enunciado:
No último passo do algoritmo quase-linear para adição de uma nova restrição a uma árvore PQR, quais são os nós que precisarão ser descoloridos?

1. Todos os nós P pretos da árvore
2. Todos os nós P cinzas da árvore
3. Todos os nós pretos da árvore
4. Todos os nós cinzas da árvore
5. NDA

Autor(a): Priscila do Nascimento Biller

119-2008

MO640 - Questão para a prova oral
Número: 119
Enunciado:
No artigo "Building PQR Trees in Almost Linear Time", de Telles e Meidanis, temos a descrição de um algoritmo para adicinar uma restricao S a uma arvore PQR T em cinco passos. O segundo passo se refere a coloração dos nós internos de T e a determinacao do ancestral comum mais recente das folhas de S. Sobre essa coloração, considere as afirmações a seguir:

I - Um nó é colorido com "cinza" quando sua intersecção com S é nula.
II - Um nó é colorido com "preto" se for ortogonal ao conjunto S.
III - Se o conjunto S estiver contido em um nó, então o nó deverá ser colorido com "branco".

Quais delas estão corretas?

1. I
2. III
3. II, III
4. I, II
5. NDA

Autor(a): Bruno Conti Marini

118-2008

MO640 - Questão para a prova oral
Número: 118
Enunciado:
Com relação aos conceitos de nós pretos, cinzas e brancos do artigo "Building PQR Trees in Almost-Linear Time" [Meidanis e Telles, 2007] e a árvore descrita abaixo onde as folhas coloridas de preto são os elementos que estão contidos nas restrições em análise, assinale a alternativa que corresponde à caracterização dos nós A, B e C:

1. A = Cinza; B = Branco; C = Branco;
2. A = Cinza; B = Cinza; C = Branco;
3. A = Cinza; B = Cinza; C = Cinza;
4. A = Preto; B = Cinza; C = Preto;
5. NDA

Autor(a): Tiago Takamoto

117-2008

MO640 - Questão para a prova oral
Número: 117
Enunciado:
No algoritmo quase-linear de construção de uma árvore PQR, qual tipo de operação domina o número de operações durante o passo de reestruturar a árvore?

1. Destruir nós.
2. Mover nós.
3. Criar nós.
4. Reverter nós.
5. NDA

Autor(a): João Paulo Pereira Zanetti

116-2008

MO640 - Questão para a prova oral
Número: 116
Enunciado:
Sobre o artigo "Building PQR Trees in Almost-Linear Time" [Meidanis e Telles, 2007], qual(is) das afirmações abaixo é (são) verdadeiras.

I- O algoritmo apresentado é offline.

II- O algoritmo incia com uma árvore universal, na qual todas as folhas são filhas de um mesmo nó P.

III- Todos os nós brancos devem ser eliminados durante a execução do algoritmo.

IV- Os conjuntos de filhos dos nós Q e R são implementados como estruturas "union-find", o que garante complexidade de tempo quase linear ao algoritmo.

1. III, apenas.
2. II e IV.
3. II, e III.
4. I, II e IV.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

115-2008

MO640 - Questão para a prova oral
Número: 115

Enunciado: Considere a sub-árvore PQR à esquerda, com os nós coloridos em preto, cinza e branco da maneira descrita no artigo Building PQR Trees in Almost-Linear Time (Telles & Meidanis, 2007). Seja o nó r o mínimo ancestral comum (LCA - least common ancestor) e seja o nó v um nó cinza que se deseja eliminar. Verifique qual das sub-árvores abaixo melhor representa o processo "transformar nó P em nó Q" ("transform P node into Q node"):

1. 
   
   
2. 
   
   
3. 
   
   
4. 
   
   
5. NDA

Autor(a): Fabio L. Usberti

114-2008

MO640 - Questão para a prova oral
Número: 114
Enunciado:
Sendo C = { abcd, bcdef, afghijk, bcdgh, ghijk }, escolha a alternativa que contem todos os conjuntos de gêmeos desta coleção:

1. abc, gh, ijk.
2. bcd, ef, hij.
3. bcd, gh, ghi.
4. bcd, gh, ijk.
5. NDA

Autor(a): Victor de Abreu Iizuka

113-2008

MO640 - Questão para a prova oral
Número: 113
Enunciado:
Seja U um conjunto de objetos e C uma coleção de subconjuntos de U. O grafo de sobreposição (overlapping graph) utilizado no artigo "On the consecutive ones property" (Meidanis et al., 1998), é definido de tal forma que seus vértices são _______________ e suas arestas incidem em dois vértices quando estes são ________________. Selecione a aternativa abaixo que melhor preenche as lacunas do texto respectivamente:

1. elementos de U; elementos consecutivos para a coleção C.
2. elementos de U; elementos não-consecutivos para a coleção C.
3. conjuntos da coleção C; dois conjuntos tal que sua união gera o conjunto U.
4. conjuntos da coleção C; dois conjuntos com interseção não-vazia e nenhum contido no outro.
5. NDA

Autor(a): Fabio L. Usberti

112-2008

MO640 - Questão para a prova oral
Número: 112
Sobre o texto "On the consecutive ones property", de Meidanis, Porto e Telles, 1998, e o algoritmo de montagem de árvores PQR proposto, considere as seguintes afirmações:

I - o algoritmo é um método ONLINE.
II - o algoritmo tem complexidade de tempo quadrática.
III - o algoritmo sempre consegue montar uma árvore PQR dado um conjunto universo e uma coleção (subconjuntos do universo).

São corretas as afirmações:

1. somente I.
2. somente II.
3. somente III.
4. somente II e III.
5. NDA

Autor(a): Gustavo Waku

111-2008

MO640 - Questão para a prova oral
Número: 111
Enunciado:
Com relação ao algoritmo de Coarsest Partition (Partição mais grossa), assinale a alternativa INCORRETA:

1. Um conjunto cujos elementos todos fazem parte da restrição em análise não sofrerá partição.
2. O primeiro passo do algoritmo é marcar cada elemento do conjunto de acordo com as restrições a que ele pertence.
3. O algoritmo é usado no contexto de árvores PQR para encontrar todos os conjuntos de gêmeos entre as restrições em análise.
4. O algoritmo pode utilizar listas ligadas para permitir que a partição dos conjuntos a cada restrição seja executada em tempo linear no tamanho da restrição.
5. NDA

Autor(a): Tiago Takamoto

110-2008

MO640 - Questão para a prova oral
Número: 110
Enunciado:
Com relação aos conceitos de árvore PQR, assinale a alternativa que contenha TODAS as sentenças que são VERDADEIRAS:

I. Dois conjuntos são ortogonais quando não apresentam sobreposição estrita.
II. A presença de um nó R numa árvore PQR significa que a matriz de entrada não tem a propriedade de Uns Consecutivos.
III. O número mínimo de filhos de um nó R é igual ao número mínimo de filhos de um nó Q.

1. I
2. I e II
3. I e III
4. I e II e III
5. NDA

Autor(a): Tiago Takamoto

109-2008

MO640 - Questão para a prova oral
Número: 109
Sobre o texto de K. S. Booth and G. S. Lueker, "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", considere as seguintes afirmações:

I - A implementação que manipula as árvores PQ discutida no artigo basicamente se divide em dois algoritmos, BUBBLE e REDUCE, onde cada um destes percorre a árvore PQ duas vezes.
II - O algoritmo REDUCE realiza a redução em uma subárvore podada de T em relação a S. ( T = árvore PQ original, S = subconjunto de U, U = conjunto universo).
III - O número de nós com ponteiros para os pais é reduzido, porque o esforço para manutenção dos ponteiros corretos geraria um trabalho pribitivo caso um nó interno que tivesse um grande número de filhos vazios fosse apagado.
IV - Se a árvore só possuir nós tipo P, em cada nó, o número de FILHOS pertinentes será sempre igual ao número de FOLHAS pertinentes.

São corretas as afirmações:

1. somente I.
2. somente II.
3. somente II e III.
4. somente IV.
5. NDA

Autor(a): Gustavo Waku

108-2008

MO640 - Questão para a prova oral
Número: 108
Enunciado:
Das afirmações abaixo, quais são verdadeiras sobre o algoritmo para a construção de árvores PQ de Booth e Lueker [1976]:
I- O algoritmo possui duas passagens, a primeira para identificação dos nós a serem processados e a segunda para aplicação de reduções.
II- Todos filhos de nós Q tem ponteiros para os pais.
III- A complexidade linear é confirmada por uma análise amortizada.

1. I e II.
2. I e III.
3. II.
4. III.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

107-2008

MO640 - Questão para a prova oral
Número: 107
Enunciado:
Dado um conjunto U = {A, B, C, D} qual conjunto de restrições abaixo inviabilizaria a construção de uma PQ-Tree, conforme descrito em [1]?

[1] Booth and Lueker, Testing for the Consecutive Ones Property, Interval Graph, and Planarity Using PQ-Tree Algorithms, 1976.

1. {A, B}, {B, C}, {C, D}
2. {A, C}, {B, D}
3. {A, C}, {A, D}, {C, D}
4. {A, C}, {A, D}, {B, D}
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

106-2008

MO640 - Questão para a prova oral
Número: 106

Enunciado:

Qual das permutações abaixo é consistente com a árvore-PQ acima?

1. ACDEGFB
2. BFDECGA
3. DEFGABC
4. GFEDBCA
5. NDA

Autor(a): Fabio L. Usberti

105-2008

MO640 - Questão para a prova oral
Número: 105
Enunciado:
Em uma PQ-tree, com relação a uma nova restrição, qual das afirmações abaixo é verdadeira?

1. Se um nó é parcial, então nenhum dos seus nós descendentes é cheio
2. Se um nó é parcial, então nenhum dos seus nós descendentes é pertinente
3. Se um nó possui algum dos seus nós descendentes vazio, então ele só pode ser um nó vazio
4. Se um nó possui algum dos seus nós descendentes cheio, então ele só pode ser um nó pertinente
5. NDA

Autor(a): Priscila do Nascimento Biller

104-2008

MO640 - Questão para a prova oral
Número: 104
Enunciado:
Dadas as afirmações abaixo, quais são verdadeiras sobre árvores PQ sobre um conjunto U:
I- Transformações de equilalência permitidas são permutações de filhos em nós P e inversão da ordem dos filhos em nós Q.
II- Em uma árvore PQ própria existem elementos do conjunto universal U que podem ser omitidos.
III- Com relação a uma nova restrição S, um nó é cheio se todas as folhas descendentes estão em S e vazio se nem todas estão.

1. I, II e III.
2. I e II.
3. Apenas I.
4. Apenas II.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

103-2008

MO640 - Questão para a prova oral
Número: 103
Enunciado:
Seja T uma árvore PQ própria sobre um conjunto universal U e construída sobre um conjunto de restrições S. Qual a alternativa falsa?

1. Cada restrição em S é um subconjunto de U.
2. Todas as árvores equivalentes a T satisfazem S.
3. A fronteira de T é uma permutação de U que satisfaz S.
4. Para qualquer conjunto de restrições existe uma árvore PQ que as satisfaz.
5. NDA

Autor(a): João Paulo Pereira Zanetti

102-2008

MO640 - Questão para a prova oral
Número:  102
Dado a árvore PQ abaixo, relativo ao conjunto U = { A, B, C, D, E, F}



Quantas árvores equivalentes a ela existem?

1. 192
2. 32
3. 48
4. 96
5. NDA

Autor(a): Gustavo Waku

101-2008

MO640 - Questão para a prova oral
Número: 101
Enunciado:
Analise a seguinte afirmação:
Numa árvore PQ sobre um conjunto U os elementos de U ocupam _______ da arvore. Cada nó P tem que ter no mínimo __ filhos, cuja ordem pode ser __________________ em transformações de equivalência. Já os nós Q tem que ter no mínimo __ filhos, cuja ordem pode ser __________________ em transformações de equivalência.
A alternativa que melhor preenche as lacunas é:

1. nós, 3, modificada arbitrariamente, 2, invertida.
2. folhas, 3, invertida, 2, modificada arbitrariamente.
3. folhas, 2, modificada arbitrariamente, 3, invertida.
4. nós, 2, invertida, 3, modificada arbitrariamente.
5. NDA.

Autor(a): Danilo Brandão Gonçalves

100-2008

MO640 - Questão para a prova oral
Número: 100
Enunciado:
Qual das alternativas abaixo é vista como uma desvantagem de usar a distância como critério de linearidade entre estruturas genéticas?

1. A distância leva em conta recombinações e apenas alguns tipos de mutações, como inserções e deleções
2. A distância leva em conta somente as mutações, deixando de lado recombinações
3. A distância leva em conta inserções mas desconsidera deleções
4. A distância nem sempre é estritamente aditiva
5. NDA

Autor(a): Priscila do Nascimento Biller

099-2008

MO640 - Questão para a prova oral
Número: 099
Enunciado:
Segundo o texto "On the topology of the genetic fine structure" discutido em aula, consirede as seguintes afirmações:

I - O teste de recombinação verifica se dados dois mutantes é possível gerar novamente a estrutura padrão que lhes deu origem.
II - O teste de recombinação é um experimento de cunho essencialmente quantitativo.
III - A matriz de recombinação indica se dois mutantes são capazes de gerar novamente a estrutura linear padrão; e quando ordenada na ordem de dicionário possui a característica de ser simétrica e para qualquer linha ou coluna, partindo da diagonal para a direita ou para baixo, a sequência de zeros forma um bloco contíguo (ininterrupto por "1"s).
IV - Os mutantes escolhidos no artigo para montagem do trabalho, são não-reversíveis e podem ter até duas modificações separadas por um bloco sem modificação.

São CORRETAS as afirmações:

1. somente I e II.
2. somente I e III.
3. somente II e IV.
4. somente II, III e IV.
5. NDA

Autor(a): Gustavo Waku

098-2008

MO640 - Questão para a prova oral
Número: 098
Enunciado:
No experimento de Benzer sao testados vírus mutantes em várias cepas de bactérias, em particular a cepa K. Imagine um experimento deste tipo onde foram criados 5 vírus mutantes (A, B, C, D e E) a partir de um vírus padrão (que consegue se reproduzir em K). Após realizados alguns experimentos chegou-se às seguintes conclusões:
- A, B, C e D não conseguem se reproduzir em K sozinhos, mas E sim.
- A e C conseguem se reproduzir em K quando misturados
- B e D não conseguem se reproduzir em K mesmo quando misturados
Pode-se dizer então que:

1. E é estável. Não existe sobreposição entre as partes mutadas de A e C. Existe sobreposição entre as partes mutadas de B e D.
2. E é estável. Existe sobreposição entre as partes mutadas de A e C. Não Existe sobreposição entre as partes mutadas de B e D.
3. E é instável. Não existe sobreposição entre as partes mutadas de A e C. Existe sobreposição entre as partes mutadas de B e D.
4. E é instável. Existe sobreposição entre as partes mutadas de A e C. Não existe sobreposição entre as partes mutadas de B e D.
5. NDA

Autor(a): Bruno Conti Marini

097-2008

MO640 - Questão para a prova oral
Número: 097
Enunciado:
Do artigo "On The Topology of the genetic fine structure" [Benzer, 1959], podemos entender que, no mapeamento genético:

1. mutação e recombinação são necessárias.
2. mutação e recombinação são dispensáveis.
3. mutação é necessária e recombinação nem sempre.
4. mutação nem sempre é necessária, mas recombinação sempre é.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

096-2008

MO640 - Questão para a prova oral
Número: 096
Enunciado:
Qual das mutações abaixo é mais dificilmente revertida?

1. Deleção.
2. Inserção.
3. Reversão.
4. Mudança em uma base.
5. NDA

Autor(a): João Paulo Pereira Zanetti

095-2008

MO640 - Questão para a prova oral
Número: 095
Enunciado:
Usando os métodos de Bergeron e colegas quanto à ordenação por translocação, assinale a alterativa que contém o número mínimo de translocações para transformar o genoma A no genoma B:

A = {(1,4,5,2),(3,6,7,8)};
B = {(1,2),(3,4,5,6,7,8)};

Dica: d(A)=n - N - c + t

1. 2
2. 3
3. 4
4. 5
5. NDA

Autor(a): Tiago Takamoto

094-2008

MO640 - Questão para a prova oral
Número: 094
Enunciado:
No problema de rearranjo de genomas sempre há uma operação DCJ (double-cut-and-join) que reduz a diferença entre o número de breakpoints e de ciclos (b - c) em uma unidade, exceto quando o genoma já se encontra ordenado. Outras características deste problema são:

1. Uma operação DCJ não pode aumentar (b - c).
2. Uma operação DCJ sempre aumenta o número de ciclos.
3. Uma operação DCJ sempre diminui o número de breakpoints.
4. a distância genômica, com relação à operação DCJ, é igual a (b - c).
5. NDA

Autor(a): Fabio L. Usberti

093-2008

MO640 - Questão para a prova oral
Número: 093
Enunciado:
Dado os genomas: A={(3 2)(1 4 8)(6 7 5)} e B={(1 2)(3 4 5)(6 7 8)} Quais das afirmativas abaixo são FALSAS:
I- Os genomas não são "co-tailed".
II- Exitem dois ciclos pretos para uma concatenação de A.
III- A translocação que gera A1={(3 4 8)(1 2)(6 7 5)}, partindo de A, é interna.

1. I.
2. II.
3. I e II.
4. I, II e III.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

092-2008

MO640 - Questão para a prova oral
Número: 092
Enunciado:
De acordo com o artigo "On Sorting by Translocations" de Bergeron, Mixtacki e Stoye, a complexidade dos algoritmos para encontrar a distância de translocação e para fazer a ordenação por translocações em genomas de tamanho n é, respectivamente:

1. O(n) e O(n²)
2. O(n) e O(n³)
3. O(n²) e O(n²)
4. O(n²) e O(n³)
5. NDA

Autor(a): Victor de Abreu Iizuka

091-2008

MO640 - Questão para a prova oral
Número: 091
Enunciado:
Sobre a operação Double-Cut-Join descrita no artigo "Efficient sorting of genomic permutations by translocation, inversion and block interchange" é incorreto afirmar que:

1. Considera diretamente obstáculos (hurdles)
2. Pode diminuir ou aumentar o número de ciclos
3. Pode gerar cromossomos circulares intermediários
4. É uma operação local que opera em quatro vértices inicialmente conectados em pares
5. NDA

Autor(a): Bruno Conti Marini

090-2008

MO640 - Questão para a prova oral
Número: 090
Enunciado:
Quais dos eventos de evolução a seguir podem ser modelados por uma ou mais aplicações da operação de double-cut-and-join?

I - Translocação
II - Reversão
III - Troca de blocos

1. Somente I e II.
2. Somente I e III.
3. Somente II e III.
4. I, II e III.
5. NDA

Autor(a): João Paulo Pereira Zanetti

089-2008

MO640 - Questão para a prova oral

Número: 089

Enunciado:
A menor fortaleza possui quantos ciclos?

1. 3
2. 6
3. 9
4. 12
5. NDA

Autor(a): Priscila do Nascimento Biller

088-2008

MO640 - Questão para a prova oral
Número: 088

Enunciado: Na literatura encontramos a fórmula da distância de reversão: d = n + 1 - c + h + f. Considere o diagrama realidade e desejo ao lado. Qual é o valor da distância de reversão? 10 11 12 13 NDA

Autor(a): Gustavo Waku

087-2008

MO640 - Questão para a prova oral
Número: 087
Enunciado:
Sobre o algoritmo de Bader, Moret e Yan para o cálculo de distância de reversão de permutações de tamanho n, podemos afirmar que:

1. Seu limitante inferior de tempo é O(n²).
2. Ele executa em O(n) para a maioria dos casos, mas não para todos.
3. Ele calcula a distância e os passos da ordenação em tempo O(n).
4. Ele calcula a distância em complexidade O(n) mas não calcula os passos da ordenação.
5. NDA.

Autor(a): Danilo Brandão Gonçalves

086-2008

MO640 - Questão para a prova oral
Número: 086
Enunciado:
Encontramos fórmulas diferentes na literatura para a distância de seqüências por reversão:

1. d(α) = n + 1 - c(α) + h(α) + f
2. d(α) = b(α) - c(α) + h(α) + f

onde n é o comprimento da seqüencia, b(α) é o número de breakpoints, h(α) é o número de obstáculos (hurdles) e f é um fator de correção para fortalezas (fortresses).

Por que há esta diferença?

1. Na 1ª fórmula c(α) é o total de ciclos menos os ciclos de tamanho 2. Na segunda c(α) é simplesmente o total de ciclos.
2. Na 2ª fórmula c(α) é o total de ciclos menos os ciclos de tamanho 2. Na primeira c(α) é simplesmente o total de ciclos.
3. Na 2ª fórmula c(α) é o total de ciclos bons. Na primeira c(α) é o total de ciclos ruins.
4. Na 1ª fórmula c(α) é o total de ciclos bons. Na segunda c(α) é o total de ciclos ruins.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

085-2008

MO640 - Questão para a prova oral
Número: 085
Enunciado: Considere o grafo de realidade e desejo a seguir, e os possíveis tipos de reversões seguras que existem. Qual dos tipo de reversão segura, se aplicandos neste momento, estarão caminhando na direção de ordená-lo com o mínimo número de reversões?

I. Reversão segura Tipo 1: definida sobre duas arestas reais divergentes em um ciclo bom. II. Reversão segura Tipo 2 (Hurdle Merging): definida sobre duas arestas reais em hurdles não consecutivos. III. Reversão segura Tipo 3 (Hurdle Cutting): definida sobre duas arestas reais de um mesmo ciclo ruim.

1. Somente I e II
2. Somente I e II
3. Somente II e III
4. O grafo consiste em uma fortaleza, logo não há reversão segura.
5. NDA

Autor(a): Fabio L. Usberti

084-2008

MO640 - Questão para a prova oral
Número: 084
Enunciado:
Considere as seguintes afirmações sobre ordenação por reversões:

I - A distância de reversão é igual ao tamanho das seqüências mais um, menos o número total de ciclos, mais o número de obstáculos e o fator de correção para fortalezas.
II - Uma reversão segura diminui o número de ciclos menos obstáculos em um.
III - Só existe uma reversão segura se existir uma boa componente.

Quais são verdadeiras?

1. Somente I e II.
2. Somente I e III.
3. Somente II e III.
4. I, II e III.
5. NDA

Autor(a): João Paulo Pereira Zanetti

083-2008

MO640 - Questão para a prova oral
Número: 083
Enunciado:
Com relação aos conceitos de ordenação por reversão (no assunto de rearranjo genômico), assinale a alternativa que corresponde ao número mínimo de reversões pelos quais a sequência abaixo terá de passar para se igualar à sequência identidade:

1. 13
2. 14
3. 15
4. 16
5. NDA

Autor(a): Tiago Takamoto

082-2008

MO640 - Questão para a prova oral
Número: 082
Enunciado:
Com relação ao Diagrama Realidade-Desejo, qual das definições abaixo está correta?

1. Ciclo próprio = tem pelo menos 4 arestas
2. Ciclo bom = possui duas arestas desejo que divergem
3. Ciclo ruim = possui duas arestas realidade que convergem
4. Ciclos sobrepostos = uma aresta realidade de um ciclo cruza uma aresta realidade de outro ciclo
5. NDA

Autor(a): Priscila do Nascimento Biller

081-2008

MO640 - Questão para a prova oral
Número:  081
Sobre o texto "Lecture 16: Genome rearrangements, sorting by reversals Saad Mneimneh" discutido em sala de aula, considere o diagrama de Realidade e Desejo abaixo, no qual os ciclos foram identificados com as letras A, B, C e D.
Assinale a alternativa correta:

o diagrama possui 4 ciclos e 4 componentes. D forma sozinho um componente ruim. A e C são ciclos bons. B é um ciclo bom. NDA

Autor(a): Gustavo Waku

080-2008

MO640 - Questão para a prova oral
Número: 080
Enunciado:
Dada a seqüência π = (-3, 2, -5, -6, 7, -8, 1, 4, 9), qual das seqüências abaixo pode ser obtida a partir de π pela aplicação de uma reversão?

1. (-3 -7 6 5 -2 -8 1 4 9)
2. (9 4 1 -8 7 -6 -5 2 -3)
3. (3 -2 5 6 -7 8 -1 -4 -9)
4. (-3 -2 -5 -6 -7 -8 1 4 9)
5. NDA

Autor(a): Danilo Brandão Gonçalves

079-2008

MO640 - Questão para a prova oral
Número: 079
Enunciado:
Segundo Mneimneh (lec 16), pode-se transformar um genoma A em um genoma B atráves de reversões (reversals). Modelando genomas como seqüências de blocos orientados, e dadas as informações abaixo sobre quatro tais seqüências, qual delas tem maior chance de ser ordenada com menos movimentos (reversões) ? Suponha que todas elas tenham o mesmo número de obstáculos.
I - Seqüência de tamanho 10 com 4 ciclos ( c(I) = 4 )
II - Seqüência de tamanho 12 com 5 ciclos ( c(II) = 5 )
III - Seqüência de tamanho 14 com 7 ciclos ( c(III) = 7 )
IV - Seqüência de tamanho 16 com 6 ciclos ( c(IV) = 6 )

1. A seqüência I.
2. A seqüência II.
3. A seqüência III.
4. A seqüência IV.
5. NDA

Autor(a): Bruno Conti Marini

078-2008

MO640 - Questão para a prova oral
Número: 078
Enunciado:
Sobre os efeitos de uma reversão no grafo de realidade e desejo, e sendo p a reversão definida por duas arestas realidade a e b, é correto afirmar que (em relação aos ciclos no grafo realidade e desejo):
I- se a e b pertencem ao mesmo ciclo e convergem, o número de ciclos se mantém;
II- se a e b pertencem ao mesmo ciclo e divergem, retira-se um ciclo;
III- se a e b pertencem a ciclos distintos, adiciona-se um novo ciclo;

1. Somente I.
2. Somente II.
3. Somente III.
4. I, II, III.
5. NDA

Autor(a): Victor de Abreu Iizuka

077-2008

MO640 - Questão para a prova oral
Número: 077
Enunciado:
No que diz respeito ao diagrama (ou grafo) de realidade e desejo, qual das alternativas abaixo NÃO corresponde a uma de suas propriedades:

1. Cada ciclo composto por duas arestas corresponde a um não-breakpoint.
2. Em cada vértice incidem exatamente duas arestas, uma real e uma desejada.
3. O número máximo de componentes do grafo é (n + 1), onde n é o número de blocos do genoma que se deseja rearranjar.
4. Os componentes conexos do grafo correspondem a ciclos de arestas alternantes entre reais e desejadas.
5. NDA

Autor(a): Fabio L. Usberti

076-2008

MO640 - Questão para a prova oral
Número: 076
Enunciado:
Dada a pertumação (-2,+1,+3,-4). Qual dos diagramas abaixo representa o "diagrama realidade desejo" da permutação apresentada com a de identidade?

1. 
2. 
3. 
4. 
5. NDA

Autor(a): Maria Angélica Lopes de Souza

075-2008

MO640 - Questão para a prova oral
Número: 075
Enunciado:
Considere o problema de ordenação por reversões. Quantos breakpoints tem a permutação (-1, +2, -4, -3, +5) em relação à identidade?

1. 2
2. 3
3. 4
4. 5
5. NDA

Autor(a): João Paulo Pereira Zanetti

074-2008

MO640 - Questão para a prova oral
Número: 074
Enunciado:
Qual o primeiro passo no algoritmo de reconciliação de montagens visto em aula?

1. Fechar gaps
2. Criar gaps em pontos problemáticos
3. Calcular estatisticas de compressão e expansão
4. Alinhar as sequências de referência e suplementar
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

073-2008

MO640 - Questão para a prova oral
Número: 073
Assinale a alternativa correta que preenche o texto abaixo:

Na atualidade, existem vários tipos de abordagens para realização de montagem de sequências.  Nos últimos anos, tornou-se muito popular uma métrica denominada N50 que é utilizada na comparação desses montadores.  Esta métrica _____ ser utilizada para dizer que uma montagem é mais correta que outra.  Se um algoritmo de montagem aplicado sobre um genoma de tamanho 70
produza contigs de tamanhos { 15, 10, 8, 7, 5, 5, 5, 5, 5, 3, 2 }, o N50 deste algoritmo é ______.

1. não pode, 7
2. pode, 7
3. não pode, 8
4. pode, 8
5. NDA

Autor(a): Gustavo Waku

072-2008

MO640 - Questão para a prova oral
Número: 072
Enunciado:
Sobre os artigos "Assembly Reconciliation" de Zimin e colegas (2008) e "Beware of mis-assembled genomes" de Salzberg e Yorke (2005), quais das afirmativas abaixo são falsas:
I- O Algoritmo "Assembly Reconciliation" utiliza leituras (reads) casadas.
II- Em "Beware of mis-assembled genomes" o autor afirma que todos os genomas disponibilizados no GenBank são confiáveis.
III- O processo usado no "Assembly Reconciliation" é simétrico para as montagens de referência e suplementar.

1. I e II.
2. I e III.
3. II.
4. II e III.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

071-2008

MO640 - Questão para a prova oral
Número: 071
Enunciado:
Com relação à ordenação de sequências por transposição, assinale a alternativa que representa o número de ciclos e suas características do grafo de ciclos apresentado abaixo:

1. Temos um 2-ciclo e um 4-ciclo
2. Temos um 2-ciclo e um 5-ciclo
3. Temos um 3-ciclo e um 4-ciclo
4. Temos um 7-ciclo
5. NDA

Autor(a): Tiago Takamoto

070-2008

MO640 - Questão para a prova oral
Número: 070
Enunciado:
Os números de breakpoints nas sequências {1, 2, 3, 5, 4} e {2, 1, 3, 4, 5, 7, 6, 8} são, respectivamente:

1. 2 e 2
2. 2 e 6
3. 3 e 2
4. 3 e 6
5. NDA

Autor(a): Bruno Conti Marini

069-2008

MO640 - Questão para a prova oral

Número: 069

Enunciado:
Considere a seqüência genômica acima, composta por duas subseqüências iguais (repeats). Uma certa montagem incorreta dessa seqüência resultou em uma compressão. Qual das montagens abaixo melhor se enquadra como sendo composta por uma compressão?

1. 
2. 
3. 
4. 
5. NDA

Ideia original de Fabio L. Usberti

068-2008

MO640 - Questão para a prova oral
Número: 068
Enunciado:
Quantos breakpoints tem a permutação 512436?

1. 2
2. 3
3. 4
4. 5
5. NDA

Autor(a): João Paulo Pereira Zanetti

067-2008

MO640 - Questão para a prova oral
Número: 067
Enunciado:
Por que o genoma da bactéria Neisseria meningitidis é interessante para se testar a eficiência de um montador:

1. Por que é um dos mais simples e fáceis de se compreender dos genomas completos
2. Por que é um dos mais difíceis de montar e rico em repeats que já foi completado.
3. Por que é extremamente longo, perto do tamanho do genoma humano.
4. Por que é rico em erros de leitura, e possui muitos reads de baixa qualidade.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

066-2008

MO640 - Questão para a prova oral
Número: 066
Enunciado:
Sobre os textos "Cap3:A DNA Sequence Assembly Program" e "An Eulerian path approach to DNA fragment assembly" discutidos em aula, consirede as seguintes afirmações:

I - O programa Cap3 utiliza a abordagem "overlap-layout-consensus" baseado na qualidade das bases dos "reads".
II - No segundo texto, a montagem do caminho euleriano é feito a partir da montagem de um grafo de Brujin no qual cada "read" é um vértice e cada "overlap" é uma aresta.
III - O programa Cap3 geralmente produz contigs maiores do que o PHRAP.
IV - Ambos os textos abordam métodos que são capazes de extrair um contig das "chimeric reads".

são CORRETAS as afirmações:

1. somente I.
2. II, III e IV.
3. II e IV.
4. somente III.
5. NDA

Autor(a): Gustavo Waku

065-2008

MO640 - Questão para a prova oral

Número: 065
Enunciado:
Qual dos passos abaixo NÃO faz parte do algoritmo de montagem do software CAP3 ?

1. O sistema define se a comparação para detectar overlaps será feita com alinhamentos globais ou semi-globais
2. Falsos overlaps são identificados e removidos
3. Cálculo dos overlaps
4. Limpeza de pontas
5. NDA

Ideia original de: Filipe Benevides Netto

064-2008

MO640 - Questão para a prova oral
Número: 064
Enunciado:
Sobre o algoritmo de montagem de DNA utilizando super-caminhos de Euler podemos afirmar que:

1. ele é mais eficiente porque diminui consideravelmente o numero de reads.
2. para lidar com repeats ele tenta mascará-los, montando um grafo onde eles não apareçam
3. o número de contigs aumenta quando se compara a algoritmos de montagem clássicos como o da Celera
4. na montagem de seu grafo, ele usa muito mais reads, mas diminui o número de contigs ao final
5. NDA

Autor(a): Danilo Brandão Gonçalves

063-2008

MO640 - Questão para a prova oral
Número: 063
Enunciado: Considere a seqüência S=GACTCGACGA de tamanho n = 10. O grafo de Bruijn (da forma definida no artigo "An Eulerian path approach to DNA fragment assembly" de P. Pevzner, H. Tang, e M. S. Waterman, 2001), considerando tuplas de tamanho l = 4, pode ser representado por qual das alternativas abaixo? DICA: Veja quais são as diferenças entre as figuras e vá eliminando as incorretas.

1. 
   
2. 
   
3. 
   
4. 
   
5. NDA

Autor(a): Fabio L. Usberti

062-2008

MO640 - Questão para a prova oral
Número: 062
Enunciado:
Assinale a afirmativa verdadeira sobre o CAP3:

1. Não utiliza valores de qualidade das bases.
2. Utiliza apenas alinhamento local.
3. Seu desempenho foi pior que Phrap no estudo comparativo utilizando BACs publicado por Huang e colegas em 1999.
4. Possui três etapas principais: (i) cortes de pontas 3' e 5' de baixa qualidade e identificação de sobreposições, removendo as falsas (ii) formação de contigs usando restrições foward-reverse (iii) alinhamento múltiplo e formação da seqüência consenso.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

061-2008

MO640 - Questão para a prova oral
Número: 061
Enunciado:
Quando é realizado o consenso nos programas CAP3 e EULER?

1. No fim, em ambos.
2. No início, em ambos.
3. No fim do CAP3 e no início do EULER.
4. No CAP3, o consenso é realizado no início e, no EULER, não existe uma fase de consenso.
5. NDA

Autor(a): João Paulo Pereira Zanetti

060-2008

MO640 - Questão para a prova oral
Número: 060
Enunciado:
Qual dos problemas abaixo NÃO é NP-difícil?

1. Inferência de Haplótipos por Pura Parcimonia
2. Inferência de Haplótipos por Resolução Máxima
3. Inferência de Haplótipos por Filogenia Perfeita
4. Programação Linear Inteira
5. NDA

Autor(a): Priscila do Nascimento Biller

059-2008

MO640 - Questão para a prova oral

Número: 059
Enunciado:
Com relação à modelagem de árvores evolucionárias e ao conceito de matriz de distância ultramétrica, assinale a alternativa que melhor preenche a seguinte matriz para que fique ultramétrica:

	a	b	c	d	e
a	0	2	[A]	1	1
b	-	0	2	[B]	2
c	-	-	0	1	1
d	-	-	-	0	[C]
e	-	-	-	-	0

1. A=1 ; B=1 ; C=2
2. A=1 ; B=2 ; C=1
3. A=2 ; B=1 ; C=2
4. A=2 ; B=3 ; C=1
5. NDA

Autor(a): Tiago Takamoto

058-2008

MO640 - Questão para a prova oral
Número: 058
Enunciado:
Sobre o início do algoritmo de Clark, é correto dizer:

1. O algortimo resolve, inicialmente, um genótipo aleatório.
2. O algortimo resolve, inicialmente, os genótipos com nenhuma ambiguidade.
3. O algortimo resolve, inicialmente, os genótipos com uma ou mais ambiguidades.
4. O algortimo resolve, inicialmente, os genótipos com nenhuma ou uma ambiguidade.
5. NDA.

Autor(a): Beto Marchesini

057-2008

MO640 - Questão para a prova oral

Número: 057
Enunciado:


Observe a árvore de distâncias acima e sua matriz correspondente, e em seguida, leia as seguintes afirmações:

I. O valor de X na matriz é igual a 2,5.
II. O valor de Y na matriz é igual a 1,5.
III. A matriz é aditiva.
IV. A matriz é ultramétrica.

São verdadeiras as afirmações:

1. I, II, III, IV.
2. I, III, IV.
3. II, III, IV.
4. I, III.
5. NDA

Autor(a): Fabio L. Usberti

056-2008

MO640 - Questão para a prova oral

Número: 056
Enunciado:
Sobre inferência de haplótipos, qual a alternativa FALSA?

1. Uma filogenia perfeita só admite uma mutação para cada sítio (locus).
2. Maximizar o número de genótipos resolvidos usando a Regra de Inferência de Clark é NP-Difícil.
3. Para um genótipo com h posições heterozigotas, são possíveis 2^h-1 pares de haplótipos.
4. O critério da Parcimônia Pura para a inferência de haplótipos encontra uma árvore filogenética com um número mínimo de folhas.
5. NDA

Autor(a): João Paulo Pereira Zanetti

055-2008

MO640 - Questão para a prova oral

Número: 055
Enunciado:
Uma árvore totalmente resolvida é uma árvore sem raiz tal que todo nó tem grau 1 ou 3. Dada uma árvore totalmente resolvida com n nós, quantas possíveis topologias binárias enraizadas podemos derivar dela?

1. 2n - 3
2. n²
3. n³ - 1
4. n!
5. NDA

Autor(a): Priscila N Biller

054-2008

MO640 - Questão para a prova oral

Número: 054
Enunciado:
O que é homoplasia?

1. Característica perdida por UM ÚNICO descendente.
2. Característica presente em um ancestral e que é passado a TODOS os seus descendentes.
3. Característica compartilhada por dois ou mais espécies que NÃO estava presente no ancestral comum a elas.
4. Característica presente em um ancestral e que passa para apenas UM dos descendentes, e NÃO está presente nos demais.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

053-2008

MO640 - Questão para a prova oral

Número: 053

Enunciado:
A tabela abaixo especifica 4 espécies e 4 características destas espécies, que podem sofrer alterações de estado 0 -> 1 ou 1-> 0. Identifique a alternativa INCORRETA para as mutações na árvore exibida ao lado da tabela, utilizando o método da parcimônia:

Species Characters 1 2 3 4 Alfa 1 0 0 1 Beta 0 0 1 0 Gamma 1 1 0 0 Delta 1 0 1 1

1. Para a caracteristica 3 são necessárias no mínimo 2 mudanças de estado.
2. Para a caracteristica 4 são necessárias no mínimo 3 mudanças de estado.
3. O número total de mudanças necessárias nesta árvore juntando todas as características é 5.
4. Esta árvore é uma árvore ótima para a tabela em questão.
5. NDA

Autor(a): Tiago Takamoto

052-2008

MO640 - Questão para a prova oral

Número: 052
Enunciado:
Em relação aos algoritmos de Fitch e de Sankoff para inferir árvores filogenéticas por parcimônia, é correto afirmar que:
I - O algoritmo de Fitch utiliza em seus cálculos uma matriz com os custos entre as mudanças de estado
II - No algoritmo de Fitch, contamos uma alteração de estado a cada união feita.
III - O algorimo de Sankoff não pode ser configurado para considerar transição e transversão diferentemente

1. I, II e III
2. I e III
3. II
4. II e III
5. NDA

Autor(a): Vitor Paulo Villarino Pinto

051-2008

MO640 - Questão para a prova oral

Número: 051
Enunciado:
Em geral, nas teorias sobre evolução, o conceito de parcimônia é utilizado com freqüência. Um exemplo disso se encontra na inferência das árvores de filogenia, onde os métodos de parcimônia são assim denominados por determinar a árvore que...

1. melhor discrima as espécies de acordo com determinadas características.
2. resulta em menor número de eventos ou mudanças de estados.
3. possui o menor número de ramificações.
4. possui o menor comprimento de ramo.
5. NDA

Autor(a): Fabio L. Usberti

050-2008

MO640 - Questão para a prova oral

Número: 050
Enunciado:
Considere as seguintes afirmações sobre inferência de filogenias baseado em características pelo critério de parcimônia:

I - O número de mudanças de estado em uma árvore depende do posicionamento da raiz na árvore.
II - O algoritmo de Fitch conta o número de mudanças de estado em uma árvore.
III - O algoritmo de Sankoff computa o número de mudanças separadamente para cada característica.

São verdadeiras:

1. Somente I.
2. Somente I e II.
3. Somente II e III.
4. I, II e III.
5. NDA

Autor(a): João Paulo Pereira Zanetti

049-2008

MO640 - Questão para a prova oral

Número: 049
Enunciado:
Considere seguintes as afirmações sobre construção de filogenias parcimoniosamente:
I- O algoritmo de Fitch não considera eventos de transição e transverção separadamente.
II- O algoritmo de Sankoff pode considerar eventos de transição e transversão.
III- Os algoritmos (Fitch e Sankoff) buscam o custo máximo da evolução (maior número de mutações).
São verdadeiras:

1. I
2. II
3. I e II
4. II e III
5. NDA

Autor(a): Maria Angélica Lopes de Souza

048-2008

MO640 - Questão para a prova oral
Número: 048
Enunciado:
Na fórmula α = uΔt vista em aula, que dá a probabilidade de mutação no modelo Jukes-Cantor, o que se pode dizer sobre o parâmetro u?

1. É uma constante quando Δt tende a zero.
2. É uma constante quando Δt tende ao infinito.
3. É uma constante válida apenas para transição.
4. É uma constante válida apenas para transversão.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

047-2008

MO640 - Questão para a prova oral
Número: 047
Enunciado:
Com relação aos modelos de Jukes-Cantor e Kimura para evolução, assinale a alternativa correta:

1. Uma transversão tem maior possibilidade de ocorrer do que uma transição.
2. Para o modelo de Jukes-Cantor, a probabilidade do nucleotídeo se manter inalterado (durante um intervalo de tempo muito pequeno) é 3 vezes menor do que a probabilidade do mesmo se alterar.
3. Para o modelo de Kimura, a probabilidade de uma transição ocorrer é A = U.T e a de uma transversão ocorrer é B = U.T, sendo T um intervalo de tempo muito pequeno e U uma constante.
4. A distância de Jukes-Cantor é dada pela razão entre a quantidade de nucleotídeos que sofreram alteração pelo total de nucleotídeos da sequência em análise.
5. NDA

Autor(a): Tiago Takamoto

046-2008

MO640 - Questão para a prova oral
Número: 046
Enunciado:
A mutação onde ocorre a troca de um nucleotídeo qualquer por outro do MESMO grupo é denominada X, enquanto que a mutação onde ocorre a troca de um nucleotídeo qualquer por outro de um grupo DIFERENTE é denominada Y. Temos que X e Y são respectivamente:

1. Transição e transversão.
2. Tradução e transversão.
3. Tradução e transcrição.
4. Transição e tradução.
5. NDA

Autor(a): Fábio L. Usberti

045-2008

MO640 - Questão para a prova oral
Número: 045
Enunciado:
Sobre o modelo de Jukes-Cantor apresentado em aula é correto afirmar que:

1. Supõe que a probabilidade de mutação é proporcional ao tempo transcorrido para qualquer intervalo de tempo.
2. Leva em consideração as taxas de transições e transversões em uma sequência.
3. Também é conhecido como modelo de dois parâmetros.
4. É o modelo de evolução mais simples existente.
5. NDA

Autor(a): Victor de Abreu Iizuka

044-2008

MO640 - Questão para a prova oral
Número: 044
Enunciado:
No modelo de Kimura, para a fórmula X(t) + Y(t) + 2 * Z(t) = 1, é correto afirmar que:

1. Y(t) é a probabilidade de haver uma transição
2. X(t) é a probabilidade de haver uma transversão
3. Y(t) + 2 * Z(t) é a probabilidade da base permanecer a mesma
4. O coeficiente 2 antes de Z(t) corresponde às duas formas de haver uma transição
5. NDA

Autor(a): Helder dos Santos Ribeiro

043-2008

MO640 - Questão para a prova oral
Número: 043
Enunciado:
Uma diferença entre o modelo de Jukes-Cantor e o modelo de Kimura é:

1. O modelo de Jukes-Cantor tem 2 parâmetros para serem considerados, enquanto que o modelo de Kimura tem 3.
2. O modelo de Jukes-Cantor utiliza a Timina, enquanto que o modelo de Kimura utiliza a Uracila para seus cálculos.
3. O modelo Jukes-Cantor leva em consideração que todos os tipos de mutações tem a mesma probabilidade de acontecer, enquanto que o modelo de Kimura leva em consideração as diferenças entre as probabilidades das transições e transversões.
4. O modelo Jukes-Cantor leva em consideração as diferenças entre as probabilidades das transições e transversões, enquanto que o modelo de Kimura leva em consideração que todos os tipos de mutações tem a mesma probabilidade de acontecer.
5. NDA

Autor(a): Beto Marchesini

042-2008

MO640 - Questão para a prova oral
Número: 042
Enunciado:
Sobre o modelo de Kimura:

1. Este modelo considera que não existe mutação entre bases de grupos diferentes.
2. Este modelo considera que as probabilidades de mutação entre quaisquer bases são sempre as mesmas.
3. Este modelo considera que a probabilidade de mutação entre bases do mesmo grupo é maior que a probabilidade de mutação entre bases de grupos diferentes.
4. Este modelo considera que a probabilidade de mutação entre bases de grupos diferentes é maior que a probabilidade de mutação entre bases do mesmo grupo.
5. NDA

Autor(a): Danilo Brandão Gonçalves

041-2008

MO640 - Questão para a prova oral
Número: 041
Enunciado:
Qual o preço a se pagar por usar o algoritmo de alinhamento que economiza espaço visto em aula:

1. É necessário saber de antemão o quanto as cadeias são semelhantes.
2. Só funciona se as sequências tiverem o mesmo tamanho.
3. O alinhamento é aproximado, e não ótimo.
4. O tempo de execução pode dobrar.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

040-2008

MO640 - Questão para a prova oral
Número: 040
Enunciado:
Vimos que existe um algoritmo para comparar sequências similares. Esse algoritmo tenta se manter na diagonal principal da matriz de similaridade com uma tolerância k. Sabemos que, caso as sequências não sejam similares, o algoritmo também vai encontrar a resposta correta. Supondo que o valor inicial de k é 1 e que este valor é dobrado após cada 'rodada', qual das alternativas abaixo melhor reflete o número de 'rodadas' do algoritmo necessárias para encontrar a solução ótima no pior caso ? Suponha que as duas sequências têm tamanho n.

1. n / 2
2. n / 4
3. log ₂ n
4. log ₄ n
5. NDA

Autor(a): Bruno Conti Marini

039-2008

MO640 - Questão para a prova oral
Número: 039
Enunciado:
A complexidade de tempo do algoritmo visto em aula para comparação de seqüências similares é dada por O(dn) onde n é o número de elementos das suas seqüências s e t, supostamente iguais no tamanho. Indique a alternativa que melhor descreve o significado do parâmetro d:

1. a largura da banda onde se está preenchendo a matriz .
2. a quantidade de gaps do alinhamento ótimo das seqüências s e t.
3. a quantidade de mismatches do alinhamento ótimo das seqüências s e t.
4. a diferença entre a similaridade entre duas seqüências iguais (de tamanho n) e a similaridade das seqüências s e t.
5. NDA

Autor(a): Fabio L. Usberti

038-2008

MO640 - Questão para a prova oral
Número: 038
Enunciado:
Sobre o algoritmo básico e a sua adaptação para espaço linear é correto afirmar que:

1. Usamos um algoritmo de divisão e conquista para o cálculo da similaridade.
2. O algoritmo básico é altamente recomendado para alinhar sequências longas devido a redução do espaço.
3. A complexidade de tempo assintótica para o cálculo da similaridade entre as sequências é de O(mn) para os dois algoritmos.
4. Sobre a complexidade de tempo assintótica para a construção dos alinhamentos ótimos, o básico realiza em O(mn) enquanto o de espaço linear realiza em O(n+m).
5. NDA

Autor(a): Victor de Abreu Iizuka

037-2008

MO640 - Questão para a prova oral
Número: 037
Enunciado:
No alinhamento semi-global, para desconsiderar espaços no *começo da primeira seqüência* (disposta na vertical), o algoritmo deve:

1. Inicializar a *primeira linha* com zeros
2. Inicializar a *primeira coluna* com zeros
3. Procurar a maior similaridade na *última linha*
4. Procurar a maior similaridade na *última coluna*
5. NDA

Autor(a): Helder dos Santos Ribeiro

036-2008

MO640 - Questão para a prova oral
Número: 036
Enunciado:
Considerando os vários algoritmos de comparação global, semi-global e local vistos em aula, que diferença NÃO existe entre eles?

1. Inicialização da matriz
2. Complexidade de pior caso do algoritmo
3. Penalização para casamentos com espaços
4. Posição em que é procurado o maior valor
5. NDA

Autor(a): Priscila do Nascimento Biller

035-2008

MO640 - Questão para a prova oral
Número: 035
Enunciado:
Qual das modificações abaixo não precisa ser feita para transformar o algoritmo de alinhamento global no algoritmo de alinhamento local?

1. Iniciar com zero a primeira coluna e a primeira linha da matriz.
2. Parar a reconstrução de um alinhamento local quando for encontrado um 0 na matriz.
3. Não deixar que os valores da matriz fiquem negativos; se o máximo se revelar negativo, deve ser substituído por 0. 
4. Procurar o maior valor da matriz inteira, para obter a similaridade e para utilizar como ponto de partida para reconstrução de um alinhamento ótimo.
5. NDA

Autor(a): Filipe Benevides Netto

034-2008

MO640 - Questão para a prova oral
Número: 034
Enunciado:
Se usarmos o algoritmo de comparação semi-global colocando a primeira e segunda strings passadas nas posições HORIZONTAL e VERTICAL, respectivamente, na matriz de comparação (note que NÃO é a colocação padrão usada no texto de referência), para ignorar espaços no final da primeira string temos que:

1. Preencher a primeira linha da matriz com zeros.
2. Preencher a primeira coluna da matriz com zeros.
3. Escolher o maior valor na última linha da matriz para montar o alinhamento.
4. Escolher o maior valor na última coluna da matriz para montar o alinhamento.
5. NDA

Autor(a): Bruno Conti Marini

033-2008

MO640 - Questão para a prova oral
Número: 033
Enunciado:

	0	A	G	T
0	0	-2	-4	-6
C	-2	0	X	-4
G	Y	-2	1	-1
T	-6	-4	-1	Z

Considere a tabela de similaridade global acima, com pesos de match = 1, mismatch = 0 e gap = -2. Indique a opção abaixo que representa os valores corretos de X, Y e Z (respectivamente) da tabela:

1. -1; -3; 0.
2. -1; -3; 2.
3. -2; -4; 0.
4. -2; -4; 2.
5. NDA

Autor(a): Fabio L. Usberti

032-2008

MO640 - Questão para a prova oral
Número: 032
Enunciado:
Assinale a alternativa correta sobre a matriz resultante do algoritmo de comparação local para duas seqüências s e t:

1. A pontuação máxima do alinhamento sempre está na última posição da matriz.
2. A posição (i,j) da matriz contém a similaridade local entre o prefixo s[1..i] de s e o prefixo t[1..j] de t.
3. A primeira linha da matriz é inicializada com 2.p (onde p é a pontuação do espaço).
4. A fórmula de recorrência para o preenchimento da matriz é a mesma da comparação global.
5. NDA

Autor(a): Victor de Abreu Iizuka

031-2008

MO640 - Questão para a prova oral
Número: 031
Enunciado:
Qual das alternativas abaixo não é uma aplicação biológica do alinhamento local?

1. Descobrir um cenário com o mínimo de alterações a aplicar em uma proteina para torná-la igual a uma outra.
2. Observar regiões que podem ter funções semelhantes em genes diferentes.
3. Calcular o grau de similaridade entre fragmentos de sequências distintas.
4. Mostrar regiões que podem ter se conservado mais ao longo da evolução de uma espécie.
5. NDA

Autor(a):Jose Augusto Salim

030-2008

MO640 - Questão para a prova oral
Número: 030
Enunciado:
Uma diferença entre a reconstrução de um alinhamento local e outro global é:

1. A reconstrução local é encerrada quando encontra-se o valor zero, enquanto que a global segue até o elemento [0,0].
2. A reconstrução local é encerrada quando atinge uma borda inicializada com zeros, enquanto que a global segue até o elemento [0,0].
3. A reconstrução local inicia-se apenas no elemento mais abaixo e à direita, enquanto que a global pode iniciar-se em qualquer elemento.
4. A reconstrução local segue até o elemento [0,0], enquanto que a global somente se encerra quando atinge uma borda inicializada com zeros.
5. NDA

Ideia original de: Beto Marchesini

029-2008

MO640 - Questão para a prova oral
Número: 029
Enunciado:
Considere as seguintes afirmações:
I- Ponto de partida para alinhamento é o maior valor da última linha da matriz
II- Similaridade refere-se ao maior valor encontrado na matriz de similaridade
III- A primeira linha da matriz, apenas, é preenchida com zeros.
Elas referem-se respectivamente a quais alinhamentos:

1. global, local, semi-local não penalizando buracos no início da primeira seqüência.
2. semi-global não penalizando buracos no fim da primeira seqüência, local, semi-local não penalizando buracos no início da primeira seqüência.
3. semi-global não penalizando buracos no início da primeira seqüência, local, semi-local não penalizando buracos no fim da primeira seqüência.
4. semi-global não penalizando buracos no início da primeira seqüência, semi-local não penalizando buracos no início da segunda seqüência, local.
5. NDA

Autor(a): Maria Angélica Lopes de Souza

028-2008

MO640 - Questão para a prova oral
Número: 028
Enunciado:
Na matriz para calcular a similaridade local, qual é este valor e até onde pode-se retroceder para encontrar um alinhamento ótimo?

1. O valor máximo em toda a matriz. Até um zero.
2. O valor máximo em toda a matriz. Até a primeira linha ou coluna.
3. O valor máximo na união da última linha e da última coluna. Até o início da matriz.
4. O valor máximo na união da última linha e da última coluna. Até a primeira linha ou coluna.
5. NDA

Autor(a): João Paulo Pereira Zanetti

027-2008

MO640 - Questão para a prova oral
Número: 027
Enunciado:
É uma desvantagem do uso de leveduras como sistema de expressão:

1. São caras.
2. São relativamente dificeis de trabalhar.
3. Presença de proteases que degradam as proteinas exógenas.
4. Não possuem enzimas responsáveis por modificações pós-traducionais.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

026-2008

MO640 - Questão para a prova oral
Número: 026
Enunciado:

Qual alternativa abaixo contém um códon de começo e um códon de fim de uma proteína num RNA mensageiro, respectivamente, no código genético bacteriano?

1. AUG e AUA
2. CCA e UUA
3. GUG e UAA
4. UUA e CGA
5. NDA

Autor: Rajiv Andrade

025-2008

MO640 - Questão para a prova oral

Número: 025
Enunciado:
Considerando seqüêrncias de entrada de tamanhos m e n, o que podemos dizer sobre a complexidade dos algoritmos de Similarity e Align do texto lido. Escolha somente uma opção:

1. A complexidade do Align é O(n).
2. A complexidade do Align é O(m + n).
3. A complexidade dos dois algoritmos acima é O(m³n).
4. Não há como calcular a complexidade se as seqüências possuirem tamanhos diferentes.
5. NDA
   

Ideia original de: Andréia G. Motta Maia

024-2008

MO640 - Questão para a prova oral
Número: 024
Enunciado:
Considere duas strings s1[1..m] e s2[1..n] para serem alinhadas e a matriz de similaridade a[i,j] definida por elas, onde 0 ≤ i ≤ m e 0 ≤ j ≤ n. Sobre a matriz de similaridade é correto afirmar que:

1. Os elementos a[i,0] para 0 ≤ i ≤ m são sempre múltiplos de -2.
2. cada elemento a[i,j] da matriz de similiaridade deve conter o peso g entre os caracteres s1[i] e s2[j].
3. O elemento a[i,j] da matriz de similiaridade deve conter a similaridade entre os caracteres s1[i] e s2[j].
4. O elemento a[i,j] da matriz de similaridade deve conter a similaridade entre as strings s1[1..i] e s2[1..j].
5. NDA

Autor(a): Gustavo Waku

023-2008

MO640 - Questão para a prova oral
Número: 023
Enunciado:
Em engenharia molecular, os sistemas de expressão são baseados na inserção de um certo gene em uma célula hospedeira para sua tradução e formação de uma proteína. Indique qual das afirmações abaixo NÃO corresponde em uma vantagem de se utilizar células de bactérias como hospedeiras em sistemas de expressão:

1. As bactérias apresentam uma fisiologia simples.
2. Alta produtividade, chegando até 10% da massa total.
3. As proteínas formadas costumam se dobrar corretamente.
4. Tempo de produção reduzido, considerando que as bactérias crescem e se multiplicam rapidamente.
5. NDA

Autor(a): Fabio L. Usberti

022-2008

MO640 - Questão para a prova oral
Número: 022
Enunciado:
Existem vários métodos para comparar duas sequências de DNA. Um deles é o método da comparação global. De qual técnica esse método faz uso e qual a sua complexidade ? (n é o tamanho da primeira sequência de DNA e m é o tamanho da segunda)

1. Programação Gulosa, O(n+m)
2. Programação Inteira, O(n*m)
3. Programação Dinâmica, O(n*m)
4. Programação Funcional, O(n+m)
5. NDA

Autor(a): Bruno Conti Marini

021-2008

MO640 - Questão para a prova oral
Número: 021
Enunciado:
Sobre o algoritmo para o cálculo da similaridade global, é correto afirmar que:

1. Para o cálculo de sim[i,j] é apenas necessário o valor de sim[i-1,j].
2. Para o cálculo de sim[i,j] é apenas necessário o valor de sim[i,j-1].
3. Para o cálculo de sim[i,j] são apenas necessários os valores de sim[i-1,j] e sim[i,j-1].
4. Para o cálculo de sim[i,j] são apenas necessários os valores de sim[i-1,j], sim[i,j-1] e sim[i-1,j-1].
5. NDA

Autor(a): Beto Marchesini

020-2008

MO640 - Questão para a prova oral
Número: 020
Enunciado:
Qual destas afirmações sobre alinhamentos de sequências é falsa?

1. Espaços podem ser inseridos no começo de sequências.
2. Podem existir alinhamentos entre sequências de tamanhos distintos.
3. O número de alinhamentos que existe entre duas sequências é exponencial.
4. Um espaço de uma sequência pode ser alinhado com um espaço de outra sequência.
5. NDA

Autor: Felipe Augusto Archangelo

019-2008

MO640 - Questão para a prova oral

Número: 019
Enunciado:
Qual dos códons abaixo é o códon de iniciação de sequência, segundo a tabela de código genético padrão?

1. AUC
2. AUG
3. GUA
4. UGA
5. NDA

Ideia original de: Victor de Abreu Iizuka

018-2008

MO640 - Questão para a prova oral

Número: 018
Enunciado:
Dadas as seqüências s e t, de tamanho m e n, respectivamente, qual é a complexidade de tempo do algoritmo básico de comparação global?

1. O(mn)
2. O(m + n)
3. O((mn)²)
4. O((m + n)²)
5. NDA

Autor(a): João Paulo Pereira Zanetti

017-2008

MO640 - Questão para a prova oral
Número: 017
Enunciado:
Quantos pares de cromossomos têm as células somáticas humanas?

1. 22
2. 23
3. 30
4. 46
5. NDA

Autor(a): Alexandre Garcia Aguado

016-2008

MO640 - Questão para a prova oral
Número: 016
Enunciado:
Marque a opção que não corresponde a um dos componentes ligados ao carbono principal de um aminoácido, desconsiderando o resíduo característico:

1. H
2. O
3. NH2
4. COOH
5. NDA

Autor(a): Rajiv Santos

015-2008

MO640 - Questão para a prova oral
Número: 015
Enunciado:
São aminoácidos:

1. alanina, valina, glicina e leucina.
2. lipase, amilase, protease e glucoamilase.
3. queratina, mucina, hemoglobina e caseína.
4. plasmócito, linfócito, leucócito e timócito.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama

014-2008

MO640 - Questão para a prova oral
Número: 014
Enunciado:
Sobre o processo de divisão celular para a produção de espermatozóides podemos afirmar que:

   I - Na produção de espermatozóides acontecem mitoses e meioses
   II - Na produção de um espermatozóide após uma meiose não acontecem mais mitoses
   III - Na produção de espermatozóides só ocorrem mitoses

estão corretas as afirmações:

1. I
2. I e II
3. II e III
4. III
5. NDA

Autor(a): Danilo Brandão Gonçalves

013-2008

MO640 - Questão para a prova oral
Número: 013
Enunciado:
Qual das afirmações abaixo é verdadeira?

1. A transcrição é o processo de tradução do RNA em proteínas, a partir de 23 pares de cromossomos.
2. Mitose é a divisão celular em que no final do processo existirão 4 células com o mesmo material genético.
3. O RNA é formado por ribose, ácido fosfórico e bases orgânicas: Purinas (Adenina e Guanina) e Pirimidinas (Citosina e Uracila)
4. O processo de divisão celular denominado meiose é composto por 4 fases: prófase, metáfase, anáfase e telófase.
5. NDA
   

Autor(a): Andréia Gonçalves Motta Maia

012-2008

MO640 - Questão para a prova oral
Número: 012
Enunciado:
O RNA transportador (tRNA) é responsável por:

1. Percorrer o DNA sintetizando RNA mensageiro
2. Ligar um códon a um aminoácido durante a tradução
3. Catalizar reações químicas durante a duplicação do DNA
4. Transportar a informação genética do núcleo ao ribossomo
5. NDA

Autor(a): Helder dos Santos Ribeiro

011-2008

MO640 - Questão para a prova oral
Número: 011
Enunciado:
Qual das afirmações é correta em relação à diferença entre RNA e DNA

1. Diferem somente no açúcar.
2. Diferem somente no fosfato.
3. Diferem somente na quantidade de fitas.
4. Diferem principalmente na quantidade de fitas, no açúcar e nas bases nitrogenadas (o RNA possui timina ao invés de uracila).
5. NDA

Autor(a): Gustavo Waku

010-2008

MO640 - Questão para a prova oral
Número: 010
Enunciado:
Uma célula diplóide com 2n=32 ao sofrer o processo de meiose origina:

1. 2 células com 16 cromossomos cada
2. 2 células com 32 cromossomos cada
3. 4 células com 16 cromossomos cada
4. 4 células com 32 cromossomos cada
5. NDA

Autor(a): Beto Marchesini

009-2008

MO640 - Questão para a prova oral
Número: 009
Enunciado:
Qual é a alternativa que representa corretamente o DOGMA central da biologia molecular

1. DNA --> (tradução) --> Proteínas --> (transcrição) --> RNA
2. RNA --> (tradução) --> Proteínas --> (transcrição) --> DNA
3. DNA --> (tradução) --> RNA --> (transcrição) --> Proteínas
4. RNA --> (transcrição) --> DNA --> (tradução) --> Proteínas
5. NDA

Autor(a): Filipe Benevides Netto

008-2008

MO640 - Questão para a prova oral
Número: 008
Enunciado:
Algumas descobertas recentes parecem contradizer o Dogma Central da Biologia Molecular. Um delas mostra que RNA viral pode ser transcrito em DNA através de uma enzima denominada:

1. ribulose reversa
2. fosfatase inversa
3. isomerase inversa
4. transcriptase reversa
5. NDA

Autor(a): José Augusto Salim

007-2008

MO640 - Questão para a prova oral
Número: 007
Enunciado:
Escolha a alternativa que melhor completa as lacunas na seguinte frase: Os glóbulos vermelhos, provenientes da medúla óssea, são altamente especializados. Durante sua maturação, eles perdem ______________, permitindo que a maior parte do espaço interno possa ser ocupado pela proteína que carrega o oxigênio, __________.

1. seu núcleo, a hemoglobina.
2. seus ribossomos, a timina.
3. suas mitocôndrias, a adenina.
4. seu complexo de Golgi, a citosina.
5. NDA

Autor(a): Bruno Conti Marini

006-2008

MO640 - Questão para a prova oral
Número: 006
Enunciado:
Indique a alternativa falsa.

1. Na intérfase ocorre duplicação do DNA.
2. Um ser humano sadio possui 23 cromossomos.
3. Durante a anáfase da mitose, as duas cromátides irmãs se separam.
4. Em uma molécula de DNA em dupla fita, a quantidade de adeninas é igual à quantidade de timinas.
5. NDA

Autor(a): Fabio L. Usberti

005-2008

MO640 - Questão para a prova oral

Número: 005
Enunciado:
O produto final da transcrição do DNA é denominado...

1. RNA mensageiro
2. RNA polimerase
3. RNA ribossômico
4. RNA transportador
5. NDA

Autor(a): Fabio L. Usberti

004-2008

MO640 - Questão para a prova oral
Número: 004
Enunciado:
Qual das seguintes bases nitrogenadas está presente no RNA, porém não no DNA?

1. Citosina
2. Guanina
3. Timina
4. Uracila
5. NDA

Autor: Felipe Augusto Archangelo

003-2008

MO640 - Questão para a prova oral
Número: 003
Enunciado:
Quais das bases orgânicas de um DNA são bases pirimídicas?

1. Adenina e Guanina
2. Citosina e Guanina
3. Citosina e Timina
4. Guanina e Timina
5. NDA

Autor(a): Victor de Abreu Iizuka

002-2008

MO640 - Questão para a prova oral
Número: 002
Enunciado:
Quais sãs as bases nitrogenadas do DNA?

1. púricas (adenenina e guanina) e primídicas (citosina e uracila)
2. púricas (adenenina e guanina) e primídicas (citosina e timina)
3. púricas (citosina e uracila) e primídicas (adenenina e guanina)
4. púricas (citosina e timina) e primídicas (adenenina e guanina)
5. NDA

Autor(a): Maria Angélica Lopes de Souza

001-2008

MO640 - Questão para a prova oral
Número: 001
Enunciado:
Qual é a ordem das fases da mitose?

1. Prófase, Anáfase, Metáfase, Telófase
2. Prófase, Anáfase, Telófase, Metáfase
3. Prófase, Metáfase, Anáfase, Telófase
4. Prófase, Telófase, Metáfase, Anáfase
5. NDA

Autor(a): Vitor Paulo Villarino Pinto

091-2007

MO640 - Questão para a prova oral
Número: 091
Enunciado:
Sobre o algoritmo quase linear para construção de árvores PQR é incorreto afirmar que:

1. Durante sua execução ele classifica cada vértice da árvore como preto, cinza ou branco.
2. Os vértices classificados como cinzas em uma iteração do algoritmo são aqueles que violam a restrição analisada naquela iteração.
3. Ele é dinâmico quanto à entrada, ou seja, para construir uma árvore PQR ele precisa receber todas as restrições desta de uma vez.
4. Ele parte da árvore universal e a modifica em cada iteração, para que ela atenda a uma nova restrição.
5. NDA

Autor(a): Mário César San Felice

090-2007

MO640 - Questão para a prova oral
Número: 090
Enunciado:
Sobre o texto de Telles-Meidanis-2007, qual a alternativa CORRETA?

1. O passo 1 do algoritmo colore de cinza as folhas da árvore.
2. No passo 2 do algoritmo um nó interno v é colorido de preto quando v está contido propriamente em S
3. Todos os nós pretos devem ser eliminados no passo 3 do algoritmo.
4. O passo 5 do algoritmo descolore todos os nós cinzas.
5. NDA

Autor(a): Douglas Gameiro Diniz

089-2007

MO640 - Questão para a prova oral
Número: 089
Enunciado:
Indique qual passo não está de acordo com o algoritmo de (Telles e Meidanis 2007):

1. Passo 1: As folhas correspondentes aos elementos de S são coloridas de preto.
2. Passo 2: Coloração dos nós internos da árvore de branco ou cinza.
3. Passo 3: Reestruturação da árvore com a eliminação dos nós cinza.
4. Passo 4: Ajuste do LCA, que se for nós R não sofre alteração.
5. NDA

Autor(a): Lucas Pedersen Parizzi

088-2007

MO640 - Questão para a prova oral
Número: 088
Enunciado:
Sobre o algoritmo do texto de Telles e Meidanis (2007), é incorreto afirmar :

1. Ao fim da execução, todos os nós devem ter ficado ou brancos ou cinzas;
2. Sua complexidade é classificada como sendo quase-linear;
3. Passa a maior parte do tempo em operações do tipo move;
4. Baseia-se em versões mais simples de templates;
5. NDA

Autor(a): Luis Felipe Strano Moraes

087-2007

MO640 - Questão para a prova oral
Número: 087
Enunciado:
No passo 3 do algoritmo para construção de Árvores PQR em tempo Quase-linear, de Telles e Meidanis 2007, podemos tirar alguns resultados do algoritmo apresentado. O incorreto é:

1. Um filho v depois de preparado nunca é P.
2. Um merge só acontece quando o nó raiz da LCA é do tipo Q ou R.
3. Caso o tipo da raiz do LCA seja P então os filhos coloridos de preto devem ser "juntados".
4. O objetivo do passo 3 é preparar caminho para a posterior eliminação dos nós de cor cinza.
5. NDA

Autor(a): Peterson Katagiri Zilli

086-2007

MO640 - Questão para a prova oral
Número: 086
Enunciado:
Sobre o algoritmo mostrado em Telles e Meidanis 2005 é correto afirmar.

1. O algoritmo colore de preto todas os nós internos que possuem pelo menos um filho preto.
2. O algoritmo colore de cinza todos os nós internos que possuem pelo menos um filho cinza.
3. O algoritmo colore de branco todos os nós internos que possuem pelo menos um filho branco.
4. O algoritmo colore de cinza apenas os nós internos que possuem uma mistura de filhos brancos e pretos.
5. NDA

Autor(a): Ulisses Martins Dias

085-2007

MO640 - Questão para a prova oral
Número: 085
Enunciado:
Dentre as operações a seguir, qual não está relacionada ao algoritmo de construção de árvores PQR em tempo quase linear, de Telles e Meidanis?

1. Encontrar o mínimo ancestral comum ("least common ancestor") de um determinado conjunto de folhas.
2. Colorir nós da árvore PQR em três cores: branco, preto e cinza.
3. Fazer com que a árvore PQR não possua nós cinzas.
4. Utilizar divisão e conquista para decompor o problema de construção da árvore PQR em dois subproblemas menores, os quais originam duas sub-árvores PQR que são transformadas em uma única árvore PQR.
5. NDA

Autor: Celmar Guimarães da Silva

084-2007

MO640 - Questão para a prova oral
Número: 084

Enunciado:
Dado a árvore PQR da Figura 1 abaixo, qual desses conjuntos não pertence à C completude intersecção C ortogonal:

Figura 1

1. FDG
2. BDFGA
3. BAFGDCE
4. EAFGDBC
5. NDA

Autor(a): Paulo Renato de Faria

083-2007

MO640 - Questão para a prova oral
Número: 083
Enunciado:
Sobre árvores PQR definidas por Meidanis-Porto-Telles-1998, qual a alternativa FALSA?

1. O domínio de uma árvore PQR T (Dom(T)) é definido como sendo a união de suas folhas.
2. Duas árvores são equivalentes se e somente se uma delas pode ser transformada na outra através de zero ou mais transformações equivalentes.
3. As duas árvores da figura abaixo (T e T') são equivalentes.
4. A fronteira das duas árvores PQR T e T' da figura abaixo são gdhefbac e cafebhdg respectivamente.
5. NDA

Autor(a): Douglas Gameiro Diniz

082-2007

MO640 - Questão para a prova oral
Número: 082
Enunciado:
Dado o conjunto universo U=abcdef e a coleção de subconjuntos C={ace, abd, ef, ade}, qual dos conjuntos inferidos não é correto:

1. ac, após aplicar "ace complemento relativo ef"
2. abcde, ao aplicar "ace união não disjunta abd"
3. abdef, pela aplicação de "abd união não disjunta ef"
4. ae, quando aplicamos "ace interseção ade"
5. NDA

Autor(a): Paulo Renato de Faria

081-2007

MO640 - Questão para a prova oral
Número: 081
Enunciado:
Quantas árvores existem na classe de equivalência da árvore abaixo?

1. 64
2. 122
3. 256
4. 768
5. NDA

Autor(a): Paulo Renato Nascimento

079-2007

MO640 - Questão para a prova oral
Número: 079
Enunciado:
Dado o conjunto universo U = {a,b,c,d,e,f,g,h} e a coleção de restrições C= { {b,f,e,h}, {f,e}, {h,d}, {b,e}, {d,g}, {b,f} }, assinale a alternativa correta.

1. A árvore PQ que atende as restrições possui pelo menos um nó Q.
2. A árvore PQR que atende as restrições não possui nó R.
3. A menor coleção completa que contém C é dada por: { {b,f,e,h}, {f,e}, {h,d}, {b,e}, {d,g}, {b,f}, {a,b,c,d,e,f,g,h}, {a}, {b}, {c}, {d},{e}, {f}, {g}, {h}} }
4. A coleção C faz com que seja implícita a restrição {b,f,e,h,d}
5. NDA

Autor(a): Ulisses Martins Dias

078-2007

MO640 - Questão para a prova oral
Número: 078
Enunciado:
Sobre árvores PQR é incorreto afirmar que:

1. Nós Q representam maior número de restrições que nós P.
2. Qualquer conjunto de restrições sobre um conjunto de elementos pode ser representado como uma árvore PQR.
3. Nós R representam menor número de restrições que nós Q.
4. Nós R surgem quando existem restrições que não podem ser atendidas simultaneamente.
5. NDA

Autor(a): Mário César San Felice

077-2007

MO640 - Questão para a prova oral

Número: 077
Enunciado:
Dada a árvore PQR abaixo, determine qual das alternativas possui conjuntos que NÃO fazem parte da coleção completa que esta árvore representa:

1. { MN } e { MO }
2. { CD } e { KL }
3. { AB }, { JK } e { LM }
4. { EFG }, { GH } e { HI }
5. NDA

Ideia original de: Daniel M. Ivasse

076-2007

MO640 - Questão para a prova oral

Número: 076
Enunciado:
Com relação a árvores PQ e PQR, marque a alternativa incorreta:

1. Toda árvore PQ é uma árvore PQR, mas o contrário não é válido.
2. Os filhos de um nó R podem permutar arbitrariamente entre si, assim como os filhos de um nó Q.
3. Intersecção, união não disjunta e complemento não contido são operações usadas para se calcular a completude ("completion") de um conjunto de restrições.
4. Sempre existe uma árvore PQR que representa um conjunto de restrições, independentemente de qual é esse conjunto.
5. NDA

Autor: Celmar Guimarães da Silva