Prova Estrutura de Dados ESAB

Prévia do material em texto

Estrutura de Dados
Questão 1 : 
A árvore binária possui no máximo dois filhos para cada nó, ou seja, as árvores binárias possuem nós com grau menor ou igual a 2, isto é, nenhum nó possui mais que dois descendentes diretos, dois filhos. A figura a seguir apresenta uma árvore binária:
data-cke-saved-src=/media/images/cacafkajfnwgilaerghargrgrgrgrgr.PNG
Figura – Árvore binária com cinco elementos.
Fonte: Elaborada pelo autor (2013).
Com base na análise da árvore apresentada, é correto afirmar que:
A resposta correta é a opção C 
Justificativa: 
Gabarito: C
Gabarito: A árvore apresentada é binaria, pois todos os nós pais possuem no máximo dois filhos, o nó 10 é a raiz da árvore, o nó 08 é pai dos nós 04 e 09, que são folhas, assim como o nó 55. O pai do nó 55 é o nó 21, que, por sua vez, tem como pai o nó 10. Nenhum nó é maior que seus filhos e a altura da árvore é 2, que é o maior nível da árvore (unidade 33).
	A
	
	a árvore não possui raiz.
	B
	
	a árvore possui todos os nós pais maiores que seus filhos.
	C
	
	a árvore possui como raiz o nó 10, a altura da árvore é 2 e o nó 08 é pai do nó 04.
	D
	
	não se trata de uma árvore binária, pois o nó 21 tem apenas um filho, o nó 55.
Questão 2 : 
Na implementação da pilha usando a lista simplesmente encadeada, a função pop() tem como finalidade remover o elemento que está no topo e atualizar o descritor topo da pilha para o elemento abaixo do topo removido, apontado pelo descritor anterior do nó. O algoritmo a seguir apresenta a remoção na pilha:
Algoritmo – Exercício
	01
	void pop(Pilha *pilha){
	02
	if(pilha->topo != NULL){
	03
	     No* aux = pilha->topo;
	04
	     pilha->topo = pilha->topo->anterior;
	05
	     free(aux);     
	06
	  }
	07
	}
