【高阶版】大学计算机-计算思维导论尔雅答案-网课家园

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

【单选题】

排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。

A、大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多

B、大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多

C、对无序数据集合，两个算法 X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢

D、以上说法都不对

【单选题】

关于“内排序”算法和“外排序”算法，下列说法不正确的是_____。

A、“内排序”算法通常是内存中数据排序常用的算法，而“外排序”算法通常是大规模数据排序常用的算法

B、“内排序”算法由于内存排序应用的频繁性，所以算法要考虑用尽可能少的步骤，而“外排序”算法由于要利用磁盘保存中间结果，所以算法主要考虑尽可能少的读写磁盘

C、无论是“内排序”算法，还是“外排序”算法，都需要考虑读写磁盘的代价问题

D、对一组需要排序的数据，能应用“内排序”算法时，尽量不用“外排序”算法

【单选题】

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答下列问题。

INSERTION-SORT(A)

for i=2 to N
{ key = A[i] ;
j =i-1;
While (j>0 and A[j]>key) do
{ A[j+1]=A[j];
j=j-1; }
A[j+1]=key;
}

SELECTION-SORT(A)

for i=1 to N-1
{ k=i;

3． for j=i+1 to N

{ if A[j]<A[k] then k=j; }
if k<>i then
{
temp =A[k];
A[k]=A[i];
A[i]=temp;
}
}

BUBBLE-SORT(A)

for i=1 to N-1
{ haschange=false;
for j=1 to N-i
{ if A[j]>A[j+1] then
{ temp =A[j];
A[j]=A[j+1];
A[j]=temp;
haschange=true;
}
}
if (haschange ==false) then break;
}

关于INSERTION-SORT算法的基本思想，下列说法正确的是_____。

A、一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束。

B、一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。

C、一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。

D、上述说法都不正确。

【单选题】

下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答下列问题。

INSERTION-SORT(A)

for i=2 to N
{ key = A[i] ;
j =i-1;
While (j>0 and A[j]>key) do
{ A[j+1]=A[j];
j=j-1; }
A[j+1]=key;
}

SELECTION-SORT(A)

for i=1 to N-1
{ k=i;

3． for j=i+1 to N

{ if A[j]<A[k] then k=j; }
if k<>i then
{
temp =A[k];
A[k]=A[i];
A[i]=temp;
}
}

BUBBLE-SORT(A)

for i=1 to N-1
{ haschange=false;
for j=1 to N-i
{ if A[j]>A[j+1] then
{ temp =A[j];
A[j]=A[j+1];
A[j]=temp;
haschange=true;
}
}
if (haschange ==false) then break;
}

关于SELECTION-SORT算法的基本思想，下列说法正确的是_____。

D、上述说法都不正确。

【单选题】

关于排序的选择法和冒泡法，下列说法不正确的是_____。

A、“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，只是寻找最小值元素的方法不一样，在效率方面没有什么差别

B、“选择法”通过将所有未排序元素与当前轮次待寻找的最小值元素进行比较，获得当前轮次的最小值元素；而“冒泡法”通过相邻元素的两两比较，一个轮次完成也能获得一个最小值元素

C、虽然“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，但选择法每轮次仅比较，没有交换，直至找到最小值后做一次交换；而冒泡法每一轮次是通过相邻元素比较来找最小值，如果不满足排序，则交换相邻两个元素，交换可能频繁发生。这样来看，选择法比冒泡法要快一些

D、上述说法有不正确的

【单选题】

阅读BUBBLE-SORT算法，已知N=20，下列说法正确的是_____。

BUBBLE-SORT(A)

for i=1 to N-1
{ haschange=false;
for j=1 to N-i
{ if A[j]>A[j+1] then
{ temp =A[j];
A[j]=A[j+1];
A[j]=temp;
haschange=true;
}
}
if (haschange ==false) then break;
}

A、第5轮次，是将第1个元素至第15个元素之间的元素，相邻者进行比较

