中国大学mooc慕课 大学计算机基础（2018秋）(西南石油大学) 答案满分完整版章节测试

荡孔舱年讼桓吧山沤饺磨剁氦

第1讲 计算机、计算与计算思维 第1讲测验

1、 计算机器的基本目标是什么？

答案: 能够执行一般的任意复杂的计算规则

2、 衡量存储设备性能的指标包括_。

答案: 其它三个选项都包括

3、 计算之树中，网络化思维是怎样概括的？

答案: 机器网络、信息网络和人-机-物互联的网络化社会

4、 计算机包括_____。

答案: 其它三个选项都包括

5、 “人”计算与“机器”计算有什么差异？

答案: 其它选项的说法都正确

6、 衡量微处理器芯片性能好坏的指标包括_。

答案: 其它选项都包括

7、 关于计算系统，下列说法正确的是_。

答案: 计算系统由微处理器、存储设备、输入设备和输出设备构成

8、 人类应具备的三大思维能力是指_____。

答案: 实验思维、理论思维和计算思维

9、 自动计算需要解决的基本问题是什么？

答案: 数据和计算规则的表示、自动存储和计算规则的自动执行

10、 电子计算机器的基本特征是什么？

答案: 其它三个选项都正确

11、 计算系统的发展方向是_。

答案: 其它三个选项都是正确的

12、 计算之树中，通用计算环境的演化思维是怎样概括的？

答案: 程序执行环境—由CPU-内存环境，到CPU-存储体系环境，到多CPU-多存储器环境，再到云计算虚拟计算环境

13、 计算之树中，两类典型的问题求解思维是指__。

答案: 算法和系统

14、 本课程中拟学习的计算思维是指_____。

答案: 蕴含在计算学科知识背后的具有贯通性和联想性的内容

15、 计算学科的计算研究什么

答案: 面向机器可自动执行的求解一般问题的计算规则

16、 摩尔定律是指_。

答案: 芯片集成晶体管的能力每18个月增长一倍，其计算能力也增长一倍

17、 下列说法正确的是_。

答案: 软盘是可移动的可更换的永久存储器

18、 IBM提出的Smart Planet基本特点是什么_。

答案: 其它选项内容结合在一起才是Smart Planet

19、 关于计算系统的网络化的说法正确的是_。

答案: 未来互联网将发展为包括物联网、社会网络、服务网络以及与现实中各种网络深度融合的网络系统

20、 为什么要学习计算思维 因为_。

答案: 不仅仅是其它三个选项的理由, 有很多理由说明大思维比小技巧更重要，思维的学习比知识的学习更重要

21、 计算之树概括了计算学科的经典思维，它是从几个维度来概括的？

答案: 六个维度：计算技术的奠基性思维、通用计算环境的演化思维、社会/自然与计算的融合思维、问题求解思维、网络化思维和数据化思维

22、 计算之树中，计算技术的奠基性思维包括__。

答案: 0和1、程序和递归

23、 如何学习计算思维？

答案: 其它三个选项都是正确的

第2讲 符号化、计算化与自动化 第2讲测验

1、 易经的乾卦是从“天”这种自然现象抽象出来的，为什么称其为“乾”而不称其为“天”呢？______。

答案: “天”是一种具体事物，只能在自然空间中应用，若变换到不同空间应用，可能会引起混淆；而“乾”是抽象空间中的概念，是指具有“天”这种事务的性质，应用于不同的空间时不会产生这种问题

2、 易经的符号化案例，启示我们______。

答案: 其它选项的说法都正确

3、 关于汉字内码，下列说法不正确的是______。

答案: 汉字内码是机器存储和显示汉字所使用的编码

4、 0和1的思维反映了语义符号化→符号计算化→计算0(和)1化→0(和)1自动化→分层构造化→构造集成化，关于此思维的说法不正确的是______。

答案: 其它三个选项的说法有不正确的

5、 假设基本门电路的符号为，已知如下电路 问该电路所实现的正确的逻辑运算为______。

答案: P = A XOR B

6、 下列说法不正确的是______。

答案: 其它三个选项的说法有不正确的

7、 已知：关于和的逻辑运算式如下：= (XOR) XOR= (AND) OR ((XOR) AND)如果= 1，= 1，= 1，则，的值为______。

答案: 1,1

8、 假设基本门电路的符号为，已知如下电路问该电路不能实现的功能为______。

答案: 当A=1，B=1， 则P=1

9、 逻辑的符号化案例，启示我们______。

答案: 其它三个选项都正确

10、 将十六进制数586转换成16位的二进制数，应该是______。

答案: 0000 0101 1000 0110

11、 若用8位0，1表示一个二进制数，其中1位即最高位为符号位，其余7位为数值位。的原码、反码和补码表示，正确的是______。

答案: 00001111，00001111，00001111

12、 若用5位0，1表示一个二进制数，其中1位即最高位为符号位，其余4位为数值位。若要进行11 – 4的操作，可转换为11 + (-4)的操作，采用补码进行运算，下列运算式及结果正确的是______。

答案: 0 1011 + 1 1100 = 0 0111

13、 已知A-Z的ASCII码是41H- 5AH，请将下面一段ASCII码存储的文件解析出来，正确的是______。 “0100 0111 0100 0101 0100 0111 0100 0110 0100 1000 0100 0010”

答案: GEGFHB

14、 计算机内部使用的编码的基本特征是______。

答案: 唯一性和公共性

15、 已知：M、N和K的值只能有一个1，其他为0，并且满足下列所有逻辑式：((M AND (NOT K)) OR ((NOT M) AND K)) = 1；(NOT N) AND ((M AND (NOT K)) OR ((NOT M) AND K)) = 1；(NOT N) AND (NOT K) = 1；问：M、N、K的值为______。

答案: 1，0，0

16、 关于十进制245的下列说法不正确的是______。

答案: 它转换为二进制表示为1101 0101

17、 已知：关于和的逻辑运算式如下：= (XOR) XOR= (AND) OR ((XOR) AND)问：如果= 1，= 0，= 1，则，的值为______。

答案: 0，1

18、 易经是用0和1符号化自然现象及其变化规律的典型案例。 下列说法不正确的是______。

答案: 易经仅仅是以自然现象为依托，对人事及未来进行占卜或算卦的一种学说

19、 逻辑运算是最基本的基于“真/假”值的运算，也可以被看作是基于“1/0”的运算，1为真，0为假。关于基本逻辑运算，下列说法不正确的是______。

答案: “异或”运算是“相同为1，不同为0”

20、 将十进制数126.375转换成二进制数，应该是______。

答案: 0111 1110.0110

21、 下列数中最大的数是______。

答案:

22、 关于计算机为什么基于二进制数来实现，下列说法不正确的是______。

答案: 其它三个选项的说法有不正确的

23、 关于二进制算术运算，下列说法不正确的是______。

答案: 二进制算术运算的符号位不能和数值位一样参与运算但能得到正确的结果

24、 关于二进制数计算部件的实现，下列说法正确的是______。

答案: 设计和实现一个最简单的计算部件只需实现逻辑与、或、非、异或等基本运算即可，则所有加减乘除运算即可由该计算部件来实现

25、 关于二进制小数的处理，下列说法不正确的是______。

答案: 其它选项的说法有不正确的

