Estrutura de dados 2014.2 AV

Prévia do material em texto

Avaliação: ESTRUTURA DE DADOS 
Tipo de Avaliação: AV 
Aluno: 
Professor: ALEXANDRE SOARES ALVES Turma: 9001/AA 
Nota da Prova: 6,0 Nota de Partic.: 2 Data: 01/09/2014 17:10:42 
 
 
1a Questão (Ref.: 201102427689) Pontos:0,5 / 1,5 
const int TAMMAX = 100; 
struct TipoLista{ 
int qtde; // descritor que representa a quantidade de elementos na lista 
int elemt[TAMMAX]; 
}; 
Fundamento no tipo de dado(registro) acima que representa uma implementação de uma lista linear sequencial. 
Construa um procedimento para adicionar um dado no final da lista. 
A lista e o dado serão passados por parâmetro. Usar o mecanismo de passagem por referência se for 
necessário. 
 
 
Resposta: void addFinalLista ( TipoLista &Lista, int dado){ if ( lista.qtde == TAM [MAX] { cout << "LISTA 
CHEIA";} else { lista elemt []lista.qtde} = dado; lista.qtde++; cout << "dado adicionado com sucesso"; }} 
 
 
Gabarito: 
void addFinalLista ( TipoLista &lista, int dado ){ 
if(lista.qtde == TAMMAX){cout << "Lista Cheia."; } 
else{ lista.elemt[lista.qtde] = dado; 
lista.qtde++; 
cout << "Dado adicionado com sucesso."; 
} } 
 
 
 
2a Questão (Ref.: 201102434765) Pontos:1,5 / 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: no *inverter ( no * ini) // ini é um ponteiro para o inicio da lista { no *a, *b, *c; a = ini;b b = NULL 
WHILE ( A!= NULL ) { c = b; b = a; a = a -> link; b -> link = c; } b; return (ini); } // *fim da função*/ 
 
 
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.: 201102406248) Pontos:0,5 / 0,5 
Podemos dizer que estrutura de dados é: 
 
 
Uma sequência de passos computacionais que transforma uma entrada em uma saída previamente 
determinada. 
 
É a saída, que satisfaz a quaisquer restrições impostas pelo problema, necessária para se calcular uma 
solução do problema. 
 
O meio para armazenar e organizar dados com o objetivo de facilitar o acesso e as modificações. 
 
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. 
 
 
 
4a Questão (Ref.: 201102406086) Pontos:0,5 / 0,5 
O que acontece ao se inserir uma informação quando já usamos toda a área disponível do vetor (topo = fim)? 
 
 
ordenação 
 
inclusão 
 
overflow 
 
underflow 
 
remoção 
 
 
 
5a Questão (Ref.: 201102406112) Pontos:0,5 / 0,5 
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 
 
 
Heapsort 
 
Shellsort 
 
Mergesort 
 
Bublesort 
 
Quicksort 
 
 
 
6a Questão (Ref.: 201102473739) Pontos:0,5 / 0,5 
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). 
 
 
I, II e III. 
 
I, III, IV e V. 
 
I, III e V. 
 
II, IV e V. 
 
II, III, IV e V. 
 
 
 
7a Questão (Ref.: 201102473734) Pontos:0,5 / 0,5 
Quando as inserções e as remoções ocorrem sempre no mesmo lado da lista, trata-se de uma estrutura de 
dados denominada. 
 
 
Vetor. 
 
Lista encadeada. 
 
Fila. 
 
Lista circular. 
 
Pilha. 
 
 
 
8a Questão (Ref.: 201102608885) Pontos:0,5 / 0,5 
As pilhas sequenciais são estruturas que guardam a ordem reversa dos dados nelas armazenados, e isto em 
muitas ocasiões é muito vantajoso. A operação usada para inserir um elemento X numa pilha é conhecida 
na literatura como PUSH (X). Para remover um elemento de uma pilha a operação é o POP( ). Assim estas 
duas funções devem implentar o algoritmo LIFO (Last In - First Out ) ou o último a entrar é o primeiro a 
sair. Sendo assim se aplicarmos as seguintes operações em uma PILHA vazia: 
PUSH(10),PUSH(5),POP(),PUSH(7),POP(),PUSH(2),POP(),POP( ). 
Quais valores restarão na pilha? 
 
 
10 e 2 
 
7 e 2 
 
Apenas o 10 
 
Nenhum, a pilha estará vazia. 
 
Apenas o 2 
 
 
 
9a Questão (Ref.: 201102608887) Pontos:1,0 / 1,0 
As filas sequenciais são estruturas de dados utilizadas em diversas aplicações, tais como fila de processo, 
fila de impressão, sistemas de senha etc. Entretanto, nas aplicações onde há muita movimentação de 
dados, inserções e remoções de dados na fila, surgem espaços ociosos que podem levar ao fenômeno 
chamado de esgotamento de memória. Para sanar este problema pode-se substituir a fila sequencial 
por: 
 
 
lista sequencial 
 
lista circular 
 
fila circular 
 
pilha sequencial 
 
pilha circular 
 
 
 
10a Questão (Ref.: 201102406068) Pontos:0,0 / 1,0 
Um apontador é uma variável que contém o endereço de outra variável. Apontadores são muito usados, em 
parte porque são, às vezes, a única forma de se expressar um processo de computação e, em parte, porque, 
normalmente, implicam um código mais compacto e eficiente que o obtido de outras formas. Considerando o 
uso de apontadores nas linguagens procedurais atuais, julgue os itens que se seguem com E se for errado e C 
se for certo. 
( ) O uso de apontadores como argumentos de funções que realizem chamada por valor não permite alteração 
de seus conteúdos de memória na função. 
( ) Com apontadores, é possível criar funções que retornem estruturas de dados complexas. 
( ) Para recuperar o valor da variável apontada, basta que o apontador seja atribuído a uma variável de mesmo 
tipo. 
( ) Arranjos de apontadores podem ser usados em funções que recebam como argumentos um número variável 
de cadeias de caracteres. 
( ) Em geral, para que um arranjo seja percorrido por um ponteiro, para cada elemento do arranjo deve-se 
adicionarao ponteiro o número de bytes que o elemento ocupa em memória. 
 
 
d) E - C - E - C - C 
 
c) E - E - C - C - E 
 
b) C - C - E - E - E 
 
e) C - E - C - E - C 
 
a) E - C - E - C - E