B、第4轮次，是将第1个元素至第20个元素之间的元素，相邻者进行比较

C、第8轮次，是将第20个元素至第12个元素之间的元素，相邻者进行比较

D、第11轮次，是将第20个元素至第1个元素之间的元素，相邻者进行比较

【单选题】

按照PageRank的思想，一个网页的重要度被定义为_____。

A、其所拥有的所有反向链接的数目

B、其所拥有的所有反向链接的加权和

C、其所拥有的所有正向链接的数目

D、其所拥有的所有正向链接的加权和

8【多选题】

关于“排序-归并”算法，下列说法正确的是_____。

A、“排序-归并”算法是一个两阶段完成排序的算法，第一个阶段称为子集合排序，第二个阶段称为归并排序

B、“排序-归并”算法是在这样环境下应用的算法：待排序数据元素数目大于或远大于内存中可装入数据元素数目

C、“排序-归并”算法可以对任意大规模的数据集合进行排序

D、“排序-归并”算法是通过多次读写磁盘完成大规模数据集合的排序工作的

9【多选题】

关于内排序和外排序算法设计的关键点，下列说法正确的是_____。

A、外排序算法体现了受限资源环境下的算法构造，这里内存是一种受限资源

B、外排序算法强调尽可能少地读写磁盘，尽可能充分地利用内存来完成算法构造

C、外排序算法体现了与内排序算法设计不一样的关注点，前者更关注磁盘读写，后者更关注CPU执行操作的步数

D、外排序算法因内存环境的变化可以采用不同的策略，而不同策略算法的性能可能有所不同，这体现了问题求解算法的多样性，体现了算法需要“优化”

10【多选题】

关于PageRank计算网页重要度的基本思想，下列说法正确的是_____

A、反向链接数越多的网页越重要----被链接次数越多越重要

B、反向链接加权和越高的网页越重要----被重要网页链接次数越多越重要

C、正向链接数越多的网页，其链接的权值越低----正向链接数越多的网页越不重要

D、以上都不对

难解性问题求解：遗传算法研究示例

【单选题】

可解性问题是指能够找到多项式时间复杂性算法进行求解的问题，难解性问题是指找不到多项式时间复杂性算法进行求解的问题。下列说法不正确的是_____。

A、P类问题是可解性问题，NP类问题是难解性问题。

B、NP类问题不一定是难解性问题，因为P类问题也一定是NP类问题

C、NP类问题不确定是否是P类问题，但NPC类问题一定是难解性问题

D、以上都正确

【单选题】

下列说法正确的是_____。

A、P类问题是计算机可以在有限时间内能够求解的问题

B、NP类问题是计算机可以在有限时间内能够求解的问题

C、NPC类问题是计算机可以在有限时间内能够求解的问题

D、上述说法都正确

【单选题】

P类问题是多项式问题(Polynomial Problem)，NP类问题是_____。

A、非多项式问题

B、非确定性多项式问题

C、非P类问题

D、确定性非多项式问题

【单选题】

下列说法不正确的是_____。

A、P类问题是总能找到一个多项式时间复杂性算法进行求解的问题

B、NP类问题是一定找不到多项式时间复杂性算法进行求解的问题

C、NP类问题是不确定能够找到多项式时间复杂性算法进行求解的问题

D、NP类问题虽然是不确定能找到多项式时间复杂性算法进行求解，但一定能找到多项式时间复杂性算法进行“解”的正确性验证的问题

【单选题】

类比计算类问题求解，下列说法不正确的是_____。

A、一个染色体即是指问题的一个“可能解”，一个基因即是“可能解”的一个编码位或若干编码位的一个组合

B、一个种群即是一个包含问题满意解的“可能解”的集合

C、适应度，即是对“可能解”的一个度量，它可以衡量“可能解”接近最优解或精确解的程度

D、复制、交叉、变异等都是产生新“可能解”的方式

【单选题】

