ExProvAnt

De DCA-Wiki

Questões de provas antigas de EA879

O seguinte programa implementa o algoritmo BubbleSort em C++ para ordenar os elementos de um vetor de inteiros, vector<int> T:

for (int passo=1; passo<=T.size()-1; ++passo)
for (int pos=1; pos<=T.size()-passo; ++pos)
if (T[pos-1] > T[pos]) {
	int temp = T[pos-1];
	T[pos-1] = T[pos];
	T[pos] = temp;
}

Mostre, passo a passo, como o vetor abaixo é ordenado por esse código:

15	12	8	10	9	5	2


Um colega seu afirmou que a estrutura vector é a melhor opção para implementar uma pilha (política LIFO – last in, first out) em C++. Você concorda ou discorda? Justifique sua resposta.



Descreva, usando texto em linguagem natural, como funciona o algoritmo de ordenação Quicksort.



Aloque os valores abaixo na seguinte estrutura de árvore binária de forma que a seqüência dos valores seja apresentada em ordem quando a árvore é percorrida segundo a estratégia de varredura:

2	5	8	9	10	12	15

(a) pré-ordem:

          (   )
         /     \
     (   )    (   )
    /     \
 (   )   (   )
        /     \
     (   )   (   )

(b) intra-ordem:

          (   )
         /     \
     (   )    (   )
    /     \
 (   )   (   )
        /     \
     (   )   (   )

(c) pós-ordem:

          (   )
         /     \
     (   )    (   )
    /     \
 (   )   (   )
        /     \
     (   )   (   )

(d) Reorganize a árvore do item (a) de forma que a árvore fique balanceada.



Em uma tabela hash com 8 posições, os valores inteiros 2, 7, 8 e 10 devem ser armazenados.

(a) Em quais posições da tabela esses valores serão armazenados se o método da divisão é utilizado?

(b) Em quais posições da tabela esses valores serão armazenados se o método do meio do quadrado é utilizado? Considere que os valores inteiros são representados com 4 bits.



O que é a técnica de folding e para que é utilizada?



Mostre como o algoritmo de ordenação radix sort move os dados da seguinte lista até alcançar o arranjo ordenado ao final do último passo, utilizando como base um dígito em base 10. Explicite nas suas anotações as informações complementares necessárias para realizar essa ordenação.

325
148
91
419
42
515
218


Cite uma vantagem e uma desvantagem do algoritmo radix sort em relação ao algoritmo quicksort.



Aplique o Algoritmo de Thompson e o Método da Construção por Subconjuntos para obter o autômato finito determinístico para reconhecer sentenças expressas pela expressão regular x(y|z)(x|y|z)*z. Apresente em suas anotações todos os passos intermediários para a obtenção de sua resposta.



Aplique o procedimento de mininização de estados e a apresente a máquina de estados finitos com o número mínimo de estados para o autômato descrito pela seguinte tabela de transições. Apresente em suas anotações todos os passos intermediários para a obtenção de sua resposta.

s0 s1 s2 s3 s4
0 s1 s2 s1 s1 s2
1 s3 s3 s4 s4 s3

Estado inicial: s0

Estados finais: { s3, s4 }



Os arranjos (ou vetores) Tn abaixo apresentados devem ser ordenados pelo algoritmo quicksort mostrado no quadro. Neste algoritmo, SWAP troca o conteúdo das duas posições indicadas e os termos “init” e “end” indicam as posições inicial e final do arranjo a ser ordenado, valendo 0 e 7, respectivamente, antes do início do algoritmo. Aplique o algoritmo de ordenação passo a passo nos dois vetores. Em seguida mostre qual é o número total de operações de comparação (X>Y e X<Y) que foram executadas nos dois casos e explique o motivo pelo qual a afirmação a seguir está (ou não está) correta: este algoritmo tem sempre uma complexidade de execução da ordem de O(n log2n), onde n é o número de elementos a ordenar.

QUIKSORT (T, init, end):

if init < end then

pos1 = init+1
pos2 = end
while true do
while T[pos1] < T[init] do
pos1 = pos1+1
while T[pos2] > T[init] do
pos2 = pos2-1
if pos1 < pos2 then
SWAP (pos1, pos2)
else
part = pos2
break
SWAP (init, part)
QUICKSORT (T, init, part-1)
QUICKSORT (T, part+1, end)

Arranjo T1: (11, 8, 22, 13, 2, 5, 4, 9)

Arranjo T2: (2, 4, 5, 8, 9, 11, 13, 22)



Apresente uma expressão regular que descreva números binários de comprimento arbitrário mas sempre terminados com o símbolo “B” e o autômato finito não-determinístico para a mesma, mostrando os detalhes de cada passo seguido na sua construção.



O que é uma árvore sintática?



Mostre a derivação e a construção descendente de uma árvore sintática com pelo menos 10 nós que represente uma sentença gerada pela gramática G = ( {0,1} , {S} , P , S ), onde P={S → 0S1 , S → ε}



Considere o seguinte trecho de um programa em C++, que manipula um objeto 'f' declarado como global:

int f1(int n) {
   int p = f.size();
   f.insert(p, n);
   return p+1;
}

int f2( ) {
   int n = f[0];
   f.erase(0);
   return n;
}

(a) Descreva textualmente o que fazem as funções f1() e f2().

