Prova Online Estrutura dados ESAB - Carolline

Prévia do material em texto

Questão 1 : 
O algoritmo a seguir apresenta a ordenação por quick sort:
data-cke-saved-src=/media/images/wefewfefefefefefefefe.PNG
A variável i representa a posição do vetor com o valor maior ou igual ao valor do pivô. Já a variável j representa a posição do valor menor ou igual ao valor do pivô à sua direta. O comando de laço da linha 7 procura pela posição do valor maior ou igual ao valor da variável pivô, e as rotinas do comando de laço while da linha 8 percorrem o vetor para localizar o valor menor ou igual ao pivô. A ordenação do vetor utiliza a recursividade, conforme as chamadas recursivas das linhas 15 e 16 do código. Assinale a alternativa que completa as lacunas do código com as instruções corretas:
Acertou! A resposta correta é a opção B 
Justificativa: 
Gabarito: B
Comentário: O método de ordenação quick sort caracteriza-se pela segmentação do vetor e pela recursividade da ordenação. Logo, cada nova chamada da função de ordenação deve começar pela posição inicial e terminar na posição final do vetor, e esses valores são passados como parâmetros na chamada da função. Como a variável i representa a busca pelo valor igual ou maior que o valor do pivô, ela deve ser inicializada com o valor do parâmetro inicial, assim, na linha 3 do algoritmo, i deve começar valendo inicial, e na linha 7, essa variável deve ser incrementada de um em um (i++) para percorrer cada posição e localizar o valor fora de ordem na parte à esquerda do vetor. Já a variável j representa a posição do valor igual ou menor que o pivô à sua direita, portanto, deve ser inicializada com o valor final do vetor e no comando de laço da linha 8, decrementado de um em um (j--). Por fim, as chamadas recursivas são realizadas para a parte à esquerda do pivô, desde que a posição da variável j seja maior que a posição inicial (j > inicial) e para a parte à direita do pivô, desde que a variável i seja menor que a posição final do vetor (i
	A
	
	0,final,i++,j--,i==inicial,j==final
	B
	
	inicial,final,i++,j--,j>inicial,i<final
	C
	
	final,inicial,i++,j--,j>final, i<inicial
	D
	
	inicial, final, i--, j++, j>inicial, i<final
Questão 2 : 
Analise o código em C a seguir:
Figura – Exemplo de código em linguagem C.
Fonte: Elaborada pelo autor (2013).
Na execução do programa, a instrução da linha 21 imprime na tela o valor da variável x. Assinale a alternativa que corresponde ao valor da variável que será apresentado.
Acertou! A resposta correta é a opção D 
Justificativa: 
Gabarito: D
Comentário: A matriz será preenchida com os valores 1, 2, 3 e 4. A rotina da função main() percorrerá todos os elementos da matriz e seguirá guardando, na variável x, a soma de todos esses valores visitados. No final da rotina, na linha 21, o valor apresentado será 10. Esse conteúdo foi estudado na unidade 10.
X<-0
X<-0 +1;(1)
X<-1 +2;(3)
X<-3 +3;(6)
X<-6 +4;(10)
	A
	
	0
	B
	
	20
	C
	
	24
	D
	
	10
Questão 3 : 
. O algoritmo a seguir apresenta a função para listagem dos valores de uma fila que recebe como parâmetro a referência para a fila que será manipulada e o código do pedido a ser pesquisado:
Algoritmo – Exercício 
	01
	void listar(FilaPedidos* pedidos, int codigo){
	02
	  No* item = pedidos->inicio;
	03
	  while((item != NULL) && (item->numeropedido != codigo)){
	04
	    printf("Pedido Numero:%d \n",item->numeropedido);
	05
	    item = item->proximo;        
	06
	  }
	07
	  system("PAUSE");   
	08
	}
Fonte: Elaborado pelo autor (2013).
Supondo que a referência da fila de pedidos aponte para a fila com os seguintes números de pedidos:
E seja informado o pedido com o código 2 como valor a ser pesquisado nesta fila, assinale a alternativa que aponta os dados mostrados na tela:
Acertou! A resposta correta é a opção A 
Justificativa: 
Gabarito: A
Comentário: A fila começará a pesquisa a partir do primeiro elemento, que é 8. Como o endereço deste elemento, armazenado na variável item, é diferente de NULL e o número de pedido 8 é diferente de 2 (código pesquisado), o valor 8 será mostrado na tela e o item será atualizado para seu próximo, portanto apontando para o próximo elemento que é 1. Como este item (1) não é NULL e o número do pedido armazenado em item é diferente de 2, o valor 1 será mostrado na tela; em seguida, item valerá o endereço do próximo, o endereço do valor 7, que não é NULL e tem o número do pedido diferente de 2. Logo, o valor 7 será mostrado na tela. Após mostrar o valor 7, o item valerá o endereço do próximo, o endereço do valor 3, que não é NULL e tem o número do pedido diferente de 2, portanto o valor 3 será mostrado na tela, e em seguida item valerá o endereço do valor 4, que não é NULL e seu número de pedido não vale 2. Então, o valor 4 é mostrado na tela e em seguida item valerá o endereço do valor 9, que não é NULL e não possui número de pedido que vale 2, portanto o valor 9 será mostrado na tela e item valerá o próximo de 9, que é NULL. Assim, no retorno do laço while a condição (item != NULL) será falsa e o laço será encerrado, terminando a execução da função, mas como o valor 2 não existe na fila, todos os elementos serão listados.
	A
	
	8, 1, 7, 3, 4 e 9
	B
	
	8, 1, 7, 3
	C
	
	Nenhum valor será mostrado na tela.
	D
	
	8, 7, 4 e 9
Questão 4 : 
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:
Acertou! 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 
Questão 5 : 
Assinale a alternativa que afirma corretamente a alocação que possui como característica a alocação de memória contígua em bloco único. 
Acertou! A resposta correta é a opção A 
Justificativa: 
Gabarito: A
Comentário: A alocação estática se caracteriza por alocar um bloco único de memória contígua, o que facilita o acesso à informação para gravação e leitura dos dados da estrutura. Na alocação dinâmica, durante a execução do programa, são requisitados blocos de memória aleatoriamente, à medida que surge a necessidade de uso, por isso os blocos são alocados dispersadamente, porém, exigem que cada bloco tenha a informação do próximo bloco que os une (unidade 5). 
	A
	
	Estática
	B
	
	Local
	C
	
	Dinâmica
	D
	
	Global
Questão 6 : 
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:
Acertou! 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 7 : 
Com base nos estudos da estrutura de dados vetor, marque com V (para verdadeiro) e F (para falso): 
I – O vetor permite criar uma variável dividida em inúmeras posições, todas do mesmo tipo de dados.
II – O vetor em C sempre começa da posição 1 e termina na posição tamanho -1.
III – Um vetor de 10 posições terá 10 endereços de memória.
IV – O vetor é um típico exemplo de alocação de memória dinâmica.
Assinale a única opção correta. 
Acertou! A resposta correta é a opção B 
Justificativa: 
Gabarito: B
Comentário: O vetor permite criar uma variável dividida em inúmeras posições, todas do mesmo tipo de dados. O vetor em C sempre começa na posição 0 e se encerra na posição do tamanho -1. Um vetor é uma estrutura de dados com várias posições, indexadas, mas com um único endereço de memória. O vetor é o típico exemplo de alocação estática, pois uma vez alocada, o bloco de memória não poder ser gerenciado (unidade 4). 
	A
	
	V – V – F – F
	B
	
	V – F – F – F
	C
	
	F – F – F – F
	D
	
	V – V – V – V
Questão 8 : 
Na inserção no final da lista circular duplamente encadeada, o primeiro elemento da lista e o último elemento da lista precisam ser ligados de forma a garantir a característica de processo cíclico da lista circular. Assinale a alternativa que apresenta corretamente as regras que representam a inserção no final da lista circular duplamente encadeada.
Acertou! A resposta correta é a opção D 
Justificativa: 
Gabarito: D
Comentário: Para que o processo cíclico seja mantido, o último deve apontar para o primeiro da lista, o que caracteriza a lista circular como uma lista sem “último”. Mas como se trata de uma lista duplamente encadeada, a cada inserção é preciso gerenciar os dois descritores de cada nó, o anterior e o próximo. Assim, o novo elemento da lista deve ter como anterior o nó que era o último da lista, e o último deve apontar como próximo para o novo elemento. Isso garante que o último e o novo estejam duplamente ligados, porém o processo cíclico não foi garantido. Para tanto, o novo deve apontar como próximo para o primeiro e o primeiro apontar como anterior para o último. Por fim, como se trata de uma inserção no final, o novo elemento deve ser setado como último da lista (unidade 25).
	A
	
	Apenas o novo elemento deve apontar como próximo para o primeiro. Depois, o novo elemento passa a ser o último da lista.
	B
	
	Apenas o primeiro deve apontar como anterior para o novo elemento. Depois, o novo elemento passa a ser o último da lista.
	C
	
	O novo elemento deve apontar como anterior para o último e o último deve apontar como próximo para o novo. Depois, o novo elemento passa a ser o último da lista.
	D
	
	O novo elemento deve apontar como anterior para o último e o último deve apontar como próximo para o novo. O novo deve apontar como próximo para o primeiro e o primeiro apontar como anterior para o novo elemento. Depois, o novo elemento passa a ser o último da lista.
Questão 9 : 
Com relação ao processo de inserção no início da lista duplamente encadeada, marque a única opção que descreve corretamente as regras a serem implementadas para esse tipo de inserção. 
Acertou! A resposta correta é a opção B 
Justificativa: 
Gabarito: B
Comentário: A inserção do início da lista duplamente encadeada deve garantir que o elemento inserido seja sempre referenciado como o primeiro da lista. Caso esse novo elemento a ser inserido não esteja em uma lista vazia, o novo elemento deverá apontar como próximo para o primeiro elemento da lista. O primeiro elemento da lista deverá apontar como anterior para o novo elemento. Assim, novo e primeiro estarão ligados corretamente. Após essas ligações, o novo elemento será atualizado como primeiro da lista. Se a lista estiver vazia, o novo elemento apontará como próximo para ele mesmo (unidade 22).
	A
	
	A inserção do início da lista tem como finalidade garantir que o elemento inserido seja definido como o primeiro da lista. Na inserção do novo elemento na lista, o primeiro elemento deverá apontar como próximo para o novo elemento inserido e o novo elemento deverá apontar como próximo para o primeiro elemento. Por fim, o novo elemento deve ser definido como primeiro da lista.
	B
	
	A inserção do início da lista tem como finalidade garantir que o elemento inserido seja definido como o primeiro da lista. Na inserção do novo elemento na lista, o primeiro elemento deverá apontar como anterior para o novo elemento inserido e o novo elemento deverá apontar como próximo para o primeiro elemento. Por fim, o novo elemento deve ser definido como primeiro da lista.
	C
	
	A inserção do início da lista tem como finalidade garantir que o elemento inserido seja definido como o primeiro da lista. Na inserção do novo elemento na lista, o último elemento deverá apontar como anterior para o novo elemento inserido e o novo elemento deverá apontar como próximo para o último. Por fim, o novo elemento deve ser definido como primeiro da lista.
	D
	
	A inserção do início da lista tem como finalidade garantir que o elemento inserido seja definido como o primeiro da lista. Na inserção do novo elemento na lista, o primeiro elemento deverá apontar como anterior para o primeiro elemento inserido e o novo elemento deverá apontar como próximo para o novo elemento. Por fim, o novo elemento deve ser definido como primeiro da lista.
Questão 10 : 
A árvore binária possui como características a existência de no máximo dois nós filhos para cada nó da árvore e o armazenamento dos valores maiores sempre à direita do nó pai e dos valores menores, à esquerda do nó pai. Assim, para localizar o maior valor da árvore, devem-se percorrer todos os nós da árvore a partir do nó raiz até que se chegue ao nó mais à direita na árvore. Assinale a alternativa que mostra o algoritmo que representa corretamente a busca pelo maior valor na árvore binária:
Acertou! A resposta correta é a opção A 
Justificativa: 
Gabarito: A
Comentário: Para localizar o maior valor da árvore binária é preciso verificar se o nó visitado (árvore) possui elemento à direita. Caso não exista um elemento à direita, o valor do nó visitado corresponde ao maior valor da árvore, portanto deve ser retornado (return arvore->valor;). Caso contrário, recursivamente, deve-se descer à direita na árvore, por isso a chamada recursiva é acharMaior(arvore->dir). Dessa forma, a cada interação da função acharMaior(), é possível caminhar na árvore até que se chegue ao elemento mais à direita, consequentemente, o maior valor da árvore (unidade 37).
	A
	
	
	B
	
	
	C
	
	
	D