遗传算法是典型的计算求解的方法，它通过“产生任何一个可能解，并验证可能解的正确性”的方法求解一个复杂问题。关于计算求解，下列说法正确的是_____。

A、可以从所有可能解的集合中产生每一个可能解，并验证可能解的正确性。利用这种策略的算法，计算机一定能够在有限时间内找到精确解

B、可以从所有可能解的集合中随机产生一些可能解，并验证可能解的正确性。利用这种策略的算法，计算机一定能够在有限时间内找到精确解

C、可以从所有可能解的集合中随机产生一些可能解，并验证可能解的正确性。利用这种策略的算法，计算机一定能够在有限时间内找到满意解

D、可以从所有可能解的集合中随机产生一些可能解，并验证可能解的正确性。利用这种策略的算法，如果随机产生的可能解越多，则计算机找到满意解的概率也越大，但耗费时间也越长

【单选题】

A、可以从所有可能解的集合中随机产生一些可能解，并验证可能解的正确性。利用这种策略的算法—可被称为随机搜索算法。则，利用随机搜索算法，计算机在有限时间内一定能够找到满意解

B、为改进随机搜索算法的求解质量，在随机产生可能解的过程中，使后一个可能解的产生与前一个可能解相关联，即在前一个可能解的基础上随机产生后一个可能解，例如一个可能解编码为“110011001100”，可以通过改变该解编码的某些位产生下一个可能解(即相关)，而改变哪些位则可随机处理。利用这种策略的算法---可被称为导向性随机搜索。则，利用导向性随机搜索，计算机在有限时间内一定能够找到满意解

C、和随机搜索相比，利用导向性随机搜索，计算机在有限时间内找到满意解的概率更大一些

D、和随机搜索相比，利用导向性随机搜索，初始的可能解对计算机在有限时间内找到满意解的概率的影响更大一些

【单选题】

遗传算法是典型的计算求解的方法，它通过“产生任何一个可能解，并验证可能解的正确性”的方法求解一个复杂问题。关于计算求解，下列说法不正确的是_____。

A、在获得满意解的概率方面，如果初始可能解被恰当选择的话，导向性随机搜索一定比随机搜索更好一些

B、在获得满意解的概率方面，群导向性随机搜索一定比导向性随机搜索更好一些：相比导向性随机搜索，群导向性随机搜索采取了多条导向搜索路径

C、遗传算法是一种群导向性随机搜索：其有一定规模的种群，即可被认为是设置了多个初始的可能解；其交叉、变异产生新可能解的方法，即可被认为是新可能解与原可能解相关联

D、利用遗传算法，计算机在有限时间内一定能够找到满意解

【单选题】

关于什么情况下应用遗传算法，下列说法正确的是_____。

A、当对某问题求解，找不到更好的多项式时间复杂性算法的时候

B、当问题的可能解能够被表达，并能够确定问题的解空间的时候

C、当能够找到可能解的适应度计算方法，即能够判断一个可能解接近精确解的程度或方向的时候

D、前述(A)(B)(C)同时满足的时候

【单选题】

为什么说会议室租用问题、测试用例选择问题和航班机组成员问题是同一个问题，下列说法不正确的是_____。

A、对这三个问题进行抽象，会议室、测试用例和机组成员都可被看作是“资源”，而讲座、软件功能测试和航班都可被看作是“任务”，则这三个问题都可被看作是：选取最少量的资源以满足其能够完成给定的所有任务

B、对这三个问题进行抽象，每个资源都能够完成一些任务，即覆盖一个任务集合。不同资源，具有不同的使用成本。上述问题都是选择具有最小成本的一些资源，使这些资源所覆盖任务集合的并集能够包含所有需要完成的任务

C、观察问题相同与否，可将问题语义剥离，形成数学模型。如果数学模型是相同的，则其是相同的问题，否则便不是相同的问题。

D、上述都不正确

【单选题】