26、 若用8位0，1表示一个二进制数，其中1位即最高位为符号位，其余7位为数值位。的原码、反码和补码表示，正确的是______。

答案: 10010010，11101101，11101110

27、 若用5位0，1表示一个二进制数，其中1位即最高位为符号位，其余4位为数值位。若要进行-7 – 4的操作，可转换为(-7) + (-4)的操作，采用补码进行运算，下列运算式及结果正确的是______。

答案: 1 1001 + 1 1100 = 1 0101

28、 若用5位0，1表示一个二进制数，其中1位即最高位为符号位，其余4位为数值位。若要进行-7 – 13的操作，可转换为(-7) + (-13)的操作，采用补码进行运算，下列运算式及结果正确的是______。

答案: 1 1001 + 1 0011 = 0 1100(溢出)

29、 关于汉字外码，下列说法不正确的是______。

答案: 汉字外码有拼音码、音型码、字型码和字模点阵码

30、 假设基本门电路的符号为已知如下电路 问该电路不能实现的功能为______。

答案: 当A=0，B=1， 则P=0

31、 假设基本门电路的符号为已知如下电路 问该电路所实现的正确的逻辑运算为______。

答案: P = A XOR B

32、 假设基本门电路的符号为已知如下电路 问该电路不能实现的功能为______。

答案: 当A=1，B=1， 则P=1

33、 关于十进制235，下列正确的是______。

答案: 其ASCII码为0011 0010 0011 0011 0011 0101

第3讲 程序与递归：组合、抽象与构造 第3讲测验

1、 关于递归定义的函数，下列说法正确的是_____。

答案: 有些递归定义的函数可以“迭代计算”，有些递归定义的函数则必须“递归计算”

2、 递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示： 任何一个A(m, n)都可以递归地进行计算，例如A(1,2)的递归计算过程如下所示：A(1,2) = A(0,A(1,1)) = A(0, A(0,A(1,0))) = A(0, A(0,A(0,1)))=A(0,A(0,2))=A(0,3)=4。请你按上述方法递归计算下列项，并判断，计算结果正确的是_____。

答案: A(1, n) = n + 2

3、 递归计算是重要的执行手段。例如一种形式的阿克曼函数如下所示： 任何一个A(n, m)都可以递归地进行计算，例如m=1时，A(n,1)的递归计算过程如下所示：m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2n请你按上述方法递归计算m=2时，即A(n,2)，并判断计算结果正确的是_____。

答案: A(n, 2) =

4、 用递归是可以定义语言的。如表述命题逻辑的一种语言可以如下定义：(1)一个命题是其值为真或假的一个判断语句；(2)如果X是一个命题，Y也是一个命题，则X and Y，X or Y, not X也是一个命题；(3)如果X是一个命题，则(X)也是一个命题，括号内的命题运算优先；(4)命题由以上方式构造。若X，Y，Z，M等均是一个命题，问不符合上述递归定义的语句是_____。

答案: ( X and Y not Z)

5、 已知f(x)=5，，其中均为自然数，新函数h可递归的构造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，请按递归式进行计算下列式子，正确的是_____。

答案: h(1，x) = 5

6、 用条件运算符定义一个过程。正确的定义为_____。

答案:

7、 一般而言，设计和实现一个计算系统，需要设计和实现_____。

答案: 基本动作、控制基本动作的指令和一个程序执行机构

8、 关于计算系统与程序，下列说法正确的是_____。

答案: 任何系统都需要程序，只是这个程序是由人来执行还是由机器自动执行，可以由机器自动执行程序的系统被称为计算系统

9、 已知一个新运算被定义为(define (newCalc x y) ( (+ x 1) ( y 2)))，问正确使用了newCalc并得到正确结果的为_____。

答案: (newCalc 4 5)，其结果为50

10、 关于“程序”和“递归”的关系，下列说法不正确的是_____。

答案: 其它选项的说法有不正确的

11、 用条件运算符定义一个过程。正确的定义为_____。

答案:

12、 已知一个运算被定义为(define (firstCalc x) (* x x))，在其基础上进一步定义新运算secondCalc为，下列运算组合式书写正确的是_____。

答案: (define (secondCalc x y z) (+ (firstCalc x) (firstCalc y) (firstCalc z)))

13、 已知一个运算被定义为(define (firstCalc x) (* x x))，在其基础上进一步定义新运算为(define (secondCalc x) (firstCalc (firstCalc (firstCalc x))))，问secondCalc表达的运算功能为_____。

答案:

14、 若要表达从1计算到n的运算组合式，(…( ( ( (* 1 1) 2) 3) 4)…n)定义一个过程。正确的定义为_____。

答案:

15、 按原始递归的定义，h是由f和g递归地构造出来的。假设已知h(n) = n!，请给出构造h的f和g的函数。正确的是_____。

答案: f()是常数为1的函数；

16、 已知，,其中均为自然数，新函数h可递归的构造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，请按递归式进行计算下列式子，不正确的是_____。

答案: h(4，x) = 12x

17、 斐波那契数列与阿克曼函数都是递归函数，但它们是不同的，下列说法不正确的是_____。

答案: 阿克曼函数也可如斐波那契数列一样自前项(第n-1项)计算到后项(第n项)

18、 已知f(x)=x，, 其中均为自然数，新函数h可递归的构造如下：h(0,x) = f(x), 且h(S(n), x) = g(h(n,x),n,x)，请按递归式进行计算下列式子，正确的是_____。

答案: h(4，x) = 5x+6

19、 已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1)))，问(newCalc (newCalc (newCalc 1 1) 2) 3)的计算结果为_____。

答案: 64

20、 已知一个新运算被定义为(define (newCalc x y) (* (+ x 1) (+ y 1)))，问(newCalc (newCalc (newCalc 1 1) (newCalc 1 1)) (newCalc 1 1))的计算结果为_____。

答案: 130

21、 关于“递归”，下列说法不正确的是_____。

答案: “递归”与递推式一样，都是自递推基础计算起，由前项(第n-1项)计算后项(第n项)，直至最终结果的获得

22、 关于程序，下列说法不正确的是_____。

答案: 其它选项的说法有不正确的

23、 关于“递归”，下列说法不正确的是_____。

答案: 其它选项的说法不全正确

24、 关于原始递归函数的理解，下列说法不正确的是_____。

答案: 其它选项的说法有不正确的

25、 对于计算式，其正确的运算组合式(前缀表示法)为_____。

答案: (/ (+ 10 (/ 20 (+ 8 4))) (+ (3 6) (* 8 2)))

26、 关于程序，下列说法不正确的是_____。

答案: 普通人是很难理解“程序”的，其也和“程序”无关

27、 请用define运算，定义一个过程实现计算，其正确定义的过程为_____。

答案: (define (cube x) (* x x x))

28、 熟悉下列运算组合式(前缀表达式)，其中结果为56的是_____。

答案: ((+ 5 3) (+ 5 2))

29、 已知一个新运算被定义为(define (newCalc x y) ( (+ x 1) ( y 2)))，问newCalc可以完成的计算功能为_____。

答案: (x+1)*2y

第4讲 冯.诺依曼计算机—机器级程序及其执行 第4讲测验

1、 关于“存储程序”，下列说法不正确的是_____。

答案: 依据“存储程序”原理，机器可由四大部分构成：运算器、存储器、输入设备和输出设备

