Aula 1 a 5

Prévia do material em texto

1.
		As estruturas de dados podem ser caracterizadas como sendo uma forma organizada de armazenar dados ou informações na memória, de modo a otimizar o acesso a estes. Muitas vezes existem algoritmos de manipulação de dados associados a estas estruturas. 
Verifique as seguintes sentenças:
I-Filas são estruturas que recuperam os dados na ordem direta em que estes foram armazenados.
II-As Pilhas são estruturas que recuperam os dados na ordem reversa em que estes foram armazenados.
III-As Pilhas são estruturas que recuperam os dados na ordem direta em que estes foram armazenados.
IV-As Filas são estruturas que recuperam os dados na ordem reversa em que estes foram armazenados.
Marque a alternativa CORRETA:
	
	
	
	As alternativas I e III estão corretas.
	
	
	As alternativas I e II estão corretas
	
	
	As alternativas II e IV estão corretas.
	
	
	Todas as alternativas estão corretas.
	
	
	As alternativas III e IV estão corretas.
	
	
	
	 
		
	
		2.
		Estão entre algumas das possíveis formas de se estruturar dados:
	
	
	
	Grafos, lista ordenada, algoritmos.
	
	
	Grafos, algoritmos, fila.
	
	
	Algoritmos, lista ordenada, vetores.
	
	
	Grafos, lista ordenada, vetores.
	
	
	Lista encadeada, vetores, algoritmos.
	
Explicação:
	FAlso.  Algoritmos não são estrutura de dados
	Grafos, algoritmos, fila.
	.
	FAlso.  Algoritmos não são estrutura de dados.
	Grafos, lista ordenada, algoritmos.
	 
	Correto.
	Grafos, lista ordenada, vetores.
	 
	FAlso.  Algoritmos não são estrutura de dados.
	Algoritmos, lista ordenada, vetores.
	 
	
FAlso.  Algoritmos não são estrutura de dados.
	Lista encadeada, vetores, algoritmos.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		3.
		Diferentes tipos de estrutura de dados são adequadas a diferentes tipos de aplicação e algumas são altamente especializadas, destinando-se a algumas tarefas específicas. Dessa forma a definição de Estrutura de Dados está expressa na alternativa:
	
	
	
	É um modo de distribuição e organização de dados em uma rede de computador de modo que possam ser usados de modo eficiente.
	
	
	São os nomes dados as variáveis na montagem de uma rotina.
	
	
	É um modo de utilização de dados nos programas de computador.
	
	
	É um modo de deleção de dados em um computador.
	
	
	É um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados de modo eficiente.
	
Explicação:
Analisando cada item :
	
	É um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados de modo eficiente.
	Correta.
	
	É um modo de distribuição e organização de dados em uma rede de computador de modo que possam ser usados de modo eficiente.
	FAlso. Não há distribuição de dados ou organização de dados em uma rede via estrutura de dados.
	
	É um modo de utilização de dados nos programas de computador.
	FAlso. Não se diz como se utiliza dados.  Variáveis armazenam dados, por exemplo e em atribuições ou em expressões também utilizamos dados.
	
	São os nomes dados as variáveis na montagem de uma rotina.
	FAlso.  Nomes de variáveis são identificadores.
	
	É um modo de deleção de dados em um computador.
Falso. Para "deletar" um dado não temos que usar estrutura de dados.
	
	
 
	
	Gabarito
Coment.
	
	
	
	 
		
	
		4.
		Leia com atenção as afirmativas abaixo e assinale a resposta correta.
I A estrutura de dados que melhor representa os diretórios ou pastas de arquivos do computador é a árvore. 
II A estrutura de dados FILA é não linear assim como o Grafo. 
III O termo folha em uma estrutura de dados é usado para um nó sem filhos e que tem grau 0, 
IV O grau de uma árvore é definido pelo número de subárvores de um nó. 
V O grafo é uma estrutura de dados que tem limitação para o número de vértices. 
VI Uma das aplicações da estrutura de dados grafo é a Computação Gráfica. 
	
	
	
	I, III, IV e VI são afirmativas verdadeiras
	
	
	I, II e V são afirmativas verdadeiras
	
	
	II, IV, V e VI são afirmativas verdadeiras
	
	
	I, II, III e VI são afirmativas verdadeiras
	
	
	II, IV e V são afirmativas verdadeiras
	
	Gabarito
Coment.
	
	
	
	 
		
	
		5.
		A forma correta para imprimir o valor do último elemento de um vetor v com n posições é:
	
	
	
	cout << v[n+1];
	
	
	cout << v[n-1];
	
	
	cin >> v[-1];
	
	
	cout << v[n];
	
	
	cout << v[ultimo];
	
	
	
	 
		
	
		6.
		Observe o trecho do programa em C++ abaixo e, após, entrar com os valores sugeridos para sua execução assinale a alternativa que representa a resposta final.
cin >> a;
cin >> b;
cin >> c;
cin >> d;
cout << a;
cout << b;
cout << c;
cout << d;
cout << d;
cout << c;
cout << b;
cout << a;
	
	
	
	Após a impressão dos valores pela ordem teremos uma fila e um grafo.
	
	
	Após a impressão dos valores pela ordem teremos duas filas.
	
	
	Após a impressão dos valores pela ordem teremos uma pilha e uma fila.
	
	
	Após a impressão dos valores pela ordem teremos duas pilhas.
	
	
	Após a impressão dos valores pela ordem teremos uma fila e uma pilha.
	
	
	
	 
		
	
		7.
		Qual estrutura de dados é mais adequada para armazenar a estrutura do diretório do sistema de arquivos de um sistema operacional?
	
	
	
	Fila
	
	
	Lista
	
	
	Pilha
	
	
	Árvore
	
	
	Grafo
	
Explicação:
A estrutura de diretórios mostra hierarquia e um relacionamento não linear. Por isso, a resposta certa é árvore.
 
Lista, pilha e fila são estruturas de dados linear.
 
Grafo é não linear, mas não é hierárquica.
	
	
	
	 
		
	
		8.
		Das estruturas de dados a seguir aquela que NÃO é uma estrutura linear é :
	
	
	
	Fila.
	
	
	Grafo.
	
	
	Pilha.
	
	
	Lista.
	
	
	Vetor.
	
Explicação:
Lineares : lista, pilha, fila, deque. Com ou sem vetor, que é linear.
Não lineares  : árvore e grafo.
	
	 
		
	
		1.
		As estruturas de dados são utilizadas para manter dados ou informações organizados na memória, o que possibilita a otimização do uso destes dados. Porém, as estruturas guardam características especiais na manipulação destes dados, assim deve-se escolher a estrutura certa ou mais adequada para uma determinada aplicação. Portanto marque a opção que representa a melhor estrutura, quando se tem como requisitos principais o acesso aleatório aos dados e alocação destes de forma contínua na memória.
	
	
	
	Fila Sequencial
	
	
	Lista Sequencial
	
	
	Pilha Encadeada
	
	
	Lista Encadeada
	
	
	Pilha Sequencial
	
	
	
	 
		
	
		2.
		É um exemplo de TAD Não Linear:
	
	
	
	Grafos
	
	
	Listas
	
	
	Filas
	
	
	Pilhas
	
	
	Filas de Prioridade
	
Explicação: Um grafo é um tipo de dados abstrato não linear
	
	
	
	 
		
	
		3.
		Na maioria dos sistemas operacionais, os arquivos são organizados hierarquicamente em um esquema de diretórios (pastas) e sub-diretórios. Qual a estrutura mais adequada para representar este problema ?
	
	
	
	grafo
	
	
	pilha
	
	
	fila
	
	
	lista
	
	
	árvore
	
	Gabarito
Coment.
	
	
	
	 
		
	
		4.
		          Os irmãos Silva irão viajar por vários países da Europa e por isso, traçaram no mapa o percurso que farão, de cidade a cidade.  Qual a estrutura de dados mais adequada para modelar este problema ?
	
	
	
	 Lista
	
	
	Grafo
	
	
	             Pilha
	
	
	Fila
	
	
	              Árvore
	
	
	
	 
		
	
		5.
		Para organizar as fotos de minha família com os ancestrais de várias gerações, minha filha usou uma estrutura de dados que é .....  Assinale a opção certa.
	
	
	
	lista
	
	
	grafo
	
	
	pilha
	
	
	árvore
	
	
	fila
	