设一个问题的解的形式为x，下列说法不正确的是_____。-

A、由x的取值空间给定的任何一个x值被称为可能解

B、满足问题约束的可能解被称为可行解

C、在任何一组可行解中求出的最优解被称为是满意解

D、所有可行解中的最优解是问题的最优解

【单选题】

遗传算法的设计在很多方面都需要引入概率，在哪些方面引入概率呢？下列说法不正确的是_____。

A、初始种群的确定可以引入概率。结合问题可能解的分布选择概率模型，将此概率模型引入初始解的随机选择过程中，则选择出的初始可能解有助于遗传算法快速地获得满意解

B、交叉规则设计可以引入概率。从待交叉两个可能解的确定，到交叉点的确定，甚至到段间距离的确定等都可以引入概率，恰当的概率模型选择有助于遗传算法快速地获得满意解

C、遗传算法处处体现着概率的应用和随机处理。当可能的方案比较多，且穷举计算量很大时，便可采用概率方式进行随机化处理。例如两个可能解“00001000 10001100”“00111000 1011 1100”，如果做两段交叉，则分段交叉点可以有16个，如果16个交叉点都选择，则可能该子解空间仍旧很大，此时可依概率选择1号位置交叉至16号位置交叉，选择几个则依概率模型确定，选择1个至16个中的某些个

D、虽然遗传算法处处可以引入概率，但其概率模型却是相同的

【单选题】

遗传算法是迭代计算求解的方法。如何终止遗传算法，下列说法正确的是_____。

A、当适应度已经达到饱和，继续进化不会产生适应度更好的近似解时，可终止遗传算法

B、当某一个可行解已经满足满意解的条件，即满意解已经找到，可终止遗传算法

C、当进化到指定的代数(进化次数限制)或者当达到一定的资源占用量(计算耗费的资源限制，如计算时间、计算占用的内存等)时可终止算法，如当产生超过一定数量的不重复可行解后即可终止

D、仅有上述(A)(B)(C)几种终止遗传算法的情况

14【多选题】

下列说法正确的是_____。

A、P类问题是计算机可以在有限时间内能够求解的问题

B、NP类问题是计算机可以在有限时间内能够验证“解”的正确性的问题

C、NPC类问题是对问题的每一个可能解，计算机都可以在有限时间内验证“解”的正确性的问题，被称为NP完全问题

D、以上都不正确

15【多选题】

非确定性多项式问题是指这样的问题，下列说法不正确的是_____。

A、它能够找到一个算法、甚至是多项式时间复杂性算法进行求解，但算法中包含“不确定性”，如“任意组合一个解，…”、“随机组合一个解，…”等

B、它能够找到一个算法、甚至是多项式时间复杂性算法进行求解，但算法是通过“猜测”方式求出问题的解

C、它能够通过“产生任何一个解，并验证解的正确性”的方法进行求解

D、它不能够找到多项式时间复杂性算法以验证给定“解”的正确性的问题

16【多选题】

关于NP类问题求解，下列说法不正确的是_____。

A、NP类问题求精确解，可能找不到多项式时间复杂性算法；但NP类问题求近似解，则一定能够找到多项式时间复杂性算法

B、NP类问题求精确解，可能找不到多项式时间复杂性算法；但NP类问题求近似解，则也可能找不到多项式时间复杂性算法

C、虽然能够找到求NP类问题近似解的多项式时间复杂性算法，但所求得的解一定不是满意解

D、既然能够找到求NP类问题近似解的多项式时间复杂性算法，则所求得的解就一定是满意解

17【多选题】

下列说法正确的是_____。

A、任何一个生物个体的性状是由其染色体确定的，染色体是由基因及其有规律的排列所构成的，因此生物个体可由染色体来代表

B、生物的繁殖过程是通过将父代染色体的基因复制到子代染色体中完成的，在复制过程中会发生基因重组或基因突变。基因重组是指同源的两个染色体之间基因的交叉组合，简称为“杂交/交配”。基因突变是指复制过程中基因信息的变异，简称“突变”