2、 已知某机器的核心部件及其结构关系如下图示意。请仔细理解该结构图，并回答问题。当CPU在读取指令阶段，下列说法正确的是_____。

答案: 第1个节拍进行A1，C3；第2个节拍进行D1，C2，D6

3、 已知某机器的核心部件及其结构关系如下图示意。请仔细理解该结构图，并回答问题。当CPU在执行指令阶段，假设当前执行的指令“00000100 00001000—将8号单元内容取出到寄存器中并与运算器中寄存器的值相乘，结果保留在中”，则下列说法正确的是_____。

答案: 第3个节拍进行A2，C3，C1；第4个节拍进行D1，C4，D2；第5个节拍进行C5

4、 已知某机器的指令集合及指令格式如下表示意。 已经编制好并存储在存储器中的一段程序如下表示意，请阅读这段程序，并回答问题。 若要使该程序完成计算，则需修正存储的数据，正确的修正是_____。

答案: 8号存储单元存放数00000000 00000011，9号存储单元存放数00000000 00001000，10号存储单元存放数00000000 00000010，11号存储单元存放数 00000000 00000110

5、 下图是一个存储器的简单模型-与或阵列图。 围绕该存储器模型，请写出由、、、产生、、、、的逻辑表达式，书写不正确的是_____。

答案:

6、 关于“图灵机”，下列说法不正确的是_____。

答案: 其它三个选项有不正确的

7、 关于“图灵机”和“计算”，下列说法不正确的是_____。

答案: 其它三个选项有不正确的

8、 下图是一个存储器的简单模型。内容为1010的存储单元的地址编码是_____。

答案: 10

9、 已知某机器的指令集合及指令格式如下表示意。 已经编制好并存储在存储器中的一段程序如下表示意，请阅读这段程序，并回答问题。 该程序所能完成的计算是_____。

答案:

10、 已知某机器的指令集合及指令格式如下表示意。 已经编制好并存储在存储器中的一段程序如下表示意，请阅读这段程序，并回答问题。 关于存储器存放的内容，下列说法正确的是_____。

答案: 3号存储单元存放的是指令，而8号存储单元存放的是数据

11、 已知某机器的核心部件及其结构关系如下图示意。请仔细理解该结构图，并回答问题。当CPU在执行000100 0000001001指令时，IR的值是_____。

答案: 00010000 00001001

12、 已知某机器的核心部件及其结构关系如下图示意。请仔细理解该结构图，并回答问题。关于机器指令的执行，则下列说法不正确的是_____。

答案: 没有时钟与节拍发生器，机器的指令也能正确地执行

13、 下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5}，其中S1为起始状态，S5为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。 该图灵机的功能是_____。

答案: 将形如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串转换为XXXYYY， XXXXYYYY的形式

14、 下图为用状态转换图示意的一个图灵机，其字母集合为{0,1,X,Y,B}，其中B为空白字符；状态集合{S1，S2，S3，S4，S5，S6}，其中S1为起始状态，S6为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。 该图灵机的功能是_____。

答案: 识别是否如000111，00001111的0、1串，即左侧连续0的个数和右侧连续1的个数相同的0、1串

15、 下图是一个存储器的简单模型。为01的存储单元，其内容是_____。

答案: 0111

16、 下图是一个存储器的简单模型。当=10时,的内容是_____。

答案: 101010

17、 已知一个存储器芯片M的4位二进制地址编码为，其8条数据线为。如果需要构造256个存储单元且每个存储单元的字长为16位的存储器，问下列说法正确的是_____。

答案: 总计需要M芯片32个

18、 关于“冯.诺依曼计算机”的结构，下列说法正确的是_____。

答案: 以“运算器”为中心的冯.诺依曼计算机和以“存储器”为中心的冯.诺依曼计算机是有差别的，前者不能实现并行利用各个部件，受限于运算器；后者可以实现并行利用各个部件

19、 已知一个存储器芯片M的4位二进制地址编码为，其8条数据线为。如果需要构造64个存储单元且每个存储单元的字长为16位的存储器，该存储器的6位二进制地址编码线为，16条数据线为，问下列说法正确的是_____。

答案: 总计需要M芯片8个，分成4组，每组两个；将分别连接到8个M芯片的上；将用一个2-4译码器进行译码形成4条控制线，每一条控制一组中的两个M芯片；将分别连接到这4个组中的第一个芯片的上，而将分别连接到这4个组中的另一个芯片的上

20、 下图是一个存储器的简单模型。下列说法不正确的是_____。

答案: 该存储器既可读出，又可写入

21、 下图是一个存储器的简单模型。当存储单元的内容是100101时，其存储单元的地址编码是_____。

答案: 00

22、 已知一个存储器芯片M的4位二进制地址编码为，其8条数据线为，下列说法正确的是_____。

答案: 该存储器共有即16个存储单元

23、 已知某机器的指令集合及指令格式如下表示意。 已经编制好并存储在存储器中的一段程序如下表示意，请阅读这段程序，并回答问题。 存储器2号存储单元中存放的指令功能是_____。

答案: 将运算器中寄存器A的数，加上10号存储单元的数，结果保留在运算器的寄存器A中

24、 已知某机器的指令集合及指令格式如下表示意。 已经编制好并存储在存储器中的一段程序如下表示意，请阅读这段程序，并回答问题。 存储器1号存储单元中存放的指令功能是_____。

答案: 将运算器中寄存器A的数，乘以9号存储单元的数2，结果保留在运算器的寄存器A中

25、 保存下一条将要执行的指令地址的寄存器是_____。

答案: PC

26、 保存正在执行指令的寄存器是_____。

答案: IR

27、 已知某机器的核心部件及其结构关系如下图示意。请仔细理解该结构图，并回答问题。当CPU在执行000100 0000001001指令时，PC的值是_____。

答案: 00000000 00000010

28、 已知某机器的指令集合及指令格式如下表示意。 已经编制好并存储在存储器中的一段程序如下表示意，请阅读这段程序，并回答问题。 若要使该程序完成任意方程式，则需修正存储的数据，正确的修正是_____。

答案: 8号存储单元存放数x的二进制数，9号存储单元存放数a的二进制数，10号存储单元存放数b的二进制数，11号存储单元存放数c的二进制数

29、 下图是一个存储器的简单模型-与或阵列图。 围绕该存储器模型，请写出由、产生、、、的逻辑表达式，书写正确的是_____。

答案:

30、 下图为用状态转换图示意的一个图灵机，其字母集合为{V，C，+，=，“空格”，；}；状态集合{S1，S2，S3，S4，S5，S6，S7}，其中S1为起始状态，S7为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，null表示什么也不写，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。 该图灵机的功能是_____。

答案: 其它三个选项全部能够识别

31、 下图为用状态转换图示意的一个图灵机，其字母集合为{V，C，+，=，“空格”，；}；状态集合{S1，S2，S3，S4，S5，S6，S7}，其中S1为起始状态，S7为终止状态；箭头表示状态转换，其上标注的如<in, out, direction>表示输入是in时，输出out，向direction方向移动一格，同时将状态按箭头方向实现转换，其中in,out均是字母集中的符号，null表示什么也不写，direction可以为R(向右移动)、L(向左移动)、N(停留在原处)。 关于该图灵机的功能，说法不正确的是_____。

答案: 其它三个选项有该图灵机不能识别的符号串形式

