Estrutura de Dados em C exercicios

Prévia do material em texto

Estrutura de Dados em C
A memória é um componente do computador responsável pelo armazenamento de dados e instruções. Ela é composta por palavras, sendo cada palavra identificada unicamente a partir de um endereço, ou seja, um endereço de memória. A alocação de memória na linguagem C pode ser de três tipos:
A) Elástica, manual e estática
B) Elástica, automática e dinâmica
C) Estática, manual e estática
D) Elástica, manual e dinâmica
E) Estática, automática e dinâmica
A alternativa "E" está correta. A alocação de memória na linguagem C pode ser de três tipos: Alocação estática, alocação automática e alocação dinâmica.
------------------------------------------------------------------------------------------------------------------------------------------------
Sabemos que todo dado armazenado em memória possui um endereço e que a definição de um ponteiro é uma variável que guarda o endereço de memória, ou seja, a localização do dado. Diante disto, a figura apresenta uma memória que armazena a variável “x” e o ponteiro para a variável “x”. Como o conteúdo do ponteiro é um endereço, a seta indica a relação entre o ponteiro e a variável que ele aponta. Qual o valor da variável “x” e este dado está armazenado em qual endereço de memória, isto é, qual é o valor armazenado pelo ponteiro “pt_x”?
A) x= 300 e pt_x =300
B) x=300 e pt_x=100
C) x=300 e pt_x=320
D) x=100 e pt_x=320
E) x=100 e pt_x=300
A alternativa "E" está correta. Na figura, o valor da variável “x” é 100 e esse dado está armazenado no endereço de memória 300. Como o ponteiro também ocupa espaço, o endereço de memória da variável “x” está armazenado no endereço 320 da memória. Sendo assim, o valor da variável “x” é 100 e o valor do ponteiro pt_x é 300 (endereço de memória da variável “x”).
------------------------------------------------------------------------------------------------------------------------------------------------
Estudamos sobre os tipos de estrutura de dados. A estrutura de dados em que o primeiro elemento inserido é o primeiro elemento a ser retirado é denominada:
A) Pilha
B) Matriz
C) Árvore binária
D) Fila
E) Lista
A alternativa "D" está correta. A estrutura de dados fila são listas em que as operações de remoção e inserção ocorrem sempre em locais específicos. A inserção é feita sempre no final da lista e a remoção sempre no início da lista. Em função disto, uma fila assume a condição FIFO.
------------------------------------------------------------------------------------------------------------------------------------------------
As estruturas de dados heterogêneas são conjuntos de dados formados por tipos de dados diferentes. Sendo assim, selecione uma das principais estruturas de dados heterogêneas.
A) Pilha
B) Matriz
C) Árvore binária
D) Registro
E) Lista
A alternativa "D" está correta. As estruturas de dados heterogêneas são conjuntos de dados formados por tipos de dados diferentes, como os registros. Os registros são úteis para os casos em que é necessário guardar informações de diversos tipos, porém, como se fossem uma única variável.
------------------------------------------------------------------------------------------------------------------------------------------------
Para acessar os membros de uma estrutura de dados struct, são empregados dois tipos de operadores: Operador de membro de estrutura . (operador de ponto) e Operador de ponteiro de estrutura -> (operador de seta). Selecione a opção correta que apresenta o comando para acessar o elemento rua de uma struct endereço que foi referenciada diretamente pela variável x.
A) printf("%s", x.rua);
B) printf(“%s”, x.->rua);
C) printf(“%s”, x->.rua);
D) printf(“%s”, rua.x);
E) printf(“%s”, rua->x);
A alternativa "A" está correta. Para acessar um membro de uma estrutura usando o operador ponto por meio do nome da estrutura, seguido por um ponto e pelo nome do campo que se quer acessar, podemos acessar e visualizar o campo rua da estrutura x (endereco) usando a seguinte declaração: printf("%s", x.rua);
------------------------------------------------------------------------------------------------------------------------------------------------
A estrutura de dados structs em linguagem C pode realizar diversas operações. Dentre as opções abaixo, identifique uma operação possível a ser realizada com uma struct.
A) Acesso aos membros de uma variável de estrutura referenciada diretamente através do operador seta (->).
B) Leitura do endereço de uma variável de estrutura através do operador ponto (.).
C) Acesso aos membros de uma variável de estrutura referenciada diretamente através do operador ponto (.)
D) Uso do operador sizeof para determinar o tempo de acesso para uma estrutura.
E) Uso do operador seta (->) para acessar uma estrutura referenciada diretamente.
A alternativa "C" está correta. A estrutura de dados structs em linguagem C pode realizar diversas operações, como atribuição de variáveis da estrutura a variáveis da estrutura do mesmo tipo, leitura do endereço de uma variável de estrutura (operador &), acesso aos membros de uma variável de estrutura e uso do operador sizeof para determinar o tamanho de uma variável de estrutura. O acesso aos membros da estrutura pode ser feito através do operador ponto (.), se for feita a referenciação direta ou operador seta (->), se forem empregados ponteiros.
------------------------------------------------------------------------------------------------------------------------------------------------
Considere que você está desenvolvendo um novo software para catalogar os jogadores de futebol. Você modelou o seu programa utilizando as structs apresentadas abaixo.
typedf struct time {
 char nome[50];
} Time;
 