C、不同染色体会产生不同生物个体的性状，其适应环境的能力也不同

D、自然界体现的是“优胜劣汰，适者生存”的丛林法则。不适应环境的生物个体将被淘汰，自然界生物的生存能力会越来越强

18【多选题】

下列说法不正确的是_____。

A、可行解集合Ê近似解集合Ê可能解集合Ê满意解集合Ê最优解集合

B、可能解集合Ê可行解集合Ê满意解集合Ê近似解集合Ê最优解集合

C、可能解集合Ê可行解集合Ê近似解集合Ê满意解集合Ê最优解集合

D、最优解集合Ê满意解集合Ê近似解集合Ê可行解集合Ê可能解集合

19【多选题】

设一个问题的解的形式为x，下列说法正确的是_____。

A、由x的取值空间给定的任何一个x值被称为可行解

B、由一个算法在任何一组可行解中求出的最优解被称为是近似解

C、符合用户期望的近似解被称为是满意解

D、所有可行解中的最优解是问题的最优解

20【多选题】

通过变异操作，使遗传算法具有局部的随机搜索能力。为什么？下列说法正确的是_____。

A、当产生一个可行解时，可以在该解的邻近解的集合中进行搜索，被称为局部搜索；该解的邻近解的集合是变化的，例如与该解有一位不同的邻近解、与该解有两位不同的邻近解，或者与该解有一个“位组合”不同的邻近解等

B、当产生一个可行解时，由于与该解的邻近解的集合可能很大，并不能穷举每一个邻近解，所以需要随机选择邻近解

C、当产生一个可行解时，通过某一位或几位的变异，便可产生该解相邻近的解。即相当于，以该解为中心，在与该解的邻近解的集合中随机选择出某个解

D、当产生的可行解接近最优解的邻域时，通过某一位或几位的变异，便可产生该解相邻近的解，此有助于使算法加速向最优解收敛

21【多选题】

通过变异操作，使遗传算法可维持群体多样性。为什么？下列说法正确的是_____。

A、由于初始解设置或经多次迭代后，很可能使一代种群中的各个可能解具有相似的结构，此时无论怎样交叉产生的新可能解，都将在与该结构相近的可能解空间搜索--这种现象被称为过早收敛

B、为避免过早收敛，有必要保持种群个体的多样性，即使种群中的可能解具有不同的结构，怎样保持不同的结构，即通过变异，打破原有相似的结构，进入到另外的空间中搜索

C、当进化到某一代时，种群的解可能具有相类似的结构，可能始终在这个类似结构的解集合中进行循环，为避免这种情况，通过对一些解应用变异操作，打破种群的解的相类似结构，有助于跳出循环，在更大空间中进行搜索

D、当产生的可行解接近最优解的邻域时，应谨慎使用变异，以免偏向最优解的结构被破坏；而当产生的可行解并未接近最优解的邻域时，可以选择较大的变异概率以保证种群解的多样性

22【多选题】

如何衡量遗传算法的性能好坏，下列说法正确的是_____。

A、近似率越高的算法，性能越好

B、在执行相同次数的迭代后，获得满意解越好的算法，性能越好

C、在达到期望满意解的前提下，迭代次数越多的算法，性能越好

D、当不同算法均应用多次后，求得满意解次数越多的算法，性能越好

声明：本站所有文章，如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

【高阶版】大学计算机-计算思维导论尔雅答案

文章展示

超星尔雅走进人工智能答案

2024年最新超星尔雅网络创业理论与实践（2024年版）答案

超星大学美育（同济大学版） 2024尔雅答案

超星心理健康与自我成长 2024尔雅答案

沟通的艺术超星尔雅学习通答案

新媒体概论超星尔雅学习通答案

近期文章

【高阶版】大学计算机-计算思维导论尔雅答案

相关文章

文章展示

标签

近期文章