Explicação:
Conforme gabarito e aula 1.
	
	
	
	 
		
	
		6.
		Assinale a alternativa correta sobre tipos abstratos de dados:
	
	
	
	Um tipo abstrato de dados deve sempre ser representado por meio dos recursos específicos de uma linguagem de programação.
	
	
	Um tipo abstrato de dados descreve, além do que se podefazer com os dados, como as operações serão efetivamente implementadas.
	
	
	É fundamental que os tipos abstratos de dados proponham um conjunto eficiente de algoritmos para realização de suas operações.
	
	
	Um tipo abstrato de dados é composto por um modelo de dados e um conjunto de operadores definidos sobre esses dados.
	
	
	Um tipo abstrato de dados é um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados eficientemente.
	
Explicação:
	
	Um tipo abstrato de dados é composto por um modelo de dados e um conjunto de operadores definidos sobre esses dados.
	Verdadeiro.  Por definição de TAD (tipo abstrato de dados).
	
	Um tipo abstrato de dados é um modo particular de armazenamento e organização de dados em um computador de modo que possam ser usados eficientemente.
	Falso.   Quando se pensa em TAD não há vínculos com implementação.
	
	Um tipo abstrato de dados descreve, além do que se pode fazer com os dados, como as operações serão efetivamente implementadas.
	FAlso.  Não se pensa em implementação quando se trabalha com TAD.
	
	É fundamental que os tipos abstratos de dados proponham um conjunto eficiente de algoritmos para realização de suas operações.
	FAlso. Não se pensa em implementação ou eficiência quando se trabalha com TAD. Se pensa na semântica das operações.
	
	Um tipo abstrato de dados deve sempre ser representado por meio dos recursos específicos de uma linguagem de programação.
	
	
 Falso : Não se pensa em programa ou na linguagem de programação, pois o TAD não está vinculado à implementação.
	
	
	
	 
		
	
		7.
		Podemos dizer que estrutura de dados é:
	
	
	
	É a saída, que satisfaz a quaisquer restrições impostas pelo problema, necessária para se calcular uma solução do problema.
	
	
	A entrada, que satisfaz a quaisquer restrições impostas pelo problema, necessária para se calcular uma solução do problema.
	
	
	O que permite o armazenamento e a recuperação de dados independentemente de seu conteúdo.
	
	
	Uma sequência de passos computacionais que transforma uma entrada em uma saída previamente determinada.
	
	
	O meio para armazenar e organizar dados com o objetivo de facilitar o acesso e as modificações.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		8.
		Preciso fazer uma relação de tudo o que levar em minha viagem de mochila pela Europa.  A estrutura de dados mais adequada para armazenar tudo que preciso levar é ...
	
	
	
	árvore
	
	
	grafo
	
	
	pilha
	
	
	lista
	
	
	fila
	
Aula 2
		1.
		 
	
	
	
	O programa executa perfeitamente, mas não mostra o valor da media já que esta função não foi chamada na função main( ).
	
	
	O programa não executa corretamente, pois o protótipo da função media( ) não apresenta a identificação dos parâmetros, mas apenas os tipos dos mesmos.
	
	
	O programa executa perfeitamente independente da ordem das funções já que existem os seus protótipos.
	
	
	O programa não executa corretamente pois as funções devem ser descritas antes da função main(), para que o compilador consiga reconhecê-las.
	
	
	O programa não executa corretamente, pois os protótipos estão fora da ordem em que as funções são descritas.
	
	
	 
		
	
		2.
		No programa abaixo em C++, que sequência de valores serão impressos ? int x; x = 15; if (x > 0) { int x; x = 25; cout << x << endl; } cout << x << endl;
	
	
	
	25 e 15
	
	
	15 e 15
	
	
	0 e 5
	
	
	25 e 25
	
	
	15 e 25
	
Explicação:
Analisando passo a passo, temos :
x é declarado e inicializado com 15. Daí, testa-se a condição do if, que é verdadeira. Em seguida, entra-se no bloco do if onde um outro x é declarado, recebe 25 e é impresso. Terminado o bloco do if, o x local ao bloco do if não é mais enxergado. Então, ao executarmos a última linha do cout, que está fora do if, vemos que o valor de  x impresso é 15.
Logo, a resposta correta é 25 e 15
	
	
	
	 
		
	
		3.
		Caso uma estrutura homogênea (vetor) seja passada como parâmetro para uma função, então:
	
	
	
	Essa passagem é "por valor"
	
	
	Essa passagem é "por referência"
	
	
	Todos os valores contidos no vetor são copiados para a função
	
	
	Haverá um erro de compilação, pois vetores não podem ser parâmetros de funções
	
	
	Essa passagem pode ser "por valor" ou "por referência"
	
Explicação:
Quando o vetor é um parâmetro de uma função ele é sempre passado por referência, não havendo outra possibilidade. Não ocorrerá erro, se o vetor for devidamente passado para a função.
	
	
	
	 
		
	
		4.
		Funções são semelhantes aos procedimentos, exceto que uma função sempre retorna um valor. Um exemplo de função seria o conjunto de instruções para calcular o fatorial de um número e após a função ser executada, ela deve retornar o fatorial do número pedido. Marque a opção que representa um protótipo de função válido.
	
	
	
	retorno nomeFuncao(parametros);
	
	
	tipo parametros(int a, int b);
	
	
	tipo parametros(parametros);
	
	
	nome tipo(parametros);
	
	
	void float(int a, int b);
	
Explicação:
Por definição, o protótipo de uma função é formado da seguinte forma :
   nome_da_função ( );
	
	
	
	 
		
	
		5.
		Considere a função a seguir e a chamada da mesma efetuada no programa principal abaixo. Indique a opção que contem o que será impresso.
int executar (int x, int &y) {
    x = y * 2;
    y = ++x;
    return x + y;
}
int main () {
int a=2, b=2, c=2;
c = executar (a, b);
cout << a << ", " << b << ", " << c;
}
	
	
	
	3, 5, 8
	
	
	2, 2, 9
	
	
	3, 2, 8
	
	
	2, 5, 10
	
	
	4, 5, 9
	
Explicação:
Fazendo um teste de mesa, temos o seguinte : 
A execução começa pela main. 
As variáveis a, b e c são iniciadas com 2.
Chama-se a função executar e são passados os valores de a e b, ou seja, 2 e 2.
Ao iniciar a execução da função executar temos que x é passado por valor e y por referência. Iniciando a função temos :
Em x = y * 2;   Daí :  x  recebe 2 * 2, que dá 4
Em y = ++x;     Daí : x é incrementado para 5 e depois y recebe 5.
Então, a soma de x + y é retornado. Ou seja, 10 é retornado.
Mas como y é passado por referência, a variável b na chamada da função foi alterada para 5.  Nada, no entanto, ocorreu com a na chamada da função, pois x foi passado por valor.
Ao voltar para main, será impresso  2, 5, 10
Portanto, qualquer outra opção é totalmente inviável.
 
 
	
	
	
	 
		
	
		6.
		Informe qual deverá ser a saída do programa abaixo:
#include 
void func(int *x)
{
 do{
 cout << *x << " ";
 (*x)--;
 }while(*x>0);
}
main()
{
 int x=5;
 func(&x);
 cout << x;
 system("pause");
}
	
	
	
	5 4 3 2 1 5
	
	
	5 4 3 2 1 0
	
	
	5 4 3 2 1 6
	
	
	5 3 4 2 1 4
	
	
	5 3 4 2 1 0
	
	
	
	 
		
	
		7.
		Sobre funções, é correto afirmar:
	
	
	
	Não devem conter variáveis locais em seu código.
	
	
	Obrigatoriamente devem retornam algum valor.
	
	
	São blocos de instruções que são executados quando são chamadas em alguma parte do programa.
	
	
	Não podem ser chamadas dentro de outras funções.
	
	
	Obrigatoriamente devem possuir parâmetros.
	
Explicação:
Uma função é um bloco de instruções que pode ser chamada a partir de outra função, que pode ter ou não parâmetros, que pode ou não retornar valor, que pode ter ou não variáveis locais.
	
	
	
	 
		
	
		8.
		Considere o trecho de um programa escrito em C++ : 