struct Jogador {
 int nr_camisa;
 char nome[30];
 Time t;
} jogador;
 
Considerando que você precise cadastrar um novo jogador chamado Manoel da Silva, que irá atuar no time da Estudante Atlético Club, com a camisa número 10, qual alternativa apresenta a forma correta de inserir os dados?
A)
Camisa->jogador = 10;
strcpy(nome->jogador, "Manoel da Silva");
strcpy(t->nome->jogador, " Estudante Atlético Club ");
B)
jogador.camisa = 10;
strcpy(jogador.nome, "Manoel da Silva");
strcpy(jogador.t.nome, " Estudante Atlético Club ");
C)
jogador.camisa = 10;
strcpy(jogador.nome, "Manoel da Silva");
strcpy(jogador.nome.nome, " Estudante Atlético Club ");
D)
jogador->camisa = 10;
strcpy(jogador->nome, "Manoel da Silva");
strcpy(jogador->t->nome, " Estudante Atlético Club ");
E)
camisa.jogador = 10;
strcpy(nome.jogador, "Manoel da Silva");
strcpy(t.nome.jogador, " Estudante Atlético Club ");
A alternativa "B" está correta. A estrutura time está aninhada na estrutura jogador, sendo a estrutura time um tipo de dados definido pelo programador. Para acessar um elemento da estrutura jogador, basta acessar a variável referenciada diretamente e o nome do campo, utilizando o operador ponto. Para os campos camisa e nome, basta utilizar jogador.camisa e jogador.nome, sendo que, para o último caso, utilizando a função strcpy. Para acessar o nome do time, deve ser considerado o aninhamento da estrutura Time referenciada pela variável t. Portanto, deve-se utilizar jogador.t.nome, empregando a função strcpy.
------------------------------------------------------------------------------------------------------------------------------------------------
Considere o trecho de código abaixo:
 
typedef struct {
 char nome[200];
 int idade;
 float salario;
} Funcionario;
Funcionario func[10];.
 
