Exercícios de revisão para segunda prova - parte 2 - 2018

Prévia do material em texto

URI - Erechim – Revisão Prova 2 de Alg. e E.D. III T 2017 prof. Neilor 
Nos próximos exercícios utilize a tabela abaixo ou indique, por exemplo CHR(3) se não quiseres desenhar o caracter “♥”
Caracter ☺ ☻ ♥ ♦ ♣ ♠ • ◘ ○ ◙ ♂ ♀ ♪ ♫ ☼ ► ◄ ↕ ‼ ¶ § ▬ ↨ ↑ ↓ → ← ∟ ↔
Valor ASCII 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Considerando os seguintes textos (desconsidere as aspas mas considere espaços se houverem):
Texto 1: “paralelepipedos polidos” Texto 2: “00000119700” Texto 3: “0001 bbbbbb111700000” --> o “b”
indica espaço em branco
Resolva as próximas questões: 
1) Comprima o Texto2 utilizando compactação de meio byte. 
2) Utilize a técnica de Comprimento de fileira (run-lenght) para comprimir o Texto3. Neste caso, o caractere especial que
indica a compressão é o caractere arroba (@). 
3) construa a tabela de Shannon-Fano para o texto 1. 
4. Considerando a árvore de Huffman ao lado:
 
que sequência de letras é representada em apenas 2 bytes por 0000101110010001 ?
5) Considere uma tabela de espalhamento (tabela hash) de comprimento m= 11, que usa endereçamento aberto (open 
addressing), a técnica de tentativa linear (linear probing) para resolver colisões e com a função de dispersão (função 
hash) h(k) = k mod n, onde k é a chave a ser inserida. Considere as seguintes operações sobre essa tabela: Inserção das 
chaves 3, 14, 15, 92, 65, 35 (nesta ordem); Remoção da chave 15; e Inserção da chave 43. Escolha a opção que 
representa esta tabela após estas operações:
a) 43 – ø – 35 – 3 – 14 – X – 92 – ø – ø – ø – 65
b) 65 – ø – 35 – 14 – ø – 92 – 3 – ø – ø – ø – 43
c) 43 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 65
d) 65 – ø – 35 – X - 14 – 92 – 3 – ø – ø – ø – 43
e) 65 – ø – 35 – 3 – 14 – 92 – ø – ø – ø – ø – 43
A
DM
E
I
T ONS
0 1
6) Ao usar o cálculo de endereço ou hashing, geralmente é necessário o uso de um método de tratamento de colisões.
Sobre esse método, é correto afirmar:
a) O tratamento de colisões é necessário apenas quando a tabela está cheia e se necessita inserir mais uma chave.
b) O tratamento de colisões é necessário para determinar o local da chave no momento da inserção na tabela.
c) O tratamento de colisões é necessário quando a tabela está vazia, pois não é possível calcular o endereço diretamente 
nesse caso.
d) O tratamento de colisões é necessário quando a chave inserida ainda não existir na tabela de endereçamento.
e) O tratamento de colisões é necessário, pois o hashing gera repetição de endereço para diferentes chaves.
7) Hashing – Seu conceito é associar chaves de pesquisa a valores. Portanto identifique qual alternativa está correta:
a.( ) Objetivo é, a partir de uma chave complexa, fazer uma busca rápida e organizar.
b.( ) Os registros em uma tabela são dificilmente endereçados a partir de várias transformações textuais sobre a chave de
pesquisa.
c.( ) A função hash é a responsável por gerar um índice a partir de determinada chave, usando uma função matemática.
d.( ) A função hash é a responsável por gerar uma lista indexada a partir de determinada chave.
e.( ) Todas estão corretas.
8) Complete os 5 espaços da matriz T Abaixo, ao utilizar o algoritmo da Mochila, para uma mochila com capacidade de 5
kg e 4 objetos:
1 2 3 4
W 4 3 2 1
1 2 3 4
V 450 550 400 300
Matriz T [5][5]
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 0 450
2 0 0 0 550 550
3 0 0 400 550 550
4 0 300 400 850
9) Considerando o grafo abaixo:
a) Utilizando Dijkstra, apresente a árvore considerando o nodo 1 como origem e o nodo 9 como destino
b) Construa a MST utilizando kruskal 
1
4
5
6
7
5
22 9
3
17
6
7
3
8
6
7
8
7
19
8
3
43 7
25
15 5
8
4
9
2