Fonte: Elaborado pelo autor (2013). 
Com base no algoritmo, analise as seguintes sentenças:
I – A instrução da linha 4 é opcional, pois a remoção do elemento do topo já ocorre na instrução da linha 3, quando o topo passa a ser o anterior do topo.
II – A instrução “if” da linha 2 verifica se a pilha está vazia e evita que a operação  remover seja executada com a pilha vazia, pois as linhas 3 a 5 só serão executadas se a pilha tiver pelo menos um elemento.
III – Se a pilha possuir um elemento apenas, como seu anterior vale NULL, ao executar a instrução da linha 3, pilha->topo = pilha->topo->anterior, o topo terá seu valor alterado para NULL.
IV – A instrução free(aux), da linha 05, é que remove fisicamente o elemento da memória, liberando o espaço que havia sido alocado.
Assinale a alternativa que apresenta apenas as afirmativas corretas:
A resposta correta é a opção C 
Justificativa: 
Gabarito: C
Comentário: A instrução da linha 3, pilha->topo = pilha->topo->anterior, faz com que o endereço do topo seja atualizado com o endereço do elemento anterior, porém, a remoção física do elemento que era topo não foi realizada, e ele continua alocando um espaço de memória que não será liberado até que o programa termine. Sendo assim, será um espaço de memória alocado e sem uso. A remoção realmente acontecerá quando a função free() for executada para esse endereço, liberando o espaço de memória alocado. Caso a pilha tenha um elemento, seu anterior valerá NULL, logo, quando a instrução da linha 3 for executada, o topo será atualizado com o anterior do único elemento (topo) que vale NULL. Portanto, o topo também valerá NULL, o que está correto, pois esse único elemento será removido. Porém, caso a pilha esteja vazia, o topo vale NULL e, ao tentar recuperar o seu anterior, um erro fatal será gerado e a execução do programa será encerrada. Por isso, verificar se lista está vazia pode solucionar esse problema (unidade 28). 
	01
	void pop(Pilha *pilha){
	02
	  if(pilha->topo != NULL{
	04
	       No* aux = pilha->topo;
	04
	       pilha->topo = pilha->topo->anterior;
	05
	       free(aux);     
	06
	  }
	07
	}
 
	A
	
	I, II e III
	B
	
	I, II e IV
	C
	
	II, III e IV
	D
	
	I e II
Questão 3 : 
Assinale a alternativa que corresponde à sintaxe correta usada para definir uma variável ponteiro em C. 
A resposta correta é a opção A 
Justificativa: 
Gabarito: A
Comentário: A definição, ou declaração de um ponteiro, tem como finalidade informar para a linguagem de programação que aquela variável guardará o endereço de uma variável e não o seu valor. Porém, sabendo o endereço da variável é possível “apontar” para ela e efetuar operações de gravação, alteração e consulta aos dados. Para declaração de uma variável do tipo ponteiro em C, é utilizado o símbolo de asterisco (*) antes do nome da variável e depois do tipo da variável (unidade 6). 
 
	A
	
	Tipo de dado, seguido de um asterisco e o nome da variável.
	B
	
	Tipo de dado, seguido da palavra pointer e o nome da variável.
	C
	
	Tipo de dado, seguido da palavra static e o nome da variável.
	D
	
	Tipo de dado, seguido da palavra dinamic e o nome da variável.
Questão 4 : 
Analise o código a seguir:
Figura – Exemplo de código em linguagem C.
Fonte: Elaborada pelo autor (2013).
Qual o valor inteiro que representa o estado civil VIUVO? Assinale a alternativa correta. 
A resposta correta é a opção C 
Justificativa: 
Gabarito: C
Comentário: Como vimos na unidade 9, um tipo enumeração em C pode ser representado por um termo (palavra) ou por um valor inteiro. Por definição, o primeiro valor do conjunto de enumeração é identificado pelo valor inteiro 0; o segundo pelo valor 1; e assim sucessivamente. Assim o valor CASADO valerá 0, o valor SOLTEIRO 1, VIUVO 2, DIVORCIADO 3 e OUTROS valerá 4.
	A
	
	0
	B
	
	1
	C
	
	2
	D
	
	3
Questão 5 : 
Com relação à busca sequencial e à busca binária, analise as seguintes sentenças:
 
I – Quanto maior a quantidade de elementos de um vetor, mais rápida será a busca sequencial.
II – A forma mais simples de busca em um vetor consiste em percorrer o vetor, elemento a elemento, para verificar se o elemento de interesse existe no vetor, ou seja, se algum dos elementos do vetor é igual ao elemento desejado.
III – A busca binária pode ser realizada em qualquer tipo de vetor, estando ele ordenado ou não.
IV – A busca sequência não poder ser realizada em vetores ordenados.
 
Assinale a alternativa que aponta apenas as sentenças verdadeiras.
A resposta correta é a opção B 
Justificativa: 
Gabarito: B
Comentário: A forma mais simples de busca em um vetor consiste em percorrer o vetor, elemento a elemento, para verificar se o elemento de interesse existe no vetor, ou seja, se algum dos elementos do vetor é igual ao elemento desejado. A busca sequencial é um algoritmo bastante simples, porém, a sua eficiência é baixa, já que é preciso percorrer todos os elementos do vetor, desde a primeira posição, até que seja localizado o valor desejado ou que o vetor se encerre. Logo, quando maior o vetor, mais demorada será a pesquisa sequencial. Uma estratégia para tornar o algoritmo de busca sequencial mais eficiente é considerar que a estrutura de dados já está ordenada. A busca binária destina-se à busca em vetores ordenados, caso contrário, não poderá ser aplicada. A ideia do algoritmo é buscar o elemento desejado, comparando-o com o elemento do meio do vetor. Se o valor do meio do vetor for igual ao elemento desejado, podemos parar a busca (unidade 45).
	A
	
	I, II, III e IV.
	B
	
	II e IV.
	C
	
	I e III.
	D
	
	I e II.
Questão 6 : 
Com relação à estrutura de dados fila e seu funcionamento, muito semelhante a uma fila de banco e a uma fila de arquivos para impressão, analise as sentenças a seguir:
	I  
	A fila é conhecida como LIFO – last in, first out.
	II  
	A fila é uma estrutura na qual as operações de inserção e retirada ocorrem apenas no início da lista.
	III
	A fila é conhecia como FIFO (first in, first out), em que os elementos que foram inseridos no início são os primeiros a serem removidos. Logo, a ordem de saída corresponde à ordem de entrada dos elementos.
	IV
	Os elementos são inseridos em um extremo da fila e removidos pelo outro extremo.
Assinale a alternativa que mostra apenas as afirmativas corretas:
A resposta correta éa opção A 
Justificativa: 
Gabarito: A
Comentário: A estrutura de dados fila possui como característica o fato de que a inserção ocorre em uma extremidade e a remoção em outra. Isso lhe garante a identificação como uma estrutura de dados FIFO (first in, first out), em que o primeiro a entrar é o primeiro a sair, logo, a ordem de saída corresponde à ordem de entrada dos elementos. Assim, em termos de operação, a fila realiza a inserção no seu final e a remoção no seu início (unidade 29).
	A
	
	III e IV
	B
	
	I e II
	C
	
	I, II, III e IV
	D
	
	Apenas a III
Questão 7 : 
O Algoritmo de Merge Sort divide a estrutura de dados em várias partes (divisão), sendo cada parte ordenada em separado (conquista) e, ao final, os segmentos previamente ordenados são combinados (combinação), resultando na estrutura de dados ordenada. Considere o vetor X com os seguintes elementos: 38, 16,27, 39,12 e 27.
Ao aplicar a primeira divisão do vetor, usando o algoritmo de merge sort, assinale a alternativa que mostra como os elementos serão divididos.
 
A resposta correta é a opção D 
Justificativa: 
Gabarito: D
Comentário: O funcionamento do algoritmo visa garantir os três passos para a ordenação da estrutura de dados: dividir, conquistar e combinar, e, para isso, o vetor é dividido, inicialmente, em duas partes, se possível com a mesma quantidade de elementos (unidade 43).
	A
	
	
	B
	
	
	C
	
	
	D
	
	
Questão 8 : 
Considere o vetor X, um vetor de inteiros com seis posições e preenchido com os valores 10, 18, 15, 21, 4, 17. O método de ordenação quick sort possui como principal característica a ordenação do vetor em partes, tendo como referência um elemento chamado de pivô, que pode ser qualquer elemento já existente no vetor. O processo de ordenação consiste em procurar um elemento que esteja à esquerda do pivô e que seja maior ou igual ao valor do pivô, e achar à direita um valor menor ou igual ao valor do pivô, e depois efetuar a troca desses valores. Considerando que o pivô é o elemento da posição 2, isto é, o valor 15, assinale a alternativa que apresenta a primeira troca dos elementos do vetor:
A resposta correta é a opção C 
Justificativa: 
Gabarito: C
Comentário: Como o elemento pivô é o valor 15 na posição 2, à direita será pesquisado o primeiro valor menor que o 15, que é o valor 4, e à esquerda será pesquisado o primeiro valor maior que 15, que é o 18, logo, os valores 18 e 4 serão trocados, e o vetor ficará assim distribuído: 10, 4, 15, 21,18 e 17 (unidade 41).
	A
	
	10 por 4
	B
	
	18 por 17
	C
	
	18 por 4
	D
	
	15 por 17
Questão 9 : 
A função de combinação é utilizada na função de segmentação do vetor, uma vez que, após a divisão dos elementos do vetor (segmentação), os dados dos segmentos devem ser ordenados por meio da combinação. O algoritmo a seguir apresenta a função de segmentação do vetor:
Algoritmo – Função de segmentação
	01
	void segmentacao(int v[],int aux[],int esq, int dir){
	02
	 int meio,i;
	03
	 if(esq<dir){
	04
	    meio=(esq+dir)/2;
	05
	    segmentacao(v,aux,esq,meio);
	06
	    segmentacao(v,aux,meio+1,dir);
	07
	    combinacao(v,aux,esq,meio+1,dir); 
	08
	  }
	09
	}
Fonte: Elaborado pelo autor (2013).
 
Analisando o código, assinale a alternativa correta.
 
A resposta correta é a opção A 
Justificativa: 
Gabarito A
Comentário: Na linha 7 do algoritmo, a função de combinação é chamada para que os segmentos criados nas rotinas recursivas das linha 5 e 6 sejam ordenados. A instrução da linha 5 é responsável por segmentar o vetor da posição inicial até o meio do vetor, e a instrução da linha 6 segmenta o vetor a partir da posição do meio do vetor até o final do vetor. Portanto, é uma função recursiva que será chamada sempre que o valor do parâmetro esq for menor que o valor do parâmetro dir (unidade 44).
	A
	
	A chamada da função segmentação na linha 5 tem como finalidade ordenar os elementos do primeiro segmento do vetor.
	B
	
	A chamada da função segmentação na linha 6 tem como finalidade ordenar os elementos do primeiro segmento do vetor.
	C
	
	A função será chamada, recursivamente, sempre que o valor do parâmetro esq for igual ao valor do parâmetro dir.
	D
	
	Não se trata de uma função recursiva.
Questão 10 : 
Há três formas de se percorrer os nós das árvores binárias e listar os elementos armazenados em cada nó: pré-fixado, central e pós-fixado. Cada uma dessas formas possui uma sequência da ordem de visita dos elementos raiz (R), esquerda (E) e direita (D), e que são visitados recursivamente. O algoritmo a seguir apresenta uma função para percorrer os elementos da árvore binária:
Algoritmo – Exercício 
	01
	void percorrer(ArvoreBinaria no){
	02
	  if (no != NULL){
	03
	    if (no->esq != NULL) percorrer (no->esq);
	04
	    if (no->dir != NULL) percorrer (no->dir);
	05
	    printf(%d\n,no->valor);
	06
	  }    
	07
	}
Fonte: Elaborado pelo autor (2013).
Este algoritmo corresponde ao percurso do tipo:
A resposta correta é a opção B 
Justificativa: 
Gabarito: B
Comentário: A forma de percurso pré-fixado é R(raiz), E (esquerda) e D (direita). Já o percurso central tem como ordem de visita dos nós E (esquerda), R (raiz) e D (direita). Por fim, o percurso pós-fixado tem como sequência E (esquerda), D (direita) e R (raiz). Como no algoritmo a ordem de visita do nó é percorrer (no->esq), depois percorrer (no->dir) e por fim printf("%d\n",no->valor), se trata portanto do percurso pós-fixado (unidade 35).
	A
	
	pós-central 
	B
	
	pós-fixado 
	C
	
	pré-fixado 
	D
	
	central