105-2008

MO640 - Multiple-choice question

In a PQ-tree, when we are adding a new restriction, which of the following statements is true?

   a. If a node is partial, then none of its children is full
   b. If a node is partial, then none of its children is pertinent
   c. If a node has any of its children empty, then it must be an empty node
   d. If a node has any of its children full, then it must be a pertinent node
   e. None of the above

Original idea by: Priscila Nascimento Biller
Translation help by: Leandro José de Bortoli

063-2015

MO640 - Multiple-choice question

According to the concept of equivalence transformations by Booth and Lueker (1976), which alternative DOES NOT represent a PQ-tree equivalent to the following tree?

a)	b)
c)	d)
e) None of the above

Original idea by: Leandro Tacioli

062-2015

MO640 - Multiple-choice question

Given the PQ-tree T below, analyze the statements:

I) FRONTIER(T) is the permutation ABCDEFGHIJKLMNOP.
II) CONSISTENT(T) has 14496 permutations.
III) T is PERTINENT(T,S) if S={A,B,G,K,M}
IV) T is PRUNED (T,S) if and only if S contains all the leaves of the tree.

Which statements are correct?

a) IV, only
b) I and III, only
c) I, III, and IV, only
d) II, III and IV, only
e) None of the above

Original Idea by: Mario Akita

078-2007

MO640 - Multiple-choice question

Which of the alternatives below is incorrect?

1. The null tree is not considered a PQ tree;
2. To obtain the frontier of a PQ tree we have to read the tree leaves from left to right;
3. Reversing the children of a P node is an equivalence transformation;  
4. Reversing the children of a Q node is an equivalence transformation;
5. None of the above 

Original idea by: Moacy Barros Correia da Silva
Translation help by: Jessica Akemi Matsuoka

106-2008

MO640 - Multiple-choice question

Given the PQ-tree below, which of the following permutations is consistent with it?

1. ACDEGFB
2. DEFGABC
3. GACEDFB
4. GFEDBCA
5. None of the above.

Original idea by: Fabio L. Usberti

Translation help by: Wesley Ide

108-2008

MO640 - Multiple-choice question

Which of the statements below are true about Booth and Lueker's linear-time algorithm to build a PQ-tree:

I - The algorithm has two steps: one to identify the nodes that must be processed and another to apply the reductions.
II - Every child of a Q node has a pointer to its parent
III - The linear complexity can be confirmed by amortized analysis

A. I and II
B. I and III
C. II
D. III
E. None of the above

Original idea by: Maria Angélica Lopes de Souza
Translation help by: Rafael Soares Padilha

061-2015

MO640 - Multiple-choice question

Find the connected compontents in the strictly overlapping graph for the clones x probes matrix below.

L1	0	1	0	0	0	1	0	1	0	0
L2	0	0	1	0	1	0	1	0	0	0
L3	0	0	1	1	0	0	1	0	0	0
L4	1	0	0	0	0	0	0	0	1	0
L5	1	0	0	0	0	0	0	1	1	0
L6	0	0	1	0	0	0	1	0	0	1
L7	0	0	0	0	0	0	0	1	0	0

a)		b)
c)		d)

e) None of the above

Original idea by: Miriam Ito