第5讲 现代计算机—复杂环境下程序执行 第5讲测验

1、 关于现代计算机系统，下列说法正确的是_____。

答案: 人们认为，计算机不仅仅包括硬件和软件，还包括网络和数据，很多的软件都可通过网络来使用，人们的注意力已经从关注软硬件转移为关注各种各样的数据

2、 关于“计算机软件”，下列说法正确的是_____。

答案: 计算机软件包括操作系统、计算机语言处理系统、辅助性工具软件以及各种应用软件

3、 关于“存储体系”，下列说法正确并完整的是_____。

答案: 其它三个选项的说法全都正确

4、 关于“磁盘”，下列说法不正确的是_____。

答案: CPU可以一个存储字一个存储字地读写磁盘

5、 关于“内存”，下列说法不正确的是_____。

答案: 当机器断电时，内存信息会短暂保留

6、 关于“操作系统”，下列说法不正确的是_____。

答案: 操作系统仅仅是管理CPU执行任何应用程序的一组程序

7、 关于操作系统体现了“分工-合作-协同”的基本思想，下面说法不正确的是_____。

答案: 其它三个选项的说法有不正确的

8、 磁盘上有一些重要的区域，那里存放着操作系统管理磁盘所要使用的重要信息。这些区域是_____。

答案: 其它三个选项全部包括

9、 操作系统管理信息的基本单位是_____。

答案: 文件

10、 文件分配表中记录的是文件在磁盘上存储的簇块链—一个簇块可以是一个扇区或是若干连续的扇区，如果文件分配表被破坏了会带来什么影响？

答案: 其它三个选项全部正确

11、 下图给出了操作系统管理磁盘与文件的基本思路图，关于“文件1”的下列说法不正确的是_？

答案: 该文件的第3个簇块是第24号簇块—此信息存放在FAT表的第32号表项中

12、 操作系统管理内存的基本思路可以用学校教务处管理教学楼和教室来类比，通过类比回答，下列哪些问题不是内存管理的基本问题？

答案: 内存与外存的信息交换问题–读写磁盘，即将外存中的信息读出到内存中，或者将内存中的信息更改返存到磁盘中

13、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。请关注图中第④号线。箭头线④的含义指将应用程序由外存中装载到内存中，这项工作被称为“程序装载作业”；关于“程序装载作业”，下列说法正确的是_。

答案: 程序装载作业是由“作业和进程管理程序”，调用“磁盘管理程序暨<程序装载>程序”完成的

14、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。请关注图中的“合作：操作系统对任务、作业和进程的管理与控制”部分，执行该“合作”工作的也是一个进程，关于该进程，下列说法不正确的是_。

答案: 执行“合作”工作的进程，是应用程序进程的一个重要组成部分

15、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。图中示意的是一个CPU面对多个进程的情况，关于这个问题，下列说法不正确的是_。

答案: 一个CPU只能执行一个进程。执行另一个进程时需将前一个进程从内存中清除以腾出空间给后一个进程使用

16、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。图中示意的是一个CPU面对多个进程的情况。现在很多的微处理器都可能是多核微处理器，即有多个CPU。关于多CPU问题，下列说法正确的是_。

答案: 多个CPU可以执行多个进程， 多个进程可以被分配到不同的CPU上同时执行

17、 操作系统有启动阶段、工作阶段和关闭阶段。问下列工作，哪些不是启动阶段的工作？

答案: 将内存内容写回外存中

18、 操作系统有启动阶段、工作阶段和关闭阶段。问下列工作，哪些不是关闭阶段的工作？

答案: 加载服务程序

19、 关于计算机系统的工作过程，下列说法不正确的是_。

答案: 计算机接通电源后执行的第一个程序就是内存中的操作系统程序

20、 关于装载进内存的程序，下列说法正确的是_。

答案: 正确的装载次序：ROM-BIOS→操作系统→应用程序

21、 你理解什么是云吗 下列说法不正确的是_。

答案: 虽然软件商通过“云”可以收集客户相关的信息，但这些信息是没有什么价值的

22、 你理解什么是云吗 下列说法不正确的是_。

答案: 普通人将自己的数据放在“云”中，更多的是他们相信云是安全的、可靠的，而云也确实是安全的、可靠的

23、 下图给出了操作系统管理磁盘与文件的基本思路图。文件分配表与所能够管理的磁盘空间大小是有关系的。例如磁盘的一簇被定义为4KB(8个扇区)，则文件分配表的大小，即表项的多少，为所能管理的簇的数目的多少。如果一个文件分配表的表项数为，问其能管理的磁盘空间为_？

答案: KB

24、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。关于“操作系统”和“应用程序”，下列说法不正确的是_。

答案: 操作系统自身的进程，不由操作系统调度和执行；操作系统仅管理各个应用程序的进程

25、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。请关注图中第⑥⑦⑧号线。箭头线⑥的含义指为管理CPU的使用，需要对每个进程的基本信息进行管理；箭头线⑦的含义指若要使CPU从一个进程的执行切换到另一个进程的执行，需要保留当前正在执行的进程的相关状态信息，并将下一个要执行进程的指令代码的存储单元地址送给CPU的程序计数器PC；箭头线⑧的含义指“进程”被CPU执行。下列说法不正确的是_。

答案: 其它选项的说法有不正确的

26、 下图给出了操作系统管理磁盘与文件的基本思路图，观察“文件2”在磁盘上的存储，图中的FAT表还没有给出其簇块链的信息。填写FAT表关于文件2的信息，下列说法不正确的是_？

答案: FAT表的第51号表项应该填写49，第49号表项应该填写End

27、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。这里的“复杂环境”是相对于“内存中单一程序由CPU执行的简单环境”。那么关于环境“复杂性的体现”，下列说法正确的是_。

答案: 其它选项都是复杂性的体现，然而复杂性不限于这些

28、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。关于“程序”与“进程”，下列说法不正确的是_。

答案: 其它选项的说法有不正确的

29、 现代计算环境是多样化的。关于现代计算环境，下列说法不正确的是_。

答案: 其它选项的说法有不正确的

30、 在使用计算机时，若直接通过断电的方式来关闭机器，会存在什么问题，下列说法不正确的是_。

答案: 因瞬时电路冲击，将造成计算机硬件，如主板等的损坏

31、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。关于“任务”、“作业”与“进程”，下列说法不正确的是_。

答案: 其它选项的说法有不正确的

32、 你理解什么是云吗 下列说法不正确的是_。

答案: 云虽可定制任意数目CPU、任意容量内存和外存构成的计算机，但这样的计算机也是没有什么实用价值的

33、 关于磁盘与文件管理，下列说法不正确的是_____。

答案: 其它选项的说法有不正确的

34、 下图给出了操作系统管理磁盘与文件的基本思路图，观察“文件3”在磁盘上的存储，图中的FAT表没有给出其全部的簇块链的信息。填写FAT表关于文件3的信息，下列说法正确的是_？

答案: FAT表的第27号表项应该填写28

35、 下图给出了操作系统管理磁盘与文件的基本思路图。文件分配表与所能够管理的磁盘空间大小是有关系的。如果磁盘的一簇被定义为1KB(2个扇区)，文件分配表的表项数为，则其能管理的磁盘空间大小为KB。现在磁盘空间已经为KB，问该如何进行管理呢_？

