Avaliação Parcial - Estrutura de Dados

Prévia do material em texto

# ESTRUTURA DE DADOS # 
 
01. Podemos dizer que estrutura de dados é: 
R.: O meio para armazenar e organizar dados com o objetivo de facilitar o acesso e 
as modificações. 
02. 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. 
R.: I, III, IV e VI são afirmativas verdadeiras. 
03. Considere a seguinte função: void dobro(int x) { x = 2 * x; } Qual valor será 
impresso na tela quando o seguinte programa principal for executado? int 
main() { int n = 3; n = n + 2; dobro(n); cout << n; return 0; } 
R.: 5 
04. Considera a FUNÇÃO abaixo: 
void inverte(int &x, int &y) 
{ int aux = x; 
x = y; 
y = aux; } 
Quais valores serão impressos na tela quando o seguinte programa principal for 
executado? 
int main() 
{ int a = 18, b = 28; 
inverte(a, b); 
cout << a <<" e "<< b; 
return 0; } 
 R.: 28 e 18 
05. Marque a afirmativa correta para a "Inserção em lista linear sequencial 
ordenada". 
R.: Consiste em adicionar um valor no vetor, mantendo a ordem existente e 
ajustando o total de elementos. 
06. 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. 
R.: estão corretas apenas as afirmativas II, III e IV. 
07. 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: 
R.: Seleção 
08. Considere as afirmativas a seguir. 
I. Uma forma muito simples de fazer uma busca em um vetor consiste em 
percorrer o vetor, elemento a elemento, para verificar se o elemento 
procurado é igual a um dos elementos do vetor. 
II. A pesquisa sequencial é extremamente simples e eficiente quando o número de 
elementos do vetor for muito grande. 
III. Na pesquisa binária, a cada interação do algoritmo o tamanho do vetor é 
dividido ao meio. 
IV. A pesquisa binária funciona corretamente quanto o conjunto de dados estiver 
desordenado. 
Assinale a alternativa correta. 
R.: Somente as afirmativas I e III são corretas. 
09. Estude atentamente o código a seguir: 
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 
R.: -1 
 
R.: for (int i = 0; i < n; i++) 
 cout << L[i].matricula << " " << L[i].nome << endl; 
10. Sobre estrutura de dados, identifique o que está correto afirmar. 
I. Pilha é uma estrutura de dados com acesso restrito aos seus elementos, uma 
vez que eles são colocados e retirados por um único lado e são ordenados 
pelo princípio LIFO (last in first out). Assim, sempre que um elemento é 
adicionado ou retirado seu topo é alterado. 
II. Pilha é o tipo de estrutura usada, por exemplo, na avaliação de expressões 
numéricas, na recursividade e pelos compiladores, na passagem de 
parâmetros para as funções. 
III. Registro é uma estrutura básica que permite guardar coleções de dados de 
diferentes tipos, sendo normalmente utilizado quando um objeto tem 
diferentes atributos, isto é, contém campos de diferentes tipos. 
IV. Lista pode conter um número qualquer de elementos, expandindo-se ou 
contraindo-se conforme o elementos são inseridos ou retirados. Nesse tipo 
de estrutura, os acessos tanto podem ser feitos sequencialmente como 
diretamente. 
V. Fila, assim como a pilha , é uma versão especial de lista, e como tal, seus 
elementos são ordenados pelo princípio LIFO (last in first out). 
R.: I, II e III. 
 11. Estão entre algumas das possíveis formas de estruturas de dados: 
 R.: Árvores binárias, pilhas, vetores 
