Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P1 2016

Prévia do material em texto

GABARITO
PCS3110 - Algoritmos e Estrutura de Dados para Engenharia Elétrica Prova 1 - 02/09/2016
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: �. Não use �.
1
Anna
2
Fábio
3
Romero
4
Anarosa
Marque as caixas ao lado para formar o seu número USP e escreva seu nome
abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instruções para a prova
1 Esta prova contém 2 questões dissertativas e 8 testes. Verifique atentamente se todas elas estão presentes. Em
caso de dúvida chame o professor.
2 Preencha seu nome e número USP. Provas não identificadas não serão corrigidas.
3 Resolva as questões dissertativas apenas no espaço a elas reservado. Respostas fornecidas fora do local a elas
destinadas não serão corrigidas.
4 A duração total da prova é de 100 minutos.
5 É proibido o uso de calculadoras e qualquer outro aparelho eletrônico.
6 É proibido retirar o grampo da prova.
7 A interpretação da questão faz parte da avaliação dos alunos. Caso considere alguma hipótese que não esteja
explicitada no enunciado, indique claramente na resposta.
8 A prova é SEM CONSULTA.
GABARITO
[2,7 pontos] Questão 1
Os algoritmos A e B apresentados a seguir têm como entradas duas variáveis inteiras x e y, com y ≥ 0. As tabelas de
rastreamento de ambos algoritmos encontram-se abaixo deles. A linha 1 da tabela de rastreamento indica os conteúdos
imediatamente após a chamada do algoritmo, ANTES da execução do primeiro passo do algoritmo.
A (x, y)
1 p = 1
2 i = y
3 while i ≥ 1
4 p = p * x
5 i = i - 1
6 return p
B (x, y)
1 if y ≤ 0
2 return 1
3 if y mod 2 == 0
4 p = B(x, y / 2)
5 return p * p
6 else p = B(x, (y - 1) / 2)
7 return p * p * x
Rastreamento para A(2,4)
PT PA x y p i i ≥ 1 A()
1 2 4
2 1 1
3 2 4
4 3 true
5 4 2
6 5 3
7 3 true
8 4 4
9 5 2
10 3 true
11 4 8
12 5 1
13 3 true
14 4 16
15 5 0
16 3 false
17 6 16 16
18 4 2
19 5 return 4
20 4 4
Rastreamento para B(2,4)
PT PA y ≤ 0 x y p y mod 2 == 0 B()
1 2 4
2 1 false
3 3 true
4 4 B(2,2) incompleto
5 2 2
6 1 false
7 3 true
8 4 B(2,1) incompleto
9 2 1
10 1 false
11 3 false
12 6 B(2,0) incompleto
13 2 0
14 1 true
15 2 return 1
16 6 1
17 7 return 2
18 4 2
19 5 return 4
20 4 4
GABARITO
a [0,6 pontos] Complete a tabela de rastreamento para A(2,4) até o algoritmo parar ou que o passo 20 do
rastreamento seja atingido, o que acontecer primeiro.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3 6
b [0,8 ponto] Complete a tabela de rastreamento para B(2,4) até o algoritmo parar ou que o passo 20 do rastrea-
mento seja atingido, o que acontecer primeiro.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 8
c [0,3 ponto] O que faz o algoritmo A(x,y)? Calcula xy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3
d [0,3 ponto] O que faz o algoritmo B(x,y)? Calcula xy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3
e [0,5 ponto] Complete o número de vezes que cada passo do algoritmo A(a,b) é executado. Apresente o número
total de passos em função de a e b.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 5
A(a,b)
Passo Instrução # de vezes
1 p = 1 1
2 i = y 1
3 while i ≥ 1 b+1
4 p = p*x b
5 i = i - 1 b
6 return p 1
Número total de passos 1+1+b+1+b+b+1 = 3b+4
executados:
GABARITO
f [0,2 ponto] Complete o número de vezes que cada passo do algoritmo B(a,b) é executado, supondo que b é
potência de 2. Apresente o número total de passos em função de a e b.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2
B(a,b)
Passo Instrução # de vezes
1 if y ≤ 0 log2b+ 2
2 return 1 1
3 if y mod 2 == 0 log2b+ 1
4 p = B(x, y/2) log2b
5 return p*p log2b
6 else p = B(x, (y-1)/2) 1
7 return p*p*x 1
Número total de passos log2b+ 2 + 1 + log2b+ 1 + log2b+
executados: +log2b+ 1 + 1 = 4log2b+ 6
[2,5 pontos] Questão 2
GABARITO
a [1,0 ponto] A Profa. Anna e seu assistente recolheram as provas de PCS3110 e cada um organizou uma pilha
ordenada (ordem numérica, menor no topo) das provas que recolheu. Agora, precisam unir as duas pilhas de
provas, pilha A e pilha B, de forma ordenada (menor no topo) para correção das provas. Para isso, escreveram
um algoritmo em pseudocódigo usando apenas as operações básicas Push(S, k), Pop(S) e Stack-Empty(S),
acrescidas pela função: Top(S), que retorna o valor do elemento no topo da pilha, sem desempilhá-lo. Complete
o pseudocódigo MergeSortedStacks(A, B) dado a seguir.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3 5 10
MergeSortedStacks(A, B)
1 Seja C uma nova pilha
2 while not Stack-Empty(A) and not Stack-Empty(B)
3 if Top(A) < Top(B)
4 Push(C, Pop(A))
5 else
6 Push(C,Pop(B))
7 if Stack-Empty(A)
8 while not Stack-Empty(B)
9 Push(C, Pop(B))
10 else
11 while not Stack-Empty(A)
12 Push(C, Pop(A))
13 Seja D uma nova pilha
14 while not Stack-Empty(C)
15 Pusc(D, Pop(C))
16 return D
GABARITO
b [0,5 pontos] Seja uma fila Q não vazia de números inteiros. Complete o algoritmo em pseudocódigo abaixo,
FindMax(Q), que encontra o máximo na fila Q. Só é permitido usar as operações básicas Enqueue(Q, k),
Dequeue(Q) e Queue-Empty(Q), acrescidas pela função Size(Q) que retorna o tamanho da fila. A fila deve
permanecer intacta depois de encontrar o elemento com valor máximo, o qual deve ser retornado por FindMax(Q).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3 5
FindMax(Q)
1 max = Dequeue(Q)
2 Enqueue(Q,max)
3 i = 1
4 while i < Size(Q)
5 next = Dequeue(Q)
6 if next > max
7 max = next
8 Enqueue(Q, next)
9 i = i + 1
10 return max
c [1,0 ponto] Sejam uma pilha S e uma fila Q inicialmente vazias, com S.topo = 0 e Q.inicio == Q.fim == 1.
Indique o conteúdo da pilha e da fila após a execução da seguinte sequência de operações:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 3 5 10
Push(S,`P'), Push(S,`E'), Push(S,`R'), Push(S,`U'), Push(S,`P'), Enqueue(Q, Pop(S)),
Enqueue(Q, Pop(S)), Push(S, Dequeue(Q)), Push(S,`S'), Push(S, Dequeue(Q)),
Enqueue(Q, Pop(S)), Enqueue(Q, Pop(S)), Enqueue(Q, Pop(S)), Pop(S).
[4,8 pontos] Testes
GABARITO
Teste 1 Na implementação de fila usando arranjo,ao invés de deixar uma posição desocupada para diferenciar se a
fila está cheia ou vazia, uma outra solução é ter um dado satélite na fila que representa se ela está vazia (um booleano
vazia). Como deve ser completada a linha 4 de Enqueue e a linha 7 de Dequeue para implementar a fila dessa forma,
considerando que o dado satélite vazia é iniciado com TRUE?
A
4 // Vazio
7 Q.inicio == Q.tamanho
B
4 Q.vazia = FALSE
7 Q.inicio == Q.fim
C
4 Q.vazia = FALSE
7 Q.inicio == Q.tamanho
D
4 Q.vazia = FALSE
7 Q.inicio 6= Q.fim
E
4 // Vazio
7 Q.inicio 6= Q.fim
Dequeue (Q)
1 if Q.inicio == Q.fim and
Q.vazia
2 error �underflow�
3 k = Q[Q.inicio]
4 if Q.inicio == Q.tamanho
5 Q.inicio = 1
6 else Q.inicio == Q.inicio +
1
7 if
8 Q.vazia = TRUE
9 return k
Enqueue (Q, k)
1 if Q.inicio == Q.fim and
not Q.vazia
2 error �overflow�
3 Q[Q.fim] = k
4
5 if Q.fim == Q.tamanho
6 Q.fim = 1
7 else Q.fim = Q.fim + 1
Teste 2 Como devem ser preenchidas as lacunas das linhas 5 e 6 para que seja implementada a função
Remove-Duplicados(L)? Essa função deve remover da lista L os elementos que possuem chaves iguais, deixando
na lista apenas o elemento com a primeira ocorrência da chave.
A
5 x.proximo.proximo.chave == atual.chave
6 x = x.proximo.proximo
B
5 x.proximo.chave == atual.chave
6 x = x.proximo.proximo
C
5 x.chave == atual.chave
6 x = x.proximo.proximo
D
5 x.proximo.chave == atual.chave
6 x.proximo = x.proximo.proximo
E
5 x.proximo.proximo.chave == atual.chave
6 x.proximo = x.proximo.proximo
Remove-Duplicados (L)
1 atual = L.inicio
2 while atual 6= NIL
3 x = atual
4 while x.proximo 6= NIL
5 if
6
7 else x = x.proximo
8 atual = atual.proximo
Teste 3 Considere o algoritmo SR(V, n), onde V é um vetor de inteiros e n é um inteiro positivo. Assinale a
alternativa errada:
A
Apenas uma das outras alternativas está errada.
B
O algoritmo SR(V,n) usa o método de divisão e con-
quista em seu projeto.
C
A chamada SR([1,2,3],3) tem saída 5.
D
SR(V,n) é um algoritmo recursivo com condição de
parada n == 1.
E
SR(V,n) calcula a soma dos n elementos do vetor V.
SR (V, n)
1 if n == 1
2 return V[1]
3 return SR(V, n-1) + V[n]
GABARITO
Teste 4 Considere as operações de inserção e remoção numa tabela Hash com colisões tratadas por encadeamento,
onde cada lista que trata as colisões é duplamente ligada. Assinale a alternativa que apresenta as instruções adequadas
para o preenchimento dos passos dos algoritmos deixados em branco.
Hash-Insert(T,x)
1 j = h(x.chave)
2
3 if
4 T[j].anterior = x
5 T[j] = x
6
Hash-Delete(T,x)
1 if
2 x.anterior.proximo = x.proximo
3 else
4 if
5 x.proximo.anterior = x.anterior
Podemos afirmar que:
A
(Hash-Insert) 1. x = T[j], 3. T[j] 6= NIL, 6. // vazio
(Hash-Delete) 1. x 6= NIL, 3. T[j].inicio.proximo = x.proximo, 4. x.proximo == NIL
B
(Hash-Insert) 1. x.proximo = T[j], 3. T[j] 6= NIL, 6. x.anterior = NIL
(Hash-Delete) 1. x.anterior 6= NIL, 3. T[j].inicio = x.proximo, 4. x.proximo 6= NIL
C
(Hash-Insert) 1. x.proximo = T[j], 3. T[j] == NIL, 6. x.anterior = T[j].inicio
(Hash-Delete) 1. x.anterior 6= NIL, 3. T[j].inicio = x.proximo, 4. x.proximo 6= NIL
D
(Hash-Insert) 1. x.proximo = T[j], 3. T[j] 6= NIL, 6. x.anterior = NIL
(Hash-Delete) 1. x 6= NIL, 3. T[j].inicio = x.proximo, 4. x.proximo == NIL
E
nenhuma das outras alternativas é correta.
Teste 5 Considere um editor de texto que possui os seguintes comandos Digitar <caractere>, que insere um
caractere no texto, e Apagar, que apaga o último caractere digitado. Para implementar a função desfazer (undo),
o editor usa uma pilha S para empilhar os comandos executados; desfazer corresponde a desempilhar o comando da
pilha, além de alterar o texto (desfazendo o comando). Qual alternativa apresenta o conteúdo da pilha S e o texto
resultante no editor após a execução das seguintes operações? Considere que o topo da pilha é o elemento mais a
direita.
Push(S, Digitar `a'), Push(S, Digitar `b'), Push(S, Digitar `c'), Pop(S), Push(S, Apagar),
Push(S, Digitar `d'), Push(S, Apagar), Pop(S)
A
Pilha: Digitar `a', Digitar `b', Apagar
Texto: a
B
Pilha: Digitar `a', Digitar `b', Digitar `d'
Texto: abd
C
Pilha: Digitar `d', Apagar, Digitar `b', Digitar `a'
Texto: ad
D
Pilha: Digitar `d', Digitar `b', Digitar `a'
Texto: dba
E
Pilha: Digitar `a', Digitar `b', Apagar, Digitar `d'
Texto: ad
GABARITO
Teste 6 Considere a chamada Selection([5,3,8,2],1) do algoritmo Selection(A, inicio) dado a seguir.
Podemos afirmar que, na segunda vez que o passo 10 do
algoritmo é iniciado, a chamada será:
A
Selection([2,3,8,5],3).
B
Selection([2,3,8,5],2).
C
Selection([3, 5, 8, 2],2).
D
Nenhuma das outras alternativas é correta.
E
Selection([3, 5, 8, 2],3).
Selection (A, inicio)
1 if inicio >= A.tamanho
2 return
3 menor = inicio
4 for j = inicio + 1 to A.tamanho
5 if A[j] < A[menor]
6 menor = j
7 temporario = A[menor]
8 A[menor] = A[inicio]
9 A[inicio] = temporario
10 Selection(A, inicio+1)
Teste 7 Seja Q uma fila circular implementada usando lista ligada. Podemos afirmar que:
A
As operações a seguir permitem retirar um elemento de uma fila com pelo menos 2 elementos, mantendo sua
característica de fila circular:
resposta = Q.inicio Q.fim.proximo = Q.inicio Q.inicio.proximo = Q.fim
B
As operações a seguir permitem inserir x numa fila não vazia, mantendo sua característica de fila circular:
x.proximo = Q.inicio Q.fim.proximo = Q.inicio.proximo
C
As operações a seguir permitem retirar o último (único) elemento da fila, esvaziando-a e mantendo sua caracte-
rística de fila circular:
if Q.fim == Q.inicio
resposta = Q.inicio Q.fim = NIL Q.inicio = NIL
D
Suponha que a fila está vazia. A sequência de operações para inserir x na fila é:
Q.inicio = x Q.fim = NIL x.proximo = x
E
Nenhuma das outras alternativas é correta.
Teste 8 Considere uma tabela Hash usando um arranjo de 5 posições, função de hash h(k) = k mod 5 e colisões
tratadas por sondagem linear (linear probing). Qual é a tabela resultante da inserção das chaves 123, 88, 72, 25 e 17,
nesta ordem?
A
[ 25 | NIL | 17 | 88 | 123 | 72 ]
B
[ 72 | 25 | 17 | 123 | 88 ]
C
[ 25 | NIL | 72 | 123 | 88 | 17 ]
D
[ 17 | 25 | 72 | 88 | 123 ]
E
[ 25 | 17 | 72 | 123 | 88 ]