答案: 将原来一簇为1KB，重新定义为一簇为16KB

36、 下图为复杂环境中，在操作系统管理下进行程序执行的基本思想示意图。复杂环境中程序的执行，需要解决_。

答案: 其它选项的所有问题，并且注意其使用的次序

37、 关于普通计算机的主机箱中有什么，下列说法正确的是_____。

答案: 主机箱中有电源，主板。主板上有微处理器和内存(条)；还有各种磁盘驱动器被连接到主板上进而接受CPU的控制；主板上还有若干个插槽，这些插槽可用于各种外部设备的接口电路板与主板的连接；主板上也有若干已做好的接口，直接用于连接各种外部设备

第6讲 由机器语言到高级语言—程序编写编译 第6讲测验

1、 关于表达式，下列说法不正确的是_____。

答案: 比较表达式中不能含有算术表达式，逻辑表达式中可以含算术表达式

2、 已知A=40；B=30；C=100；D=50，计算表达式　(A + (C – B) *3) / D　的值，结果为_____。

答案: 5

3、 已知A=40；B=30；C=100；D=50，计算表达式　(A * A – B * B) + D　的值，结果为_____。

答案: 750

4、 已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式　(A > B) and (B < C )的值，结果为_____。

答案: 真

5、 已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式C > A +B +D的值，结果为_____。

答案: 假

6、 已知程序如下，若X=10, Y=50, Z=30该程序执行完成后，X的值为_____。X=Z+Y；
IfY<Z{
X=X–Y；}
Else{
X=X–Z；}
X=X–Y；
IfX<Z{X=Y+20；}
X=X–Z；
IfX>Y{X=X–Y；}

答案: 40

7、 读程序，并回答问题：程序行(60)执行了多少次？次数为_____。(10) N=6；
(20) X=0；
(30) Y=1；
(40) ForI=1ToN-1Step1
(50) Z=X+Y；
(60) X=Y；
(70) Y=Z；
(80) NextI；

答案: 5

8、 关于计算机语言的编译，下列说法不正确的是_____。

答案: 其它三个选项有不正确的

9、 已知如下多元素变量，已知I=2；J=4；则M[I][J]的值为_____。

答案: 44

10、 已知如下多元素变量，已知I=2；J=2；则M[I+1][J+1]的值为_____。

答案: 0

11、 已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式　(A > B +20 ) or (B +60 < C )的值，结果为_____。

答案: 真

12、 已知如下多元素变量，已知I=1；J=1；则M[I+1][J]+2的值为_____。

答案: 47

13、 已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式A + A * 5的值，结果为_____。

答案: 240

14、 已知如下多元素变量。 执行下列程序，执行完成后，Sum1和Sum2的值分别为_____。(10)intJ；
(20)intSum1=0，Sum2=0；
(30)ForJ=1to4Step1
(40){Sum1=Sum1+M[J][J]；
(50)Sum2=Sum2+M[5-J][5-J]；}

答案: 66,66

15、 已知函数Fact的程序如下，在执行Fact(4)的过程中，Fact函数被调用的次数为_____。 LongIntFact(intn)
{ LongIntx;
If(n>1)
{ x=Fact(n-1);
return(n+x)*2;}
elsereturn1;
}

答案: 4

16、 已知程序如下，该程序实现的功能为_____。main()
{
inti,n;
longsum=0,p=1;
…//输入n值的语句，略
for(i=1;i<=n;i++)
{
p=pi;
sum=sum+p;
}
…//输出sum值的语句，略
}

答案: sum = 1!+2!+…+n!

17、 已知X=21，Y=15，Z=22，计算表达式((X>Y) or (Y>Z)) and ((X<Y) or (Y<Z))的值，结果为_____。

答案: 真

18、 已知X=21，Y=15，Z=22，计算表达式((X>Y) AND (Y>Z)) OR ((X<Y) AND (Y<Z))的值，结果为_____。

答案: 假

19、 已知程序如下，若X=30, Y=30, Z=30该程序执行完成后，X的值为_____。X=Z+Y；
IfY<Z{
X=X–Y；}
Else{
X=X–Z；}
X=X–Y；
IfX<Z{X=Y+20；}
X=X–Z；
IfX>Y{X=X–Y；}

答案: 20

20、 读程序，并回答问题：该程序执行完成后，X的值为_____。X=1；
Y=2；
Sum=0；
Do{ 　Sum=X+Y；
X=X+1；
Y=Y+1；
}While(Sum<=20)；

答案: 11

21、 读程序，并回答问题：该程序执行完成后，Z的值为_____。(10) N=6；
(20) X=0；
(30) Y=1；
(40) ForI=1ToN-1Step1
(50) Z=X+Y；
(60) X=Y；
(70) Y=Z；
(80) NextI；

答案: 8

22、 已知函数Fact的程序如下，在执行Fact(5)的过程中，Fact函数被调用的次数为_____。 LongIntFact(intn)
{ LongIntx;
If(n>1)
{ x=Fact(n-1);
returnn*x;}
elsereturn1;
}

答案: 5

23、 关于不同抽象层面的计算机，下列说法不正确的是_____。

答案: 不同抽象层次的计算机指的是各种抽象层次的硬件系统，只有硬件计算机才能被称为计算机

24、 已知函数Fact的程序如下，Fact(4)的值为_____。 LongIntFact(intn)
{ LongIntx;
If(n>1)
{ x=Fact(n-1);
return(n+x)*2;}
elsereturn1;
}

答案: 44

25、 关于计算机语言，下列说法不正确的是_____。

答案: 所有源程序最后都需被转换为汇编语言程序，机器才能够执行

26、 关于普通计算机语言(或者说程序)的基本构成要素，下列说法最完整的是_____。

答案: 常量与变量、表达式、语句和函数

27、 读程序，并回答问题：该程序执行完成后，N的值为_____。N=101;
IfN/2==0Then
N=N/2;
Else
N=N*3+1;
EndIf

答案: 304

28、 关于计算机语言，下列说法不正确的是_____。

答案: 其它三个选项有不正确的

29、 从语言编译角度看计算机语言，下列说法不正确的是_____。

答案: 其它三个选项有不正确的

30、 已知如下多元素变量。 执行下列程序，执行完成后，Sum1和Sum2的值分别为_____。(10)intI=3，J；
(20)intSum1=0，Sum2=0；
(30)ForJ=1to4Step1
(40){Sum1=Sum1+M[I][J]；
(50)Sum2=Sum2+M[J][I]；}

答案: 149,105

31、 已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式A < A * 5的值，结果为_____。

答案: 真

32、 已知如下多元素变量。 执行下列程序，程序执行完成后，Sum1和Sum2的值分别为_____。(10)intJ；
(20)intSum1=0，Sum2=0；
(30)ForJ=1to4Step1
(40){Sum1=Sum1+M[J][J]；
(50)Sum2=Sum2+M[5-J][J]；}

答案: 66,95

33、 已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式(A> B) and (A<=B)的值，结果为_____。

答案: 假

34、 读程序，并回答问题：该程序执行完成后，K的值为_____。(10)K=0；
(20)I=2；
(30)While(I<=8)
(40){K=K+I；
(50)I=I+2；}

答案: 20

35、 已知X=21，Y=15，Z=22，计算表达式((X>Y) AND (Y>Z)) OR ((X<Z) AND (Y<Z))的值，结果为_____。