int func1 (long num) {
    int n, na=1;
    while (num / 10 != 0){
          na += 1;
          num /= 10;
    }
    return na;
}
main() {
     cout << func1 (132041);
}
Marque a opção correta que mostra o que é impresso na tela.
	
	
	
	2
	
	
	4
	
	
	1
	
	
	3
	
	
	6
		1.
		Assinale a opção certa.
 Quando não se escreve o protótipo de uma função ...
	
	
	
	O programa não funcionará de forma alguma.
	
	
	A chamada da função não poderá ser feita em qualquer hipótese.
	
	
	É preciso definir a função antes do programa principal.A definição da função deverá ser escrita, obrigatoriamente, após o programa principal.
	
	
	A chamada da função poderá ser feita em qualquer hipótese.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		2.
		Considere o trecho de um programa escrito em C++ : 
int func1 (int n1, int n2) {
    int soma=0;
    for (    ; n1 < n2 ; n1 +=  2) {
         soma +=  n1;
     }
    return soma;
}
main() {
    cout << func1(1.20);
}
Marque a opção correta que mostra o que é impresso na tela.
	
	
	
	90
	
	
	102
	
	
	104
	
	
	80
	
	
	100
	
Explicação:
int func1 (int n1, int n2) {
    int soma=0;
    for (    ; n1 < n2 ; n1 +=  2) {
         soma +=  n1;
     }
    return soma;
}
main() {
    cout << func1(1,20);
}
Fazendo passo a passo :
	n1
	n2
	soma
	1
	20
	0
	3
	 
	1
	5
	 
	4
	7
	 
	9
	9
	 
	16
	11
	 
	25
	13
	 
	36
	15
	 
	49
	17
	 
	64
	19
	 
	81
	21 ... Teste dará falso
	 
	100
Retorna o valor 100 que é impresso na main.
	
	
	
	 
		
	
		3.
		Blocos únicos de códigos que realizam diversas tarefas distintas são de difícil manutenção. Portanto, utiliza-se a técnica da modularização de programas, a fim de facilitar a implementação e a manutenção dos programas. Esta técnica tem como principal elemento:
	
	
	
	As funções
	
	
	As Filas
	
	
	Os Grafos
	
	
	Os Vetores
	
	
	As Estruturas de Dados
	
	
	
	 
		
	
		4.
		Considere as seguintes afirmativas :
I) Os vetores em C++, quando passados como parâmetros de funções,  são obrigatoriamente passados "por valor" e não "por referência".
II) Variáveis globais são um recurso adequado para troca de informações entre funções distintas.
III) Caso uma função necessite retornar mais de um valor ao programa que a chamou, deve fazê-lo usando parâmetros passados "por valor".
As afirmativas corretas são:
	
	
	
	Apenas II
	
	
	Apenas I
	
	
	Apenas I e II
	
	
	Nenhuma está correta
	
	
	Apenas III
	
Explicação:
Analisando cada afirmativa ...
I .   Falso. Em C++ os vetores passados como parâmetros são sempre passados por referência.
II.  FAlso. Variáveis globais são uma péssima forma de usar recursos, comprometendo principalmente a manutenção do programa.
III.  FAlso.  A função poderá retornar explicitamente um valor com return, mas terá que passar o outro parâmetro por referência e não por valor. Outra forma, será passar todos os parâmetros por referência.
Portanto, não opção correta.
	
	
	
	 
		
	
		5.
		Para compararmos vetores de char, usaremos a função _____________________ . Para copiarmos o conteúdo de um vetor de char nas posições ocupadas por outro vetor de char, usaremos a função ______________________ .
	
	
	
	strcat(); e strcpy() ;
	
	
	strcmp(); e strcmpi ();
	
	
	strcmp(); e strcat();
	
	
	strcmp(); e strcpy();
	
	
	strcmp(); e strlen() ;
	
Explicação:
Nâo há outra possíbilidade de resposta.  Em cstring estão declaradas as funções da opção correta, que fazem exatamente o que foi mencionado no enunciado.
Ainda a saber :   strcat concatena e strlen conta o número de caracteres
	
	
	
	 
		
	
		6.
		Considere os trechos abaixo:
int valor = 100;
void eureka (int &z)   {
    int temp = 25;
     z--;
     temp = temp - 10;
     valor = valor - temp;
     cout << "Auxiliar = " << temp << endl;
}
int main()  {
     int R = 1000;
     eureka(R);
     cout << "Result = " <<  R << "  Valor  = " << valor << endl;
}
Assinale a opção correta.
	
	
	
	Será impresso
Auxiliar = 15
Result = 999  Valor = 85
sendo que z é um  parâmetro passado por referência
 
 
	
	
	Será impresso
Auxiliar = 15
Result = 1000  Valor = 100
sendo que z é um  parâmetro passado por referência
 
 
	
	
	Será impresso 
Auxiliar = 15 
Result = 1000 Valor = 85 
sendo que z é um parâmetro passado por referência 
	
	
	Será impresso
Auxiliar = 15
Result = 999  Valor = 85
sendo que z é um  parâmetro passado por valor
 
 
	
	
	Será impresso
Auxiliar = 15
Result = 1000  Valor = 85
sendo que z é um  parâmetro passado por valor
 
 
	
Explicação:
Questão objetiva. Só é possível ser marcada a opção indicada no gabarito.
Vejamos a análise passo a passo do trecho de código....
int valor = 100;
void eureka (int &z)   {
    int temp = 25;
     z--;
     temp = temp - 10;
     valor = valor - temp;
     cout << "Auxiliar = " << temp << endl;
}
int main()  {
     int R = 1000;
     eureka(R);
     cout << "Result = " <<  R << "  Valor  = " << valor << endl;
}
Passo a passo ....
Temos que valor recebeu 100 e valor é uma variável global.
Começando a execução pela main, temos que eureka é chamada e o valor 1000 é passado.
Iniciando a execução de eureka temos que :
    temp (local à eureka) recebe o valor 25, depois o valor 1000 passado é decrementado para 999, temp recebe 15, valor recebe 100-15, que dá 85. Daí, o valor de temp é impresso, sendo mostrado na tela :     Auxiliar = 15.  DAí, a função termina e volta-se para a main.  Lá na main, após a chamada da eureka, temos a seguinte impressão :
    Result = 999   Valor = 85
Note que para R valer 999 só foi possível porque z é um parâmetro passado por referência.
	
	
	
	 
		
	
		7.
		  Assinale a opção CORRETA.  O protótipo da função que permitirá calcular o volume de um paralelepípedo com medidas a, b e c  de acordo com o trecho da  chamada  :     cout << "Volume  =   "  <<  volume(a,b,c);
	
	
	
	float volume (float, float);
	
	
	float volume (float ; float ; float);
	
	
	void volume (float , float);
	
	
	void volume (float, float, float &);
	
	
	float  volume (float, float, float);
	
Explicação:
Resposta única.
Pela chamada da função
cout << "Volume  =   "  <<  volume(a,b,c);
temos que a função retorna um valor, que pelo enunciado, vemos que é do tipo float. Há ainda os valores de a, b e c que são medidas de uma figura geométrica. Logo, a, b e c são do tipo float.
Como protótipo é uma declaração temos :
tipo de retorno da função seguido do seu nome seguido de parênteses e dentro dos parênteses, temos os tipos das variáveis que estavam na chamada da função.
Logo :   float volume(float, float, float);  
Note a vírgula para separar os tipos e o ponto  e vírgula ao final.
 
	
	
	
	 
		
	
		8.
		Assinale a alternativa que apresenta duas formas de passagem de parâmetros para uma rotina ou função:
	
	
	
	Por inferência e por valor.
	
	
	Por memória e por disco.
	
	
	Por teste e por reforço.
	
	
	Por reforço e por referência.
	
	
	Por valor e por referência
 Aula 3 
	
	 
		
	
		1.
		Qual das seguintes estruturas de dados é classificada como heterogênea?
	
	
	
	Registro
	
	
	Pilha
	
	
	Loop
	
	
	Vetor
	
	
	Fila
	
Explicação:
Registro permite agregar dados de tipos diferentes.
Vetor permite agregar dados do mesmo tipo.
Pilha e fila implementadas com vetor ou lista encadeada.
Loop : termo genérico para repetições.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		2.
		Marque a afirmativa correta para a "Inserção em lista linear sequencial ordenada".
	
	
	
	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.
	
	
	Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos.
	
	
	É 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.
	
