Estrutura de Dados AV 11-2014

Prévia do material em texto

Período de não visualização da prova: desde 06/11/2014 até 25/11/2014. 
 
 
 
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 
 
Seleção 
 Bolha 
 
Inserção 
 
Hash 
 
 
 2a Questão (Ref.: 201107307583) Pontos: 0,0 / 0,5 
Um programador recebeu a tarefa de construir um programa que receba uma cadeia de caracteres e verifique 
se esta cadeia de caracteres é um PALÍNDROME, sabendo-se que um PALÍNDROME apresenta a mesma 
sequência de caracteres da esquerda pra direita, quanto da direita para esquerda, marque a opção que possui a 
estrutura de dados mais adequada a este programa. 
 
 
 
Grafos 
 
Árvores 
 Pilha Sequencial 
 Lista Sequencial 
 
Fila Sequencial 
 
 
 3a Questão (Ref.: 201107290684) Pontos: 0,5 / 0,5 
 
 Navegadores para internet armazenam os últimos endereços visitados em uma estrutura de 
dados. Cada vez que um novo site é visitado, o endereço do site é adicionado na estrutura de 
endereços. Quando se aciona o retorno ("back"), o navegador permite que o usuário retorne no 
último site visitado e retira o endereço do site da estrutura de dados. 
Assinale a estrutura de dados mais adequada para este problema. 
 
 
 
fila 
 
grafo 
 pilha 
 
árvore 
 
lista 
 
 
 4a Questão (Ref.: 201107153152) Pontos: 0,5 / 0,5 
Assinale a opção certa. 
 Quando não se escreve o protótipo de uma função ... 
 
 
 
A chamada da função poderá ser feita em qualquer hipótese. 
 
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. 
 
O programa não funcionará de forma alguma. 
 
 
 5a Questão (Ref.: 201107077547) Pontos: 0,0 / 0,5 
No contexto de estrutura de dados, uma pilha é: 
 
 
 
um tipo de lista linear em que as operações de inserção são realizadas em uma extremidade e as 
operações de remoção são realizadas em outra extremidade. 
 um tipo de lista linear em que as operações de inserção e remoção são realizadas na extremidade 
denominada topo. 
 
um tipo de lista linear em que as operações de inserção e remoção são realizadas aleatoriamente. 
 uma lista do tipo FIFO. 
 
uma lista do tipo LILO. 
 
 
 6a Questão (Ref.: 201107325003) Pontos: 0,0 / 1,0 
Tenho uma lista encadeada de processos para ler e despachar, mas obedeço a ordem de chegada, ou seja, 
o primeiro processo que chega é o primeiro processo a ser atendido por mim. Sabendo que cada processo 
é do tipo Processo, previamente definido e que a lista é do tipo Lista, assinale a opção que corretamente 
implementa a retirada de um processo da lista, que pode ter um ou mais processos. 
 Considere p um ponteiro para o primeiro nó da lista e ainda, 
struct Lista { 
 Processo p; 
 struct Lista *link; 
 }; 
 
 
 Lista *retirar(Lista *p) 
{ 
 delete p; 
 p = p->link; 
 return p; 
} 
 Lista retirar(Lista *p) 
{ 
 Lista *aux = p; 
 p = p->link; 
 return p; 
} 
 Lista *retirar(Lista *p) 
{ 
 Lista *aux = p; 
 p = p->link; 
 delete aux; 
 return p; 
} 
 Lista *retirar(Lista *p) 
{ 
 Lista *aux = p; 
 while (p->link->link !=NULL) 
 p = p->link; 
 delete p->link; 
 p->link = NULL; 
 return p; 
} 
 Lista *retirar(Lista *p) 
{ 
 Lista *aux = p; 
 while (p->link->link !=NULL) 
 p = p->link; 
 p->link = NULL; 
 return p; 
} 
 
 
 7a Questão (Ref.: 201107089056) Pontos: 0,5 / 0,5 
Existem vários tipos de algoritmos para realizar a ordenação dos elementos, onde um algoritmo de ordenação 
deve rearranjar o vetor de forma a estabelecer uma ordem entre os elementos. Marque a alternativa correta 
que cita o algoritmo cuja descrição é: "considera cada elemento uma vez inserindo-o em seu lugar correto entre 
os elementos que já estão em ordem". E o seu passo a passo pode ser descrito como: "o elemento é inserido 
entre os ordenados movendo-se os elementos maiores que ele uma posição para a direita e posteriormente 
inserindo-o na posição vaga". 
 
 
 Inserção 
 
Bolha 
 
Seleção 
 
MergeSort 
 
QuickSort 
 
 
 8a Questão (Ref.: 201107624559) Pontos: 0,0 / 1,0 
Na Alocação dinâmica, temos alguma regras a considerar. Leia atentamente as afirmativas abaixo e assinale 
a correta. 
 
I Alocou com new, desaloca com free 
II Alocou com new[], desaloca com delete 
III Alocou com new[], desaloca com delete[] 
IV Alocou com new[], desaloca com free[] 
V Alocou com new, desaloca com delete 
 
 
 I, II, III e V estão corretas 
 III e V estão corretas 
 II e V estão corretas 
 I e III estão corretas 
 I e IV estão corretas 
 
 
 9a Questão (Ref.: 201107114128) Pontos: 0,5 / 1,5 
 Os agentes Leo e Lia receberam sequências de números de seus contatos. Para 
saberem qual o próximo passo da missão, precisam descobrir que números se repetem 
nas sequências recebidas por cada um. 
 Faça uma função que receba dois vetores v e w de inteiros como parâmetros e gere um vetor z, resultante 
da interseção entre v e w. 
Protótipo da função : 
 bool intersecao(int v[ ], int w[ ], int z [ ], int nv , int nw , int &n); 
onde nv: quantidade de elementos em v 
 nw : quantidade de elementos em w 
 n : quantidade de elementos no vetor z 
Note : 
• Inicialmente n vale zero. 
• Deverá ser retornado true (sucesso na interseção) ou false (fracasso na interseção). 
 
 
Resposta: bool intersecao (int v[], int w[], int z[], int nv, int nw, int &n){ bool achou = false; for(i=0;i<nv;i++) 
for(j=o;j<nw;j++) if(v[i]==v[j]){ n = achou; return i; } return -1; } 
 
 
Gabarito: 
bool intersecao(int v[], int w[], int inter[], int nv , int nw , int &n) { 
bool achou = false; 
for (int i = 0; i < nv; i++) 
for (int j = 0; j < nw; j++) 
if (v[i] == w[j]) { 
inter[n] = v[i]; 
achou = true; 
n++; 
} 
return achou; 
} 
 
 
Fundamentação do(a) Professor(a): DEveria montar o vetor z com os elementos comuns a v e w, mas não fez. 
Veja que deveria retornar true ou false. 
 
 
 10a Questão (Ref.: 201107292423) Pontos: 0,0 / 1,5 
 Faça uma função em C++ para criar uma lista duplamente encadeada com um nó e 
armazenar neste nó o valor 100. Note que deverá ser retornado o ponteiro para o nó 
criado. Considere 
 struct nodupla { 
 int dado; 
 struct *dlink, *elink; 
 }; 
 
e o seguinte protótipo : nodupla *cria(); 
 
 
 
Resposta: nodupla *cria = new nodupla{ p->nodupla=*dlink p->*dlink->*elink } 
 
 
Gabarito: 
nodupla *cria() 
{ 
 nodupla *novo; 
 
 novo = new nodupla; 
 novo->dado = 100; 
 novo->elink = novo->dlink = NULL; 
 return novo; 
 
}