CURSO DE TECNÓLOGO EM ANÁLISE E
DESENVOLVIMENTO DE SISTEMAS
TURMA 2008/1 – 3 PERÍODO / MÓDULO V
AVALIAÇÃO A2 – DATA 2/4/2009
ESTRUTURAS DE DADOS
2009/1
Dados de identificação do Acadêmico:
Nome: _______________________________________ Login:___________
CA:__________________ Cidade:____________________________UF____
CARTÃO – RESPOSTA
QUESTÃO
RESPOSTA
QUESTÃO
RESPOSTA
A
1
2
3
4
F
1
2
3
4
B
1
2
3
4
G
1
2
3
4
C
1
2
3
4
H
1
2
3
4
D
1
2
3
4
I
1
2
3
4
E
1
2
3
4
J
1
2
3
4
Dados de identificação do Tutor:
Nome: _______________________________________ Login:___________
CA:__________________ Cidade:__________________UF______________
INSTRUÇÕES:
 A prova está composta de 10 questões de A a J, e 4 alternativas enumeradas de 1 a 4.
 Utilize caneta esferográfica azul ou preta para preenchimento do cartão-resposta.
 O cartão-resposta deve ser preenchido, assinado, destacado e entregue ao Tutor.
 Questões rasuradas serão anuladas.
 Sem o devido preenchimento do CAMPO DE IDENTIFICAÇÃO, o cartão-resposta não terá validade.
 Somente terão acesso às notas lançadas no boletim os acadêmicos regularmente matriculados.
 Os acadêmicos têm três dias após a divulgação do gabarito oficial para requerer revisão de questões
