Tvc2-EDLII-1-11-Tarde.GabaritoPublicado

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; 
}