Qual das opções apresenta a sintaxe correta na qual seja preenchido corretamente o elemento de uma posição do vetor de struct?
A) &Funcionario[indice].idade;
B) &Funcionario[indice];
C) &func.idade[indice];
D) &func[indice].idade;
E) &func.idade;
A alternativa "D" está correta. Para preencher corretamente o elemento de uma posição do vetor, é necessário indicar a posição do vetor de struct seguido pelo elemento a ser preenchido, portanto, a sintaxe correta é &nome_vetor_struct[indice].nome_membro_struct,isto é, para preencher o vetor, você deve selecionar o vetor, seu índice e o membro a que se refere na struct. Por exemplo: &func[i].idade
------------------------------------------------------------------------------------------------------------------------------------------------
Estudamos sobre modularização na programação, que é a divisão do código do programa em sub-rotinas. Assinale a alternativa que contenha tipos de sub-rotinas:
A) Pilhas e filas
B) Sub-rotina local e global
C) Procedimento e função
D) Passagem por valor e por referência
E) Matrizes e vetores
A alternativa "C" está correta. Na modularização do código de um programa, os tipos de sub-rotinas encontradas são as funções e os procedimentos.
------------------------------------------------------------------------------------------------------------------------------------------------
Assinale a alternativa que contenha a afirmativa correta sobre função e procedimento:
A) Não existe diferença entre função e procedimento.
B) As funções são um tipo de procedimento e podem ser usadas apenas uma vez no código do programa.
C) As funções sempre retornam algum valor a quem as chamou, e os procedimentos não retornam valor algum.
D) Os procedimentos sempre retornam algum valor a quem os chamou, e as funções não retornam valor algum.
E) Os procedimentos são um tipo de função com o objetivo apenas de chamar uma ou várias funções.
A alternativa "C" está correta. Na modularização do código de um programa, os tipos de sub-rotinas encontradas são as funções e os procedimentos. As funções são um tipo de procedimento que retorna algum valor para quem as chamou, diferente do procedimento, que não retorna nenhum valor.
------------------------------------------------------------------------------------------------------------------------------------------------
Na linguagem de programação C, as funções predefinidas estão nas bibliotecas da linguagem. Cada biblioteca-padrão tem um cabeçalho que contém os protótipos para todas as funções, assim como definições de vários tipos de dados e constantes que são necessárias para as mesmas. Uma dessas bibliotecas tem a seguinte explicação: Funções de entrada e saída padrão. Assinale-a:
A) stdio.h
B) stdlib.h
C) ctype.h
D) dos.h
E) string.h
A alternativa "A" está correta. A biblioteca stdio.h contém várias funções de entrada e saída, como : scanf, printf, getc, gets, putc, puts, entre outras funções.
------------------------------------------------------------------------------------------------------------------------------------------------
Considere o Programa C, listado a seguir.
 
#include <stdio.h>
int main(void) {
int a, *y, z;
x = 5;
y = &x;
z = 10;
scanf(“%d”, y);
printf(“%d %d ”, x, z);
}
Assinale a alternativa que representa o que será impresso pelo programa se o usuário digitar 15, como entrada de dados:
A) 10 15
B) 15 10
C) 5 10
D) 5 15
E) Null pointer
A alternativa "B" está correta. Observe no código que o valor digitado será armazenado na variável y, que é um ponteiro para a variável x. Sendo assim, o valor impresso na variável x é 15. Como a variável z recebe no código o valor 10, será impresso esse valor.
------------------------------------------------------------------------------------------------------------------------------------------------
Na programação em módulos, o programa principal se comunica com as sub-rotinas através de passagem de parâmetro. Sobre os tipos de passagem, assinale a sentença correta:
A) Os parâmetros da função na sua declaração são chamados de variáveis globais.
B) Os parâmetros atuais ou reais são os argumentos da função.
C) Na passagem por valor, o parâmetro real é passado para o parâmetro formal com o uso dos ponteiros.
D) Na passagem por referência é realizada uma cópia do valor a ser passado.
E) Tanto na passagem por valor como por referência, os tipos dos parâmetros podem ser distintos.
A alternativa "B" está correta. Os parâmetros são passados para uma função de acordo com a sua posição. Na chamada da função, os parâmetros são chamados parâmetros atuais/reais ou argumentos.
------------------------------------------------------------------------------------------------------------------------------------------------
Analise o seguinte código implementado na linguagem C com passagem de parâmetro por referência entre a função main e a função soma.
  
int soma(int *a, int *b) {
*a = *a + *b;
return *a;
}
int main() {
int x=5, y=3;
y = soma(x, y);
printf(“%d”, x+y);
return(0);
}
Assinale a opção que corrige o código:
A) Linha 1: int soma(int a, int b) {
B) Linha 8: printf(“%d”, y);
C) Linha 6: int x=5; int y=3;
D) Linha 2: a = *a + *b;
E) Linha 7 y = soma(&x, &y);
A alternativa "E" está correta. A passagem por referência passa o endereço de memória do argumento. Nesse caso, usa-se o operador & para referenciar o endereço de memória da variável.
------------------------------------------------------------------------------------------------------------------------------------------------
Nas linguagens de programação, as variáveis são vinculadas aos seus valores em tempo de execução. E o escopo de uma vinculação é o conjunto de trechos de um programa que se consegue usar as variáveis. No caso da linguagem C, as variáveis são divididas quanto ao escopo em três tipos. Assinale a opção que apresenta esses três tipos:
A) Variáveis por valor, variáveis por referência e variáveis por argumento
B) Variáveis locais, variáveis globais e parâmetros formais
C) Parâmetros formais, parâmetros informais e sem parâmetro
D) Parâmetros formais, variáveis internas e variáveis externas
E) Parâmetros atuais, parâmetros reais e parâmetro formais
A alternativa "B" está correta. No caso da linguagem C, as variáveis são divididas quanto ao escopo em três tipos: Variáveis locais, variáveis globais e parâmetros formais.
------------------------------------------------------------------------------------------------------------------------------------------------
Analise o seguinte código implementado na linguagem C.
  
