AV Estrutura de Dados 2014.2

Prévia do material em texto

Av 2014 - Estrutura de Dados 
 
Como é a lógica do LIFO? 
 
 
Resposta: Estrutura linear PILHA que usa a lógica LIFO. LIFO: Last In, último que entra é o primeiro a sair, First 
Out. Como uma pilha de pratos, o último colocado na pilha vai ser o primerio a ser retirado. 
 
 
Gabarito: O primeiro que entra na pilha é o último que sai. 
 
 
 
 2a Questão (Ref.: 201002160420) Pontos: 0,0 / 1,5 
Considere uma lista simplesmente encadeada não circular de inteiros e o tipo 
 
 struct no { 
 int dado; 
 struct no *link; 
 }; 
Faça uma função para inverter a lista e retornar o ponteiro para o início da lista resultante. 
Protótipo : no *inverter(no *ini); //ini aponta para o início da lista 
 
 
Resposta: 
 
 
Gabarito: no *inverter ( no *ini) // ini é um ponteiro para o início da lista { no *a, *b, *c; a = ini; b = NULL; 
while (a != NULL) { c = b; b = a; a = a->link; b->link = c; } ini = b; return(ini); } /* fim da função */ 
 
 
 
 3a Questão (Ref.: 201002135330) Pontos: 0,5 / 0,5 
Existem vários algoritmos de busca em estruturas de dados, um destes realiza a busca em vetores, e requer 
acesso aleatório aos elementos desta estrutura e parte do pressuposto de que os dados do vetor estejam 
ordenados e utiliza a técnica de divisão e conquista comparando o elemento desejado com o elemento do meio 
do vetor. Esta técnica ainda verifica se o elemento do meio do vetor for o desejado, a busca termina. Caso 
contrário, se o elemento do meio vier antes do elemento buscado, então a busca continua na metade posterior 
do vetor. E se o elemento do meio vier depois da chave, a busca continua na metade anterior do vetor. O 
algoritmo que utiliza esta metodologia é: 
 
 
Inserção 
 
Pesquisa sequencial 
 
Bolha 
 
Seleção 
 
Pesquisa binária 
 
 
 
 4a Questão (Ref.: 201002131935) Pontos: 0,0 / 0,5 
Marque a afirmativa correta para a "Ordenação em Listas Lineares Sequenciais". 
 
 
Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos. 
 
Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos. 
 
Consiste em fazer uma busca em um vetor já ordenado, dividindo o espaço de busca ao meio e 
verificando se o dado está no meio ou, antes do meio ou depois do meio. 
 
É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente. 
 
Consiste em fazer uma busca em um vetor desordenado, dividindo o espaço de busca ao meio e 
verificando se o dado está no meio ou, antes do meio ou depois do meio. 
 
 
 
 5a Questão (Ref.: 201002131910) Pontos: 0,5 / 0,5 
Estão entre algumas das possíveis formas de se estruturar dados: 
 
 
Grafos, lista ordenada, vetores. 
 
Grafos, lista ordenada, algoritmos. 
 
Algoritmos, lista ordenada, vetores. 
 
Grafos, algoritmos, fila. 
 
Lista encadeada, vetores, algoritmos. 
 
 
 
 6a Questão (Ref.: 201002132269) Pontos: 1,0 / 1,0 
As listas encadeadas podem ser elaboradas de duas formas utilizando uma técnica de encadeamento 
simplesmente ou encadeamento duplo. O que difere uma lista simplesmente encadeada de uma lista 
duplamente encadeada? 
 
 
Em uma lista duplamente encadeada cada nó aponta para nó seguinte e para o primeiro nó da fila. 
 
Em uma lista duplamente encadeada, cada nó aponta para um nó enquanto a lista simplesmente 
encadeada aponta para mais de um nó. 
 
Em uma lista duplamente encadeada cada nó aponta para nó seguinte. 
 
Em uma lista simplesmente encadeada cada nó aponta para nó seguinte e para o nó anterior. 
 
Em uma lista simplesmente encadeada cada nó aponta para um único nó enquanto a lista duplamente 
encadeada aponta para mais de um nó. 
 
 
 
 7a Questão (Ref.: 201002337044) Pontos: 0,0 / 0,5 
 Considere uma pilha sequencial P com capacidade para n elementos. 
 Sabendo que P é do tipo Pilha definido a seguir, marque a opção que corretamente 
implementa a operação de empilhamento, considerando que o topo da pilha recebeu -1 na 
inicialização. 
 
struct Pilha { 
 int v[n], topo; 
 }; 
 
 
 void empilhar(Pilha P, int valor) { 
 if (P.topo == n) 
 cout << "Pilha cheia."; 
 else { 
 P.topo++; 
 P.v[P.topo] = valor; 
 } 
} 
 void empilhar(Pilha P, int valor) { 
 if (P.topo == n - 1) 
 cout << "Pilha cheia."; 
 else { 
 P.topo++; 
 P.v[P.topo] = valor; 
 } 
} 
 void empilhar(Pilha &P, int valor) { 
 if (P.topo == n - 1) 
 cout << "Pilha cheia."; 
 else { 
 P.topo++; 
 P.v[P.topo] = valor; 
 } 
} 
 void empilhar(Pilha &P, int valor) { 
 if (P.topo == n - 1) 
 cout << "Pilha cheia."; 
 else 
 P.v[P.topo] = valor; 
} 
 
 void empilhar(Pilha &P, int valor) { 
 if (topo == n - 1) 
 cout << "Pilha cheia."; 
 else { 
 topo++; 
 v[topo] = valor; 
 } 
} 
 
 
 
 8a Questão (Ref.: 201002131742) Pontos: 0,5 / 0,5 
O que acontece quando tentamos retirar um elemento de uma pilha que já está vazia? 
 
 
Ordenação. 
 
Remoção. 
 
Underflow. 
 
Overflow. 
 
Inclusão. 
 
 
 
 9a Questão (Ref.: 201002334547) Pontos: 1,0 / 1,0 
Seja uma lista encadeada cujos nodos são formados pelo seguinte tipo de dado: 
struct empregado{ 
 long int matricula; 
 float salario; 
 empregado *proximo; 
}; 
 
Suponha que o ponteiro pont tenha o endereço de um nodo da lista, o qual se deseja atribuir um novo 
valor para o campo salario. Marque a alternativa que corretamente altera o valor do campo salario 
para 5000.00. 
 
 
pont.salario=5000.00; 
 
pont.empregado.salario=5000.00 
 
pont.empregado->salario=5000.00; 
 
salario=5000.00; 
 
pont->empregado->salario=5000.00; 
 
 
 
 10a Questão (Ref.: 201002123813) Pontos: 0,5 / 0,5 
Assinale a alternativa que apresenta duas formas de passagem de parâmetros para uma rotina ou função: 
 
 
Por memória e por disco. 
 
Por teste e por reforço. 
 
Por valor e por referência 
 
Por reforço e por referência. 
 
Por inferência e por valor.