(b) Qual o tipo de estrutura definido na biblioteca STL de C++ é o mais adequado para o objeto 'f', considerando que este será manipulado apenas por f1() e f2()? Justifique sua resposta.

(c) Baseado na sua resposta ao item acima, introduza modificações nos códigos de f1() e f2() de modo a torná-los mais compactos e eficientes.



Uma gramática com símbolo sentencial S e símbolos terminais 0 e 1 tem as seguintes produções:

S → 0 S 1

S → 1

Para esta gramática, a seguinte tabela de deslocamento e redução (tabela DR) foi obtida:

0 1 $
S D (Acc)
0 S S
1 R R
$ S S

(a) Mostre como a sentença 00111 é processada pelo analisador de deslocamento e redução com esta tabela associada. Para cada passo, mostre a estrutura de pilha, a sentença e a próxima ação (D ou R).

(b) Apresente a árvore gramatical correspondente ao reconhecimento da sentença 00111, indicando em que ordem os nós foram criados no processo de reconhecimento usando este analisador.

(c) Que tipo de derivação canônica está associada ao reconhecimento de uma sentença ao se utilizar um analisador de deslocamento e redução? Apresente esta derivação para a sentença 00111.

(d) Mostre como a tabela DR foi obtida.




A tabela abaixo é uma estrutura equivalente a uma lista ligada. A primeira coluna é a chave do nó e a segunda coluna indica a posição na tabela do próximo nó. A primeira posição da tabela (0) aponta o primeiro nó da lista; um valor 0 para próximo nó indica o fim da lista. Não é apresentada uma estrutura auxiliar que contém, em ordem, as posições na tabela que correspondem a nós disponíveis.

posição	chave	próximo
0	-	3
1	9	2
2	2	0
3	5	7
4	7	0
5	1	4
6	4	2
7	3	1

(a) Apresente a estrutura da lista acima usando a notação gráfica usual para listas ligadas.

(b) Considerando sempre como ponto de partida a tabela original, mostre a tabela resultante após a execução das seguintes operações de lista:

(i) retirar da lista: removeNode(3)
(ii) inserir no início da lista: insertNode(4)
(iii) inserir no final da lista: appendNode(6)

(c) Usando os procedimentos para manipular uma tabela T, tais como insertTableAt, getKey, getValue e numberOfElements, descreva o algoritmo para o procedimento appendNode.



Dado que o campo "chave" tem quatro bits de largura, mostre na tabela abaixo o efeito de cada passo da aplicação do algoritmo radixSort para ordenar essas chaves usando em cada passo um campo de dois bits para a contagem.

Posição	chave
1	9			
2	2			
3	5			
4	7			
5	1			
6	4			
7	3			


Os componentes centrais de um compilador são os analisadores léxico e sintático.

a) no que consiste as análises léxica e sintática?

b) como a análise léxica e sintática são integradas no compilador?

c) cite dois exemplos de erros produzidos por cada analisador.

d) explique, de forma intuitiva, porque a análise sintática é bem mais complexa que a análise léxica.



Considere o seguinte programa escrito em C, que não apresenta erros de compilação e gera com sucesso código executável:

1 #include <stdio.h>
2 main(int argc, char *argv[]) {
3 FILE *b, *c;
4 b = fopen(argv[1],"r");
5 c = fopen("a","w");
6 do fputc(fgetc(b),c);
7 while(!feof(b));
8 }

O que acontece quando o executável gerado for invocado

(a) sem argumentos na linha de comando;

(b) com um argumento que é o nome de um arquivo existente; e

(c) com um argumento que é o nome de arquivo que não existe?

(d) Modifique o programa de forma a incluir tratamento para todas as condições de erro.



Considere a gramática G com Vn = {S, A,B,C}, Vt = {x, y, z}, símbolo sentencial S e as seguintes produções (ε é a string vazia):

R1: S → AxByC

R2: A → xAx

R3: A → ε

R4: B → By

R5: B → ε

R6: C → zAz

Para a sentença x x x y y z x x z, apresente

(a) a derivação canônica mais à direita;

(b) a derivação canônica mais à esquerda; e

(c) a árvore sintática.



Dada a expressão regular (xx)*(y|z)zz*

(a) Construa, usando o método da construção de Thompson, o autômato finito não-determinístico que reconhece as seqüências de símbolos que formam sentenças na linguagem regular correspondente.

(b) Converta o autômato do item (a) para um autômato finito determinístico usando o método da construção de subconjuntos.

(c) Converta o autômato finito determinístico obtido para outro equivalente com o menor número possível de estados.



Represente, usando a notação formal para gramáticas, a linguagem descrita pela expressão regular aa*bb*.

Apresente a mesma gramática utilizando a notação de grafos sintáticos e a notação BNF (padrão, sem extensões).



Aplique o algoritmo de Thompson, o método da construção de subconjuntos e o procedimento de minimização de estados para desenvolver o autômato finito com número mínimo de estados para reconhecer sentenças descritas pela expressão regular aa*bb*.



Desenvolva o analisador sintático de precedência fraca para reconhecer sentenças da gramática G = ( {b, e, s}, { C, Z}, P, Z) com o conjunto de produções P com os seguintes elementos:

Z → b C e

C → s

C → s Z

Mostre como o analisador opera para reconhecer a sentença bsbsee.

Ferramentas pessoais