Magna Concursos
2285600 Ano: 2014
Disciplina: TI - Desenvolvimento de Sistemas
Banca: UFSCAR
Orgão: UFSCAR
Provas:

Um programador foi escalado para implementar um sub-programa que verifica se uma árvore binária qualquer é uma árvore binária de busca (ABB). Este sub-programa deve retornar “1” apenas quando a raiz da árvore binária fornecida como parâmetro for uma árvore binária de busca e retornar “0” caso contrário. Este programador implementou, na linguagem C, dois algoritmos distintos (Algoritmo 1 e Algoritmo 2) e está em dúvida sobre qual implementação ele deve utilizar. Considere a representação da árvore pelos nós dinâmicos definidos pelo “struct _no”. Como critério de corretude, considere a solução do problema conforme o enunciado e, como critério de eficiência, o número de comparações.

typedef struct _no no;
struct _no {
int info; // valor do nó
no* esq; // filho da esquerda
no* dir; // filho da direita
};

// Algoritmo 1
int verificaABB1(no* n) {
if(!n)
return 1;
if(n->esq && n->esq->info > n->info)
return 0;
if(n->dir && n->dir->info < n->info)
return 0;
return verificaABB1(n->esq) &&
verificaABB1(n->dir);
}

// Algoritmo 2
int verificaABB2(no* n) {
// INT_MIN: menor inteiro possivel
// INT_MAX: maior inteiro possivel
return vABB2(n,INT_MIN,INT_MAX);
}
int vABB2(no* n, int min, int max) {
if(!n)
return 1;
if(n->info < min || n->info > max)
return 0;
return vABB2(n->esq,min,n->info-1) &&
vABB2(n->dir,n->info+1,max)
}

Qual das seguintes alternativas é verdadeira?

 
Comentários 1
×
Cadernos
×
Flashcards
×
Estatísticas
×
Reportar um erro
×

Provas

Questão presente nas seguintes provas

Analista de TI

60 Questões