Prévia do material em texto

UNIVERSIDADE FEDERAL DE RONDÔNIA ESTRUTURA DE DADOS PROVA 2B 14/09/2023 NOME: MATRÍCULA: Questão 1 (1,0): Explique porque os arquivos abertos devem ser fechados. Questão 2 (1,0): Faça um programa que um vetor numérico pelo teclado e o escreve em um arquivo. Questão 3 (1,0): Discuta as diferenças e semelhanças entre a memória principal (RAM) e a memória secundária (os arquivos). Questão 4 (1,0): que é fragmentação externa de um arquivo no disco? Por que ela ocorre e quais são seus efeitos? Questão 5 (1,0): Os discos são considerados o gargalo de um sistema computacional. Explique como este problema pode ser minimizado Questão 6 (1,0): Quantos bits são necessários para codificar a mensagem "mississippi"? Apresenta a árvore de Huffman, os códigos e calcule o número total de bits. Questão 7 (1,0): O que é uma lista invertida? Quando ela é útil? Como ela é mantida em memória secundária? Questão 8 (3,0): Suponha que um arquivo de dados com 4.000 registros, mantido em disco, deve ser ordenado em um computador cuja memória interna acomoda no máximo 400 registros por vez, usando o procedimento de intercalação. Essa mesma área de memória interna é usada como buffer de entrada para leitura de dados do disco, e o sistema conta com um buffer de saída adicional que acomoda 100 registros. a) Quantas corridas serão geradas e quantos registros haverá em cada corrida? b) Durante a intercalação, quantos registros serão lidos de cada corrida cada vez que ela é acessada? Justifique. c) Quantos seeks serão realizados para ler dados durante o processo de intercalação (excluindo a fase de geração de corridas)? Quantos serão realizados para escrever dados? Justifique. Questão 9 (1,0): Uma partição de disco rígido é formatada com um sistema de arquivos que utiliza alocação encadeada baseada em tabela de alocação de arquivos (FAT). Após a formatação, a partição possui setores de 512 bytes e tamanho de bloco (cluster) de 2048 bytes. Ao criar um arquivo nessa partição, gravar 1 byte e fechá-lo, qual espaço esse arquivo ocupa na área de dados da partição?UNIVERSIDADE FEDERAL DE RONDÔNIA ESTRUTURA DE DADOS PROVA 3A DATA: / ALUNO: Questão 1 (1,0): Uma árvore B é um tipo de árvore que se mantém balanceada com o decorrer do tempo. Para tanto, ela usa uma série de operações que garantem a manutenção de uma série de propriedades importantes, uma das quais é a ordem da árvore que pode ser definida como o número máximo de elementos que podem ser armazenados em um nó da árvore. Com base nesses conceitos, qual das situações a seguir representa uma propriedade das árvores B? A) Em uma árvore B de ordem maior do que 1, não é permitido que uma folha armazene apenas um elemento. B) Em uma árvore B de ordem d, a raiz armazena um número de elementos n tal que 2d. C) Em uma árvore B de ordem d, pode haver folhas em alturas diferentes da árvore até que tenham sido inseridos, pelo menos, 2d+1 elementos. D) Em um nó de uma árvore B que contenha n elementos não vazios, podem-se ter, no máximo, n/2 ponteiros apontando para vazio (nil ou null). E) Em um nó interno de uma árvore B que contenha n elementos, têm-se exatamente n+1 ponteiros que não apontam para vazio (nil ou null). Questão 2 (2,0): Qual a diferença entre uma árvore B e uma B*? Quais as vantagens da árvore B*? Quais as desvantagens? Como se compara a altura mínima dessas árvores Questão 3 (2,0): o que é uma árvore B virtual? Como implementá-la ? Quais as vantagens e desvantagens? Questão 4 (2,0): Mostre a cada passo, as árvores que resultam depois de remoção das chaves A, B, Q e R da árvore-B de ordem 5 na figura a seguir: M DH QU ABC EFG IJKLNO RST VW Questão 5 (2,0): Criar uma árvore-B+ pela inserção das chaves A, B, C, D, E, F, G, H, I e J, nesta ordem Ordem da árvore: 3 -Blocos mínimo de 2 registros máximo de 3 registrosUNIVERSIDADE FEDERAL DE RONDÔNIA ESTRUTURA DE DADOS PROVA REPOSITIVA 17/10/2023 ALUNO: Questão 1 (1,0): Ache a Árvore Geradora Mínima do grafo abaixo utilizando o Algoritmo de Prim começando do vértice A do grafo a seguir. A B C D E F G H I J A 0 15 10 19 0 0 0 0 0 B 15 0 0 7 17 0 0 C 10 0 0 16 0 14 0 D 19 7 16 0 12 6 3 E 0 17 0 12 0 0 20 13 0 0 F 0 0 14 6 0 0 9 0 5 0 G 0 0 3 20 9 0 4 1 11 H 0 0 13 0 4 0 0 2 I 00000510 18 J 0 0 0 0 0 0 11 2 18 0 Questão 2 (2,0): Seja um grafo G cujos vértices são os inteiros de 1 a 8 e os vértices adjacentes a cada vértice são dados pela tabela abaixo: Vértice Vértices Adjacentes 1 234 2 134 3 124 4 1236 5 678 6 457 7 568 8 57 (a) Desenhe o grafo G. (b) Represente o grafo por meio de uma matriz de adjacência. (c) Represente o grafo por meio de uma lista de adjacência. (d) Mostre qual é número cromático deste grafo. (e) G é um grafo Euleriano? Por quê? Questão 3 (1,5): As aplicações usualmente armazenam as informações em arquivos organizando-as em campos e registros. Explique as diferentes maneiras pelas quais um campo pode ser armazenado em um arquivo para posterior recuperação. Questão 4 (1,5): Quais as diferenças entre os algoritmos Key-sort e K-way merge sort? Questão 5 (2,0): Mostre a cada passo a configuração de uma árvore-B* de ordem 3 ao se inserirem as chaves: Questão 6 (2,0): Suponha que você vai remover uma chave em uma árvore-B, a qual causa underflow na página. Se pela página irmã do lado direito é necessária concatenação, e pela página irmã do lado esquerdo é possível redistribuição, qual opção você escolheria? Por quê?UNIVERSIDADE FEDERAL DE RONDÔNIA ESTRUTURA DE DADOS PROVA 1 10/08/2023 ALUNO: MATRÍCULA: 1) (1,0) Um grafo não direcionado no qual todos os pares de vértices são adjacentes, isto é, possui arestas ligando todos os vértices entre si, é um grafo: A) Desconexo. B) Completo. C) Ponderado. D) Livre. E) Hipergrafo. 2) (1,0) Qual é a implementação no qual um grafo G (V,A) contendo n vértices é uma matriz nxn de bits, em que A[i,i] é 1 (ou verdadeiro, no caso de booleanos) se e somente se existe um arco do vértice i para o vértice j. A) Matriz de incidência. B) Lista de adjacência. C) Matriz de adjacência. D) Lista de incidência. E) Matriz quadrada completa. 3) (1,0) Qual é o algoritmo de busca em grafos no qual a busca inicia-se a partir de um nodo raiz e percorre cada caminho de forma a in o mais longe possível antes de passar para outro caminho? A) Topológica. B) Largura. C) Abrangência. D) Pós-ordem. E) Profundidade. 4) (1,0) Sobre grafos, assinale a alternativa correta. A) Um grafo ponderado é um grafo não direcionado em que todos os pares de vértices são adjacentes, isto é, há arestas ligando todos os vértices entre si. B) Todo grafo completo tem pesos associados às suas arestas. C) Um caminho em um grafo é complexo se todos os vértices do caminho são distintos. D) grau de um vértice em um grafo não direcionado é o número de arestas que incidem nele. E) Se existir um caminho de X a y, então X é alcançável a partir de via y. 5) (1,0) Determine se o grafo abaixo é bipartido e justifique sua resposta. b C a d e 6) (1,0) Existe um grafo simples com cinco vértices dos seguintes graus? Se existir, desenhe um possível grafo. Se não, justifique. A) 3, 3, 3, 3, 2 B) 3, 4, 3, 4, 3 7) (1,0) o código abaixo pode ser utilizado para atravessar um grafo. Entrada: um gráfico G e um vértice de G Saída: todos os vértices alcançáveis de V marcadosfunção func : marque V para todas as arestas adjacentes a V, faça se vértice W não estiver marcado, então Chame recursivamente func fim se fim para fim função Entre os diversos tipos de algoritmos utilizados para atravessar grafos, esse código implementa o algoritmo: A) busca em profundidade ou Depth-First Search. B) busca em largura ou Breadth-First Search. C) busca melhor-primeiro ou Best-First Search D) busca exaustiva ou Brute-Force Search. 8) (1,0) Usando o algoritmo de dijkstra, determine a distância mínima do nó 1 a todos os outros e indique os caminhos. Apresente os resultados passo-a -passo. 2 2 4 15 21 1 4 6 6 3 9 7 3 16 5 9) (1,0) Execute os algoritmos de Prim e Kruskal para o grafo abaixo. 2 7 6 2 2 2 4 1 5 4 1 8 4 1 3 7 3 4 7 10) (1,0) Considere a tabela de tarefas a seguir para a construção de uma casa de madeira: TAREFAS PRÉ-REQUISITOS DIAS 1. Limpeza do terreno Nenhum 4 2. Produção e colocação da fundação 1 3 3. Produção da estrutura 2 7 4. Colocação do telhado 3 6 5. Colocação das tábuas externas 3 4 6. Instalação do encanamento e fiação 5 6 7. Colocação das janelas e portas 3 5 8. Instalação das janelas e portas 6 5 9. Pintura do interior 7 e 8 5 a) Construa o diagrama PERT. b) Determine o tempo mínimo para construir a casa.