答案: 真

36、 读程序，并回答问题：程序行(40)执行了多少次？次数为_____。(10)K=0；
(20)I=2；
(30)While(I<=8)
(40){K=K+I；
(50)I=I+2；}

答案: 4

37、 已知程序如下，当程序行(60)执行了3次以后，Product和Counter的值分别为_____。(10)main()
(20){intcounter；
(30)…//输入N值的语句，略
(40)longproduct=1；
(50)forcounter=1toNstep2
(60){product=product*counter；}
(70)returnproduct;
(80)}

答案: 15，5

38、 已知程序如下，若X=10, Y=20, Z=30，该程序执行完成后，X的值为_____。X=Z+Y；
IfY<Z{
X=X–Y；}
Else{
X=X–Z；}
X=X–Y；
IfX<Z{X=Y+20；}
X=X–Z；
IfX>Y{X=X–Y；}

答案: 10

39、 读程序，并回答问题：该程序执行完成后，Sum的值为_____。X=1；
Y=2；
Sum=0；
Do{ 　Sum=X+Y；
X=X+1；
Y=Y+1；
}While(Sum<=20)；

答案: 21

40、 已知函数Fact的程序如下，Fact(4)的值为_____。 LongIntFact(intn)
{ LongIntx;
If(n>1)
{ x=Fact(n-1);
returnn*x;}
elsereturn1;
}

答案: 24

41、 关于不同抽象层面的计算机，由低层向应用层(高层)的基本层次划分是_____。

答案: 微程序机器实际机器操作系统机器汇编语言机器高级语言机器

42、 已知程序如下，该程序实现的功能为_____。(10)main()
(20){intcounter；
(30)…//输入N值的语句，假设N为偶数，略
(40)longproduct=1；
(50)forcounter=1toNstep2
(60){product=productcounter；}
(70)returnproduct;
(80)}

答案: product = 135…* (N-1)

第一章 信息的表示 第一章 信息的表示-在线测试

1、 1024的二进制表示可以记为____。

答案: 10000000000B

2、 关于汉字内码，下列说法不正确的是_____。

答案: 汉字内码是机器存储和显示汉字所使用的编码

3、 计算机内部使用的编码的基本特征是_____。

答案: 唯一性、公共性和易于记忆便于识认性

4、 若用5位0，1表示一个二进制数，其中1位即最高位为符号位，其余4位为数值位。若要进行11 – 4 的操作，可转换为11 + (-4)的操作，采用补码进行运算，下列运算式及结果正确的是_____。

答案: 0 1011 + 1 1100 = 0 0111

5、 在计算机中，信息的最小单位是_____。

答案: 位

6、 与二进制数11111110等值的十进制数是_。

答案: 254

7、 “人”计算与“机器”计算有什么差异 __

答案: “人”计算宁愿使用复杂的计算规则，以便减少计算量能够获取结果，“机器”计算则需使用简单的计算规则，以便于能够做出执行规则的机器;
“机器”计算使用的计算规则可能很简单但计算量却很大，尽管这样，对越来越多的计算，机器也能够完成计算结果的获得;
“机器”可以采用“人”所使用的计算规则，也可以不采用“人”所使用的规则

8、 下列说法正确的是_____。

答案: 数值信息可采用二进制数进行表示;
非数值信息可采用基于0/1的编码进行表示;
任何信息，若想用计算机进行处理，只需要将其用0和1表示出来即可

第7讲 算法-程序与计算系统之灵魂 第7讲测验

1、 一般而言，算法设计完成后，需要进行算法的模拟与分析。通常从哪些方面，进行算法的模拟与分析？

答案: 其它三个选项全部

2、 阅读下面的程序，其时间复杂度为___intindex=5;
intcondition=1;
if(condition==1)then
index++;
else
index–；
fori=1to100
forj=1to200
index=index+2;

答案: O(1)

3、 一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：算法的时间复杂性T(n)，可以通过评估算法基本语句的执行次数来获得。分析下列算法的时间复杂性。Startofthealgorithm(算法开始)
(1)输入结点的数目n；
(2)当前最短路径Path设为空，当前最短距离Dtemp设为最大值；
注：一个路径是n个结点的一个组合，任何一个结点在路经中不能重复出现
(3)组合一条新路径NewPath并计算该路径的距离D；
(4)如果D<Dtemp则Path=NewPath，且Dtemp=D；
(5)如果所有路径组合完毕，则结束；否则转第(3)步继续执行；
(6)输出Path及Dtemp；
Endofthealgorithm(算法结束)该算法的时间复杂性表达正确的是___。

答案: O(n!)

4、 一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：分析下列算法的时间复杂性。StartoftheAlgorithm
(1)S[1]=1;Sum=0;初始化距离数组D[n][n];
/I层的循环，即下列步骤为每次找出一个城市，I从2到n，即从找出第2个城市一直到找出第n个城市
(2)I=2;
/K层的循环，即下列步骤为从所有未访问过的城市中查找距离S[I-1]最近的城市j，K依然从2到n寻找
(3)K=2;
(4)将Dtemp设为一个大数(比所有两个城市之间的距离都大)
/L层的循环，即下列步骤为判断一个城市是否已被访问过，如果已被访问，则跳过该城市，寻找新的城市，L从1到I-1，因为已经有I-1个城市被访问过。
(5)L=1；
(6)如果S[L]==K，转步骤(10)；
(7)L=L+1；
(8)如果L<I，转步骤(6)；
/L层的循环结束
(9)如果D[K,S[I-1]]<Dtemp，j=K，Dtemp＝D[K,S[I-1]]；
(10)K=K+1;
(11)如果K<=N，转步骤(5)。
/K层的循环结束
(12)S[I]=j;
(13)Sum=Sum+Dtemp;
(14)I=I+1;
(15)如果I<=N，转步骤(3)，否则，转步骤(16);
/I层的循环结束
(16)Sum=Sum+D[1,j]；
(17)逐个输出S[N]中的全部元素;
(18)输出Sum。
EndoftheAlgorithm该算法的时间复杂性表达正确的是___。

答案:

5、 哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题： 参见图(c)，增加哪些边，使得能够找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？

答案: CG边

6、 哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题： 下面所示的图(c)，能否找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？

答案: 一定不能找到

7、 TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答 关于下列四个数学抽象，说法正确的是_____。

答案: 数学抽象I、II、III和IV都可以被认为是TSP问题

8、 数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示： 关于数组和存储器，下列说法不正确的是_____。

答案: 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个存储单元的地址

9、 堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。假定当前堆栈顶端指针top=10，欲将栈底的元素取出，其他的元素仍然保持在栈中，则需要进行_次弹出操作，_ 次推入操作

答案: 10，9

10、 阅读下列算法，回答：算法执行的结果为___。Startofthealgorithm(算法开始)
(1)N=10；
(2)i=2；sum=2；
(3)如果i<=N，则执行第(4)步，否则转到第(8)步执行；
(4)如果i%2==0则转到第(6)步执行；
(5)sum=sum+i；
(6)i=i+1；
(7)返回到第(3)步继续执行；
(8)输出sum的结果。
Endofthealgorithm(算法结束)

答案: 26

11、 算法的时间复杂性，可以表达为关于问题规模n的一个函数T(n)，T(n)可以用大O表示法来处理。问T(n)=O(f(n))是什么意思？正确的是___。