12. 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. 
R.: retorno nomeFuncao(parametros); 
13. Em C++, quando uma variável é declarada como uma struct, o acesso para 
atribuição e leitura dos membros (campos) deste registro se dá pelo operador: 
R.: ∙ (ponto). 
14. Entre os diversos algoritmos de pesquisa existentes, certamente os mais 
famosos são os da pesquisa sequencial e o da pesquisa binária. A busca ou pesquisa 
sequencial pode ser aplicada em vetores independente destes estarem ordenados, 
entretanto a busca binária só se aplica em vetores ordenados. 
Seja o vetor A= {10,35,41,55,69,70,98}, suponha que o número 70 foi pesquisado 
pelo algoritmo da busca sequencial e também pelo algoritmo da busca binária, 
ambos algoritmos realizam testes nos elementos do vetor até achar o que procuram 
ou definirem que o elemento não se encontra no vetor. Sendo assim marque a 
alternativa que expressa o número de testes realizados pela busca sequencial e o 
número de testes realizados pela busca binária, respectivamente, até encontrarem o 
70. 
R.: 6 e 2 
15. Estude atentamente o código a seguir: 
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 
R.: 0 
16. São métodos ou algoritmos conhecidos de ordenação de dados por troca: 
R.: bubble sort e quicksort 
17. Com relação as listas lineares sequenciais: 
I. Uma lista linear sequencial é um vetor em linguagens estruturadas, também 
chamado de array. 
II. II - Um elemento de uma lista linear sequencial pode ser acessado diretamente 
através de um índice. 
III. III - Uma lista linear sequencial pode ter elementos de um mesmo tipo, ou de 
tipos diferentes. 
R.: Apenas as afirmações I e II estão corretas. 
18. Assinale a alternativa correta sobre tipos abstratos de dados: 
R.: Um tipo abstrato de dados é composto por ummodelo de dados e um conjunto de 
operadores definidos sobre esses dados. 
19. A que estrutura pertence a definição: " Uma estrutura não linear que é um 
conjunto de nós e suas conexões entre eles e não há limitação de vértices. Muito 
utilizada para representação de percursos em mapas." 
R.: grafos 
20. Na passagem por ____________________ , o endereço da variável da função 
chamadora é passado para a função chamada e, dessa forma, o valor poderá ser 
alterado, ou não. 
R.: referência 
21. #include < iostream > 
 using namespace std; 
void SOMA(float a, int b) { 
 float result = a+b; 
 cout << "A soma de " << a << " com " << b << " é: " << result; 
} 
int main() 
{ 
int a; 
float b; 
a = 10; b = 12.3; 
SOMA(b,a); 
} 
A função SOMA acima possui as seguintes características: 
R.: Não retorna valor e possui parâmetros. 
22. 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. 
R.: vet[10].nota=5.7; 
23. 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. 
R.: 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; 
 } 
 } 
} 
} 
24. O código a seguir representa a implementação do algoritmo de ordenação por 
Bolha ( Bubble Sort). Da forma que está implementado executa uma ordenação em 
ordem crescente num vetor. Marque a alternativa que representa a alteração no 
código, de modo que o mesmo passe a realizar ordenação em ordem decrescente. 
void bolha(int vet[], int tam) 
{ 
int j,i, aux; 
for (i=0; i<tam -1; i++) 
for(j=tam-1; j>i; j--) 
if(vet[j] < vet[j-1] ) 
{ 
aux=vet[j]; 
vet[j]= vet[j-1]; 
vet[j-1]=aux; 
} 
} 
R.: if(vet[j-1] < vet[j] ) 
{ 
aux=vet[j]; 
vet[j]= vet[j-1]; 
vet[j-1]=aux; 
} 
25. Sabendo-se que o método de ordenção bolha ou bubble sort realiza a troca de 
elementos adjacentes até que todos os elementos de um vetor esteja ordenado. 
Então, se submetermos a sequencia de inteiros armazenada em um vetor 
inicialmente na seguinte ordem : 4, 2, 5, 1. 
Pode-se dizer que quando o maior elemento do vetor alcançar sua posição final, a 
ordenação apresentada no vetor é: 
R.: 2,4,1,5 
26. 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]; 
 }; 
R.: Retorna a posição do valor c em v , se o valor c for encontrado em v. 
27. __________________________ é 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. 
R.: Lista Linear Sequencial