int soma(int a, int b) {
int s;
s = a + b;
return s;
}
int main() {
int x=5, y=10;
int z ;
z = soma(x, y);
printf(“%d”, z);
return(0);
}
Assinale a opção correta:
A) As variáveis a e b são variáveis globais.
B) As variáveis x e y são parâmetros formais.
C) A variável z está vinculada à função é main e por isso é uma variável global.
D) O escopo de vinculação da variável s está definido pela função soma.
E) Esse programa não tem variável local, todas são globais.
A alternativa "D" está correta. A variável s está declarada dentro da função soma, portanto é uma variável local da função soma e seu escopo está vinculado à execução da função.
------------------------------------------------------------------------------------------------------------------------------------------------
Listas lineares ordenadas são estruturas de dados nas quais a posição relativa dos seus elementos reflete uma ordem que sempre deve ser respeitada. Suponha um vetor V em linguagem C com n posições que implementa uma lista desse tipo. É correto afirmar-se que:
A) Se V [ 1 ] < V [ 0 ], então, V [ i ] < V [ i + 1 ]
B) Se V [ 1 ] > V [ 0 ], então, V [ i ] > V [ i + 1 ]
C) Se V [ 1 ] < V [ 0 ], então, V [ i + 1 ] > V [ i ]
D) Se V [ 1 ] > V [ 0 ], então, V [ i + 1 ] > V [ i ].
E) Se V [ 1 ] > V [ 0 ], então, V [ i + 1] < V [ i ]
A alternativa "D" está correta. Como se trata de uma lista ordenada, é necessário descobrir-se se a ordenação é crescente ou decrescente. A afirmação de que V [ 1 ] > V [ 0 ] indica uma lista ordenada crescente, cuja generalização é V [ i + 1 ] > V [ i ].
------------------------------------------------------------------------------------------------------------------------------------------------
Sobre listas lineares alocadas sequencialmente, é verdadeiro que:
A) Evitam o desperdício de memória.
B) São eficientes no acesso ao elemento da lista.
C) A inserção ocorre sempre na mesma posição.
D) Não permitem o percurso em ambos os sentidos.
E) A chavede busca em uma lista ordenada não precisa ser única.
A alternativa "B" está correta. A implementação por meio de alocação sequencial permite o acesso direto à posição de memória de cada elemento da lista, possuindo, assim, acesso eficiente.
------------------------------------------------------------------------------------------------------------------------------------------------
Sobre listas lineares implementadas por meio de alocação encadeada, são feitas as seguintes afirmativas:
I)Em uma lista ordenada, os endereços de memória de seus nós também estarão ordenados.
II)Uma lista duplamente encadeada não pode ser usada para implementar uma lista ordenada.
III)Para acessar um nó, é necessário percorrer todos os seus predecessores.
A alternativa que contém apenas afirmativa(s) verdadeira(s) é:
A) I
B) II
C) III
D) II e III
E) I e II
A alternativa "C" está correta. A alocação sequencial aloca os espaços de memória em tempo de execução, não sendo seus endereços conhecidos previamente. Assim, para acessar um nó, é necessário percorrer os antecessores, pois cada um guarda o endereço do seguinte. Pela mesma razão, não é possível se afirmar qual a relação entre os endereços dos nós. Por fim, o duplo encadeamento não viola a ordem existente entre os elementos de uma lista ordenada.
------------------------------------------------------------------------------------------------------------------------------------------------
A concatenação de duas listas A e B é uma operação que faz o último nó de A ser seguido pelo primeiro nó de B, unindo-as e produzindo uma lista cujo número de nós é igual à soma do número de nós de cada lista individual. Considere as listas não ordenadas L1 e L2, ambas implementadas por alocação simplesmente encadeada. L1 possui m nós e L2 possui n nós. Sobre a concatenação de L1 e L2, é correto afirmar-se que:
A) Serão percorridos m nós
B) Serão percorridos n nós.
C) Serão percorridos m + n nós.
D) Serão percorridos m * n nós.
E) Serão percorridos m + 1 nós.
A alternativa "A" está correta. Concatenar L1 e L2 significa fazer o último nó de L1 apontar para o primeiro de L2. Como em alocação encadeada não é possível o acesso direto, será necessário percorrer todos os nós de L1 para atingir seu último nó e, assim, realizar o apontamento para o primeiro nó de L2. Entretanto, L2 não precisa ser percorrida. Assim, serão percorridos m nós.
------------------------------------------------------------------------------------------------------------------------------------------------
Considere uma pilha que inicialmente possui os seguintes elementos: A, D, R, K, P. A execução de uma operação de desempilhamento (pop) retira o elemento “A”. Em seguida são executadas as operações pop e push (empilha o elemento passado como parâmetro) na sequência: pop (), push (H), push (A). Após essas operações, é correto afirmar que a pilha resultante é:
A) H, A, R, K, P
B) R, K, P, H, A
C) A, H, R, K, P
D) A, H, D, R, K
E) H, D, R, K, P
A alternativa "C" está correta. Uma pilha somente admite remoção por uma extremidade, chamada topo. Se a execução de pop () removeu A, então o topo da pilha está à esquerda. Assim, repetir pop () removerá D, e push (H), push (A) empilharão H e A nessa ordem, de forma que A está no topo.
------------------------------------------------------------------------------------------------------------------------------------------------
Qual das afirmativas apresenta corretamente uma vantagem de se implementar pilhas em alocação encadeada?
A) Evita o desperdício de memória.
B) Permite a remoção de nós do meio da pilha.
C)Possui tamanho virtualmente ilimitado.
D) Facilita o acesso direto ao nó.
E) Não é necessário o uso de ponteiro auxiliar no deslocamento de um nó.
A alternativa "A" está correta. Na alocação encadeada, a memória é alocada em tempo de execução. Isso permite que sejam alocadas tantas porções de memória quanto se necessite, o que faz com que não haja um limite teórico. O limite é, de fato, a memória disponível no computador.
------------------------------------------------------------------------------------------------------------------------------------------------
A regra de que o elemento mais antigo numa lista é o primeiro a ser removido corresponde, respectivamente, ao conceito e ao nome de:
A) FIFO e FILA
B) LIFO e FILA
C) FIFO e PILHA
D) LIFO e PILHA
E) LIFO e DEQUE
A alternativa "A" está correta.O elemento mais antigo foi o primeiro a ser inserido e é o primeiro a ser removido, isso corresponde ao conceito de First in, First Out (FIFO) e caracteriza a FILA.
------------------------------------------------------------------------------------------------------------------------------------------------
Uma empresa desenvolveu um teclado sem fio para ser utilizado em celulares. Entretanto, devido a vários fatores, a transmissão dos eventos (digitação) para o celular é mais lenta do que a velocidade de digitação de alguém experiente. Para evitar a perda de dados, a empresa resolveu introduzir um buffer para guardar as teclas digitadas e enviar para o celular à medida que este for processando os dados. A estrutura de dados adequada para implementar esse buffer é uma:
A) Pilha
B) Fila
C) Deque
D) Lista ordenada
E) Lista duplamente encadeada
A alternativa "B" está correta. O buffer tem que garantir que a ordem dos caracteres digitados não se altere. A estrutura de dados que garante isso é a fila.
------------------------------------------------------------------------------------------------------------------------------------------------
 Analise as afirmativas abaixo e marque a opção correta.
