Prova Discursiva Estrutura de Dados

Prévia do material em texto

Questão A:
Em outras palavras, se p é um nó qualquer então:
  p->chave   ≤
Questões
Resposta da A 
Link Principal - https://uploaddeimagens.com.br/imagens/arvore_binaria_de_busca-jpg
Link Alternativo -  https://ibb.co/gMtmXm
 
Resposta da B -  O caminho para se chegar até o nó 4:  15 – 3 – 8 e 4.
 
Resposta da C 
Link Principal - https://uploaddeimagens.com.br/imagens/arvorebinaria-_remocao-jpg
Link Alternativo - https://ibb.co/gw0LCm
A partir do filho da esquerda do número 3 localiza-se o elemento que está a direita dele.
É esse nó que irá substituir o nó que está sendo excluído da árvore, deve se tomar o cuidado de atualizar os ponteiros tanto do pai do 3 como do pai do 4 e dos filhos que ele passará a ter, antes de remover o nó que comporta o número 3 e o 4 assumir o seu lugar.
 
Resposta da D 
Ela é uma Árvore Binária Degenerada.
Link Principal - https://uploaddeimagens.com.br/imagens/arvore_degenerada-jpg
Link Alternativo -  https://ibb.co/mSo1JR
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 
Questão B:
Resposta da A
Eu acredito que seja lista, por um momento cheguei a pensar que poderia ser fila mas se analisarmos existem ultrapassagens ou seja não enquadra na lei de uma fila que é FIFO ( First In First Out). Pensando deste modo a lista é a melhor opção pois assim conseguimos uma manipulação melhor de dados.
Fiz o exercício em lista dinâmica duplamente encadeada, uma lista dinâmica não é limitada apesar de ter colocado uma quantidade máxima pra ela.
Utilizei duplo encadeamento assim fica muito melhor a manipulação da lista, tornando mais fácil a manipulação do código-fonte.
Também fiz uso do nó descritivo facilitando ainda mais a manipulação da lista, podendo controlar a quantidade de elementos que ela possui, a quantidade máxima que ela suporta, e um apontamento para o início e fim.
Resposta da B e C
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>
typedef struct informacao
{
	int velocidade, numRegistro, tempo; /*  velocidade dele, numero único de registro do automóvel
										e o tempo que ele permanecerá no anel   */
	short faixa;    /* faixa em que ele está */
}info;
struct elementos
{
	struct informacao dados;    /*  dados dos veículos  */
	struct elementos* prox, *ant;   /* os apontamentos para os próximos e anteriores da lista   */
};
/** nó discritor    */
struct noDiscritor
{
	struct elementos* pInicio, *pFinal; /*  apontamento para o inicio da lista e para o final  */
	unsigned long qtd, MAX; /*  quantidade de elementos que a lista possui e quantidade máxima que
							ela pode possuir    */
};
/*  apenas typedefs para facilitar a manipulação das mesmas */
typedef struct elementos elem;
typedef struct noDiscritor lista;
short criaLista(lista**, unsigned long);
short liberaLista(lista*);
short criaNo(elem**, info);
short listaVazia(lista*);
short listaCheia(lista*);
short consultaListaPos(lista* , unsigned long , info*);
short insereListaFinal(lista*, info);
short alteraFaixa(lista*, int, short);
short alteraVelocidade(lista* , int, int);
short ImprimirLista(lista*);
short removeInicio(lista*);
void pausa();
void main()
{
lista* li;
info veiculo;
int i, j, op;
int tam = 10;
long max = 10, qtd = 10;
short bol;
setlocale(LC_ALL, ""); /* adiciona os acentos brasileiros */
srand(time(NULL));    /* cria seeds diferentes toda vez que é executado o programa    */
criaLista(&li, max);    /* cria a lista */
for (i = 0; i < 10; ++i)  /*  cria os 10 primeiros elementos aleatórios */
{
	veiculo.faixa = rand() % 2 + 1; /* faixa só pode ser 1 ou 2, desta maneira ele escolherá aleatoriamente um dos dois*/
	veiculo.numRegistro = rand() % 999999 + 1; /* numero de registro    */
	veiculo.velocidade = rand() % 100;  /* velocidade, do veiculo aleatório até 100 km */
	veiculo.tempo = rand() % 40 + 1; /* tempo do veiculo, ele ficara no maximo mas pode mudar o limite caso queira*/
	insereListaFinal(li, veiculo); /* insere o veiculo na lista  */
}
printf("Começando a Inserir Carros:\n");
ImprimirLista(li); /* imprimirá a lista de veiculos */
                                             
op = rand() % 4 + 1;    /* na primeira vez op não pode ser 0 por isso o + 1   */
while (op != 0) /* ficara escolhendo as funções aleatóriamente, até que op seja 0 */
{
	switch (op) /* escolherá aleatóriamente a função  */
	{
	case 1:
		tam = rand() % tam + 1;
		for (i = 0; i < tam; ++i, --qtd)
		{
			bol = removeInicio(li);
			if (bol != 1)
				break;
		}
		if (qtd < 0)    /* checa se o for não foi executado mais uma vez após chegar em lista vaiza, caso chegue*/
			qtd = 0;    /* caso sim atribui zero a qtd */
		break;
	case 2:
		tam = rand() % max + 1;
		for (i = 0; i < tam; ++i, ++qtd)
		{
			veiculo.faixa = rand() % 2 + 1;
			veiculo.numRegistro = rand() % 999999 + 1;
			veiculo.velocidade = rand() % 200;
			veiculo.tempo = rand() % 120 + 1;
			bol = insereListaFinal(li, veiculo);
			if (bol != 1)
				break;
		}
		if (qtd > max)  /* checa se não foi tentado introduzir uma elemento a mais caso a lista esta cheia*/
			qtd = max;  /* caso sim, diminui o valor de qtd para o max*/
		break;
	case 3:
		tam = rand() % qtd + 1;
		for (j = 0; j < tam; ++j)
		{
			i = rand() % qtd + 1;
			consultaListaPos(li, (unsigned long)(i), &veiculo); /* casting do i para evitar erros */
			alteraVelocidade(li, veiculo.numRegistro, rand() % 200);
		}
		break;
	case 4:
		tam = rand() % qtd + 1;
		for (j = 0; j < tam; ++j)
		{
			i = rand() % qtd + 1;
			consultaListaPos(li, (unsigned long)(i), &veiculo); /* casting do i para evitar erros */
			alteraFaixa(li, veiculo.numRegistro, rand() % 2 + 1);
		}
		break;
	}
	op = rand() % 5;    /* limite 5, ou seja, poderá conter valores de 0 a 4    */
	
}
printf("\nNova Simulação: \n");
ImprimirLista(li); /* imprime a lista para nós vermos o resultado final   */
liberaLista(li);    /* libera a lista   */
pausa();
}
/** informações do veiculo    */
/** elementos da lista  */
void pausa()
{
	printf("\n Pressione uma Tecla");
	_getch();
}
short criaLista(lista** li, unsigned long MAX) /*    note que a lista é passada como ** de lista
											   isto se deve a passagem por referência    */
{
	*li = (lista*)malloc(sizeof(lista)); /* aloca a lista*/
	if (!li)      /*   verifica se a lista foi alocada corretamente, caso contrario retorna -1    */
		return -1;
	(*li)->pInicio = NULL;  /* seta os apontamentos para NULL   */
	(*li)->pFinal = NULL;
	(*li)->qtd = 0;         /* inicia o qtd em 0    */
	(*li)->MAX = MAX;       /* inicia o max no valor passado pelos parâmetros */
	return 1;   /* retorna 1 pois a alocação foi um sucesso */
	pausa();
}
short liberaLista(lista* li)
{
	elem* no;   /* cria nó auxiliar, para poder andar pela lista e ir liberando, assim não perde
				o apontamento para o inicio da lista */
	if (!li)  /* verifica se a lista existe   */
		return -1;
	while ((li->pInicio) != NULL) /*  enquanto houver elemento na lista, remova os elementos */
	{
		no = li->pInicio;   /* utiliza o nó para não perder o apontamento da lista */
		li->pInicio = li->pInicio->prox;    /*  atribua a próxima posição da lista ao inicio */
		free(no);   /* remove antigo inicio */
	}
	free(li);   /* remove lista */
	return 1;   /* retorna 1 a liberação foi um sucesso */
	pausa();
}
short criaNo(elem** no, info dado)
{
	*no = (elem*)malloc(sizeof(elem)); /*   aloca o nó  */
	if (!no)      /*  verifica se não houve erro ao alocar.   */
		return 0;  /*    retorna 0 caso falha  */
	(*no)->dados = dado;    /* atribui os dados passados ao nó  */
	(*no)->prox = NULL;     /* seta os apontamentos em NULL.    */
	(*no)->ant = NULL;
	return 1;   /*  retorna 1  caso sucesso */
	pausa();
}
short listaVazia(lista* li)
{
	if (!li)               /*  verifica se a lista existe  */
		return -1;
	return (li->qtd == 0);  /*retorna um 1 caso seja vazia, ou 0 caso o oposto */
}
short listaCheia(lista* li)
{
	if (!li)
		return -1;
	return (li->qtd == li->MAX);
	pausa();
}
short insereListaFinal(lista* li, info dado) /* passa a lista que deseja a inserção, e o dado a ser inserido.    */
{
	elem* no;   /* no auxiliar para poder inserir na lista  */
	short bol = criaNo(&no, dado);  /*  função que cria o nó */
	if ((!li) || (!bol))  /* verifica se a lista e o nó é existentes  */
		return -1;
	if (listaCheia(li))   /* verifica se a lista está cheia */
		return 0;
	no->ant = li->pFinal;   /* seta o apontamento do anterior do nó no final da lista   */
	if (listaVazia(li))    /* caso a lista seja vazia o final e o inicio irão apontar para nó  */
		li->pInicio = no;
	else
		li->pFinal->prox = no;  /* caso contrario o antigo final apontará para nó   */
	li->pFinal = no;    /* nó vira o novo final */
	++li->qtd;          /* atualiza a quantidade de elementos da lista  */
	return 1;
	pausa();
}
short removeInicio(lista* li)
{
	elem* no; /*    cria o nó que ira auxiliar a liberar o dado desejado    */
	if (!li)  /* verifica se lista existe */
		return -1;
	if (listaVazia(li))   /* verifica se a lista não esta vazia   */
		return 0;
	no = li->pInicio;   /* aponta o no ao inicio da lista   */
	if (li->qtd == 1)     /* caso tenha apenas um elemento, a lista se tornará vazia. */
	{
		li->pFinal = NULL;  /* mudando o apontamento para NULL  */
		li->pInicio = NULL;
	}
	else
	{
		li->pInicio = li->pInicio->prox;    /* caso contrario, atualize a apontamento para o novo inicio    */
		li->pInicio->ant = NULL;            /* atualize o apontamento do novo inicio, desvinculando-o do anterior   */
	}
	--li->qtd;  /* atualize a quantidade de elementos   */
	free(no);   /* libere o antigo inicio   */
	return 1;
	pausa();
}
short consultaListaPos(lista* li, unsigned long pos, info* dado) /*  passe a lista por parâmetro, a posição que																 deseja consultar e onde ira receber o dado  */
{
	elem* no;                   /* no auxiliar, para percorrer a lista, assim não perde o apontamento para o inicio   */
	register unsigned long i; /* contador   */
	if (!li)  /* checa se a lista existe  */
		return -1;
	if ((listaVazia(li)) || (pos <= 0) || (pos > li->qtd))    /* chega se a lista esta vazia, ou, posição é 0 ou inferior
															  ou se posição é maior que a quantidade de elementos da lista    */
		return 0;
	for (i = 1, no = li->pInicio; (i != pos) && (no != NULL); ++i, no = no->prox);    /*  encontra a posição do dado  */
	if (no == NULL)   /* verifica se a posição era de fato existente  */
		return 0;
	*dado = no->dados;  /* atribuir ao dado, o dado da lista    */
	return 1;
	pausa();
}
short alteraFaixa(lista* li, int numRegistro, short faixa) 
{
	elem* no; /* nó auxiliar, para percorrer a lista    */
	if (!li)  /* verifica se a lista existe   */
		return -1;
	if (listaVazia(li))   /* verifica se a mesma não é vazia  */
		return 0;
	if (li->pInicio->dados.numRegistro == numRegistro)    /* se for igual o numRegisto, atribua o novo valor  */
	{
		li->pInicio->dados.faixa = faixa;
		return 1;
	}
	if (li->pFinal->dados.numRegistro == numRegistro) /* similar ao anterior  */
	{
		li->pFinal->dados.faixa = faixa;
		return 1;
	}
	if ((no = li->pInicio->prox) == NULL) /* aponta o nó ao próximo e checa se a lista não contém somente um elemento */
		return 0;
	while ((no != li->pFinal) && (no->dados.numRegistro != numRegistro))  /* encontra o veiculo   */
		no = no->prox;
	if (no == li->pFinal) /* checa se foi encontrado mesmo de fato    */
		return 0;
	no->dados.faixa = faixa;    /* atribui o novo valor faixa   */
	return 1;
	pausa();
}
short alteraVelocidade(lista* li, int numRegistro, int velocidade)
{
	elem* no;
	if (!li)
		return -1;
	if (listaVazia(li))
		return 0;
	if (li->pInicio->dados.numRegistro == numRegistro)
	{
		li->pInicio->dados.velocidade = velocidade;
		return 1;
	}
	if (li->pFinal->dados.numRegistro == numRegistro)
	{
		li->pFinal->dados.velocidade = velocidade;
		return 1;
	}
	if ((no = li->pInicio->prox) == NULL)
		return 0;
	while ((no != li->pFinal) && (no->dados.numRegistro != numRegistro))
		no = no->prox;
	if (no == li->pFinal)
		return 0;
	no->dados.velocidade = velocidade;
	return 1;
	pausa();
}
short ImprimirLista(lista* li)
{
	elem* no;
	register unsigned long i;
	setlocale(LC_ALL, ""); /* comando da locale.h para poder ter acentos    */
	if (!li)
		return -1;
	if (listaVazia(li))
		return 0;
	printf("\n\t##### ...Imprimindo Veículos na via... #####\n");
	for (no = li->pInicio, i = 1; no != NULL; no = no->prox, ++i)
		printf("\n%luº Carro:"
			"\nFaixa: %hi"
			"\nVelocidade: %3i km/h"
			"\nNumero de Registro: %6i."
			"\nTempo que Permanecerá: %3i min"
			"\n ----------\n", i, no->dados.faixa, no->dados.velocidade, no->dados.numRegistro, no->dados.tempo);
	printf("\n\t##### ...Termino da Impressão de Veículos no Anel viário... #####\n");
	
	return 1;
	pausa();
}