Explicação:
Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos. 
Só pode ocorrer, no entanto, se a lista não estiver cheia.
	
	
	
	 
		
	
		3.
		Em C++, quando uma variável é declarada como uma struct, o acesso para atribuição e leitura dos membros (campos) deste registro sedá pelo operador :
	
	
	
	, (vírgula).
	
	
	& (e comercial ou eitza).
	
	
	-> (seta).
	
	
	∙ (ponto).
	
	
	* (asterisco).
	
Explicação:
Por definição, o operador que permite acessar os campos de uma variável struct é o ponto (.).
 
	
	
	
	 
		
	
		4.
		Os métodos de ordenação são muito utilizados em estruturas de dados para facilitar a busca e a recuperação posterior de itens de conjuntos ordenados. Existem vários métodos de ordenação, por este motivo, marque corretamente a alternativa que apresenta o código do método de seleção.
	
	
	
	int ordena(float v[], float valor, int n) {
 int ini = 0, fim = n-1, meio;
   while (ini >= fim){
     meio = ini/2;
     if (v[meio] == valor)
       return meio;  
     if (valor < v[meio])
       fim = meio -1;
     else
       ini = meio+1;
}
	
	
	int ordena(float v[], float valor, int n) { 
     int ini = 0, fim = n -1, meio; 
    while (ini <= fim){ 
        meio = (ini + fim)/2; 
        if (v[meio] == valor) 
              return meio; 
        if (valor < v[meio]) 
             fim = meio -1; 
        else 
             ini = meio+1; 
    } 
    return -1; 
}
	
	
	void ordena (int v[], int n){ 
       int i, j, aux; 
       for (j = 1; j < n; j++) 
           for (i=j; i > 0 && v[i-1]> v[i]; i--){ 
              aux = v[i-1]; 
              v[i-1] = v[i]; 
              v[i] = aux; 
            } 
}
	
	
	int ordena(float v[], float valor, int n){
   for (int i = 0; i < n; i++)
     if (v[i] == valor)
       return i;
   return -1;
}
	
	
	void ordena(int v[], int n){ 
int i, j, menor, aux; 
for (j = 0; j < n-1; j++) { 
    for (i = j+1; i < n; i++) { 
         if (v[i] < v[j]) { 
             aux = v[j]; 
             v[j] = v[i]; 
             v[i] = aux; 
        } 
    } 
} 
}
	
Explicação:
Na ordenação por seleção, a idéia é sempre procurar o menor elemento do vetor e inseri-lo no início do vetor. Procuramos o menor valor do vetor e colocamos ele em vetor.
Procuramos o menor valor do vetor excluindo o já colocado e colocamos ele em vetor. E assim vamos indo até termos todo o vetor ordenado.
Partindo sempre a partir do último elemento reordenado (a partir do i), o programa procura o menor elemento no vetor e o substitue pelo elemento i atual.
É o que está ocorrendo na primeira opção!
	
	Gabarito
Coment.
	
	
	
	 
		
	
		5.
		o programa de computador necessita preencher uma lista de alunos (nome e nota) até que a lista esteja cheia. Sabe-se que a lista tem capacidade para 25 alunos. Utilizando agregados heterogêneos, qual o trecho de código que exibe a melhor forma de solucionar este problema?
	
	
	
	for (int i = 0; i < 25; i++) { cin >> lista->nome; cin >> lista->nota; }
	
	
	for (int i = 0; i < 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	
	
	int i = 0; while( i < 25) { cin >> lista[i].nome; cin >> lista[i].cargo; i ++; }
	
	
	for (int i = 0; i <= 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	
	
	for (int i = 0; i < 25; i++) { cin >> lista[i]->nome; cin >> lista[i]->nota; }
	
Explicação:
Analisando cada item :
	for (int i = 0; i <= 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	>> Falso.  Veja que se há 25 itens, os índices começarão de 0 e irao até 24  e não 25.
 
	for (int i = 0; i < 25; i++) { cin >> lista[i]->nome; cin >> lista[i]->nota; }
	 
	>> Falso.  Para acessar o campo de struct é ponto e não seta.  lista[i] é uma struct e não um ponteiro.
 
	for (int i = 0; i < 25; i++) { cin >> lista->nome; cin >> lista->nota; }
	 
	 >> Falso. Para acessar o campo de struct é ponto e não seta.  lista é um vetor e lista[i] é um componente de lista.  Usamos o operador seta quando temos ponteiro para struct.
 
	for (int i = 0; i < 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	
	>> Verdadeiro.
 
	int i = 0; while( i < 25) { cin >> lista[i].nome; cin >> lista[i].cargo; i ++; }
 
>> Falso, porque foi pedido nome e nota e não cargo.
	 
 
 
	
	
	
	 
		
	
		6.
		Pode-se definir uma estrutura heterogênea como sendo um conjunto de elementos, geralmente, agrupados sob uma lógica e associados por um nome. Esses elementos podem ser variáveis simples, matrizes ou ainda outras estruturas. Seja a definição de uma estrutura como: struct aluno { string nome; float media; }; Suponha ainda que exista um vetor desta estrutura, definido como: aluno vet [ 10]; Marque a alternativa em que é atribuída de forma correta a media 6.0 para o quarto elemento deste vetor.
	
	
	
	aluno[3].media=6.0;
	
	
	vet[3].aluno=6.0;
	
	
	vet[3].media=6.0;
	
	
	aluno[3].10=6.0;
	
	
	aluno[10]=6.0;
	
	
	
	 
		
	
		7.
		Marque a opção correta, considerando 
struct Livro { 
int codigo; 
float preco; 
} liv; 
	
	
	
	Livro->liv.codigo = 12345;
	
	
	liv.preco = 30.70;
	
	
	Livro.liv.codigo = 12345;
	
	
	Livro.codigo = 12345;
	
	
	liv->preco = 30.70;
	
	
	
	 
		
	
		8.
		Pode-se definir uma estrutura heterogênea como sendo um conjunto de elementos, geralmente, agrupados sob uma lógica e associados por um nome.
Esses elementos podem ser variáveis simples, matrizes ou ainda outras estruturas. Seja a definição de uma estrutura como:
struct aluno {
string nome;
float nota;
};
Suponha ainda que exista um vetor desta estrutura, definido como:
aluno vet [100];
Marque a alternativa em que é atribuída de forma correta a nota 5.7 para o décimo primeiro elemento deste vetor.
	
	
	
	aluno.vet[10].nota=5.7;
	
	
	vet[10]=aluno.5.7;
	
	
	vet[10].aluno.nota=5.7 ;
	
	
	aluno.vet[10]=5.7;
		1.
		Dadas as afirmativas abaixo, identifique as corretas e marque a alternativa verdadeira.
I- Vetores e matrizes servem apenas para construir agregados de dados heterogêneos.
II- Registros em C++ são tipos de dados compostos formados por mais de um tipo  de dados.
III- Na Linguagem C++, "struct" é uma palavra reservada que serve para definir registros.
IV- Registros são tipos de dados heterogêneos.
	
	
	
	estão corretas apenas as afirmativas II, III e IV.
	
	
	todas as afirmativas estão corretas.
	
	
	estão corretas apenas as afirmativas I, II e III.
	
	
	estão corretas apenas as afirmativas I, II e IV.
	
	
	estão corretas apenas as afirmativas I, III e IV.
	
Explicação:
Analisando as afirmativas, temos :
Afirmativa I :  Falso.  Vetores e matrizes são agregados homogêneos.
Afirmativas II, III e IV : Estão corretas. Basicamente, structs são agregados heterogêneos.
Logo, a opção correta é estão corretas apenas as afirmativas II, III e IV.
	
	
	
	 
		
	
		2.
		Com relação à struct,  é correto afirmar que :
	
	
	
	Cada elemento da struct é chamado campo e cada campo deve ser, obrigatoriamente, de um tipo de dados distinto de outro campo.
	
	
	Cada elemento da struct  é chamado componente.
	
	
	Cada elemento da struct é denominado membro ou campo, sendo que a struct pode armazenar elementos de tipos diferentes ou não.
	
	
	A struct é sempre definida dentro da main.
	
	
	Não é possível criar um vetor de structs, pois o vetor trabalha apenas com dados do mesmo tipo.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		3.
		Pode-se definir uma estrutura heterogênea como sendo um conjunto de elementos, geralmente, agrupados sob uma lógica e associados por um nome.
Esses elementos podem ser variáveis simples, matrizes ou ainda outras estruturas. Seja a definição de uma estrutura como:
 
 struct  aluno {
              string nome;
              float   nota;
};
 
Suponha ainda que exista um vetor desta estrutura, definido como:
 aluno vet [ 100];
 
Marque a alternativa em que é atribuída de forma correta a nota 5.7 para o décimo primeiro elemento deste vetor.
	
	
	
	vet[10].aluno.nota=5.7 ;
	
	
	aluno.vet[10].nota=5.7;
	
	
	vet[10]=aluno.5.7;
	
	
	aluno.vet[10]=5.7;
	
	
	vet[10].nota=5.7;
	
	
	
	 
		
	
		4.
		o programa de computador necessita preencher uma lista de alunos (nome e nota) até que a lista esteja cheia. Sabe-se que a lista tem capacidadepara 25 alunos. Utilizando agregados heterogêneos, qual o trecho de código que exibe a melhor forma de solucionar este problema?
	
	
	
	for (int i = 0; i < 25; i++) { cin >> lista[i]->nome; cin >> lista[i]->nota; }
	
	
	for (int i = 0; i < 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	
	
	for (int i = 0; i <= 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	
	
	int i = 0; while( i < 25) { cin >> lista[i].nome; cin >> lista[i].cargo; i ++; }
	
	
	for (int i = 0; i < 25; i++) { cin >> lista->nome; cin >> lista->nota; }
	
Explicação:
Analisando cada item :
	for (int i = 0; i <= 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	>> Falso.  Veja que se há 25 itens, os índices começarão de 0 e irao até 24  e não 25.
 
	for (int i = 0; i < 25; i++) { cin >> lista[i]->nome; cin >> lista[i]->nota; }
	 
	>> Falso.  Para acessar o campo de struct é ponto e não seta.  lista[i] é uma struct e não um ponteiro.
 
	for (int i = 0; i < 25; i++) { cin >> lista->nome; cin >> lista->nota; }
	 
	 >> Falso. Para acessar o campo de struct é ponto e não seta.  lista é um vetor e lista[i] é um componente de lista.  Usamos o operador seta quando temos ponteiro para struct.
 
	for (int i = 0; i < 25; i++) { cin >> lista[i].nome; cin >> lista[i].nota; }
	
	>> Verdadeiro.
 
	int i = 0; while( i < 25) { cin >> lista[i].nome; cin >> lista[i].cargo; i ++; }
 
>> Falso, porque foi pedido nome e nota e não cargo.
	 
 
 
	
	
	
	 
		
	
		5.
		Pode-se definir uma estrutura heterogênea como sendo um conjunto de elementos, geralmente, agrupados sob uma lógica e associados por um nome. Esses elementos podem ser variáveis simples, matrizes ou ainda outras estruturas. Seja a definição de uma estrutura como: struct aluno { string nome; float media; }; Suponha ainda que exista um vetor desta estrutura, definido como: aluno vet [ 10]; Marque a alternativa em que é atribuída de forma correta a media 6.0 para o quarto elemento deste vetor.
	
	
	
	aluno[3].media=6.0;
	
	
	aluno[3].10=6.0;
	
	
	vet[3].media=6.0;
	
	
	vet[3].aluno=6.0;
	
	
	aluno[10]=6.0;
	
	
	
	 
		
	
		6.
		Marque a opção correta, considerando 
struct Livro { 
int codigo; 
float preco; 
} liv; 
	
	
	
	Livro.codigo = 12345;
	
	
	Livro.liv.codigo = 12345;
	
	
	Livro->liv.codigo = 12345;
	
	
	liv->preco = 30.70;
	
	
	liv.preco = 30.70;
	
	
	
	 
		
	
		7.
		Pode-se definir uma estrutura heterogênea como sendo um conjunto de elementos, geralmente, agrupados sob uma lógica e associados por um nome.
Esses elementos podem ser variáveis simples, matrizes ou ainda outras estruturas. Seja a definição de uma estrutura como:
struct aluno {
string nome;
float nota;
};
Suponha ainda que exista um vetor desta estrutura, definido como:
aluno vet [100];
Marque a alternativa em que é atribuída de forma correta a nota 5.7 para o décimo primeiro elemento deste vetor.
	
	
	
	vet[10].aluno.nota=5.7 ;
	
	
	aluno.vet[10]=5.7;
	
	
	vet[10].nota=5.7;
	
	
	aluno.vet[10].nota=5.7;
	
	
	vet[10]=aluno.5.7;
	
	
	
	 
		
	
		8.
		Os métodos de ordenação são muito utilizados em estruturas de dados para facilitar a busca e a recuperação posterior de itens de conjuntos ordenados. Existem vários métodos de ordenação, por este motivo, marque corretamente a alternativa que apresenta o código do método de seleção.
	
	
	
	void ordena(int v[], int n){ 
int i, j, menor, aux; 
for (j = 0; j < n-1; j++) { 
    for (i = j+1; i < n; i++) { 
         if (v[i] < v[j]) { 
             aux = v[j]; 
             v[j] = v[i]; 
             v[i] = aux; 
        } 
    } 
} 
}
	
	
	int ordena(float v[], float valor, int n) {
 int ini = 0, fim = n-1, meio;
   while (ini >= fim){
     meio = ini/2;
     if (v[meio] == valor)
       return meio;  
     if (valor < v[meio])
       fim = meio -1;
     else
       ini = meio+1;
}
	
	
	void ordena (int v[], int n){ 
       int i, j, aux; 
       for (j = 1; j < n; j++) 
           for (i=j; i > 0 && v[i-1]> v[i]; i--){ 
              aux = v[i-1]; 
              v[i-1] = v[i]; 
              v[i] = aux; 
            } 
}
	
	
	int ordena(float v[], float valor, int n){
   for (int i = 0; i < n; i++)
     if (v[i] == valor)
       return i;
   return -1;
}
	
	
	int ordena(float v[], float valor, int n) { 
     int ini = 0, fim = n -1, meio; 
    while (ini <= fim){ 
        meio = (ini + fim)/2; 
        if (v[meio] == valor) 
              return meio; 
        if (valor < v[meio]) 
             fim = meio -1; 
        else 
             ini = meio+1; 
    } 
    return -1; 
}
Aula 4 
		1.
		O seguinte trecho de programa abaixo representa qual tipo de estrutura de ordenação?
void ordenar(float v[], int n) // n é o no. de elementos em v
{
 int i , // índice
 aux, // auxiliar para troca
trocou = true,
fim = n - 1;
while (trocou)
{
    trocou = false; // sinaliza que é falso que trocou
     for (i = 0; i < fim; i++)
     {
       if (v[i] > v[i+1])
       {
         aux = v[i];
         v[i] = v[i+1];
         v[i+1] = aux;
         // sinaliza que é verdadeiro que trocou
         trocou = true;
        } // fim if
    } // fim for
 fim--; // decrementa o fim
} // fim while
} // fim da função
	
	
	
	Shellsort
	
	
	Quicksort
	
	
	Heapsort
	
	
	Bublesort
	
	
	Mergesort
	
	Gabarito
Coment.
	
	
	
	 
		
	
		2.
		Sabendo-se que o método de seleção também é um método de ordenação que baseia seu algoritmo em trocas entre os elementos de um vetor, se submetermos a sequencia de inteiros armazenada em um vetor inicialmente na seguinte ordem : 13, 23, 3, 8, 1. Pode-se dizer que quando o menor elemento do vetor alcançar sua posição final, a ordenação apresentada no vetor é:
	
	
	
	1,23,13,8,3
	
	
	1,23,3,8,13
	
	
	1,8,3,23,13
	
	
	1,3,23,8,13
	
	
	1,13,23,8,3
	
	Gabarito
Coment.
	
	
	
	 
		
	
		3.
		Suponha uma listagem, contendo número de inscrição e pontuação (ordenada pelo número de inscrição) dos candidatos para o cargo de Analista de Sistemas de uma grande empresa pública. São 1024 candidatos inscritos e o sistema implementado para consulta do resultado, permite busca binária ou busca sequencial pelo número de inscrição. O número máximo de comparações executadas se fosse utilizada a busca binária e se fosse utilizada busca sequencial, respectivamente, seria de:
	
	
	
	1024 e 512
	
	
	10 e 10
	
	
	10 e 1024
	
	
	9 e 10
	
	
	9 e 9
	
	Gabarito
Coment.
	
	
	
	 
		
	
		4.
		Os métodos de ordenação são muito utilizados para facilitar a recuperação posterior de itens ordenados. Existem vários métodos de ordenação, por esse motivo, assinale corretamente a alternativa que mostra o nome do método que utiliza a estratégia de ordenação por trocas de vizinhos e é considerado o método mais simples.
	
	
	
	Binária
	
	
	Inserção
	
	
	Hash
	
	
	Bolha
	
	
	Seleção
	
	Gabarito
Coment.
	
	
	
	 
		
	
		5.
		Marque a afirmativa correta para a "inserção incremental".
	
	
	
	A técnica é boa quando os dados ficam uniformemente distribuídos entre os seus compartimentos.
	
	
	É um tipo de ordenação por intercalação
	
	
	Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
	
	
	Os pivôs são escolhidos aleatoriamente.
	
	
	É um tipo de sequenciação por intercalação.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		6.
		O resultado do concurso para o cargo de uma empresa está armazenado em um vetor, que contém em cada um de seus elementos o número de inscrição, o nome e a nota obtida pelo candidato. Este vetor está ordenado pelo número de inscrição. Para realização de uma consulta que, dado um número de inscrição, apresenta o nome e nota do candidato, um programador utilizou um algoritmo de busca que realiza sucessivas divisões no vetor, comparando o número de inscrição procurado com o número de inscrição do candidato posicionado no meio do vetor. Se o candidato posicionadodo meio do vetor tiver o número de inscrição igual ao número de inscrição procurado, a busca termina com sucesso. Caso contrário, se candidato posicionado do meio do vetor tiver número de inscrição menor que o procurado, então a busca continua na metade posterior do vetor. E finalmente, se candidato posicionado do meio do vetor tiver número de inscrição maior que o procurado, a busca continua na metade anterior do vetor. O algoritmo utilizado pelo programador trata-se do método denominado busca:
	
	
	
	randômica.
	
	
	por contagem.
	
	
	por comparação.
	
	
	binária.
	
	
	linear.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		7.
		Considere a seguinte função busca escrita em linguagem C++ :
bool busca(int vetor[ ], int n, int tam)
{
    int ini=0, mid;
    while (ini <= tam)
    {
         cout << " x ";
         mid = (ini + tam)/2;
         if (vetor[mid] == n)
             return true;
         else if (n > vetor[mid])
             ini = mid+1;
         else
             tam = mid-1;
    }
    return false;
}
Qual a quantidade total de impressões da letra x nas buscas pelos números n = 4, n = 2 e n = 0 no vetor [1,2,3,4,5,6,7,8], sendo tam = 7 ?
int vetor[] = {1,2,3,4,5,6,7,8};
busca(vetor, 4, 7);
busca(vetor, 2, 7);
busca(vetor, 0, 7);
	
	
	
	9
	
	
	5
	
	
	6
	
	
	4
	
	
	8
	
Explicação:
Na 1a. execução da busca... para n = 4 temos impresso :  x
Na 2a. execução da busca ... para n = 2   temos impresso :  x    x
Na 3a. execução da busca ... para n = 0   temos impresso :  x   x   x 
Total de impressões da letra x :  6
	
	
	
	 
		
	
		8.
		Marque a afirmativa correta para a "Busca ou pesquisa binária".
	
	
	
	Consiste em adicionar um valor no vetor, mantendo a ordem existente e ajustando o total de elementos.
	
	
	É o processo pelo qual um conjunto de dados é colocado em uma ordem crescente ou decrescente.
	
	
	Consiste em adicionar um valor no vetor, alterando a ordem existente e ajustando o total de elementos.
	
	
	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.
	
	
	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.
		1.
		Nos métodos de ordenação interna, quais são aqueles classificados como tipo método simples?
	
	
	
	Insert Sort, Bubble Sort e Shell Sort
	
	
	Insert Sort, Bubble Sort e Quick Sort
	
	
	Shell Sort, Quick Sort e Heap Sort
	
	
	Selection Sort, Shell Sort e Bubble Sort
	
	
	Selection Sort, Insert Sort e Bubble Sort
	
	Gabarito
Coment.
	
	
	Gabarito
Coment.
	
	
	Gabarito
Coment.
	
	
	
	 
		
	
		2.
		Para consultarmos uma estrutura de dados, normalmente, empregamos um tipo de pesquisa de dados. O trecho de programa a seguir refere-se a uma pesquisa por um elemento único (sua primeira ocorrência), em um conjunto de elementos de dados armazenado em uma estrutura de acesso indexado e aleatório. Selecione a opção correspondente ao algoritmo utilizado, no programa, para a referida pesquisa:
int busca(float v[], float valor, int n) {
int ini = 0, fim = n -1, meio;
while (ini <= fim) {
meio = (ini + fim)/2;
if (v[meio] == valor)  return meio;
if (valor < v[meio]) fim = meio -1;
  else ini = meio+1;
}
return -1;
}
	
	
	
	pesquisa cadeias indexada
	
	
	pesquisa de cadeias
	
	
	pesquisa sequencial
	
	
	pesquisa indexada
	
	
	pesquisa binária
	
	Gabarito
Coment.
	
	
	
	 
		
	
		3.
		Seja a seguinte função de ordenação:
void ordena( int n, int v[])
{
   int i, j, x;
   for (j = 1; j < n; ++j) {
      x = v[j];
      for (i = j-1; i >= 0 && v[i] > x; --i) 
         v[i+1] = v[i];
      v[i+1] = x;
   }
}
Pode-se dizer que é uma função de ordenação:
	
	
	
	Que utiliza o método inserção e realiza uma ordenação decrescente nos elementos do vetor v.
	
	
	Que utiliza o método inserção e realiza uma ordenação crescente nos elementos do vetor v.
	
	
	Que utiliza o método seleção e realiza uma ordenação crescente nos elementos do vetor v.
	
	
	Que utiliza o método seleção e realiza uma ordenação decrescente nos elementos do vetor v.
	
	
	Que utiliza o método bolha e realiza uma ordenação crescente nos elementos do vetor v.
	
	
	
	 
		
	
		4.
		Qual a importância de se entender a "ordenação" de dados ?
	
	
	
	A ordenação é a base na qual, muitos programas são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	
	
	A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	
	
	A ordenação é a base na qual, muitos sistemas são construídos. Entendendo a ordenação, tem-se conhecimento para resolver outros problemas.
	
	
	A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se conhecimento para resolver outros problemas.
	
	
	A ordenação é a base na qual, muitos algoritmos são construídos. Entendendo a ordenação, tem-se conhecimento para manter outros problemas.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		5.
		Qual característica NÃO podemos atribuir a PESQUISA BINÁRIA.
	
	
	
	É eficiente quando se trata de listas ordenadas
	
	
	São realizadas sucessivas divisões da lista ao meio.
	
	
	A lista pode estar desordenada.
	
	
	Quando o valor pesquisado é maior do que a chave do MEIO da lista, devemos dispensar  a metade que vem antes do meio da lista.
	
	
	A lista precisa estar ordenada.
	
Explicação: Na pesquisa binária a lista obrigatoriamente deverá estar ORDENADA.
	
	
	
	 
		
	
		6.
		Caso seja empregada uma busca binária em uma lista sequencial ordenada com 2048 valores, qual seria o número máximo de comparações para encontrar um valor que esteja na lista?
	
	
	
	10
	
	
	9
	
	
	8
	
	
	11
	
	
	12
	
Explicação:
Como a busca binária sai continuamente dividindo o conjunto de dados ao meio (em duas partes), então vamos fatorar e organizar o resultado como potência de base 2.
 Fatorando 2048 temos 2 11
 Portanto, a resposta é 11.
	
	
	
	 
		
	
		7.
		O resultado do concurso para o cargo de uma empresa está armazenado em um vetor, que contém em cada um de seus elementos o nome e a nota obtida pelo candidato. Deseja-se que este vetor seja ordenado pela nota, em ordem decrescente. Sendo o vetor pequeno (poucos elementos), o programador responsável por desenvolver este algoritmo, escolheu um método de ordenação que executa os seguintes passos:
· Selecione candidato com maior nota entre todos e troque-o com o candidato que está na primeira posição do vetor;
· Selecione o segundo maior e troque-o com o candidato que está na segunda posição;
· Os passos descritos anteriormente são seguidos para a terceira nota, quarta nota e assim por diante até que reste apenas um candidato.
O algoritmo utilizado pelo programador trata-se do método de ordenação denominado:
	
	
	
	Inserção
	
	
	Heapsort
	
	
	Seleção
	
	
	Quicksort
	
	
	Bolha
	
	Gabarito
Coment.
	
	
	
	 
		
	
		8.
		Com a utilização das estruturas de dados e seus tipos, em algumas situações é imprescindível a criação de funções que façam determinada verificação ou ação nestas estruturas. Dessa forma, analise a função abaixo e marque corretamente a alternativa que descreve as funcionalidades desta.
int funcao(float v[], float vl, int n)
{
   for (int i = 0; i < n; i++)
     if (v[i] == vl)
       return i;
   return -1;
}
	
	
	
	Resulta em erro, se o valor de vl não estiver dentro de v.
	
	
	Retorna -1 se o valor de vl estiver dentro de v.
	
	
	Retorna -1 se o valor de n foi encontrado.
	
	
	Retorna a posição de v se o valor vl foi encontrado.
	
	
	Retorna o valor de vl se o valor n foi encontrado.
	
Explicação:
A função apresentada é a busca sequencial. Note que ela retorna o índice do elemento vl, quando   o valorvl é encontrado e ela retorna -1 caso o valor vl não for encontrado.
Aula 5
		1.
		Considere as seguintes afirmações sobre Listas Sequenciais:
I  - São estruturas lineares que utilizam as primeiras posições de um vetor para armazenar os dados de interesse.
II - São compostas pelo conjunto dos dados que se deseja armazenar e por uma variável inteira que indica a quantidade de dados armazenados.
III - Os dados são sempre inseridos ou removidos no final da lista, tomando-se o cuidado de atualizar a quantidade de dados da mesma.
IV - A lista pode admitir ou não admitir que haja dados repetidos (listas podem ser com ou sem repetição).
Marque a opção que contém apenas todas  as afirmações verdadeiras:
	
	
	
	I, III, IV
	
	
	I, II
	
	
	I, II, IV
	
	
	I, II, III, IV
	
	
	I, II, III
	
Explicação:
Analisando cada afirmativa :
 
I  - São estruturas lineares que utilizam as primeiras posições de um vetor para armazenar os dados de interesse.
Verdadeiro.  As inserções vão ocorrendo do início do vetor (índice zero) em direção ao fim.
II - São compostas pelo conjunto dos dados que se deseja armazenar e por uma variável inteira que indica a quantidade de dados
armazenados.
Verdadeiro. Armazenam-se os dados  e controla-se a quantidade de dados na lista.
III - Os dados são sempre inseridos ou removidos no final da lista, tomando-se o cuidado de atualizar a quantidade de dados 
da mesma.
Falso. A inserção pode ser no início,  no meio ou no final da lista. Na verdade, pode ocorrer inserção e remoção em qualquer  posição.
IV - A lista pode admitir ou não admitir que haja dados repetidos (listas podem ser com ou sem repetição).
Verdadeiro.  Uma lista pode ou não ter dados repetidos.
Resposta certa : As afirmativas I, II, IV estão certas
	
	
	
	 
		
	
		2.
		Em relação às listas sequenciais, considere as seguintes afirmações:
I - são estruturas lineares que utilizam vetores para armazenamento dos dados;
II - os componentes da lista são os dados que se deseja armazenar e um valor inteiro com a quantidade de dados da lista;
III - os dados são sempre inseridos ou removidos no final da lista, tomando-se sempre o cuidado de atualizar a quantidade de dados da lista;
IV - listas podem apresentar dados repetidos ou não admitir repetição (listas com e sem repetição).
Assinale a opção que contém apenas todas as afirmativas corretas:
	
	
	
	II, III, IV
	
	
	I, II, IV
	
	
	I, II
	
	
	I, II, III
	
	
	I, II, III, IV
	
Explicação:
Analisando cada afirmativa :
I - são estruturas lineares que utilizam vetores para armazenamento dos dados;
Verdadeira.  O vetor é sequencial e tem tamanho pré-definido.
II - os componentes da lista são os dados que se deseja armazenar e um valor inteiro com a quantidade de dados da lista;
Verdadeira.
III - os dados são sempre inseridos ou removidos no final da lista, tomando-se sempre o cuidado de atualizar a quantidade de dados da lista;
Falso, pois é possível inserirmos em qualquer posição da lista.
IV - listas podem apresentar dados repetidos ou não admitir repetição (listas com e sem repetição).
Verdadeiro.
Logo, as afirmativas I, II e IV estão corretas
	
	
	
	 
		
	
		3.
		Com relação as listas lineares sequenciais:
I - Uma lista linear sequencial é um vetor em linguagens estruturadas, também chamado de array.
II - Um elemento de uma lista linear sequencial pode ser acessado diretamente através de um índice.
III - Uma lista linear sequencial pode ter elementos de um mesmo tipo, ou de tipos diferentes.
	
	
	
	Apenas as afirmações II está corretas.
	
	
	Apenas as afirmações II e III estão corretas.
	
	
	Apenas as afirmações I e II estão corretas.
	
	
	Apenas a afirmação I está correta.
	
	
	Apenas as afirmações I e III estão corretas.
	
	Gabarito
Coment.
	
	
	
	 
		
	
		4.
		Analise a função abaixo, considerando o tipo Livro  e marque a opção correta.
int R2D2 (Livro v[ ], int c, int n)  {
for (int i = 0; i < n; i++)
    if (v[i].codigo == c)
       return i;
         return -1;
}
onde 
struct Livro  {
          int codigo;
          char autor[30];
 };
	
	
	
	Ocorre erro na função R2D2 se o valor de c não estiver sido encontrado em v.
	
	
	Retorna a posição do valor c em v , se o valor c for encontrado em v.
	
	
	Retorna -1 se o valor de c estiver em v.
	
	
	Retorna -1 se o valor de n foi encontrado.
	
	
	Retorna o valor de c se o valor n foi encontrado.
	
Explicação:
Questão objetiva. A função realiza uma busca sequencial.
A cada rodada do loop é verificado se o código de v[i] é igual ao valor de c, passado como parâmetro. Se o código estiver em v[i], então a posição i é retornada. Se o teste do if nunca tiver sucesso, então, sairemos do for sem sucesso e ao final, será retornado -1, que não pode ser índice ou posição de qualquer valor no vetor.
	
	
	
	 
		
	
		5.
		__________________________ é uma lista linear em que a alocação de memória pode ser estática, e que a forma de armazenamento é contígua ou sequencial na memória. Usamos este tipo de lista quando se tem em mente um tamanho pré-definido, ou seja, quando se sabe até onde a lista pode crescer.
	
	
	
	Lista Linear de Alocação de Memória
	
	
	Lista Linear Não Alocada
	
	
	Lista Linear Não Sequencial
	
	
	Lista Linear Sequencial
	
	
	Lista Não Linear
	
	
	
	 
		
	
		6.
		Considere uma lista com n  livros, em que cada livro é modelado pela struct :
 
struct Livro {
                            string titulo,  editora, autor;
                            float preco;
};
 
A função X abaixo
 
void X (Livro v[ ], int &n, Livro L)
{
     v[n] = L;
     n++;
    cout << "Operação realizada com sucesso.";
}
 
implementa a operação de :
	
	
	
	Substituição
	
	
	Ordenação por inserção
	
	
	Inicialização
	
	
	Inserção
	
	
	Busca
	
	Gabarito
Coment.
	
	
	
	 
		
	
		7.
		São métodos ou algoritmos conhecidos de ordenação de dados por troca:
	
	
	
	ordenação shell e hashing.
	
	
	quicksort e hashing.
	
	
	hashing e bubble sort.
	
	
	busca por ordenação e ordenação shell.
	
	
	bubble sort e quicksort.
	
Explicação:
Bubble sort é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.
 
O Quicksort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada.
 
	
	
	
	 
		
	
		8.
		Considere as seguintes afirmações: I. Só podemos ter uma matriz de no máximo duas dimensões. Exemplo: C[100][100]. II. Ao declararmos um vetor int A[10], se escrevemos A[2] acessamos o segundo elemento do vetor. III. Uma string declarada como char B[30] armazena no máximo 30 caracteres. Escolha a alternativa correta:
	
	
	
	Estão corretas apenas as afirmativas I e II.
	
	
	Estão corretas apenas as afirmativas I e III.
	
	
	Está correta apenas a afirmativa I.
	
	
	Nenhuma afirmação está correta.
	
	
	Está correta apenas a afirmativa II.
	
Explicação:
Analisando cada afirmativa :
  I. Só podemos ter uma matriz de no máximo duas dimensões. Exemplo: C[100][100].
 Falso.  Podemos ter matrizes unidimensionais, tridimensionais, etc...
 II. Ao declararmos um vetor int A[10], se escrevemos A[2] acessamos o segundo elemento do vetor.
Falso.  Em C++ o índice inicial é zero.Logo, A[2] é o elemento de índice 2, ou seja, o 3o. elemento do vetor.
III. Uma string declarada como char B[30] armazena no máximo 30 caracteres. Escolha a alternativa correta:
Falso. B pode armazenar no máximo 29 caracteres que sejam dados, pois existe uma área para o caracter nulo.
Logo, todas as opções são falsas
	
	 
		
	
		1.
		
	
	
	
	for (int i = 0; i < n; i++)
   cout << L[i].matricula << "  "  << L[i].nome << endl;
	
	
	for (int i = 0; i < n; i++)
   cout << L.matricula << "  "  << L.nome << endl;
	
	
	for (int i = 0; i < n; i++)
   cout << L.matricula[i] << "  "  << L.nome[i] << endl;
	
	
	for (int i = 0; i < n; i++)
   cout << L[i].matricula << "  "  << L[i].nome[30] << endl;
	
	
	for (int i = 0; i < n; i++)
   cout << L[i] << endl;
	
	Gabarito
Coment.
	
	
	
	 
		
	
		2.
		Estude atentamente o código a segir: 
int deciframe(int v[ ], int tam, int e){ 
int i = 0, f = tam -1, m; 
while ( i <= f ){ 
m = ( i + f ) / 2; 
if ( v[m] == e ) { return m; } 
if ( e < v[m] ) { f = m - 1; } 
else { i = m + 1; } 
} 
return -1; 
} 
Sabendo que a chamada da mesma foi feita com os parâmetros recebendo os seguintes valores, o que ela retornaria? 
v[10] = {0, 2, 4, 6, 8, 10, 20, 100} 
tam = 8 
e = -6
	
	
	
	-1
	
	
	6
	
	
	0
	
	
	3
	
	
	4
	
Explicação:
Analisando
int deciframe(int v[ ], int tam, int e)  { 
int i = 0, f = tam -1, m; 
while ( i <= f ){ 
   m = ( i + f ) / 2; 
   if ( v[m] == e ) { return m; } 
   if ( e < v[m] )
      { f = m - 1; } 
   else
      { i = m + 1; } 
} 
return -1; 
} 
Sabendo que a chamada da mesma foi feita com os parâmetros recebendo os seguintes valores, o que ela retornaria? 
v[10] = {0, 2, 4, 6, 8, 10, 20, 100} 
tam = 8 
e = -6
Está procurando pelo valor e = -6. Como se sabe pelo estudo da busca binária e olhando o código dado, temos que -6 não existe na lista então a função irá retornar -1 (vide última linha da função). SE a busca tivesse sucesso, o teste do 1o. if no while seria verdadeiro e então o índice m de v seria retornado. Mas não é o caso, pois -6 não foi encontrado.
	
	
	
	 
		
	
		3.
		Considere uma lista sequencial L com n fichas de professores, sendo que cada ficha de professor é modelada pela struct : 
struct professor { 
int matricula; 
char titulo[30]; 
}; 
e a lista L é assim declarada : professor L[n]; 
Assinale o trecho que corretamente exibe todas as matrículas e titulações de todos os n professores de L . 
	
	
	
	for (int i = 0; i < n; i++) 
cout << L.matricula << " " << L.titulo << endl;
	
	
	for (int i = 0; i < n; i++) 
cout << L[i] << endl; 
	
	
	for (int i = 0; i < n; i++)
cout << L[i].matricula << " " << L[i].titulo << endl;
	
	
	for (int i = 0; i < n; i++) 
cout << L[i].matricula << " " << L[i].titulo[30] << endl;
	
	
	for (int i = 0; i < n; i++) 
cout << L.matricula[i] << " " << L.titulo[i] << endl;
	
Explicação:
Como L é um vetor de n elementos do tipo professor. Então, para percorrer o vetor de índice i temos que fazer L[i] seguido do ponto seguido do campo, que pode ser matricula ou titulo.
Assiim, a opção correta é 
for (int i = 0; i < n; i++)
   cout << L[i].matricula << " " << L[i].titulo << endl;
	
	
	
	 
		
	
		4.
		As estruturas de dados em programação são muito utilizadas para tornar o acesso aos dados mais eficiente e organizado. A estrutura de dados considerada mais simples e tem como característica apresentar apenas uma dimensão é:
	
	
	
	Matriz
	
	
	Vetor
	
	
	Registro
	
	
	Função
	
	
	Variável
	
	Gabarito
Coment.
	
	
	
	 
		
	
		5.
		As estruturas de dados são utilizadas para manter dados ou informações organizados na memória, o que possibilita a otimização do uso destes dados. Porém, as estruturas guardam características especiais na manipulação destes dados, assim deve-se escolher a estrutura certa ou mais adequada para uma determinada aplicação. Portanto marque a opção que representa a melhor estrutura, quando se tem como requisitos principais o acesso aleatório aos dados e alocação destes de forma contínua na memória.
	
	
	
	Pilha Sequencial
	
	
	Fila Sequencial
	
	
	Lista Encadeada
	
	
	Pilha Encadeada
	
	
	Lista Sequencial
	
	Gabarito
Coment.
	
	
	
	 
		
	
		6.
		São métodos ou algoritmos conhecidos de ordenação de dados por troca:
	
	
	
	busca por ordenação e ordenação shell.
	
	
	hashing e bubble sort.
	
	
	bubble sort e quicksort.
	
	
	quicksort e hashing.
	
	
	ordenação shell e hashing.
	
Explicação:
Bubble sort é o algoritmo mais simples, mas o menos eficientes. Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.
 
O Quicksort é o algoritmo mais eficiente na ordenação por comparação. Nele se escolhe um elemento chamado de pivô, a partir disto é organizada a lista para que todos os números anteriores a ele sejam menores que ele, e todos os números posteriores a ele sejam maiores que ele. Ao final desse processo o número pivô já está em sua posição final. Os dois grupos desordenados recursivamente sofreram o mesmo processo até que a lista esteja ordenada.
 
	
	
	
	 
		
	
		7.
		Considere as seguintes afirmações: I. Só podemos ter uma matriz de no máximo duas dimensões. Exemplo: C[100][100]. II. Ao declararmos um vetor int A[10], se escrevemos A[2] acessamos o segundo elemento do vetor. III. Uma string declarada como char B[30] armazena no máximo 30 caracteres. Escolha a alternativa correta:
	
	
	
	Nenhuma afirmação está correta.
	
	
	Está correta apenas a afirmativa I.
	
	
	Está correta apenas a afirmativa II.
	
	
	Estão corretas apenas as afirmativas I e III.
	
	
	Estão corretas apenas as afirmativas I e II.
	
Explicação:
Analisando cada afirmativa :
  I. Só podemos ter uma matriz de no máximo duas dimensões. Exemplo: C[100][100].
 Falso.  Podemos ter matrizes unidimensionais, tridimensionais, etc...
 II. Ao declararmos um vetor int A[10], se escrevemos A[2] acessamos o segundo elemento do vetor.
Falso.  Em C++ o índice inicial é zero. Logo, A[2] é o elemento de índice 2, ou seja, o 3o. elemento do vetor.
III. Uma string declarada como char B[30] armazena no máximo 30 caracteres. Escolha a alternativa correta:
Falso. B pode armazenar no máximo 29 caracteres que sejam dados, pois existe uma área para o caracter nulo.
Logo, todas as opções são falsas.