答案: T(n)是与f(n)同数量级的函数

12、 算法的时间复杂性T(n)，可以通过计算算法基本语句的执行次数来获得。分析下列程序的时间复杂性。(10)K=0；
(20)I=2；
(30)While(I<=8)
(40){K=K+I；
(50)I=I+2；}该程序时间复杂性表达正确的是___。

答案: O(1)

13、 对于算法类问题求解，下列说法正确的是___。

答案: 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤

14、 哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题： 下面所示的图(d)和图(e)，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？

答案: 图(d)一定不能找到；图(e)一定能够找到

15、 TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答关于TSP问题的遍历算法和贪心算法，下列说法正确的是_____。

答案: 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些

16、 算法是计算系统的灵魂，为什么？不正确的是_____。

答案: 问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛

17、 哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：对河流隔开的m块陆地上建造的n座桥梁，能否找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径呢？

答案: 不确定能不能找到

18、 背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下： 假定求解该问题的一种贪心策略是：优先选择能装下盒子中价格最高的，依据该算法策略所得到的解的总价值是_____。

答案: 15

19、 背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下： 假定求解该问题的一种贪心策略是：最大程度地利用背包的容量（15kg），依据该算法策略所得到的解的总价值是_____。

答案: 8

20、 关于数据结构，下列说法不正确的是_？

答案: 在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针

21、 关于算法的特性，下列说法不正确的是_____。

答案: 算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性

22、 关于算法的命题，下列说法不正确的是_____。

答案: 算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的

23、 关于算法与程序、计算机语言之间的关系，下列说法不正确的是_____。

答案: 算法只能由高级（计算机）语言实现，不能通过机器语言实现

24、 哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：哥尼斯堡七桥问题的路径能够找到吗？

答案: 一定不能找到

25、 哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题： 哥尼斯堡七桥问题，给我们的启示是_____。

答案: 其它三个选项都正确

26、 背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下： 该背包问题的可能解的数量是_____。

答案: 32

27、 背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下： 假定求解该问题的一种贪心策略是：优先选择能装下盒子中单位重量价值最高的，依据该算法策略所得到的解的总价值是_____。

答案: 15

28、 TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答关于TSP，下列说法不正确的是_____。

答案: TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合

29、 TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答关于TSP的贪心算法的求解思想，下列说法不正确的是_____。

答案: 贪心算法确定的路径，是由局部最优(即在看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的

30、 数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示： 请对照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[4][2]元素所对应的存储单元的存储地址为_____。

答案: 00000000 00001000

31、 堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。有关堆栈数据结构的基本运算，说法不正确的是_____。

答案: 其它三个选项的说法有不正确的

32、 关于数据结构，下列说法不正确的是_____。

答案: 其它选项的说法有不正确的

33、 哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题： 参见下图(f)，下列说法正确的是_____。

答案: 对两个顶点D和G，可以找到一条路径，从D出发走遍每一座桥，且每座桥仅走过一次，最后终止于G

34、 背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下： 使用遍历算法策略所得到的解的总价值是_____。

答案: 15

35、 “树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。 关于“树”这种数据结构，下列说法不正确的是_____。

答案: 其它三个选项的说法有不正确的

36、 堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。有关堆栈数据结构的说法，不正确的是_____。

答案: 堆栈按照先进先出（FIFO, First In First Out）的原理运作

37、 程序流程图是表达算法控制结构或者说算法步骤的重要方法。观察下图I.，没有错误的流程图为___。

答案: 没有无错误的流程图

38、 TSP算法流程图如下图I.示意，回答问题：最内层循环(L变量控制的循环)的作用是___。

答案: 用于判断某个城市是否是已访问过的城市

39、 算法的时间复杂性T(n)，可以通过计算算法基本语句的执行次数来获得。分析下列程序的时间复杂性。(10)sum=0；
(20)For(i=1;i<=n;i++)
(30)For(j=1;j<=n;j++)
(40)For(k=1;k<=j;k++)
(50)sum=sum+1；该程序时间复杂性表达正确的是___。

答案:

40、 算法的时间复杂性T(n)，可以通过计算算法基本语句的执行次数来获得。分析下列程序的时间复杂性。(10)sum=0；
(20)For(i=1;i<=n;i++)
(30)For(j=1;j<=n;j++)
(40)For(k=1;k<=5;k++)
(50)sum=sum+1；该程序时间复杂性表达正确的是___。

答案:

41、 一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：为什么要评估算法的复杂性？下列说法不正确的是___。

答案: 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的

42、 数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示： 请参照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[i][j]元素，与对应存储单元的存储地址的转换关系正确的为_____。

答案: D[i][j]元素的存储地址=数组的起始地址+((i-1)每行的列数+j-1)单一元素占用存储单元的数目

43、 “树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。 参照上图(I)，下列说法不正确的是_____。

答案: 当数据元素不发生变化，而只是数据元素之间的关系发生变化时，既需要调整数据元素本身，又需要调整其对应的左指针数组或右指针数组中的值来完成

44、 “树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。 上图(I)表示的数据的逻辑关系，下列正确的是_____。

答案: 图II.(d)

45、 “树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。 如想使图(I)，改变为存储下图IV所示的逻辑关系，下列四步操作都是需要的，但有些操作的内容却是不正确的。不正确的是_____。

答案: 将00000000 00010010号存储单元的值修改为00000000 00000010

46、 TSP算法流程图如下图I.示意，回答问题：中层循环(K变量控制的循环)的作用是___。

答案: 用于寻找距当前城市距离最近的城市

47、 TSP算法流程图如下图I.示意，回答问题：外层循环(I变量控制的循环)的作用是___。

答案: 用于完整地产生一个路径

48、 关于算法类问题的基本求解步骤，下列说法不正确的是___。

答案: 其它三个选项的说法有不正确的

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

1、 外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。 参见图示。如果：内存块数为，每块可装载个元素，待排序元素集合所占用磁盘块数，则关于此集合的排序问题，下列说法正确的是_____。

答案: 首先将待排序元素集合划分为4个子集合，每个子集合为6块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再对这4个已排序子集合进行归并操作，完成最终排序

2、 PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。 前述说过 PageRank，通过不断地计算来计算网页重要度，即由第(m-1)次的网页重要度来计算第(m)次的网页重要度，那么网页重要度的初始值应如何获得呢下列说法正确的是_____。

答案: 随机产生各网页重要度的一组值，使网页重要度界于0和1之间，但该组值对最终结果没有影响

3、 关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。 针对下列问题求解方法：对n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找次数最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。问该方法涉及到几类算法，说法正确的是_____。

答案: 涉及其它选项的全部算法

4、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}阅读BUBBLE-SORT算法，其中关于haschange变量的作用，下列说法不正确的是_____。

答案: 其它选项的说法有不正确的

