TRABALHO DEPEND EstruturaDados 2016 1

Prévia do material em texto

�
��
 
			 
INSTRUÇÕES / RECOMENDAÇÕES SOBRE A AVALIAÇÃO
a) Leia com atenção todas as questões antes de responder;
b) Verifique se há algum erro na digitação da avaliação;
c) Tire as dúvidas durante a explicação da avaliação pelo professor;
d) Cada questão vale ____ ponto;
e) É proibida a consulta a livros e textos ou cadernos ou conversar com o colega;
f) Questões com borrões ou rasuras serão anuladas;
g) Escreva com letra legível;
h) Nas questões objetivas marque apenas uma alternativa de caneta esferográfica azul ou preta;
i) Questões respondidas a lápis não serão corrigidas.
j) É proibido o uso de telefone celular ou qualquer outro meio de comunicação.
k) Não é permitido o uso de corretivo;
l) Todos os itens acima devem ser obedecidos sob pena de o aluno ter sua prova recolhida pelo professor ou fiscal.
No desenvolvimento de um software que analisa bases de DNA, representadas pelas letras A, C, G, T, utilizou-se as estruturas de dados: pilha e fila. Considere que, se uma sequência representa uma pilha, o topo é o elemento mais à esquerda; e se uma sequência representa uma fila, a sua frente é o elemento mais à esquerda. Analise o seguinte cenário: “a sequência inicial ficou armazenada na primeira estrutura de dados na seguinte ordem: (A,G,T,C,A,G,T,T). Cada elemento foi retirado da primeira estrutura de dados e inserido na segunda estrutura de dados, e a sequência ficou armazenada na seguinte ordem: (T,T,G,A,C,T,G,A). Finalmente, cada elemento foi retirado da segunda estrutura de dados e inserido na terceira estrutura de dados e a sequência ficou armazenada na seguinte ordem: (T,T,G,A,C,T,G,A)”. Qual a única sequência de estruturas de dados apresentadas a seguir pode ter sido usada no cenário descrito acima?(0,5)
�
Fila - Pilha - Pilha.
Fila - Fila - Pilha.
Pilha - Fila - Pilha.
Fila - Pilha - Fila.
Pilha - Pilha – Pilha
�
Mostre a situação da pilha P, inicialmente vazia, após a execução de cada uma das operações a seguir (0,5):
�
Push(P,a);
Push(P,b);
Push(P,c);
Push(P,Top(P));
Push(P,Pop(P));
Pop(P);
Push(P,e);
Pop(P);
�
A pilha é uma estrutura de dados que permite a inserção/remoção de itens dinamicamente seguindo a norma de último a entrar, primeiro a sair. Suponha que para uma estrutura de dados, tipo pilha, são definidos os comandos(0,5):
• PUSH (p, n): Empilha um número “n” em uma estrutura de dados do tipo pilha “p”;
• POP (p): Desempilha o elemento no topo da pilha.
Considere que, em uma estrutura de dados tipo pilha “p”, inicialmente vazia, sejam executados os seguintes comandos:
PUSH (p, 25)
POP (p)
PUSH (p, 12)
PUSH (p, 5)
PUSH (p, 20)
POP (p)
PUSH (p, 4)
PUSH (p, 11)
POP (p)
PUSH (p, 4)
PUSH (p, 7)
POP (p)
POP (p)
Após a execução dos comandos, o elemento no topo da pilha “p” e a soma dos elementos armazenados na pilha “p” são, respectivamente,
�
 4 e 21.
7 e 32.
4 e 25.
7 e 29.
11 e 40
�
Para os próximos exercícios (4 e 5), considere as seguintes rotinas como disponíveis. 
Pilha_Vazia(p) – retorna T se a pilha P estiver vazia e F se estiver cheia; 
Pilha_Cheia(p) – retorna T se a pilha P estiver cheia e f se estiver vazia; 
Empilha(p,x) – insere o elemento X no inicio da pilha P; 
Desempilha(p) – remove o 1º elemento da pilha P e retorna o conteúdo como valor da função; 
Imprime(p) – imprime a pilha P. 
Desenhe a evolução da pilha (de tamanho máximo de 8 elementos) e mostre o que será impresso no vídeo, considerando a execução da seqüência de instruções abaixo(0,5):
Empilha(p,’b’), pilha_cheia(p), Empilha(p,’s’); Empilha(p,’a’), Empilha(p,’c’), Desempilha(p), Desempilha(p), Empilha(p,’h’), Empilha(p,’d’), Empilha(p,’f’); Desempilha(p), Empilha(p,’n’), Empilha(p,’b’), pilha_cheia(p), Desempilha(p), Empilha(p,’m’), Desempilha(p),Desempilha(p), Desempilha(p), Imprime(p), pilha_vazia(p)
Escreva os comandos para montar a pilha apresentada abaixo, conforme o modelo: 
Quando há mais de um elemento na mesma posição da pilha (linha na representação), 
significa que o da esquerda foi removido, antes da inclusão do outro elemento. (1,0)
�
Empilha(p,´A´)
Empilha(p,’B’)
Desempilha(p)
Empilha(p,’C’)
Empilha(p,’D’)
Desempilha(p)
Empilha(p,’E’)
Desempilha(p)
Empilha(p,’F’)
Empilha(p,’G’)
Empilha(p,’H’)
Desempilha(p)
Empilha(p,’I’)
Empilha(p,’J’)
Empilha(p,’K’)
Imprime(p)
�
a)
Para os próximos exercícios (6), considere as seguintes rotinas como disponíveis.
Fila_Vazia(f) – retorna T se a fila F estiver vazia e F se estiver cheia;
fila_Cheia(f) – retorna T se a fila F estiver cheia e F se estiver vazia;
Insere(f,x) – insere o elemento X no final da fila F;
Remove(f) – remove o 1º elemento da fila F;
Imprime(f) – imprime a Fila F.
Considere que existam duas filas vazias denominadas F1 e F2. Execute as instruções do trecho de algoritmo abaixo. Deixe as representações das filas como elas estão no ponto determinado. Preencha as ilustrações de cada fila nos pontos definidos: A, B e C. 
Considere que os dados a serem lidos no algoritmo são: { 3, 6, 8, 2, 5, 1, 7, 4, 0, 5}. (2,0)
INSTITUTO TERESINA DE ENSINO E CULTURA
CURSO: CIÊNCIA DA COMPUTAÇÃO
DISCIPLINA: ESTRUTURA DE DADOS
PROFESSOR: LUCIANI VIEIRA
NOME : ____________________________________________________________
ANO: 2016/2	SEMESTRE: - TURMA: – TURNO: – DATA: / / 		
�PAGE \* MERGEFORMAT�1�
�PAGE \* MERGEFORMAT�4