1 – Não existe algoritmo de ordenação capaz de executar em um tempo inferior à complexidade de O (n log n).
2 – Métodos de ordenação interna executam em memória principal (RAM) somente, enquanto métodos de ordenação externa executam em memória secundária, porém podem usar memória principal também.
3 – Somente algoritmos de ordenação não baseados em comparação podem executar em um tempo inferior à O(n log n).
A) Somente a afirmativa 1 está correta.
B) Somente a afirmativa 2 está correta.
C) Somente a afirmativa 3 está correta.
D) As afirmativas 2 e 3 estão corretas.
E) As afirmativas 1, 2 e 3 estão corretas.
A alternativa "D" está correta. Letra D, a afirmativa 1 está incorreta, algoritmos não baseados em comparação entre elementos da sequência a ser ordenada não estão sujeitos ao limite de complexidade de O(n log n).
------------------------------------------------------------------------------------------------------------------------------------------------
Marque a alternativa correta em relação à estabilidade de um algoritmo de ordenação.
A) Um algoritmo instável possui necessariamente complexidade computacional alta.
B) Um algoritmo instável tem complexidade de espaço superior à O(n).
C) Um algoritmo estável pode necessitar de menos operações que um algoritmo instável, entretanto, isto não reduz a complexidade computacional do algoritmo.
D) Algoritmos estáveis sempre executam em uma complexidade de O(n log n).
E) Algoritmos internos sempre são estáveis.
A alternativa "C" está correta. A estabilidade pode reduzir o número de operações em algumas instâncias, porém não reduz a complexidade computacional do algoritmo.
------------------------------------------------------------------------------------------------------------------------------------------------
Quando apresentamos uma sequência já ordenada para os algoritmos da bolha e para o Insert Sort, é correto afirmar que:
A) O método da bolha irá executar mais rápido, uma vez que, para sequências ordenadas, o método da bolha executa n-1 comparações, enquanto o Insert Sort executa n (n-1)/2 comparações.
B) O Insert Sort irá executar mais rápido, uma vez que, para sequências ordenadas, o método executa n-1 comparações, enquanto o método da bolha sempre executa n (n-1)/2 comparações.
C) Ambos executam sempre em O(n2) operações.
D) Ambos executam sempre em tempo linear para as instâncias já ordenadas.E) A sequência ordenada não é o melhor caso dos métodos analisados.
A alternativa "D" está correta. Gabarito comentado: Letra D, o método da bolha e o Insert Sort executam em tempo linear para o melhor caso. Em ambos algoritmos, o melhor caso é a sequência ordenada.
------------------------------------------------------------------------------------------------------------------------------------------------
Comparando o Selection Sort com o Bubble Sort e o Insert Sort, é correto afirmar que:
A) Os três têm a mesma complexidade computacional.
B) Podemos afirmar que o Bubble Sort e o Insert Sort são mais eficientes que o Selection Sort.
C) Podemos afirmar que o Selection Sort e o Insert Sort são mais eficientes que o Bubble Sort.
D) Podemos afirmar que o Selection Sort e Bubble Sort são mais eficientes que o Insert Sort.
E) O Bubble Sort é o mais eficiente entre os três.
A alternativa "A" está correta. Não há base, além da complexidade computacional, para afirmar que um algoritmo é melhor que outro. Como os três têm a mesma complexidade, são considerados equivalentes.
------------------------------------------------------------------------------------------------------------------------------------------------
Sobre a estrutura de dados chamada árvore, está correto o que se afirma em:
A) Duas subárvores distintas de um mesmo nó pai podem conter nós em comum.
B) O grau de uma árvore é definido como o grau de todos os seus nós.
C) O maior nível de uma árvore é numericamente igual à sua altura.
D) Um nó folha necessariamente estará no penúltimo ou no último nível de uma árvore.
E) O nó raiz é aquele que não possui relação de ancestralidade com outros nós da árvore
A alternativa "C" está correta. Tanto o nível quanto a altura são calculados contando-se a partir do valor 1, a altura. E a altura da árvore é definida como sendo o maior valor entre os níveis de seus nós.
------------------------------------------------------------------------------------------------------------------------------------------------
Sejam as afirmações a seguir:
I. Se duas árvores puderem ser tornadas coincidentes com a permutação de um nó pai com seu nó filho, então essas árvores são isomorfas.
II. Isomorfismo é uma propriedade que não se aplica a árvores representadas por diagramas de inclusão.
III. Duas árvores isomorfas têm a mesma altura.
São verdadeiras, apenas:
A) I
B) II
C) III
D) I e III
E) I, II e III
A alternativa "C" está correta. O isomorfismo entre duas árvores diz respeito à possibilidade de elas serem tornadas coincidentes pela permutação de suas subárvores. Permutar as subárvores apenas alterna suas posições relativas, mas não permite alterar a altura de uma árvore. Isto pode ser provado por contradição. Suponha que a permutação tenha alterado a altura da árvore para torná-la coincidente com a outra. Neste caso, se a altura mudou, obrigatoriamente algum nó mudou de nível, pois não há inserção ou remoção de nó. Então, para que ambas as árvores sejam coincidentes, fez-se necessário permutar as subárvores e mudar o nível de algum nó, o que contraria a definição de isomorfismo.
------------------------------------------------------------------------------------------------------------------------------------------------
Árvores binárias são um tipo particular de árvores em que se admite que seus nós possuam até 2 filhos. Sobre tal característica, qual afirmativa apresenta-se correta?
A) Os nós de uma árvore binária podem possuir 3 subárvores vazias.
B) Os nós folha, em uma árvore binária, possuem grau 2.
C) Todos os nós de uma árvore binária possuem grau 2.
D) Cada nível acomoda a metade de nós do nível anterior.
E) Cada nível tem condição de acomodar o dobro de nós do nível anterior.
A alternativa "E" está correta. Uma árvore binária, por definição, é uma árvore cujo nó, seja qual for, pode ter até 2 filhos. Assim, o nó raiz pode ter 2 filhos, logo, o nível 2 acomoda o dobro de nós do nível 1. Cada nó do nível 2, por sua vez, pode ter dois filhos. Então, o nível 3 pode acomodar 4 nós. É fácil ver que cada nó de um nível permite acomodar 2 nós filhos no nível seguinte. Logo, cada nível de uma árvore binária permite acomodar o dobro de nós do nível anterior.
------------------------------------------------------------------------------------------------------------------------------------------------
Percorrer uma árvore binária é uma forma de realizar sistematicamente uma operação sobre seus nós. Durante o percurso, pode ser necessário acessar um nó mais de uma vez. Sobre este tema, a única opção que apresenta uma afirmativa correta é:
A) No percurso em pré-ordem, um nó pode ser visitado mais de uma vez.
B) O percurso em pós-ordem não visita todos os nós em uma árvore zigue-zague.
C) O percurso em ordem simétrica visita todos os nós da árvore somente uma vez.
D) O percurso em pós-ordem sempre visita os nós na sequência inversa do percurso em pré-ordem.
E) Apenas o percurso em ordem simétrica consegue visitar todos os nós em uma árvore.
A alternativa "C" está correta. Todas as 3 formas de percorrer uma árvore, pré-ordem, ordem simétrica e pós-ordem visitam todos os nós da árvore binária uma única vez. A diferença dos percursos é a ordem com que os nós são visitados.
------------------------------------------------------------------------------------------------------------------------------------------------
Árvores binárias de busca (ABB) são uma aplicação de árvores binárias para solucionar problemas de busca. Para isso, uma ABB tem seus nós rotulados de forma que estes guardem uma relação de precedência entre os que pertencem às subárvores esquerda e direita. Marque a única opção que contém uma afirmação correta sobre ABB.
A) Os nós da subárvore direita de um nó v têm rótulos menores do que v .
B) Todos os nós da subárvore esquerda sempre têm rótulos menores que os nós da subárvore direita.
C) Os nós das subárvores de um nó v têm rótulos maiores do que v.
D) Se um nó s é inserido na ABB e já existe outro nó p com o mesmo rótulo, s é inserido na subárvore oposta a p.
E) Os nós da subárvore esquerda de um nó v  têm rótulos maiores do que v .
A alternativa "B" está correta. Uma ABB é definida de maneira que qualquer que seja o nó v da árvore, os nós pertencentes à subárvore esquerda de v têm rótulo menor do que v e os nós pertencentes à subárvore à direita de v têm rótulo maior do que v.
------------------------------------------------------------------------------------------------------------------------------------------------
Sobre árvores AVL, analise as afirmações a seguir:
I) Toda árvore cheia é uma árvore AVL.
II) Toda árvore AVL é uma árvore cheia.
III) Balancear uma árvore AVL desregulada implica transformá-la numa árvore completa.
São verdadeiras apenas:
A) I
B) II
C) II e III
D) I e II
E) I e III
A alternativa "A" está correta. Uma árvore cheia só admite nós com subárvore vazia no último nível. Então, todos os nós dos níveis anteriores não possuem árvores vazias. Pela definição, também inferimos que todos os nós do último nível são folhas, pois, do contrário, existiria pelo menos um nó no penúltimo nível com uma subárvore vazia. Nesta configuração, as subárvores esquerda e direita de um nó v qualquer sempre têm a mesma altura e, portanto, uma árvore cheia é AVL.