Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNIVERSIDADE FEDERAL DE JUIZ DE FORA INSTITUTO DE CIÊNCIAS EXATAS DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 2º TVC de Estrutura de Dados e Laboratório de Programação II – 30/05/2011 ALUNO (A) _______________________________________________________________ Turma Lab:_____ ED:_____ ATENÇÃO: Estrutura de Dados: questões de 1 a 4. Laboratório de Programação II: questões de 3 a 5. Sempre que necessário, apresentar as definições das estruturas de dados. _______________________________________________________________________________________________________________________________________________________________________________________________________________________ 1) Considere um fila representada por contiguidade dos nós (possui os campos C e F que são inteiros que armazenam o índice do início e do fim da fila). Vimos que se forem executados um determinado número de operações de entrada e saída, a fila se torna cheia – embora haja espaço no início do vetor. Quais são as soluções mais comuns para contornar este tipo de problema. (15) 1. Deslocar todos os elementos da fila para o início do vetor para permitir novas entradas. 2. Toda vez que ocorrer uma saída, a fila é deslocada de uma posição de forma que fique sempre no início do vetor. 3. Usar fila circular. _______________________________________________________________________________________________________________________________________________________________________________________________________________________ 2) Desenvolver o procedimento Insere(Lista: L, int: val) que insere valores inteiros val numa lista simplesmente encadeada com descritor. Os valores devem ficar em ordem crescente na lista L. Definir todos os tipos utilizados para definir a lista (isto é, descritor e no). DICA: se val é menor que o primeiro da lista, insira-o no início; se val é maior que o último da lista, insira-o no fim da lista; senão insira-o apropriadamente no meio da lista. (20) Em pseudolinguagem: tipo RN = ref NO; tipo Lista = ref DESCRITOR; tipo DESCRITOR = reg (RN: PRIMEIRO; int: N; RN: ULTIMO); tipo NO = reg (int: X; RN: PROXIMO); proc InserePrimeiro(Lista:L, int: VAL) RN:Q ConstroiNO(VAL); L.PRIMEIRO Q; L.ULTIMO Q; fim-proc; proc Insere(Lista: L, int: VAL) {Considera L ≠ nil. Descritor alocado} se L.N > 0 então {lista não vazia} se VAL <= L.PRIMEIRO.X entao InsereInicio(L, VAL); senao se VAL >= L.ULTIMO.X então InsereFim(L, VAL); senao InsereMeio(L, VAL); fim-se; fim-se; senao InserePrimeiro(L, VAL); fim-se; L.N L.N + 1; fim-proc; proc InsereMeio(Lista: L, int: VAL) RN:Q ConstroiNO(VAL); RN:P L.PRIMEIRO; RN:AP; equanto VAL > P.X faca AP P; P P.PROXIMO; fim-enquanto; Q.PROXIMO P; AP.PROXIMO Q; fim-proc; proc InsereInicio(Lista: L, int: VAL) RN:Q ConstroiNO(VAL); Q.PROXIMO L.PRIMEIRO; L.PRIMEIRO Q; fim-proc; proc InsereFim(Lista: L, int: VAL) RN:Q ConstroiNO(VAL); L.ULTIMO.PROXIMO Q; *incluir L.ULTIMO Q; fim-proc; funcao ConstroiNO(int: X):RN {Configura um nó com valores adequados e retorna uma referencia para este nó} RN:Q; aloque(Q); Q.X X; Q.PROXIMO nil; ConstroiNO Q; fim-funcao; UNIVERSIDADE FEDERAL DE JUIZ DE FORA INSTITUTO DE CIÊNCIAS EXATAS DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 3) Escreva um procedimento para converter um número inteiro em um número expresso em um sistema de número cuja base (ou raiz) é 2. A conversão é realizada pela divisão repetitiva, pela base 2, e então tomando-se os restos da divisão na ordem inversa. Por exemplo, para converter para binário, o número 6 exige três de tais divisões: 6/2 = 3 com resto 0, 3/2=1 com resto 1 e, finalmente, 1/2 = 0 com resto 1. Os restos 0, 1 e 1 são colocados na ordem inversa, de modo que o binário equivalente de (6)10 é igual a 110 na base 2. (35) proc converteBin(int: n) int: bit; enquanto n > 0 faça bit n mod 2; n n div 2; empilha(p, bit); fim-enquanto; enquanto não(vazia(p)) faça imprima(desempilha(p)); fim-enquanto; fim-proc; void converteBin(int n) { char bit; while(n > 0){ bit = n%2; n = n/2; empilha(p, bit); } while(!vazia(p)) printf("%c",desempilha(p)); } _______________________________________________________________________________________________________________________________________________________________________________________________________________________ 4) A seguir, é apresentado um procedimento que realiza operações sobre a pilha p. Suponha que y contém o caracter '&'. (30) a) Qual é o conteúdo da pilha p nos pontos sinalizados no procedimento por PONTO1 e PONTO2? b) Quais são os valores finais de x e sucesso e o conteúdo da pilha p no término da execução do procedimento abaixo? Em C: Em Pseudolinguagem: void executa(){ int sucesso; char x,y = '&'; Pilha *p = cria(); empilha(p,'+'); if(!vazia(p)){ x = desempilha(p); sucesso = 1; } else sucesso = 0; //PONTO 1 if(!vazia(p)){ x = desempilha(p); sucesso = 1; } else sucesso = 0; //PONTO 2 empilha(p,'('); empilha(p,y); if(!vazia(p)){ x = desempilha(p); sucesso = 1; } else sucesso = 0; } proc executa int: sucesso; car: x; car: y '&'; Pilha p cria(); empilha(p,'+'); se não(vazia(p)) x desempilha(p); sucesso 1; senao sucesso 0; fim-se; //PONTO 1 se não(vazia(p)) x desempilha(p); sucesso 1; senao sucesso 0; fim-se; //PONTO 2 empilha(p,'('); empilha(p,y); se não(vazia(p)) x desempilha(p); sucesso 1; senao sucesso 0; fim-se; fim-proc; a) b) PONTO1 PONTO2 FINAL Conteúdo da pilha p vazia vazia x sucesso p ‘&’ 1 ‘(‘ UNIVERSIDADE FEDERAL DE JUIZ DE FORA INSTITUTO DE CIÊNCIAS EXATAS DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 5) Considere a lista simplesmente encadeada L de números inteiros. L é do tipo Lista definido abaixo: typedef struct lista Lista; struct lista{ int info; struct lista *prox; }; Desenvolver um procedimento/função – que tem como entrada um inteiro n e a lista L – para: a) inserir vários nós com valor val nas posições k, onde k é um múltiplo de n. Isto é, inserir nós de n em n na lista. Protótipo da função void insere(Lista *L, int n, int val). b) contar e retornar o número de nós da lista L cujo valor é igual a n. Protótipo da função int conta(Lista *L, int n). (35) Duas possibilidades: // Insere o novo nó antes do nó em k void insere(Lista *L, int n, int val) { int i = 0; Lista *atual = L; Lista *ant = NULL; while(atual != NULL) { if(i % n == 0) { Lista *novo = (Lista *)malloc(sizeof(Lista)); novo->info = val; novo->prox = atual; if(ant != NULL) ant->prox = novo; } ant = atual; atual = atual->prox; i++; } } // Insere o novo nó depois do nó em k void insere(Lista *L, int n, int val) { int i = 1; Lista *atual = L; while(atual != NULL) { if(i % n == 0) { Lista *novo = (Lista *)malloc(sizeof(Lista)); novo->info = val; novo->prox = atual->prox; atual->prox = novo; atual = atual->prox; } atual = atual->prox; i++; } } int conta(Lista *L,int n) { int cont = 0; Lista *aux; for(aux = L; aux != NULL; aux = aux->prox) { if(aux->info == n) cont++; } return cont; }
Compartilhar