013-2007

MO640 - Questão para a prova oral
Número: 013
Enunciado: Sejam P, G e L algoritmos estudados em classe para efetuar alinhamentos pontas livres, global e local, respectivamente. Considerando as afirmações a seguir, indique a alternativa que as relaciona adequadamente a esses algoritmos.
I) Possuem relações de recorrência iguais na recursão.
II) Possuem condições-base iguais na recursão.
III) Podem ser implementados com complexidade de tempo O(nm), onde n e m são os tamanhos das seqüências a serem alinhadas.
IV) Podem ser implementados com complexidade linear de espaço.

1. I: LP; II: GP; III: LP; IV: GL.
2. I: GL; II: GLP; III: GP; IV: GLP.
3. I: GP; II: LP; III: GLP; IV: GLP.
4. I: GLP; II: GL; III: GL; IV: LP.
5. NDA

Autor(a): Celmar Guimarães da Silva