(recursos). Devem constar os seguintes dados para análise: Tipo da avaliação, Etapa, identificação da
questão e justificativa do pedido. Mais esclarecimentos acerca dos procedimentos para pedidos de
Recursos acessem a página WWW.unitins.br/logisticaavaliacao.
_____________________________________
Assinatura do acadêmico
______________________________________
Assinatura do Tutor
__________________________________________, _____/_____/2009
Local
1
PROF.
ESTRUTURAS DE DADOS
ALEXANDRE ROSSINI
MARCELO RIBEIRO
MARCO ANTONIO
NAPOLEÃO PÓVOA
SILVANO MALFATTI
A. Dentro do contexto da teoria dos métodos de pesquisa em tabelas, analise as afirmativas a seguir.
i.
ii.
iii.
Tabelas são arquivos.
Um SGBD manipula arquivos, enquanto um editor de textos manipula apenas tabelas.
Portanto os termos são distintos.
A pesquisa em arquivos sequenciais tem seu algoritmo modificado para adaptar-se às
tabelas.
1. Apenas a afirmativa i está correta.
2. Apenas a afirmativa ii está correta.
3. Apenas as afirmativas i e ii estão correta.
4. Apenas as afirmativas ii e iii estão corretas.
COMENTÁRIO: A resposta é a alternativa 1 porque, dentro do contexto da teoria dos métodos de
pesquisa em tabelas, as tabelas são arquivos cujo formato interno é tabular. Nessa teoria podemos
nos referir tanto ao termo arquivo quanto tabela sem mudança de sentido. Assim, a afirmativa I
está correta, conforme, também, declarado no material impresso, e, a afirmativa II está incorreta.
A afirmativa III erra ao declarar sobre uma suposta mudança em seu algoritmo para adaptar-se às
tabelas, considerando-as diferentes dos arquivos. Desta forma, a Alternativa 1 está correta, pois
declara que apenas a afirmativa I é verdade.
B. Quais das técnicas de pesquisa necessitam obrigatoriamente que o conjunto de dados esteja
ordenado pelo campo chave?
1. Pesquisa sequencial e pesquisa binária.
2. Pesquisa binária e pesquisa por cálculo de endereço (hashing).
3. Pesquisa sequencial e pesquisa por cálculo de endereço (hashing).
4. Pesquisa binária e pesquisa sequencial com otimização por blocos.
COMENTÁRIO: A alternativa correta da questão é a de número 4. A pesquisa sequencial consiste
em passar por todos os registros um a um sem a necessidade de estarem ordenados. A pesquisa por
cálculo de endereço utiliza uma fórmula matemática aplicada sobre o dado de entrada para inserir
e buscar os dados. A pesquisa binária e a otimizada por blocos necessitam que os dados estejam
ordenados para que a busca possa ser dividida em subconjuntos.
C. A necessidade de compressão de dados é algo comumente relacionado à vida das pessoas. Sobre
os algoritmos de compressão, não é verdade que
1. o algoritmo de frequência de caracteres ocorre em nível de bytes e de Huffman em bits.
2. para implementar o algoritmo de Huffman é necessário utilizar uma árvore binária de busca.
3. a ideia por trás do algoritmo de Huffman e do LZW (Lempel-Ziv-Welch) é de substituir um ou
mais símbolos por códigos, para isso os códigos devem ser menores que as sequências
representadas por eles.
2
4. o algoritmo de frequência de caracteres é utilizado para compactar arquivos contendo texto
alfabético.
COMENTÁRIO: A resposta é a alternativa de número 2 porque para implementar o algoritmo de
Huffman é necessário utilizar uma árvore binária e não binária de busca. A alternativa 1 é
verdadeira porque: no algoritmo de frequência de caracteres, cada caractere é representado por
um byte e a compressão se dá pela redução de caracteres da mensagem original; no algoritmo de
Huffman a idéia é representar os símbolos que ocorrem com maior frequência com menos bits e os
que acontecem com menor frequência com mais bits (terceiro parágrafo da página 93 da apostila).
A alternativa 3 também é verdadeira. A afirmação encontra-se literalmente no primeiro parágrafo
do item 6.1 da página 90 da apostila. Por fim, a alternativa 4 também é verdade e pode ser
encontrado no terceiro parágrafo da página 97 da apostila: “Assim como no algoritmo de
Huffman, o LZW procura substituir sequências de símbolos por códigos. Para obter a compressão
de dados, os códigos devem ser menores que as sequências representadas por eles”.
D. Considere a árvore, a seguir, obtida a partir do algoritmo de Huffman e utilize o algoritmo para
decodificação. A sequência 1001101110 terá como resultado?
1. casta
2. casca
3. saca
4. tasca
COMENTÁRIO: A alternativa 1 é a correta. Para solucionar esta questão, primeiramente é
necessário saber que no Algoritmo de Huffman, ao percorrer a árvore, para cada visita a um filho
à esquerda, um 0 (zero) será obtido, por outro lado, cada visita a um filho à direita, um 1 é obtido
(página 96 da apostila). Dessa forma, para facilitar a visualização da árvore, temos:
Assim, basta percorrer a árvore respeitando os valores da sequência apresentada até que se
chegue a um nó folha. Sempre que chegar a um nó folha, inicia-se o percurso novamente pela raiz
até que se acabe a sequência a ser decodificada. Dessa forma, ao realizar a decodificação da
sequência: 1001101110 temos o “c” como primeiro caractere, pois o percurso da árvore dá-se
3
para a direita e logo para a esquerda (10) partindo da raiz. O segundo caractere é dado com
apenas uma visita para a esquerda (0) e temos o caractere “a”. Assim, resta ainda a parte em
negrito da sequência (1001101110). E novamente, partindo-se da raiz, o percurso dá-se para
direita, direita e então para a esquerda e chega-se ao nó folha “s”. Agora, a parte restante para
decodificação é 1110. Retomando o percurso a partir da raiz, o percurso dá-se para direita, direita
e direita. Novamente, chega-se a um nó folha, dessa vez o nó “t”. E assim, para concluir toda a
decodificação, resta apenas um dado da sequência, o 0 (zero). E partindo novamente da raiz,
ocorre apenas a visitação do nó folha “a”. Dessa forma, o resultado da decodificação é: “casta”.
E. Analise a expressão aritmética a seguir
(chave % 2) * 5
e considere que:
 a expressão é utilizada no método hash;
 a chave recebe valores inteiros;
 o resultado da expressão representa o endereço de um registro.
