(*9)参见图示。如果：内存块数为Bmemory=8，待排序元素集合所占用磁盘块数Bproblem=80，首先，80个磁盘块的待排序元素集合被分成10个子集合，分别进行子集合排序；然后再进行归并处理完成最终排序。关于归并操作，几个子集合同时装入内存进行归并就被称为几路归并，则下列说法不正确的是_____。
(A)对10个已排序子集合可以先进行2个5路归并形成2个子集合，然后再进行1个2路归并便可完成最终的排序；
(B)对10个已排序子集合可以先进行3个3路归并形成3个子集合，外加剩余子集合共4个子集合，然后再进行1个4路归并便可完成最终的排序；
(C)对10个已排序子集合可以先进行1个5路归并形成1个子集合，外加剩余5个子集合共6个子集合，再进行1个6路归并便可完成最终的排序；
(D)前述(A)(B)(C)归并策略都可以，但性能有所不同，最好的是(A)策略。
答案：D 解释：
本题考核对归并策略性能的理解。
(A)(B)(C)的归并策略都可以，但是最好的是(C)策略，因为(C)仅有5个子集合进行了2个轮次的归并，5个子集合进行了一个轮次的归并；(A)所有10个子集合都进行了2个轮次的归并；所以(D)错误。
具体内容请参考第八章课件之“基本排序算法--外排序算法”。
(*10)已知内存块数为Bmemory，待排序元素集合所占用磁盘块数Bproblem，设计一个“排序-归并”算法的基本思路，下列描述不正确的是_____。
(A)首先划分子集合，每个子集合最大可为Bmemory块，可以划分为Bproblem/Bmemory个子集合。这样划分的理由：一是子集合可以全部装载入内存执行内排序，二是最大限度地利用内存产生尽可能少数目的子集合；
(B)将Bmemory块内存留出两块，一块作为输出数据块，一块用于待比较元素数据块。其余Bmemory-2块用于装载尽可能多数目的子集合，即尽可能采用更多路的归并。这样做的理由：尽可能最大限度地利用内存，以便减少归并的次数；
(C)如果子集合参与归并一次被称为一个轮次，则整个数据集的轮次是指该数据集中参与归并次数最多的子集合的轮次。归并算法应考虑以尽可能少轮次的归并为目标来衡量各种不同归并策略的好坏。也可以定义一个参数“子集合轮次累积和”，即所有子集合参与归并轮次的总和，来衡量性能好坏，即“子集合轮次累积和”越小，算法性能越好；
(D)假设Bmemory=6，Bproblem=60，则按照上述(A)(B)(C)思想，可自动确定出：子集合数目=10，第一次将10个子集合分成3组(3个、3个和4个)并分别采用3路归并和4路归并将其归并成3个子集合；第二次对这3个集合再采用3路归并完成最终的排序。这样做的算法是最优的。
(E)假设Bmemory=6，Bproblem=60，则按照上述(A)(B)(C)思想，可自动确定出：子集合数目=10，第一次采用4路归并分别对8个子集合、4个一组归并成2个子集合；第二次对这2个集合与剩余的2个子集合一起采用4路归并完成最终的排序。这样做的算法是最优的；
答案：D
解释：
本题考核“排序-归并”算法的设计。
(A)(B)(C)的说法都是正确的，(E)相比(D)而言最优，因为E仅有8个子集合进行了2个轮次的归并，2个子集合进行了一个轮次的归并，而D所有10个子集合都进行了2个轮次的归并。从“子集合轮次累积和”角度(E)比(D)优，所以(D)错误。
具体内容请参考第八章课件之“基本排序算法--外排序算法”。
(11)关于内排序和外排序算法设计的关键点，下列说法不正确的是_____。
(A)外排序算法体现了受限资源环境下的算法构造，这里内存是一种受限资源； (B)外排序算法强调尽可能少地读写磁盘，尽可能充分地利用内存来完成算法构造； (C)外排序算法体现了与内排序算法设计不一样的关注点，前者更关注磁盘读写，后者更关注CPU执行操作的步数；
(D)外排序算法因内存环境的变化可以采用不同的策略，而不同策略算法的性能可能有所不同，这体现了问题求解算法的多样性，体现了算法需要“优化”；
(E)上述说法有不正确的。
答案：E 解释：
本题考核内排序和外排序的区别。
内排序是指待排序的数据可一次性地装入内存中，即排序者可以完整地看到和操纵所有数据，使用数组或其他数据结构便可进行统一的排序处理的排序问题；外排序是指待排序的数据保存在磁盘上，不能一次性装入内存，即排序者不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理的排序问题； (A)(B) (C)(D)的叙述都是正确的，所以(E)错误。
具体内容请参考第八章课件。
7、PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答下列问题。
图I.
(1)关于PageRank计算网页重要度的基本思想，下列说法正确的是_____。
(A)反向链接数越多的网页越重要----被链接次数越多越重要；
(B)反向链接加权和越高的网页越重要----被重要网页链接次数越多越重要；
(C)正向链接数越多的网页，其链接的权值越低----正向链接数越多的网页越不重要； (D)上述全部。
答案：D 解释：
本题考查PageRank的基本思想--通俗语义。
一个网页的重要度等于其所有反向链接的加权和，所以反向链接加权和越高的网页越重要，反向链接数越多的网页越重要；一个正向链接的权值等于网页的重要度除以其正向链接数，所以正向链接数越多的网页，其链接的权值越低，所以(A)(B)(C)都正确，选(D)。
具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。 (2-1)按照PageRank的思想，一个网页的重要度被定义为_____。
(A)其所拥有的所有反向链接的数目； (B)其所拥有的所有正向链接的数目； (C)其所拥有的所有链接的数目； (D)上述都不正确。
答案：D 解释：
本题考查PageRank对网页重要度的定义。
一个网页的重要度等于其所有反向链接的加权和，所以(A)(B)(C)都不正确，选(D)。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。
(2-2)按照PageRank的思想，一个网页的重要度被定义为_____。
(A)其所拥有的所有反向链接的数目； (B)其所拥有的所有反向链接的加权和； (C)其所拥有的所有正向链接的数目； (D)其所拥有的所有正向链接的加权和；。
答案：B 解释：
本题考查PageRank对网页重要度的定义。
一个网页的重要度等于其所有反向链接的加权和，所以(B)正确。
具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。
(3)按照PageRank的思想，一个网页链接的权值被定义为_____。
(A)网页重要度除以该网页所拥有的正向链接数； (B)网页重要度除以该网页所拥有的反向链接数；
(C)网页重要度除以该网页所拥有的所有链接数； (D)上述都不正确；。
答案：A 解释：
本题考查PageRank对链接权值的定义。
一个网页链接的权值等于网页的重要度除以其正向链接数，所以(A)正确。 具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。
(4)PageRank将网页的链接关系，抽象为一个n ? n的矩阵A：网页被从1到n进行编号；如果网页i有一个指向网页j的链接，则矩阵的aij元素(即第i行第j列元素)值为1，否则矩阵aij元素值为0。然后将A做一个转置处理(即矩阵的行列互换)，形成转置矩阵AT，为什么要转置，原因是_____。
(A)有利于体现反向链接的重要性；
(B)有利于更好地区分反向链接与正向链接；
(C)有利于计算权值矩阵(可被称为转移概率矩阵M)：将AT的一列中的各行除以该列中1的个数，即可形成权值矩阵M；
(D)有利于由AT计算的权值矩阵M与网页重要度矩阵R的乘积符合网页重要度的计算方法：反向链接的加权和。
答案：D 解释：
本题考查PageRank对网页链接关系的抽象--邻接矩阵及其转置的理解。
将A转置的原因是有利于由AT计算的权值矩阵M与网页重要度矩阵R的乘积符合网页重要度的计算方法：反向链接的加权和，选(D)。
具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。
(5)PageRank算法中出现了一个“转移概率矩阵”，参见下图，其意义是_____。
(A)转移概率矩阵是基于网页链接关系矩阵AT计算得到的，按列来看是，网页j有多少个正向链接，其权值为多少分之一，反映了链接权值的计算方法；
(B)转移概率矩阵是基于网页链接关系矩阵AT计算得到的，按行来看是，网页i有多少个反向链接及其权值，可反映网页i的重要度计算方法即：，由其他网页的重要度及其权值计算该网页i的重要度；
(C)网页i的重要度Ri可以迭代地计算得到，设第m次得到的Ri记为Ri(m)，称为网页重要度Ri的一个状态，则状态转移概率为Ri由一个状态转变为另一个状态的概率；
(D)状态转移概率可广泛用于计算客观事物呈现状态序列S(0),...., S(m-1),S(m),...，而S(m)的计算仅由S(m-1)的值来确定的情况；
(E)上述说法都正确。
答案：E 解释：
本题考查PageRank对转移概率矩阵的理解。 (A)(B)(C) (D)的叙述都正确，所以选(E)。
具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。
(6)前述说过 PageRank网页i重要度Ri可以通过迭代地计算得到，即由m-1状态下各个网页的重要度R(m-1)，依转移概率矩阵计算m状态下网页重要度R(m)，参见下图。
关于网页重要度的计算过程，下列说法正确的是_____。
(A)在得到了转移概率矩阵M后，任意给出网页重要度的一组值，记为R(0)，是一向量，参见下图，继续进行(B)；
(B)不断地计算R(m)=M?R(m-1)，m从0开始，为迭代次数。当R(m) = R(m-1)时，迭代计算终止，此时的向量R即为所求的各个网页的重要度；
(C)选项(A)(B)是将状态序列R(0)，...，R(m-1)，R(m)，...不断迭代产生后趋于稳定的，或者说收敛的R(m)，作为最终的R，即是已知M情况下，求方程R = MR的解；
(D)上述说法都正确。
答案：D 解释：
本题考查PageRank对迭代法计算的理解。
网页重要度的计算过程正如(A)(B)所示，(C)是对(A)(B)的一个总结，都是正确的，所以选(D)。
具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。
(7)前述说过 PageRank，通过不断地计算R(m)=M?R(m-1)来计算网页重要度，即由第(m-1)次的网页重要度来计算第(m)次的网页重要度，那么网页重要度的初始值R(0)应如何获得呢? 下列说法正确的是_____。
(A)随机产生各网页重要度的一组值，该组值对最终计算结果没有影响；
(B)由专家给出各网页重要度的一组值，该组值的质量好坏直接影响计算结果； (C)设定各网页重要度都是1；
(D)随机产生各网页重要度的一组值，使网页重要度界于0和1之间，但该组值对最终结果没有影响。
答案：D 解释：
本题考查PageRank对初始值的处理方法的理解。
网页重要度的初始值R(0) 是随机产生各网页重要度的一组值，使网页重要度界于0和1之间，但该组值对最终结果没有影响，选(D)。
具体内容请参考第九章课件之“PageRank排序—排序问题的不同思考方法”。