《大学计算机—计算思维导论?哈工》学习笔记（4）

第8讲 问题-算法与环境：排序算法研究示例

1.外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法大数据排序，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。参见图示。如果：内存块数为 ，每块可装载 个元素，待排序元素集合所占用磁盘块数 ，则关于此集合的排序问题，下列说法正确的是（首先将待排序元素集合划分为4个子集合，每个子集合为6块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再对这4个已排序子集合进行归并操作，完成最终排序）。

2.下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。针对上述三个算法，回答问题：针对按成绩降序排列的数据表，假设记录数为n，关于算法A2，下列说法正确的是（算法A2在最好的情况下是读取1条记录，在最差的情况是读取n条记录，才能得到结果）。

3.下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。阅读BUBBLE-SORT算法，已知N=20，下列说法正确的是（第5轮次，是将第1个元素至第15个元素之间的元素，相邻者进行比较）。

4.PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。按照PageRank的思想，一个网页的重要度被定义为（其所拥有的所有反向链接的加权和）。

5.外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。参见图示。如果：内存块数为，待排序元素集合所占用磁盘块数，采用排序-归并算法进行升序排序，下列说法正确的是（算法以磁盘块读写次数衡量的时间复杂性为）。

（编辑：百客网 - 百科网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!