Nesse contexto, analise as afirmativas.
i.
ii.
iii.
A expressão utilizada não gera colisões para registros com valores inferiores a 100.
O uso dos valores 20 e 47 como chaves não colidirão um com outro.
A expressão funciona somente para chaves pares.
1. Apenas a afirmativa i está correta.
2. Apenas a afirmativa ii está correta.
3. Apenas as afirmativas i e ii estão corretas.
4. Apenas as afirmativas ii e iii estão corretas.
COMENTÁRIO: A alternativa 2 é a correta. Considerando que a expressão dada é utilizada no
cálculo do endereçamento hash, podemos analisar que essa expressão retorna o resto da divisão da
chave por 2 multiplicado por 5. Dessa forma, temos que o resto da divisão da chave por 2 será 0 ou
1. Esse valor multiplicado por 5 terá como possíveis endereços 0 ou 5. Nesse ponto, podemos
concluir que essa expressão não é nenhum pouco recomendável para o cálculo de endereço hash.
Pois somente é possível gerar dois endereços. E assim, a afirmação “i” não é correta, pois diz que
não ocorrem colisões para valores inferiores a 100, e como pode-se notar, somente é possível
endereçar duas posições, valor bem inferior a 100. A afirmação “ii” diz que os valores 20 e 47
certamente não colidirão um com outro. Porém...
F. Considere somente os símbolos e a frequência de caracteres da tabela a seguir.
Símbolo
T
A
D
S
Frequência
8
6
3
1
Qual será o código binário utilizado para representar o símbolo ‘S’ no processo de compactação
através do algoritmo de Huffman?
1. 011
2. 100
3. 101
4. 111
4
COMENTÁRIO: A resposta correta é a de número 2.
G. Aplique o algoritmo de Dijkstra na ilustração a seguir e determine a situação final da matriz de
menores caminhos. Considere como origem FAZENDA e destino CIDADE GRANDE.
1.
DESTINO
FECHADO
FAZENDA
SIM
CUSTO OU
DISTÂNCIA
0
ORIGEM
FAZENDA
5
2.
3.
4.
CIDADE HISTÓRICA
CIDADE PEQUENA
CIDADE MÉDIA
CIDADE GRANDE
SIM
SIM
SIM
SIM
DESTINO
FECHADO
FAZENDA
CIDADE HISTÓRICA
CIDADE PEQUENA
CIDADE MÉDIA
CIDADE GRANDE
SIM
SIM
SIM
SIM
SIM
DESTINO
FECHADO
FAZENDA
CIDADE HISTÓRICA
CIDADE PEQUENA
CIDADE MÉDIA
CIDADE GRANDE
SIM
SIM
SIM
SIM
SIM
DESTINO
FECHADO
FAZENDA
CIDADE HISTÓRICA
CIDADE PEQUENA
CIDADE MÉDIA
CIDADE GRANDE
SIM
SIM
SIM
SIM
SIM
1
3
4
5
CUSTO OU
DISTÂNCIA
0
1
5
3
5
CUSTO OU
DISTÂNCIA
0
1
5
4
5
CUSTO OU
DISTÂNCIA
0
1
5
3
4
FAZENDA
FAZENDA
CIDADE PEQUENA
CIDADE HISTÓRICA
ORIGEM
FAZENDA
FAZENDA
FAZENDA
CIDADE HISTÓRICA
CIDADE HISTÓRICA
ORIGEM
FAZENDA
FAZENDA
FAZENDA
CIDADE PEQUENA
CIDADE MÉDIA
ORIGEM
FAZENDA
FAZENDA
FAZENDA
CIDADE HISTÓRICA
CIDADE MÉDIA
COMENTÁRIO: A resposta correta é a alternativa de número 4.
H. Com base na técnica de hashing, não é possível afirmar que:
1. funciona somente para arquivos ordenados pelo campo chave.
2. consiste de uma técnica para alocação e busca de registros em posições aleatórias de memória.
3. denomina-se colisão, quando duas ou mais chaves diferentes recebem o mesmo endereço de
memória.
4. uma das técnicas que pode ser utilizada para lidar com a colisão é o encadeamento.
COMENTÁRIO: A alternativa correta é a de número 1. Por tratar-se de uma técnica que permite
o acesso e a busca a registros em posições aleatórias, cujo endereço de memória é calculado
através de uma fórmula matemática, não é necessário que o arquivo esteja ordenado.
I. Acerca dos conceitos estudados sobre grafos valorados e sobre o algoritmo de Dijkstra, não se
pode afirmar que:
1. um grafo valorado sempre tem associado a uma aresta um peso, positivo ou negativo, relacionado
normalmente a um custo ou distância e pode variar conforme a necessidade.
6
2. um digrafo é um par ordenado composto, respectivamente, pelo arco de origem e pelo arco de
destino, podendo a origem e o destino serem o mesmo arco.
3. o algoritmo de Dijkstra calcula o custo mínimo de um determinado vértice para todos os demais
vértices do grafo, e admite que suas arestas possuam valores negativos.
4. o algoritmo de Dijkstra considera que um vértice estará fechado quando já tiver sido obtido um
caminho de custo mínimo do vértice tomado como origem da busca até um vértice tomado como
destino. Caso contrário ele é dito aberto.
COMENTÁRIO: A resposta desta questão é a alternativa 3, pois o algoritmo de Dijkstra não
garante a exatidão da solução caso haja a presença de alguma aresta com valor negativo. Por isso
tal algoritmo não admite arestas com pesos negativos. A alternativa 1 está correta pois um grafo
valorado tem associado a sua aresta um peso relacionado a um custo ou distância e admite valores
positivos e negativos. Quem não admite arestas com valores negativos é o algoritmo de Dijkstra. A
alternativa 2 também está correta pois um digrafo pode ter com arco origem e arco destino o
mesmo vértice de um grafo. E a alternativa 4 também é correta pois um vértice está fechado apenas
quando já tiver sido obtido o caminho de menor custo do vértice raiz até um determinado vértice
destino.
J. Com respeito à aplicabilidade dos grafos com a realidade prática de nossa sociedade
contemporânea, analise as afirmativas.
i.
ii.
iii.
Vértices: times de vôlei. Arcos: Jogos entre os times durante um campeonato.
Vértices: casas de um tabuleiro de damas. Arcos: Existe um arco de A para B se uma dama
pode ir de A para B em um único movimento.
Vértices: rotas das formigas da espécie X do formigueiro até a margem de um determinado
rio. Arcos: formigas das espécies Y localizadas ao lado da Margem de um rio.
Qual(is) é(são) exemplos de uso de grafos?
1. Somente I
2. Somente III
3. Somente I e II
4. Somente II e III
COMENTÁRIO: A alternativa correta é a número 3. Dentro do contexto da teoria dos grafos, I e
II são exemplos práticos de grafos. Já III não é um exemplo bem definido de grafo pois seus termos
estão em contextos diferentes. A situação III seria um exemplo bem definido de grafo, caso as
formigas fossem da mesma espécie e, também, os vértices do grafo (ao invés das rotas) e, as rotas
das formigas entre si mesmas fossem os arcos do grafo. Assim, a alternativa 3 está correta pois cita
apenas I e II como exemplos bem definidos de grafos.
Coordenação do curso de Tecnólogo em Análise de Desenvolvimento de Sistemas
UNITINS - EAD
7