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

Prévia do material em texto

y +1/1/60+ y
PCS3110 - Algoritmos e Estruturas de Dados para a Engenharia Elétrica Prova 1 - 01/09/2017
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
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 Marcos 2 Fábio 3 Romero 4 Anarosa
Marque as caixas ao lado para formar o seu número USP, as caixas acima para
sua turma e 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. Alunos cujos NUSP possuem
7 dígitos devem iniciar o preenchimento com um ZERO, da esquerda para a direita.
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, relógios, incluindo analógicos e/ou mecânicos 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.
y y
y +1/2/59+ y
[2,6 pontos] Questão 1
Suponha o algoritmo A, cujo código é fornecido,
que recebe e manipula uma lista duplamente ligada.
Suponha ainda o uso da função List-Delete(L,x),
que apaga de L o elemento apontado por x.
a) [valor 1,6 pontos] Continue (na outra folha) o
rastreamento para A (L), preenchendo as linhas 16
a 30 (caso o algoritmo não termine no passo 30 não
precisa prosseguir o rastreamento após essa linha).
Para indicar na tabela um determinado elemento
use o valor da respectiva chave entre chaves. Por exem-
plo: o conteúdo de L.inicio, que é um ponteiro para o
elemento que possui chave de valor 20, deve ser repre-
sentado por {20}.
Obs: PR = Passo do Rastreamento; PA = Passo do
Algoritmo.
Suponha a lista L inicialmente com a configuração
abaixo.
A (L)
1 if L.inicio.proximo == NIL
2 print L.inicio.chave
3 else
4 e = L.inicio; m = e; c = e.chave
5 while e.proximo 6= NIL
6 e = e.proximo
7 if c > e.chave
8 c = e.chave; m = e
9 print c
10 List-Delete(L, m)
11 A(L)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6 7 8 9 10 20
b) [valor 0,5 pontos] O que será impresso após a execução completa do algoritmo A ?
05 10 20
c) [valor 0,5 pontos] Qual o objetivo do algoritmo A ?
Imprimir em ordem crescente as chaves de todos os elementos da lista, eliminando todos os elementos da lista durante
o processo, exceto um que possuir a chave com maior valor.
y y
y +1/3/58+ y
PR PA L e m c L.inicio.proximo e.proximo c > Observação
== NIL 6= NIL e.chave
1a. chamada
1 { 20, 05, 10 } de A
2 1 FALSE
3 4 {20} {20} 20
4 5 TRUE
5 6 {05}
6 7 TRUE
7 8 {05} 05
8 5 TRUE
9 6 {10}
10 7 FALSE
11 5 FALSE
12 9 "Imprime"05
13 10 {20, 10} Apaga {05} de L
Passo não
14 11 completado
2a. chamada
15 {20, 10} de A
16 1 FALSE
17 4 { 20 } { 20 } 20
18 5 TRUE
19 6 { 10 }
20 7 TRUE
21 8 { 10 } 10
22 5 FALSE
23 9 Imprime 10
24 10 {20} Elimina 10
passo não
25 11 completado
26 3a. chamada de A
27 1 TRUE
28 2 Imprime 20
retorna
29 11 PR 25
retorna
30 11 PR 14
y y
y +1/4/57+ y
[2,6 pontos] Questão 2
Atualmente, sistemas de gerenciamento de senhas não registram as senhas propriamente ditas, mas sim seus embara-
lhamentos. Um exemplo de algoritmo que faz este tipo de embaralhamento é o SHA2. Suponha que um tal sistema
usa uma Tabela Hash T, com uma função hash h(chave) e resolução de conflito por encadeamento definido por listas
duplamente ligadas para gerenciar os pares (login, senha). Cada elemento x armazenado em T é, na verdade, um par
(login,senhaEmbaralhada)).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6 7 8 9 10 20
a) [valor 0,6 pontos] Complete a função Autentica(T , x) que recebe a tabela T e o apontador x para o elemento
a ser autenticado e devolve TRUE, se a senha for identificada como pertencente àquele login, ou FALSE caso contrário.
Autentica (T, x)
1 y = T[ h(x.login)]
2 while y 6= NIL and y.login 6= x.login
3 y = y.proximo
4 if x.senha == y.senha
5 return TRUE
6 return FALSE
b) [valor 0,4 pontos] Descreva o que acontece durante a execução das linhas 2 e 3 da função Autentica (T,x)
Nestas linhas acontece a busca pelo elemento apontado por x para verificar se o login dado como entrada encontra-se
armazenado na lista ligada encabeçada por T[h(x.login)]. Como o elemento é composto pelo login e pela senha
embaralhada, a busca é feita pelo login armazenado em x. Se ele for encontrado estará em y.login, caso contrário y
== NIL.
c) [valor 0,9 pontos] Complete a função RecuperaSenha(T, login, email), que recebe a tabela, o login e o email
do usuário que requisitou nova senha, cria nova senha, encontra o usuário que requisitou nova senha, troca a informação
sobre a senha na tabela e envia ao usuário um e-mail com a nova senha. Supõe-se que o email foi verificado como
pertencente ao usuário antes que esta função seja invocada pelo sistema. Usamos as funções ListSearch(), que faz
busca em uma lista ligada vista em sala de aula, geraSenha() que gera uma senha embaralhada aleatoriamente e
EnviaEmail(email, senha), que envia o conteúdo “senha” para o e-mail “email”.
Soluções possíveis:
RecuperaSenha (T, login, email)
1 j = h(login)
2 passw = geraSenha()
3 x = List-Search (T[j], login)
4 x.senha = SHA2(passw)
5 return EnviaEmail (email, passw)
RecuperaSenha (T, login, email)
1 j = login
2 passw = geraSenha()
3 x = List-Search (T[h(j)], j)
4 x.senha = SHA2(passw)
5 return EnviaEmail (email, passw)
y y
y +1/5/56+ y
d) [valor 0,7 pontos] Considere uma tabela Hash com encadeamento, que armazena os pares (login, senha) conforme
descrito acima, onde os logins são definidos por sequências de 4 dígitos decimais entre 0 e 4.
Para h a função hash que, a cada sequência de 4 dígitos decimais atribui a soma dos dígitos da sequência, dese-
nhe a tabela resultante, ao final da execução da sequência de operações: Chained-Hash-Insert(T,{0012, ab34@}),
Chained-Hash-Insert(T,{3214, 6tr54}), Chained-Hash-Insert(T,{0023, kinG2}), Chained-Hash-Insert(T,{1002,
fi3*1}), Chained-Hash-Insert(T,{1004, kh8@0}), Chained-Hash-Insert(T,{3020, zl*3e}),
Chained-Hash-Insert(T,{1234, gh*s2}).
Chained-Hash-Insert (T,x)
1 j = h(x.chave)
2 x.proximo = T[j].inicio
3 if T[j].inicio 6= NIL //lista não vazia
4 T[j].inicio.anterior = x
5 T[j].inicio = x
6 x.anterior = NIL
exemplo de elemento da Tabela Hash
(0132,8f*2@)
0 −→ (1234 gh*s2) ←→ (3214 6tr54)
1 −→
2 −→
3 −→
4 −→ (1002 fi3*1) ←→ (0012 ab34@)
5 −→
6 −→ (3020 zl*3e) ←→ (1004 kh8@0) ←→ (0023 kinG2)
7 −→
8 −→
9 −→ .
y y
y +1/6/55+ y
[4,8 pontos] Testes
Teste 1 Arranjo é um conjunto estático de variáveis de um mesmo tipo, o qual é armazenado sequencialmente
na memória. Considere as seguintes afirmações sobre um arranjo de listas ligadas, ou seja, um arranjo em que cada
posição é uma lista ligada.
(I) Para obter a chave do segundo elemento da lista ligada na posição 2 do arranjo de listas ligadas A é necessário
fazer A[2].inicio.proximo.chave.(II) A quantidade de listas ligadas é estática, mas a quantidade de elementos em cada uma é dinâmica.
(III) As funções List-Insert e List-Delete precisam ser alteradas para que elas possam funcionar corretamente
com listas ligadas que estão em um arranjo.
A Nenhuma afirmação é correta.
B Apenas as afirmações I e II são corretas.
C Apenas as afirmações I e III são corretas.
D Todas as afirmações são corretas.
E Apenas a afirmação I é correta.
F Apenas a afirmação III é correta.
G Apenas a afirmação II é correta.
H Apenas as afirmações II e III são corretas.
Teste 2 A seguir é apresentado o algoritmo Crescente(L) que verifica se uma lista ligada L está em ordem crescente.
Crescente (L)
1 return Crescente-Auxiliar(L.inicio)
Crescente-Auxiliar (e)
1 if e == NIL or e.proximo == NIL
2 return TRUE
3 return e.chave ≤ e.proximo.chave and
Crescente-Auxiliar(e.proximo)
Considere as seguintes afirmações:
(I) Para verificar se uma lista ligada está em ordem decrescente, é só trocar o ≤ da linha 3 em Crescente-Auxiliar
para ≥.
(II) O caso base da recursão em Crescente-Auxiliar poderia ser simplesmente e == NIL.
(III) A função Crescente não é recursiva, mas a função Crescente-Auxiliar é.
(IV) O resultado da função é o mesmo se trocarmos a ordem das condições e.chave ≤ e.proximo.chave e
Crescente-Auxiliar(e.proximo), na linha 3 de Crescente-Auxiliar.
A Apenas as afirmações II e IV são corretas.
B Apenas as afirmações I, III e IV são corretas.
C Apenas a afirmação IV é correta.
D Apenas as afirmações II, III e IV são corretas.
E Apenas a afirmação I é correta.
F Apenas as afirmações I e II são corretas.
G Apenas a afirmação III é correta.
H Todas as afirmações são corretas.
I Apenas as afirmações I e IV são corretas.
J Apenas as afirmações III e IV são corretas.
K Apenas a afirmação II é correta.
L Apenas as afirmações I, II e III são corretas.
M Nenhuma afirmação é correta.
N Apenas as afirmações I, II e IV são corretas.
O Apenas as afirmações II e III são corretas.
P Apenas as afirmações I e III são corretas.
y y
y +1/7/54+ y
Teste 3 Onde devem ser colocados os comandos Push(P, atual) e menor = Menor(P) para que o algoritmo
Menor(P) encontre recursivamente o menor elemento de uma pilha P e mantendo o conteúdo da pilha ao final do
algoritmo?
Menor (P)
1 if Stack-Empty(P)
2 error “Pilha vazia”
3
4 atual = Pop(P)
5
6 if Stack-Empty(P)
7 menor = atual
8
9 else
10
11 if atual < menor
12 menor = atual
13
14 return menor
A Push(P, atual): linha 5; menor = Menor(P): linha 10
B Push(P, atual): linha 10; menor = Menor(P): linha 5
C Push(P, atual): linha 5; menor = Menor(P): linha 3
D Push(P, atual): linha 13; menor = Menor(P): linha 5
E Push(P, atual): linha 13, menor = Menor(P): linha 10
Teste 4 Existem várias formas de implementar o conceito de uma fila usando arranjo de forma circular. Na forma
vista em aula, consideramos que o inicio é a posição do elemento a ser retirado da lista e o fim é a posição de inserção
do próximo elemento da fila. A seguir são apresentados os algoritmos Enqueue(Q, k) e Dequeue(Q) sem overflow e
underflow.
Enqueue (Q, k)
1 Q[Q.fim] = k
2 if Q.fim == Q.tamanho
3 Q.fim = 1
4 else Q.fim = Q.fim + 1
Dequeue (Q)
1 k = Q[Q.inicio]
2 if Q.inicio == Q.tamanho
3 Q.inicio = 1
4 else Q.inicio = Q.inicio + 1
5 return k
Considere uma outra implementação, na qual o fim representa o último elemento da fila. Quais alterações precisam ser
feitas nesses algoritmos?
A Enqueue: trocar a linha 1 para Q[Q.fim + 1] = k
Dequeue: Nada.
B Enqueue: colocar a linha 1 depois da linha 4.
Dequeue: trocar a linha 2 para Q.inicio = Q.tamanho + 1
C Enqueue: trocar a linha 1 para Q[Q.fim + 1] = k
Dequeue: trocar a linha 2 para Q.inicio = Q.tamanho + 1
D Enqueue: trocar a linha 2 para if Q.fim == Q.tamanho + 1
Dequeue: Nada.
E Enqueue: trocar a linha 2 para if Q.fim == Q.tamanho + 1
Dequeue: trocar a linha 2 para Q.inicio = Q.tamanho + 1
F Enqueue: colocar a linha 1 depois da linha 4.
Dequeue: Nada.
y y
y +1/8/53+ y
Teste 5 A tabela hash T a seguir tem capacidade de comportar 7 registros e trata colisões usando a estratégia
de endereçamento aberto: em caso de colisão, o registro é colocado na próxima célula vazia à direita (circularmente).
Assuma que a função de hash utilizada é: hash(chave) = chave mod T.tamanho. DEL indica que o conteúdo da célula
foi apagado anteriormente.
Dado o estado da tabela mostrado, assinale a opção que mostra corretamente o seu conteúdo após a execução dos seguin-
tes da seguinte sequência de operações: Hash-Insert(T, 40) ; Hash-Insert(T, 7) ; Hash-Delete(T, 20) ; Hash-Insert(T, 17).
T: / / / 73 DEL 12 20
A T: 7 DEL / 17 73 40 12
B T: 7 / / 17 DEL 40 DEL
C T: 40 7 / 73 17 12 DEL
D T: 7 / 17 17 DEL 12 /
E T: 40 7 17 73 DEL 12 /
Enunciado para testes que usam a estrutura SQ
Deseja-se construir uma estrutura de dados SQ, que possa operar como fila ou como pilha. Para isso, é usada
uma lista ligada simples e não circular sobre a qual são implementadas as operações Push, Pop, Enqueue e Dequeue,
conforme mostrado a seguir:
Push (SQ, x)
1 x.proximo = SQ.inicio
2 SQ.inicio = x
Enqueue (SQ, x)
1 Push(SQ,x)
1 (SQ)
1 x = SQ.inicio
2 if x 6= NIL
3 2 = 3
4 return x
4 (SQ)
1 x = SQ.inicio
2 if x == NIL //vazio
3 return NIL
4 if x.proximo == NIL
5 5
6 return x
7 while x.proximo.proximo 6= NIL
8 x = x.proximo
9 ultimo = 6
10 6 = NIL
11 return ultimo
Teste 6 Como devem ser preenchidas?
1 ?
A Pop
B Dequeue
2 ?
A L.inicio
B x.proximo
C x
D x.chave
E x.proximo.proximo
3 ?
A x
B L.inicio
C NIL
D x.proximo.proximo
E x.proximo
Teste 7 Como devem ser preenchidas?
4 ?
A Pop
B Dequeue
5 ?
A L.inicio = NIL
B x =x.proximo
C x = NIL
D L.inicio = x
E L.inicio = x.proximo
6 ?
A x.proximo.proximo
B x.chave
C x.proximo
D L.inicio
E xy y
y +1/9/52+ y
Teste 8 Deseja-se alterar a implementação da fila/pilha SQ, substituindo a lista ligada simples por uma lista duplamente
ligada. Assinale as alternativas que preenchem corretamente as lacunas para que a operação Push seja implementada.
Push (SQ, x)
1 x.proximo = SQ.inicio
2 SQ.inicio = x
3 x.anterior = 1
4 if x.proximo 6= NIL
5 2 = 3
Como devem ser preenchidas?
1 ?
A x
B x.proximo.anterior
C L.inicio
D NIL
E x.proximo
2 ?
A x
B L.inicio
C NIL
D x.proximo.anterior
E x.proximo
3
A x.proximo.anterior
B L.inicio
C x.proximo
D NIL
E x
y y