5、 下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 算法A1Start of algorithm A1Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。End of algorithm A1算法A2Start of algorithm A2Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step 3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。End of algorithm A2算法A3Start of algorithm A3Step 1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step 2.计算中间记录位置I = (Start+Finish)/2，读取第I条记录。Step 3.判断第I条记录的成绩与给定查找分数：(3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2；(3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2；(3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。End of algorithm A3针对上述三个算法，回答问题：针对按成绩降序排列的数据表，假设记录数为n，关于算法A2，下列说法正确的是_____。

答案: 算法A2在最好的情况下是读取1条记录，在最差的情况是读取n条记录，才能得到结果

6、 外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。 参见图示。如果：内存块数为，待排序元素集合所占用磁盘块数，进行升序排序。如果：归并过程中，整体的数据集被从磁盘读入内存，再由内存写回磁盘，被称为一个轮次，则下列说法正确的是_____。

答案: 该数据集可以经过多于3个轮次的2路归并完成最终排序

7、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}关于INSERTION-SORT算法的基本思想，下列说法正确的是_____。

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

8、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}阅读BUBBLE-SORT算法，下列说法正确的是_____。

答案: 该算法在N=20时，最多要执行19个轮次的内循环

9、 外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。 参见图示。如果：内存块数为，每块可装载个元素，待排序元素集合所占用磁盘块数，采用排序-归并算法进行升序排序，下列说法正确的是_____。

答案: 算法以磁盘块读写次数衡量的时间复杂性为

10、 PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。 PageRank将网页的链接关系，抽象为一个n′n的矩阵A：网页被从1到n进行编号；如果网页i有一个指向网页j的链接，则矩阵的元素(即第i行第j列元素)值为1，否则矩阵元素值为0。然后将A做一个转置处理(即矩阵的行列互换)，形成转置矩阵，为什么要转置，原因是_____。

答案: 有利于由计算的权值矩阵M与网页重要度矩阵R的乘积符合网页重要度的计算方法：反向链接的加权和

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

答案: 其它三个选项全部正确

12、 外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。 参见图示。如果：内存块数为，待排序元素集合所占用磁盘块数，进行升序排序。如果：从磁盘装入内存，再从内存写回磁盘，被称为内存利用了一次，则下列说法正确的是_____。

答案: 该数据集基于“排序-归并”策略完成最终排序，需要利用内存19次

13、 外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。 关于内排序和外排序算法设计的关键点，下列说法不正确的是_____。

答案: 其它选项的说法有不正确的

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

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

15、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}关于SELECTION-SORT算法的基本思想，下列说法正确的是_____。

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

16、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}关于排序的选择法和冒泡法，下列说法不正确的是_____。

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

17、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}关于三种排序算法，下列说法正确的是_____。

答案: 尽管细致比较三种算法的执行时间是有差别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行

18、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}阅读BUBBLE-SORT算法，已知N=20，下列说法正确的是_____。

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

19、 外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。 关于“排序-归并”算法，下列说法不正确的是_____。

答案: 其它三个选项有不正确的

20、 外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。 参见图示，内存块数为，每块可装载个元素，如果经过一个轮次的归并操作便能完成排序，则关于待排序元素集合的大小，下列说法正确的是_____。

答案: 待排序元素数目应

21、 下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 算法A1Start of algorithm A1Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。End of algorithm A1算法A2Start of algorithm A2Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step 3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。End of algorithm A2算法A3Start of algorithm A3Step 1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step 2.计算中间记录位置I = (Start+Finish)/2，读取第I条记录。Step 3.判断第I条记录的成绩与给定查找分数：(3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2；(3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2；(3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。End of algorithm A3针对上述三个算法，回答问题：关于三个算法的复杂性，下列说法正确的是_____。

答案: 算法A1和A2的时间复杂性为O(n)，算法A3的时间复杂性为

22、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}关于BUBBLE-SORT算法的基本思想，下列说法正确的是_____。

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

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

答案: 其它选项都不正确

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

答案: 其所拥有的所有反向链接的加权和

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

答案: 网页重要度除以该网页所拥有的正向链接数

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

答案: 算法以磁盘块读写次数衡量的时间复杂性为

27、 下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 算法A1Start of algorithm A1Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。End of algorithm A1算法A2Start of algorithm A2Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step 3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。End of algorithm A2算法A3Start of algorithm A3Step 1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step 2.计算中间记录位置I = (Start+Finish)/2，读取第I条记录。Step 3.判断第I条记录的成绩与给定查找分数：(3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2；(3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2；(3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。End of algorithm A3关于算法A1, A2, A3的快慢问题，下列说法正确的是_____。

答案: 算法A3快于算法A2， 算法A2快于算法A1

28、 下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 算法A1Start of algorithm A1Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。End of algorithm A1算法A2Start of algorithm A2Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step 3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。End of algorithm A2算法A3Start of algorithm A3Step 1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step 2.计算中间记录位置I = (Start+Finish)/2，读取第I条记录。Step 3.判断第I条记录的成绩与给定查找分数：(3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2；(3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2；(3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。End of algorithm A3关于算法A3，下列说法正确的是_____。

答案: 对已按成绩进行降序排列的数据表，算法A3都适用

29、 下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 算法A1Start of algorithm A1Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。End of algorithm A1算法A2Start of algorithm A2Step 1.从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。Step 2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step 3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。End of algorithm A2算法A3Start of algorithm A3Step 1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step 2.计算中间记录位置I = (Start+Finish)/2，读取第I条记录。Step 3.判断第I条记录的成绩与给定查找分数：(3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2；(3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2；(3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。End of algorithm A3针对上述三个算法，回答问题：关于算法A3和算法A1，下列说法正确的是_____。

答案: 如果数据表中记录数越多，则算法A3相比算法A1的优势越明显，即查找时间越短

30、 关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。 上图给出了一种“自动获取文档关键词”的方法，关于该方法的表述，最好的是_____。

答案: 文档中去掉标点符号和一些辅助词汇， 出现次数最多且次数达到一定数值的词汇必定是关键词

31、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}阅读INSERTION-SORT算法，关于第4.行至第6.行间程序段的作用，下列说法正确的是_____。

答案: 将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向后移动一个位置

32、 下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1.fori=2toN
2.{key=A[i];
3.j=i-1;
4.While(j>0andA[j]>key)do
5.{A[j+1]=A[j];
6.j=j-1;}
7.A[j+1]=key;
8.}

SELECTION-SORT(A)
1.fori=1toN-1
2.{k=i;
3．forj=i+1toN
4.{ifA[j]<A[k]thenk=j;}
5.ifk<>ithen
6.{
7.temp=A[k];
8.A[k]=A[i];
9.A[i]=temp;
10.}
11.}

BUBBLE-SORT(A)
1.fori=1toN-1
2.{haschange=false;
3.forj=1toN-i
4.{ifA[j]>A[j+1]then
5.{temp=A[j];
6.A[j]=A[j+1];
7.A[j]=temp;
8.haschange=true;
9.}
10.}
11.if(haschange==false)thenbreak;
12.}阅读SELECTION-SORT算法，关于第3.行至第4.行间程序段的作用，下列说法正确的是_____。

答案: 循环地在未排序元素集合中找最小值元素的位置，该位置保存在变量k中

---

上方为免费预览版答案，如需购买完整答案，请点击下方红字

点击这里,购买完整版答案

---

为了方便下次阅读，建议在浏览器添加书签收藏本网页

添加书签方法：

1.电脑按键盘的Ctrl键+D键即可收藏本网页

2.手机浏览器可以添加书签收藏本网页

---

我们的公众号

打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP

本公众号可查看各种网课答案，还可免费查看大学教材答案

点击这里，可查看公众号功能介绍

---

 

疚谓富类盆唇擞菏酥狡就鲍镐