Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Ediberto – Trabalho AV1
3.Considere uma lista duplamente encadeada de livros em que cada nó ou nodo é do tipo nodupla definido a seguir: struct nodupla { int codigo; string autor; struct nodupla *dlink; // aponta para o nó à direita struct nodupla *elink; // aponta para o nó à esquerda }; sendo nodupla *p; //ponteiro para o início da lista, que pode estar vazia Escreva uma função em C++ para inserir um novo livro no início da lista. Para isso, considere o seguinte protótipo : nodupla *inserir(nodupla *p, int codigo, string autor);
Resposta:
nodupla *novo;
novo=new nodupla;
novo->codigo=codigo;
novo->dlink=p;
novo->elink=NULL;
if(p!=NULL)
p->elink=novo;
p=novo
4.Ao criarmos uma rotina para inserir um dado em uma LISTA de dados duplamente encadeada e circular, nos deparamos com as seguintes cuidados:
Resposta: Posso inserir no começo, no meio ou no fim.
5.Nas estruturas dinâmicas a alocação de memória ocorre em tempo de execução, assim pode-se controlar durante a execução do programa o tamanho da estrutura. Entretanto, é imprescindível o uso de ponteiros nestas estruturas, explique o porquê:
Resposta: Na declaração de um vetor é preciso dimensioná-lo, o que significa que devemos saber, de antemão, quanto espaço seria necessário, isto é, tínhamos de prover o número máximo de elementos no vetor durante a codificação. Por isso é imprescindível o uso de ponteiros nas estruturas.
6.Em uma lista duplamente encadeada, seus nodos são compostos por campos cujos tipos podem ser de diferentes naturezas, entretanto dois de seus campos devem ser ponteiros para o mesmo tipo do nodo, são estes os ponteiros ant e prox, que apontam, respectivamente, para o nodo anterior e para o próximo nodo. Esta característica permite que a estrutura seja percorrida em ambos os sentidos. Assim analisando as operações a seguir: p->ant->prox=p->prox; p->prox->ant=p->ant; Sendo p um ponteiro que aponta para um dos nodos da lista, pode-se afirmar que:
Resposta: As operações removem o nodo apontado pelo ponteiro p.
7.Considere o tipo nodupla assim definido:
struct nodupla { int dado; struct nodupla
*dlink, //aponta para o nó à direita
*elinlk; //aponta para o nó à esquerda };
e uma lista duplamente encadeada, cujo primeiro nó é apontado por p, sendo nodupla *p;
Pede-se : Sabendo-se que a função imprimir dada abaixo possui um ou mais erros, acerte-a, reescrevendo-a inteiramente de forma correta. imprimir(nodupla *p) { while (p != NULL) { cout << " " << p->dado; } }
Resposta: imprimir(nodupla*p){
while(p!=NULL){
cout<< p->dado<<" ";
p=p->dlink;
}
}
8.Os registros também conhecidos como estruturas, são estruturas de dados do tipo heterogêneo, ou seja, permitem que valores de tipos diferentes possam ser armazenados em uma mesma estrutura. Analisando a estrutura abaixo, a mesma pode ser utilizada para qual tipo de estrutura de dados, marque a alternativa correta. struct nomeRegistro{ int info; struct nomeRegistro* ant; struct nomeRegistro* prox; }; typedef struct nomeRegistro NOMEREGISTRO;
Resposta: Lista duplamente encadeada.
9.Qual a estrutura de dados usada na implementação do método Round Robin operacional UNIX ?
Resposta: Lista duplamente encadeada.
10.A partir da definição de lista simplesmente encadeada, implementar uma função que insira um novo valor inteiro no início da lista simplesmente encadeada. Protótipo: void InserirIni (pont *L, int x);
Resposta: void InserirIni (pont *L, int x){
no *aux;
aux->x=x;
if(no == NULL){
no=aux;
aux->L=NULL;
}
}
11.Diga o que faz a função Descobrir, que recebe um ponteiro para o último nó de uma lista circular simplesmente encadeada, que pode ser vazia. Considere o tipo no assim definido:
struct no{ int dado; struct no *link; }; no
*Descobrir(no *a, int valor) { no *aux;
aux = new no;
aux->dado = valor;
if (a == NULL) { a = aux; a->link = a; }
else
{ aux->link = a->link; a->link = aux; }
return a; } // fim da função
Resposta: Se ela for vazia, o 'a' vai receber o valor do ponteiro aux que por sua vez , possui o valor da variavel 'valor', que assim retornará o 'a 'para a função.
12.Defina uma Lista Simplesmente Encadeada Circular.
Resposta: Uma lista é denominada circular quando o conteúdo do campo prox do último nó é igual ao endereço do primeiro nó. Obs: não há NULL indicando fim em listas circulares.
13. Defina uma Lista Duplamente Encadeada
É uma estrutura de dados ligada que consiste de um conjunto de registros sequencialmente ligados chamados de nós e é uma extensão da lista simplesmente ligada.
14.Considere uma lista duplamente encadeada não circular de livros, sendo que cada livro possui código e preço. Escreva as instruções necessárias, na main(), para criar um nó desta lista sabendo que cada nó é do tipo noDupla definido a seguir :
struct noDupla { int codigo; float preco; struct noDupla
*dlink, //aponta para o nó à direita
*elink; //aponta para o nó à esquerda };
Resposta:
15.Meu filho precisa trabalhar com a estrutura de dados fila, mais especificamente, fila sequencial circular com contador. Para isso, o 1º. passo é inicializar a fila. Sabendo que, struct Fila { int inicio, fim, contador; float v[100]; }; modela f que é do tipo Fila, ajude meu filho a inicializar a fila f, implementando uma função com o seguinte protótipo: Fila inicializar(Fila f);
Resposta:
#include<iostream>
using namespace std;
struct Fila {
int inicio, fim, contador;
float v[100];
};
void criarFila( struct Fila *f){
f->inicio =0;
}
16.Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada nó armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa estrutura,
Resposta: o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.
17.Em relação às estruturas de dados, considere: I. Um tipo abstrato de dados está desvinculado de sua implementação, ou seja, a sua definição visa a preocupação com o que ele faz e não como ele faz. II. A lista duplamente encadeada além de saber o próximo nó, cada elemento também conhece o nó anterior a ele na lista, o que facilita a remoção de um elemento e a exibição dos elementos na ordem inversa. III. A implementação dinâmica de pilhas possui as mesmas vantagens que as listas dinâmicas, ou seja, não é necessário saber a quantidade máxima de elementos que serão armazenados. IV. Lista, pilha, fila e array são casos típicos de estruturas lineares, enquanto grafo e heap são casos típicos de estruturas não lineares. É correto o que se afirma em:
Resposta: I,II, III E IV corretas.
18.Faça uma função em C++ para imprimir todos os dados de uma lista duplamente encadeada não vazia de alunos. Considere struct nodupla { int matricula; float media; struct *dlink, //ponteiro para o nó à direita *elink; //ponteiro para o nó à esquerda }; e o seguinte protótipo : void mostrar(nodupla *p);
Resposta:
19.Faça uma função em C++ para criar uma lista duplamente encadeada com apenas um nó e armazenar neste nó a matrícula 100 e a média 9.0. Deverá ser retornado o ponteiro para o nó criado. Considere struct nodupla { int matricula; float media; struct *dlink, *elink; }; e o seguinte protótipo : nodupla *cria();
Resposta:
20.Uma lista simplesmente encadeada pode ser transformada em uma lista duplamente encadeada em tempo O(1), porque para transformar uma lista simplesmente encadeada em duplamente encadeada basta fazer uma cópia invertida de cada ponteiro (o destino do novo ponteiro passa a ser a origem do ponteiro original e vice-versa) e existe um número constante e limitado de cópias a fazer. Analisando as afirmações acima, conclui-se que:
Resposta: As duas afirmações
3.Considere uma
lista duplamente encadeada de livros em que cada nó ou nodo é do tipo nodupla definido a seguir: struct nodupla { int codigo; string autor; struct nodupla *dlink; // aponta para o nó à direita struct nodupla *elink; // aponta para o nó à esquerda }; sendo nodupla *p; //ponteiro para o início da lista, que pode estar vazia Escreva uma função em C++ para inserir um novo livro no início da lista. Para isso, considere o seguinte protótipo : nodupla *inserir(nodupla *p, int codigo, string autor);
Resposta:
nodupla *novo;
novo=new nodupla;
novo->codigo=codigo;
novo->dlink=p;
novo->elink=NULL;
if(p!=NULL)
p->elink=novo;
p=novo
4.Ao criarmos uma rotina para inserir um dado em uma LISTA de dados duplamente encadeada e circular, nos deparamos com as seguintes cuidados:
Resposta: Posso inserir no começo, no meio ou no fim.
5.Nas estruturas dinâmicas a alocação de memória ocorre em tempo de execução, assim pode-se controlar durante a execução do programa o tamanho da estrutura. Entretanto, é imprescindível o uso de ponteiros nestas estruturas, explique o porquê:
Resposta: Na declaração de um vetor é preciso dimensioná-lo, o que significa que devemos saber, de antemão, quanto espaço seria necessário, isto é, tínhamos de prover o número máximo de elementos no vetor durante a codificação. Por isso é imprescindível o uso de ponteiros nas estruturas.
6.Em uma lista duplamente encadeada, seus nodos são compostos por campos cujos tipos podem ser de diferentes naturezas, entretanto dois de seus campos devem ser ponteiros para o mesmo tipo do nodo, são estes os ponteiros ant e prox, que apontam, respectivamente, para o nodo anterior e para o próximo nodo. Esta característica permite que a estrutura seja percorrida em ambos os sentidos. Assim analisando as operações a seguir: p->ant->prox=p->prox; p->prox->ant=p->ant; Sendo p um ponteiro que aponta para um dos nodos da lista, pode-se afirmar que:
Resposta: As operações removem o nodo apontado pelo ponteiro p.
7.Considere o tipo nodupla assim definido:
struct nodupla { int dado; struct nodupla
*dlink, //aponta para o nó à direita
*elinlk; //aponta para o nó à esquerda };
e uma lista duplamente encadeada, cujo primeiro nó é apontado por p, sendo nodupla *p;
Pede-se : Sabendo-se que a função imprimir dada abaixo possui um ou mais erros, acerte-a, reescrevendo-a inteiramente de forma correta. imprimir(nodupla *p) { while (p != NULL) { cout << " " << p->dado; } }
Resposta: imprimir(nodupla*p){
while(p!=NULL){
cout<< p->dado<<" ";
p=p->dlink;
}
}
8.Os registros também conhecidos como estruturas, são estruturas de dados do tipo heterogêneo, ou seja, permitem que valores de tipos diferentes possam ser armazenados em uma mesma estrutura. Analisando a estrutura abaixo, a mesma pode ser utilizada para qual tipo de estrutura de dados, marque a alternativa correta. struct nomeRegistro{ int info; struct nomeRegistro* ant; struct nomeRegistro* prox; }; typedef struct nomeRegistro NOMEREGISTRO;
Resposta: Lista duplamente encadeada.
9.Qual a estrutura de dados usada na implementação do método Round Robin operacional UNIX ?
Resposta: Lista duplamente encadeada.
10.A partir da definição de lista simplesmente encadeada, implementar uma função que insira um novo valor inteiro no início da lista simplesmente encadeada. Protótipo: void InserirIni (pont *L, int x);
Resposta: void InserirIni (pont *L, int x){
no *aux;
aux->x=x;
if(no == NULL){
no=aux;
aux->L=NULL;
}
}
11.Diga o que faz a função Descobrir, que recebe um ponteiro para o último nó de uma lista circular simplesmente encadeada, que pode ser vazia. Considere o tipo no assim definido:
struct no{ int dado; struct no *link; }; no
*Descobrir(no *a, int valor) { no *aux;
aux = new no;
aux->dado = valor;
if (a == NULL) { a = aux; a->link = a; }
else
{ aux->link = a->link; a->link = aux; }
return a; } // fim da função
Resposta: Se ela for vazia, o 'a' vai receber o valor do ponteiro aux que por sua vez , possui o valor da variavel 'valor', que assim retornará o 'a 'para a função.
12.Defina uma Lista Simplesmente Encadeada Circular.
Resposta: Uma lista é denominada circular quando o conteúdo do campo prox do último nó é igual ao endereço do primeiro nó. Obs: não há NULL indicando fim em listas circulares.
13. Defina uma Lista Duplamente Encadeada
É uma estrutura de dados ligada que consiste de um conjunto de registros sequencialmente ligados chamados de nós e é uma extensão da lista simplesmente ligada.
14.Considere uma lista duplamente encadeada não circular de livros, sendo que cada livro possui código e preço. Escreva as instruções necessárias, na main(), para criar um nó desta lista sabendo que cada nó é do tipo noDupla definido a seguir :
struct noDupla { int codigo; float preco; struct noDupla
*dlink, //aponta para o nó à direita
*elink; //aponta para o nó à esquerda };
Resposta: int main(int codigo, float preco){
noDupla *novo = new noDupla;
novo->codigo=codigo;
novo->dlink=NULL;
novo->elink=NULL;
}
15.Meu filho precisa trabalhar com a estrutura de dados fila, mais especificamente, fila sequencial circular com contador. Para isso, o 1º. passo é inicializar a fila. Sabendo que, struct Fila { int inicio, fim, contador; float v[100]; }; modela f que é do tipo Fila, ajude meu filho a inicializar a fila f, implementando uma função com o seguinte protótipo: Fila inicializar(Fila f);
Resposta:
#include<iostream>
using namespace std;
struct Fila {
int inicio, fim, contador;
float v[100];
};
void criarFila( struct Fila *f){
f->inicio =0;
}
16.Uma lista ligada é uma estrutura que corresponde a uma sequência lógica de entradas ou nós. Cada nó armazena a localização do próximo elemento na sequência, ou seja, de seu nó sucessor. Nessa estrutura,
Resposta: o armazenamento de uma lista não requer uma área contígua de memória. Como listas são estruturas dinâmicas, normalmente são definidos procedimentos que permitem criar e remover nós na memória.
17.Em relação às estruturas de dados, considere: I. Um tipo abstrato de dados está desvinculado de sua implementação, ou seja, a sua definição visa a preocupação com o que ele faz e não como ele faz. II. A lista duplamente encadeada além de saber o próximo nó, cada elemento também conhece o nó anterior a ele na lista, o que facilita a remoção de um elemento e a exibição dos elementos na ordem inversa. III. A implementação dinâmica de pilhas possui as mesmas vantagens que as listas dinâmicas, ou seja, não é necessário saber a quantidade máxima de elementos que serão armazenados. IV. Lista, pilha, fila e array são casos típicos de estruturas lineares, enquanto grafo e heap são casos típicos de estruturas não lineares. É correto o que se afirma em:
Resposta: I,II, III E IV corretas.
18.Faça uma função em C++ para imprimir todos os dados de uma lista duplamente encadeada não vazia de alunos. Considere struct nodupla { int matricula; float media; struct *dlink, //ponteiro para o nó à direita *elink; //ponteiro para o nó à esquerda }; e o seguinte protótipo : void mostrar(nodupla *p);
Resposta: nodupla *novo = new nodupla;
novo->matricula=10;
novo->media=10;
novo->dlink=NULL;
novo->elink=NULL;
19.Faça uma função em C++ para criar uma lista duplamente encadeada com apenas um nó e armazenar neste nó a matrícula 100 e a média 9.0. Deverá ser retornado o ponteiro para o nó criado. Considere struct nodupla { int matricula; float media; struct *dlink, *elink; }; e o seguinte protótipo : nodupla *cria();
Resposta: nodupla *cria(int matricula, float media){
nodupla *novo = new nodupla;
novo->matricula=100;
novo->media=10;
novo->dlink=NULL;
novo->elink=NULL;
}
20.Uma lista simplesmente encadeada pode ser transformada em uma lista duplamente encadeada em tempo O(1), porque para transformar uma lista simplesmente
encadeada em duplamente encadeada basta fazer uma cópia invertida de cada ponteiro (o destino do novo ponteiro passa a ser a origem do ponteiro original e vice-versa) e existe um número constante e limitado de cópias a fazer. Analisando as afirmações acima, conclui-se que:
Resposta: As duas afirmações
