大学MOOC 计算与信息素养(哈尔滨师范大学)1003404001 最新慕课完整章节测试答案
第6讲 由机器语言到高级语言---程序编写编译
文章目录
第6讲之模拟练习题
1、单选题：
读程序，并回答问题：该程序执行完成后，N的值为_____。N = 101;
If N/2 == 0 Then
N = N/2;
Else
N = N * 3 + 1;
End If
选项：
A: 101
B: 55.5
C: 304
D: 167.5
答案: 【 304】
2、单选题：
已知程序如下，若X=30, Y=30, Z=30该程序执行完成后，X的值为_____。X = Z + Y；
If Y < Z {
X = X – Y； }
Else{
X= X – Z； }
X = X – Y；
If X < Z { X = Y +20； }
X = X – Z；
If X > Y { X = X – Y； }
选项：
A: 10
B: 20
C: 30
D: 40
答案: 【 20】
3、单选题：
读程序，并回答问题：该程序执行完成后，X的值为_____。 X=1；
Y=2；
Sum=0；
Do { Sum = X+Y；
X=X+1；
Y=Y+1；
} While (Sum<=20)；
选项：
A: 8
B: 9
C: 10
D: 11
答案: 【 11】
4、单选题：
读程序，并回答问题：程序行(60)执行了多少次？次数为_____。 (10) N = 6；
(20) X = 0；
(30) Y = 1；
(40) For I = 1 To N-1 Step 1
(50) Z = X + Y；
(60) X = Y；
(70) Y = Z；
(80) Next I；
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 5】
5、单选题：
已知函数Fact的程序如下，在执行Fact(5)的过程中，Fact函数被调用的次数为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return n*x; }
else return 1;
}
选项：
A: 3
B: 4
C: 5
D: 6
答案: 【 5】
6、单选题：
已知程序如下，该程序实现的功能为_____。(10) main()
(20) { int counter；
(30) ... //输入N值的语句，略
(40) long product = 1；
(50) for counter = 1 to N step 2
(60) { product = product * counter； }
(70) return product;
(80) }
选项：
A: product = 1*2*3*...*(N-1)
B: product = 1+ 2+3+...+ (N-1)
C: product = 1*3*5*...* (N-1)
D: product = 1+3+5+...+(N-1)
答案: 【 product = 1*3*5*...* (N-1)】
7、单选题：
关于计算机语言的编译，下列说法不正确的是_____。
选项：
A: 需要“分词”，将其中的常量、变量名和保留字识别出来，并分类及编号
B: 需要识别每一条语句所对应的“模式”。任意语句的常量和变量名被归为“标识符”类别，而标识符与保留字的不同组合关系构成了语句的模式；计算机语言是由有限的语句模式构成的
C: 对每一种模式，都有相应的组合构造方法，即模式可被认为是由原子模式或说基本模式通过组合的方法构造出来的，对原子模式或者基本模式可以事先写好其相应的目标语言的指令或语句
D: 上述有不正确的
答案: 【 上述有不正确的】
8、单选题：
关于普通计算机语言(或者说程序)的基本构成要素，下列说法最完整的是_____。
选项：
A: 常量与变量和表达式
B: 常量与变量、表达式和语句
C: 常量与变量、表达式、语句和函数
D: 都不完整
答案: 【 常量与变量、表达式、语句和函数】
9、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式A < A * 5的值，结果为_____。
选项：
A: 40
B: 200
C: 真
D: 假
答案: 【 真】
10、单选题：
已知如下多元素变量，已知I=2；J=4；则M[I][J]的值为_____。
选项：
A: 44
B: 83
C: 22
D: 21
答案: 【 44】
11、单选题：
已知如下多元素变量，已知I=2；J=2；则M[I+1][J+1]的值为_____。
选项：
A: 39
B: 11
C: 0
D: 16
答案: 【 0】
12、单选题：
已知程序如下，若X=10, Y=50, Z=30该程序执行完成后，X的值为_____。X = Z + Y；
If Y < Z {
X = X – Y； }
Else{
X= X – Z； }
X = X – Y；
If X < Z { X = Y +20； }
X = X – Z；
If X > Y { X = X – Y； }
选项：
A: 10
B: 20
C: 30
D: 40
答案: 【 40】
13、单选题：
已知如下多元素变量。
执行下列程序，执行完成后，Sum1和Sum2的值分别为_____。
(10) int I = 3，J；
(20) int Sum1=0，Sum2=0；
(30) For J=1 to 4 Step 1
(40) { Sum1 = Sum1 + M[I][J]；
(50) Sum2 = Sum2 + M[J][I]； }
选项：
A: 576,576
B: 136,175
C: 149,105
D: 105,149
答案: 【 149,105】
14、单选题：
读程序，并回答问题：该程序执行完成后，Sum的值为_____。 X=1；
Y=2；
Sum=0；
Do { Sum = X+Y；
X=X+1；
Y=Y+1；
} While (Sum<=20)；
选项：
A: 20
B: 21
C: 19
D: 18
答案: 【 21】
15、单选题：
已知如下多元素变量。
执行下列程序，执行完成后，Sum1和Sum2的值分别为_____。
(10) int J；
(20) int Sum1=0，Sum2=0；
(30) For J=1 to 4 Step 1
(40) { Sum1 = Sum1 + M[J][J]；
(50) Sum2 = Sum2 + M[5-J][5-J]； }
选项：
A: 95,95
B: 95,66
C: 66,95
D: 66,66
答案: 【 66,66】
16、单选题：
读程序，并回答问题：该程序执行完成后，K的值为_____。 (10) K = 0；
(20) I = 2；
(30) While(I<=8)
(40) { K = K + I;
(50) I = I + 2;}
选项：
A: 35
B: 20
C: 36
D: 12
答案: 【 20】
17、单选题：
关于不同抽象层面的计算机，由低层向应用层(高层)的基本层次划分是_____。
选项：
A: 高级语言机器
汇编语言机器操作系统机器实际机器微程序机器
B: 实际机器
微程序机器操作系统机器汇编语言机器高级语言机器
C: 微程序机器实际机器操作系统机器汇编语言机器高级语言机器
D: 上述都不正确
答案: 【 微程序机器实际机器操作系统机器汇编语言机器高级语言机器】
18、单选题：
已知函数Fact的程序如下，Fact(4)的值为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return (n+x)*2; }
else return 1;
}
选项：
A: 14
B: 24
C: 44
D: 64
答案: 【 44】
19、单选题：
关于计算机语言，下列说法不正确的是_____。
选项：
A: 汇编语言和机器语言是以指令为单位来编写程序
B: 高级语言是以语句为单位来编写程序，一条语句相当于若干条指令(或者说一条语句可用若干条指令来实现)
C: 面向对象语言或可视化构造语言是以对象(类)为单位来编写程序，一个对象相当于若干条语句((或者说一个对象可用若干条语句来实现)
D: 上述有不正确的
答案: 【 上述有不正确的】
20、单选题：
从语言编译角度看计算机语言，下列说法不正确的是_____。
选项：
A: 计算机语言就是由标识符和保留字构成的，标识符是可由程序员按规则任意命名的符号，而保留字则是编译器识别语句模式的重要符号
B: 计算机语言定义了基本元素的集合，以及基本元素的组合构造规则，所谓基本元素即是指标识符和保留字，所谓组合构造规则即是指语句的书写模式，即不同标识符和保留字的组合规则
C: 标识符可以是常量、变量名，也可以是函数名；保留字可以是赋值符号如“=”、语句结束符号如“；”、基本运算符号如“+”“-”“*”“/”、程序段落符号如“{ }”等，保留字还可以是其他语句模式的标志性符号
D: 上述有不正确的
答案: 【 上述有不正确的】
21、单选题：
已知A=40；B=30；C=100；D=50，计算表达式 (A * A - B * B) + D 的值，结果为_____。
选项：
A: 70
B: 150
C: 570
D: 750
答案: 【 750】
22、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式(A > B) and (A<=B)的值，结果为_____。
选项：
A: 40
B: 200
C: 真
D: 假
答案: 【 假】
23、单选题：
已知如下多元素变量。
执行下列程序，程序执行完成后，Sum1和Sum2的值分别为_____。
(10) int J；
(20) int Sum1=0，Sum2=0；
(30) For J=1 to 4 Step 1
(40) { Sum1 = Sum1 + M[J][J]；
(50) Sum2 = Sum2 + M[5-J][J]； }
选项：
A: 95,95
B: 95,66
C: 66,95
D: 66,66
答案: 【 66,95】
24、单选题：
读程序，并回答问题：该程序执行完成后，Z的值为_____。 (10) N = 6；
(20) X = 0；
(30) Y = 1；
(40) For I = 1 To N-1 Step 1
(50) Z = X + Y；
(60) X = Y；
(70) Y = Z；
(80) Next I；
选项：
A: 3
B: 5
C: 8
D: 13
答案: 【 8】
25、单选题：
已知函数Fact的程序如下，Fact(4)的值为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return n*x; }
else return 1;
}
选项：
A: 10
B: 24
C: 120
D: 15
答案: 【 24】
26、单选题：
关于计算机语言，下列说法不正确的是_____。
选项：
A: 所有源程序最后都需被转换为汇编语言程序，机器才能够执行
B: 所谓“高级语言”和“低级语言”是指其和机器硬件的相关程度，不涉及机器硬件的语言为高级语言，而与机器硬件相关的语言则为低级语言
C: 低级语言程序执行效率高是因为用低级语言编程时可以充分利用硬件的各种特殊性，而高级语言则只能使用硬件的标准结构
D: 高级语言编程效率高是因为其可用大粒度积木块来构造程序，比一行行语句、一条条指令来编程效率高出很多
答案: 【 所有源程序最后都需被转换为汇编语言程序，机器才能够执行】
27、单选题：
关于表达式，下列说法不正确的是_____。
选项：
A: 由常量、变量及各种算术运算符构造的表达式，被称为算术表达式，其结果为一数值
B: 由常量、变量和各种比较运算符构造的表达式，被称为比较表达式，其结果只能为逻辑“真”或“假”
C: 由常量、变量和各种逻辑运算符构造的表达式，被称为逻辑表达式，其结果只能为逻辑“真”或“假”
D: 比较表达式中不能含有算术表达式，逻辑表达式中可以含算术表达式
答案: 【 比较表达式中不能含有算术表达式，逻辑表达式中可以含算术表达式】
28、单选题：
已知A=40；B=30；C=100；D=50，计算表达式 (A + (C – B) *3) / D 的值，结果为_____。
选项：
A: 5
B: -5
C: 10
D: 4
答案: 【 5】
29、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式 (A > B +20 ) or (B +60 < C )的值，结果为_____。
选项：
A: 100
B: 30
C: 真
D: 假
答案: 【 真】
30、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式A + A * 5的值，结果为_____。
选项：
A: 400
B: 240
C: 真
D: 假
答案: 【 240】
31、单选题：
关于不同抽象层面的计算机，下列说法不正确的是_____。
选项：
A: 实际机器层面之上，不同层次的计算机即是指各种层次的软件系统
B: 实际机器层面之上，不同层次的计算机，其本质是为用户提供一个计算机语言，用户可用该语言表达具体的操作需求，同时提供一个编译器将操作需求转换为机器可以执行的程序，最终实现用户的操作需求
C: 不同抽象层次的计算机指的是各种抽象层次的硬件系统，只有硬件计算机才能被称为计算机
D: 上述有不正确的
答案: 【 不同抽象层次的计算机指的是各种抽象层次的硬件系统，只有硬件计算机才能被称为计算机】
32、单选题：
已知程序如下，若X=10, Y=20, Z=30，该程序执行完成后，X的值为_____。X = Z + Y；
If Y < Z {
X = X – Y； }
Else{
X= X – Z； }
X = X – Y；
If X < Z { X = Y +20； }
X = X – Z；
If X > Y { X = X – Y； }
选项：
A: 10
B: 20
C: 30
D: 40
答案: 【 10】
33、单选题：
读程序，并回答问题：程序行(40)执行了多少次？次数为_____。 (10) K = 0；
(20) I = 2；
(30) While(I<=8)
(40) { K = K + I;
(50) I = I + 2;}
选项：
A: 2
B: 4
C: 6
D: 8
答案: 【 4】
34、单选题：
已知函数Fact的程序如下，在执行Fact(4)的过程中，Fact函数被调用的次数为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return (n+x)*2; }
else return 1;
}
选项：
A: 3
B: 4
C: 5
D: 6
答案: 【 4】
35、单选题：
已知程序如下，该程序实现的功能为_____。main()
{
int i,n;
long sum = 0, p = 1;
...//输入n值的语句，略
for(i = 1; i <= n; i++)
{
p = p * i;
sum = sum + p;
}
...//输出sum值的语句，略
}
选项：
A: sum = 1*2*3*...*n
B: sum = 1!+2!+...+n!
C: sum = 1+2+3+...+n
D: sum = 1*2+2*3+(n-1)*n
答案: 【 sum = 1!+2!+...+n!】
36、单选题：
已知程序如下，当程序行(60)执行了3次以后，Product和Counter的值分别为_____。(10) main()
(20) { int counter；
(30) ... //输入N值的语句，略
(40) long product = 1；
(50) for counter = 1 to N step 2
(60) { product = product * counter； }
(70) return product;
(80) }
选项：
A: 105，5
B: 15，7
C: 15，5
D: 105，7
答案: 【 15，5】
37、单选题：
已知如下多元素变量，已知I=1；J=1；则M[I+1][J]+2的值为_____。
选项：
A: 13
B: 47
C: 8
D: 10
答案: 【 47】
38、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式 (A > B) and (B < C )的值，结果为_____。
选项：
A: 100
B: 30
C: 真
D: 假
答案: 【 真】
39、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式C > A +B +D的值，结果为_____。
选项：
A: 120
B: 100
C: 真
D: 假
答案: 【 假】
40、单选题：
已知X=21， Y=15， Z=22，计算表达式 ((X>Y) or (Y>Z)) and ((X<Y) or (Y<Z))的值，结果为_____。
选项：
A: 10
B: 4
C: 真
D: 假
答案: 【 真】
41、单选题：
已知X=21， Y=15， Z=22，计算表达式 ((X>Y) AND (Y>Z)) OR ((X<Y) AND (Y<Z))的值，结果为_____。
选项：
A: 10
B: 4
C: 真
D: 假
答案: 【 假】
42、单选题：
已知X=21， Y=15， Z=22，计算表达式 ((X>Y) AND (Y>Z)) OR ((X<Z) AND (Y<Z))的值，结果为_____。
选项：
A: 真
B: 假
C: 9
D: 4
答案: 【 真】
第6讲测验
1、单选题：
关于表达式，下列说法不正确的是_____。
选项：
A: 比较表达式中不能含有算术表达式，逻辑表达式中可以含算术表达式
B: 由常量、变量及各种算术运算符构造的表达式，被称为算术表达式，其结果为一数值
C: 由常量、变量和各种比较运算符构造的表达式，被称为比较表达式，其结果只能为逻辑“真”或“假”
D: 由常量、变量和各种逻辑运算符构造的表达式，被称为逻辑表达式，其结果只能为逻辑“真”或“假”
答案: 【 比较表达式中不能含有算术表达式，逻辑表达式中可以含算术表达式】
2、单选题：
已知A=40；B=30；C=100；D=50，计算表达式 (A + (C – B) *3) / D 的值，结果为_____。
选项：
A: 5
B: -5
C: 10
D: 4
答案: 【 5】
3、单选题：
已知A=40；B=30；C=100；D=50，计算表达式 (A * A - B * B) + D 的值，结果为_____。
选项：
A: 750
B: 70
C: 150
D: 570
答案: 【 750】
4、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式 (A > B) and (B < C )的值，结果为_____。
选项：
A: 真
B: 100
C: 30
D: 假
答案: 【 真】
5、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式C > A +B +D的值，结果为_____。
选项：
A: 假
B: 真
C: 120
D: 100
答案: 【 假】
6、单选题：
已知程序如下，若X=10, Y=50, Z=30该程序执行完成后，X的值为_____。X = Z + Y；
If Y < Z {
X = X – Y； }
Else{
X= X – Z； }
X = X – Y；
If X < Z { X = Y +20； }
X = X – Z；
If X > Y { X = X – Y； }
选项：
A: 40
B: 10
C: 20
D: 30
答案: 【 40】
7、单选题：
读程序，并回答问题：程序行(60)执行了多少次？次数为_____。 (10) N = 6；
(20) X = 0；
(30) Y = 1；
(40) For I = 1 To N-1 Step 1
(50) Z = X + Y；
(60) X = Y；
(70) Y = Z；
(80) Next I；
选项：
A: 5
B: 4
C: 6
D: 7
答案: 【 5】
8、单选题：
关于计算机语言的编译，下列说法不正确的是_____。
选项：
A: 其它三个选项有不正确的
B: 需要“分词”，将其中的常量、变量名和保留字识别出来，并分类及编号
C: 需要识别每一条语句所对应的“模式”。任意语句的常量和变量名被归为“标识符”类别，而标识符与保留字的不同组合关系构成了语句的模式；计算机语言是由有限的语句模式构成的
D: 对每一种模式，都有相应的组合构造方法，即模式可被认为是由原子模式或说基本模式通过组合的方法构造出来的，对原子模式或者基本模式可以事先写好其相应的目标语言的指令或语句
E: 按照模式由原子模式的组合次序，可将模式语句转换成目标语言的指令或语句；进一步按照分类及编号将常量、变量名代入形成最终的目标语言程序，完成编译
答案: 【 其它三个选项有不正确的】
9、单选题：
已知如下多元素变量，已知I=2；J=4；则M[I][J]的值为_____。
选项：
A: 44
B: 83
C: 22
D: 21
E: 其它选项的说法都不正确
答案: 【 44】
10、单选题：
已知如下多元素变量，已知I=2；J=2；则M[I+1][J+1]的值为_____。
选项：
A: 0
B: 39
C: 11
D: 16
E: 其它选项的说法都不正确
答案: 【 0】
11、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式 (A > B +20 ) or (B +60 < C )的值，结果为_____。
选项：
A: 真
B: 100
C: 30
D: 假
答案: 【 真】
12、单选题：
已知如下多元素变量，已知I=1；J=1；则M[I+1][J]+2的值为_____。
选项：
A: 47
B: 13
C: 8
D: 10
E: 其它选项的说法都不正确
答案: 【 47】
13、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式A + A * 5的值，结果为_____。
选项：
A: 240
B: 400
C: 真
D: 假
答案: 【 240】
14、单选题：
已知如下多元素变量。
执行下列程序，执行完成后，Sum1和Sum2的值分别为_____。
(10) int J；
(20) int Sum1=0，Sum2=0；
(30) For J=1 to 4 Step 1
(40) { Sum1 = Sum1 + M[J][J]；
(50) Sum2 = Sum2 + M[5-J][5-J]； }
选项：
A: 66,66
B: 95,95
C: 95,66
D: 66,95
E: 其它选项的说法都不正确
答案: 【 66,66】
15、单选题：
已知函数Fact的程序如下，在执行Fact(4)的过程中，Fact函数被调用的次数为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return (n+x)*2; }
else return 1;
}
选项：
A: 4
B: 3
C: 5
D: 6
答案: 【 4】
16、单选题：
已知程序如下，该程序实现的功能为_____。main()
{
int i,n;
long sum = 0, p = 1;
...//输入n值的语句，略
for(i = 1; i <= n; i++)
{
p = p * i;
sum = sum + p;
}
...//输出sum值的语句，略
}
选项：
A: sum = 1!+2!+...+n!
B: sum = 1*2*3*...*n
C: sum = 1+2+3+...+n
D: sum = 1*2+2*3+(n-1)*n
答案: 【 sum = 1!+2!+...+n!】
17、单选题：
已知X=21， Y=15， Z=22，计算表达式 ((X>Y) or (Y>Z)) and ((X<Y) or (Y<Z))的值，结果为_____。
选项：
A: 真
B: 10
C: 4
D: 假
答案: 【 真】
18、单选题：
已知X=21， Y=15， Z=22，计算表达式 ((X>Y) AND (Y>Z)) OR ((X<Y) AND (Y<Z))的值，结果为_____。
选项：
A: 假
B: 10
C: 4
D: 真
答案: 【 假】
19、单选题：
已知程序如下，若X=30, Y=30, Z=30该程序执行完成后，X的值为_____。X = Z + Y；
If Y < Z {
X = X – Y； }
Else{
X= X – Z； }
X = X – Y；
If X < Z { X = Y +20； }
X = X – Z；
If X > Y { X = X – Y； }
选项：
A: 20
B: 10
C: 30
D: 40
答案: 【 20】
20、单选题：
读程序，并回答问题：该程序执行完成后，X的值为_____。 X=1；
Y=2；
Sum=0；
Do { Sum = X+Y；
X=X+1；
Y=Y+1；
} While (Sum<=20)；
选项：
A: 11
B: 10
C: 9
D: 8
答案: 【 11】
21、单选题：
读程序，并回答问题：该程序执行完成后，Z的值为_____。 (10) N = 6；
(20) X = 0；
(30) Y = 1；
(40) For I = 1 To N-1 Step 1
(50) Z = X + Y；
(60) X = Y；
(70) Y = Z；
(80) Next I；
选项：
A: 8
B: 3
C: 5
D: 13
答案: 【 8】
22、单选题：
已知函数Fact的程序如下，在执行Fact(5)的过程中，Fact函数被调用的次数为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return n*x; }
else return 1;
}
选项：
A: 5
B: 3
C: 4
D: 6
答案: 【 5】
23、单选题：
关于不同抽象层面的计算机，下列说法不正确的是_____。
选项：
A: 不同抽象层次的计算机指的是各种抽象层次的硬件系统，只有硬件计算机才能被称为计算机
B: 实际机器层面之上，不同层次的计算机即是指各种层次的软件系统
C: 实际机器层面之上，不同层次的计算机，其本质是为用户提供一个计算机语言，用户可用该语言表达具体的操作需求，同时提供一个编译器将操作需求转换为机器可以执行的程序，最终实现用户的操作需求
D: 其它三个选项有不正确的
答案: 【 不同抽象层次的计算机指的是各种抽象层次的硬件系统，只有硬件计算机才能被称为计算机】
24、单选题：
已知函数Fact的程序如下，Fact(4)的值为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return (n+x)*2; }
else return 1;
}
选项：
A: 44
B: 14
C: 24
D: 64
答案: 【 44】
25、单选题：
关于计算机语言，下列说法不正确的是_____。
选项：
A: 所有源程序最后都需被转换为汇编语言程序，机器才能够执行
B: 所谓“高级语言”和“低级语言”是指其和机器硬件的相关程度，不涉及机器硬件的语言为高级语言，而与机器硬件相关的语言则为低级语言
C: 低级语言程序执行效率高是因为用低级语言编程时可以充分利用硬件的各种特殊性，而高级语言则只能使用硬件的标准结构
D: 高级语言编程效率高是因为其可用大粒度积木块来构造程序，比一行行语句、一条条指令来编程效率高出很多
答案: 【 所有源程序最后都需被转换为汇编语言程序，机器才能够执行】
26、单选题：
关于普通计算机语言(或者说程序)的基本构成要素，下列说法最完整的是_____。
选项：
A: 常量与变量、表达式、语句和函数
B: 常量与变量和表达式
C: 常量与变量、表达式和语句
D: 都不完整
答案: 【 常量与变量、表达式、语句和函数】
27、单选题：
读程序，并回答问题：该程序执行完成后，N的值为_____。N = 101;
If N/2 == 0 Then
N = N/2;
Else
N = N * 3 + 1;
End If
选项：
A: 304
B: 101
C: 55.5
D: 167.5
答案: 【 304】
28、单选题：
关于计算机语言，下列说法不正确的是_____。
选项：
A: 其它三个选项有不正确的
B: 汇编语言和机器语言是以指令为单位来编写程序
C: 高级语言是以语句为单位来编写程序，一条语句相当于若干条指令(或者说一条语句可用若干条指令来实现)
D: 面向对象语言或可视化构造语言是以对象(类)为单位来编写程序，一个对象相当于若干条语句((或者说一个对象可用若干条语句来实现)
E: 我们可以设计一种新语言，让用户以其更熟悉的对象(类)来编写源程序，然后提供一个编译器将该源程序转换成某种已广泛使用的高级语言源程序，就可以让机器执行该程序
答案: 【 其它三个选项有不正确的】
29、单选题：
从语言编译角度看计算机语言，下列说法不正确的是_____。
选项：
A: 其它三个选项有不正确的
B: 计算机语言就是由标识符和保留字构成的，标识符是可由程序员按规则任意命名的符号，而保留字则是编译器识别语句模式的重要符号
C: 计算机语言定义了基本元素的集合，以及基本元素的组合构造规则，所谓基本元素即是指标识符和保留字，所谓组合构造规则即是指语句的书写模式，即不同标识符和保留字的组合规则
D: 标识符可以是常量、变量名，也可以是函数名；保留字可以是赋值符号如“=”、语句结束符号如“；”、基本运算符号如“+”“-”“*”“/”、程序段落符号如“{ }”等，保留字还可以是其他语句模式的标志性符号
答案: 【 其它三个选项有不正确的】
30、单选题：
已知如下多元素变量。
执行下列程序，执行完成后，Sum1和Sum2的值分别为_____。
(10) int I = 3，J；
(20) int Sum1=0，Sum2=0；
(30) For J=1 to 4 Step 1
(40) { Sum1 = Sum1 + M[I][J]；
(50) Sum2 = Sum2 + M[J][I]； }
选项：
A: 149,105
B: 576,576
C: 136,175
D: 105,149
E: 其它选项的说法都不正确
答案: 【 149,105】
31、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式A < A * 5的值，结果为_____。
选项：
A: 真
B: 假
C: 40
D: 200
答案: 【 真】
32、单选题：
已知如下多元素变量。
执行下列程序，程序执行完成后，Sum1和Sum2的值分别为_____。
(10) int J；
(20) int Sum1=0，Sum2=0；
(30) For J=1 to 4 Step 1
(40) { Sum1 = Sum1 + M[J][J]；
(50) Sum2 = Sum2 + M[5-J][J]； }
选项：
A: 66,95
B: 95,95
C: 95,66
D: 66,66
E: 其它选项的说法都不正确
答案: 【 66,95】
33、单选题：
已知A=40；B=30；C=100；D=50，逻辑“与”运算符为and，“或”运算符为or，“非”运算符为not。计算表达式(A> B) and (A<=B)的值，结果为_____。
选项：
A: 假
B: 40
C: 200
D: 真
答案: 【 假】
34、单选题：
读程序，并回答问题：该程序执行完成后，K的值为_____。(10) K = 0；
(20) I = 2；
(30) While (I<=8)
(40) { K = K + I；
(50) I = I + 2；}
选项：
A: 20
B: 35
C: 36
D: 12
答案: 【 20】
35、单选题：
已知X=21， Y=15， Z=22，计算表达式 ((X>Y) AND (Y>Z)) OR ((X<Z) AND (Y<Z))的值，结果为_____。
选项：
A: 真
B: 假
C: 4
D: 10
答案: 【 真】
36、单选题：
读程序，并回答问题：程序行(40)执行了多少次？次数为_____。(10) K = 0；
(20) I = 2；
(30) While (I<=8)
(40) { K = K + I；
(50) I = I + 2；}
选项：
A: 4
B: 2
C: 6
D: 8
答案: 【 4】
37、单选题：
已知程序如下，当程序行(60)执行了3次以后，Product和Counter的值分别为_____。(10) main()
(20) { int counter；
(30) ... //输入N值的语句，略
(40) long product = 1；
(50) for counter = 1 to N step 2
(60) { product = product * counter； }
(70) return product;
(80) }
选项：
A: 15，5
B: 105，5
C: 15，7
D: 105，7
答案: 【 15，5】
38、单选题：
已知程序如下，若X=10, Y=20, Z=30，该程序执行完成后，X的值为_____。X = Z + Y；
If Y < Z {
X = X – Y； }
Else{
X= X – Z； }
X = X – Y；
If X < Z { X = Y +20； }
X = X – Z；
If X > Y { X = X – Y； }
选项：
A: 10
B: 20
C: 30
D: 40
答案: 【 10】
39、单选题：
读程序，并回答问题：该程序执行完成后，Sum的值为_____。 X=1；
Y=2；
Sum=0；
Do { Sum = X+Y；
X=X+1；
Y=Y+1；
} While (Sum<=20)；
选项：
A: 21
B: 20
C: 19
D: 18
答案: 【 21】
40、单选题：
已知函数Fact的程序如下，Fact(4)的值为_____。 Long Int Fact(int n)
{ Long Int x;
If (n > 1)
{ x = Fact(n-1);
return n*x; }
else return 1;
}
选项：
A: 24
B: 10
C: 120
D: 15
答案: 【 24】
41、单选题：
关于不同抽象层面的计算机，由低层向应用层(高层)的基本层次划分是_____。
选项：
A: 微程序机器实际机器操作系统机器汇编语言机器高级语言机器
B: 高级语言机器汇编语言机器操作系统机器实际机器微程序机器
C: 实际机器微程序机器操作系统机器汇编语言机器高级语言机器
D: 其它三个选项都不正确
答案: 【 微程序机器实际机器操作系统机器汇编语言机器高级语言机器】
42、单选题：
已知程序如下，该程序实现的功能为_____。(10) main()
(20) { int counter；
(30) ... //输入N值的语句，假设N为偶数，略
(40) long product = 1；
(50) for counter = 1 to N step 2
(60) { product = product * counter； }
(70) return product;
(80) }
选项：
A: product = 1*3*5*...* (N-1)
B: product = 1*2*3*...*(N-1)
C: product = 1+ 2+3+...+ (N-1)
D: product = 1+3+5+...+(N-1)
答案: 【 product = 1*3*5*...* (N-1)】
第7讲 算法-程序与计算系统之灵魂
第7讲之模拟练习题
1、单选题：
关于算法的命题，下列说法不正确的是_____。
选项：
A: 算法规定了任务执行/问题求解的一系列、有限的步骤
B: 算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的
C: 算法可以没有输入，但必须有输出
D: 算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成
答案: 【 算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的】
2、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：哥尼斯堡七桥问题的路径能够找到吗？
选项：
A: 一定能够找到
B: 一定不能找到
C: 不确定能不能找到
D: 其它三个选项都不正确
答案: 【 一定不能找到】
3、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
哥尼斯堡七桥问题，推而广之就是m个顶点n条边的图的“一笔画”问题，我们可以给出一个算法来求解该问题，即“对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径”。 关于该算法的基本思想，下列说法正确的是_____。
选项：
A: 以任何一个顶点为起点，按照图的“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解
B: 以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解
C: 首先判断该问题是否有解，若无解，则直接退出；若有解，则以任何一个顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解
D: 首先判断该问题是否有解，若无解，则直接退出；若有解，则选择一个奇数度的顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解
答案: 【 首先判断该问题是否有解，若无解，则直接退出；若有解，则选择一个奇数度的顶点为起点，按照图的未访问过“边”的指示，找到按该边与该顶点相连的下一个顶点，并标记该边为“已访问”，依次循环，直到所有的边都被访问过为止，便可找到给定问题的解】
4、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
假定求解该问题的一种贪心策略是：最大程度地利用背包的容量（15kg），依据该算法策略所得到的解的总价值是_____。
选项：
A: 8
B: 15
C: 14
D: 13
答案: 【 8】
5、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径，则需满足以下条件_____。
选项：
A: m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点
B: 每个顶点的度应为偶数
C: 既需要满足(A)又需要满足(B)
D: 上述条件还不够，还需满足更多条件
答案: 【 既需要满足(A)又需要满足(B)】
6、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
参见下图(f)，下列说法正确的是_____。
选项：
A: 对{A、B、C、D、E、F、G}中的任意两个顶点X和Y，都可以找到一条路径，从X出发 走遍每一座桥，且每座桥仅走过一次，最后终止于Y
B: 对两个顶点A和B，可以找到一条路径，从A出发 走遍每一座桥，且每座桥仅走过一次，最后终止于B
C: 对两个顶点D和G，可以找到一条路径，从D出发 走遍每一座桥，且每座桥仅走过一次，最后终止于G
D: 对{A、B、C、D、E、F、G}中的任意两个顶点X和Y，都找不到一条路径，从X出发 走遍每一座桥，且每座桥仅走过一次，最后终止于Y
答案: 【 对两个顶点D和G，可以找到一条路径，从D出发 走遍每一座桥，且每座桥仅走过一次，最后终止于G】
7、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
假定有N个物品，其价值分别为
，重量分别为
，背包所能承受的总重量为
，为物品i定义一个决策变量
，其中
表示选择该物品，
表示不选择该物品。下面哪些描述共同构成了该问题的数学模型_____。
选项：
A: 问题的目标函数是
B: 问题的目标函数是
C: 问题解所应满足的约束是
D: 前述(A)和(C)
答案: 【 前述(A)和(C)】
8、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
下面所示的图(c)，能否找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？
选项：
A: 一定能够找到
B: 一定不能找到
C: 不确定能不能找到
D: 其它三个选项都不正确
答案: 【 一定不能找到】
9、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
参见图(c)，增加哪些边，使得能够找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？
选项：
A: BG边
B: AG边
C: CG边
D: AD边
答案: 【 CG边】
10、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径，则需满足以下条件_____。
选项：
A: m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点
B: 每个顶点的度应为偶数
C: 既需要满足(A)又需要满足(B)
D: 不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径
答案: 【 不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径】
11、单选题：
关于算法的特性，下列说法不正确的是_____。
选项：
A: 算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性
B: 算法的步骤必须要确切地定义，不能有歧义性，此即算法的确定性
C: 算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性
D: 算法中有待执行的运算和操作必须是相当基本的，可以由机器自动完成，进一步，算法应能在有限时间内完成，此即算法的能行性
答案: 【 算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性】
12、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
下面所示的图(d)和图(e)，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？
选项：
A: 图(d)和图(e)都一定不能找到
B: 图(d)一定能够找到；图(e)一定不能找到
C: 图(d)一定不能找到；图(e)一定能够找到
D: 图(d)和图(e)都一定能够找到
答案: 【 图(d)一定不能找到；图(e)一定能够找到】
13、单选题：
关于算法与程序、计算机语言之间的关系，下列说法不正确的是_____。
选项：
A: 算法是解决问题的步骤，某个问题可能有多个求解算法
B: 算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行
C: 算法只能由高级（计算机）语言实现，不能通过机器语言实现
D: 求解问题的多个算法不一定获得相同的解
答案: 【 算法只能由高级（计算机）语言实现，不能通过机器语言实现】
14、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
该背包问题的可能解的数量是_____。
选项：
A: 5
B: 10
C: 32
D: 64
答案: 【 32】
15、单选题：
算法是计算系统的灵魂，为什么？不正确的是_____。
选项：
A: 计算系统是执行程序的系统，而程序是用计算机语言表达的算法
B: 一个问题的求解可以通过构造算法来解决，“是否会编程序”本质上讲是“能否想出求解该问题的算法”
C: 一个算法不仅可以解决一个具体问题，它可以在变换输入输出的情况下，求解一个问题系列
D: 问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛
答案: 【 问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛】
16、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：对河流隔开的m块陆地上建造的n座桥梁，能否找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径呢？
选项：
A: 一定能够找到
B: 一定不能找到
C: 不确定能不能找到
D: 其它三个选项都不正确
答案: 【 不确定能不能找到】
17、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
对河流隔开的m块陆地上建造的n座桥梁，若要找到走遍这n座桥且只许走过每座桥一次的路径，则需满足以下条件_____。
选项：
A: m个顶点n条边的图应是连通的，即由一个顶点出发可沿边到达任何一个其他顶点
B: 每个顶点的度应为偶数，或者，只有两个顶点的度为奇数而其他顶点的度均为偶数
C: 既需要满足(A)又需要满足(B)
D: 不满足上述条件(A)(B)(C)的图也能找出满足题目规定要求的路径
答案: 【 既需要满足(A)又需要满足(B)】
18、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
哥尼斯堡七桥问题，给我们的启示是_____。
选项：
A: 一个具体问题应该进行数学抽象，基于数学抽象进行问题求解
B: 一个具体问题的求解，进行数学建模后，通过模型中的性质分析可以判断该问题是否有解，如果有解，则可以进行计算；而如果无解，则无需进行计算
C: 一个具体问题的求解方法，进行数学建模后，可反映出一类问题的求解方法，例如哥尼斯堡七桥问题的求解方法，建立“图”后，可反映任意n座桥的求解方法
D: 上述全部
答案: 【 上述全部】
19、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
假定求解该问题的一种贪心策略是：优先选择能装下盒子中价格最高的，依据该算法策略所得到的解的总价值是_____。
选项：
A: 16
B: 15
C: 14
D: 13
答案: 【 15】
20、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
假定求解该问题的一种贪心策略是：优先选择能装下盒子中单位重量价值最高的，依据该算法策略所得到的解的总价值是_____。
选项：
A: 16
B: 15
C: 14
D: 13
答案: 【 15】
21、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
使用遍历算法策略所得到的解的总价值是_____。
选项：
A: 8
B: 15
C: 14
D: 13
答案: 【 15】
22、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:关于TSP问题的遍历算法和贪心算法，下列说法正确的是_____。
选项：
A: 对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更快一些，而遍历算法更慢一些
B: 对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是遍历算法更快一些，而贪心算法更慢一些
C: 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些
D: 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些
答案: 【 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些】
23、单选题：
数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
请对照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[4][2]元素所对应的存储单元的存储地址为_____。
选项：
A: 00000000 00000101
B: 00000000 00001000
C: 00000000 00001010
D: 上述都不正确
答案: 【 00000000 00001000】
24、单选题：
数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
请参照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[i][j]元素，与对应存储单元的存储地址的转换关系正确的为_____。
选项：
A: D[i][j]元素的存储地址=数组的起始地址+((i-1)*每行的列数+j-1)*单一元素占用存储单元的数目
B: D[i][j]元素的存储地址=数组的起始地址+(i-1)*每行的列数+j-1；此公式在任何情况下都正确
C: D[i][j]元素的存储地址=数组的起始地址+((j-1)*每行的列数+i-1)*单一元素占用存储单元的数目
D: D[i][j]元素的存储地址=数组的起始地址+(j-1)*每行的列数+i-1；此公式在任何情况下都正确
答案: 【 D[i][j]元素的存储地址=数组的起始地址+((i-1)*每行的列数+j-1)*单一元素占用存储单元的数目】
25、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
参照上图(I)，下列说法不正确的是_____。
选项：
A: 当数据元素不发生变化，而只是数据元素之间的关系发生变化时，可以通过调整数据元素对应的左指针数组或右指针数组中的值来完成
B: 当数据元素不发生变化，而只是数据元素之间的关系发生变化时，既需要调整数据元素本身，又需要调整其对应的左指针数组或右指针数组中的值来完成
C: 相同的数据元素，不同的左指针和右指针可以反映数据元素之间不同的关系
D: 图(I)说明，一个数据元素最多只能有两个子元素，一个是左子元素，一个是右子元素
答案: 【 当数据元素不发生变化，而只是数据元素之间的关系发生变化时，既需要调整数据元素本身，又需要调整其对应的左指针数组或右指针数组中的值来完成】
26、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
上图(I)表示的数据的逻辑关系，下列正确的是_____。
选项：
A: 图II.(a)
B: 图II.(b)
C: 图II.(c)
D: 图II.(d)
答案: 【 图II.(d)】
27、单选题：
TSP算法流程图如下图I.示意，回答问题：最内层循环(L变量控制的循环)的作用是_________。
选项：
A: 用于判断某个城市是否是已访问过的城市
B: 用于寻找距当前城市距离最近的城市
C: 用于完整地产生一个路径
D: 上述都不是
答案: 【 用于判断某个城市是否是已访问过的城市】
28、单选题：
TSP算法流程图如下图I.示意，回答问题：外层循环(I变量控制的循环)的作用是_________。
选项：
A: 用于判断某个城市是否是已访问过的城市
B: 用于寻找距当前城市距离最近的城市
C: 用于完整地产生一个路径
D: 上述都不是
答案: 【 用于完整地产生一个路径】
29、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：算法的时间复杂性，可以表达为关于问题规模n的一个函数T(n)，T(n)可以用大O表示法来处理。问T(n)=O(f(n))是什么意思？正确的是_________。
选项：
A: T(n)是关于f(n)的一个函数
B: T(n)是与f(n)同数量级的函数
C: T(n)是将函数f(n)代入O(x)中所形成的新函数
D: T(n)是依据f(n)计算出来的
答案: 【 T(n)是与f(n)同数量级的函数】
30、单选题：
对于算法类问题求解，下列说法正确的是_________。
选项：
A: 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计三个基本步骤
B: 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的正确性与复杂性分析四个基本步骤
C: 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤
D: 上述说法都正确
答案: 【 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤】
31、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:下列哪些问题可应用求解TSP的算法，正确的是_____。
选项：
A: 电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)
B: n个盘子在三个柱子上的移动问题(梵天塔问题或者说汉诺塔问题)
C: n座桥， 走过每座桥且仅走过一次的问题(图的遍历问题)
D: 上述(A)(B)(C)都可以
答案: 【 电路板上需要钻n个孔，选择一条最短路径使机器移动并完成所有孔的钻孔工作的问题(机器在电路板上钻孔的调度问题)】
32、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
关于“树”这种数据结构，下列说法不正确的是_____。
选项：
A: “树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系
B: “树”可以采用两个数组来组织树型数据，其中一个数组用于存储数据元素本身，另一个数组用于存储与该数据元素发生某种关系的另一个数据元素的存储位置
C: “树”可以采用三个数组来组织树型数据，其中一个数组用于存储数据元素本身，另外两个数组用于存储与该数据元素发生某种关系的另外两个数据元素的存储位置
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
33、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
如想使图(I)，改变为存储下图III所示的逻辑关系，操作正确的是_____。
选项：
A: 将00000000 00001000号存储单元的值修改00000000 01101110(即十进制的110)
B: 将00000000 00011010号存储单元的值修改为00000000 0000011
C: 将00000000 00010001号存储单元的值修改为00000000 00000000(即Null)，将00000000 00010011号存储单元的值修改为00000000 00001000
D: 上述(A)(B)(C)都需要正确完成
答案: 【 上述(A)(B)(C)都需要正确完成】
34、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
如想使图(I)，改变为存储下图IV所示的逻辑关系，下列四步操作都是需要的，但有些操作的内容却是不正确的。不正确的是_____。
选项：
A: 将00000000 00001000号存储单元的值修改为00000000 01010101
B: 将00000000 00010010号存储单元的值修改为00000000 00000010
C: 将00000000 00011010号存储单元的值修改为00000000 00000000(即Null)
D: 将00000000 00001010号存储单元的值修改为00000000 00001000
答案: 【 将00000000 00010010号存储单元的值修改为00000000 00000010】
35、单选题：
观察下图II.，该流程图中存在错误，下列说法最完整准确的是_________。
选项：
A: 条件判断框不应为矩形，而应为菱形或六角形
B: 条件判断框中引出的箭头应标记Yes(是)或No(否)，表明条件满足或不满足时的程序走向
C: 仅仅包含错误(A)和(B)
D: 除错误(A)和(B)外，还包括其他错误
答案: 【 除错误(A)和(B)外，还包括其他错误】
36、单选题：
TSP算法流程图如下图I.示意，回答问题：中层循环(K变量控制的循环)的作用是_________。
选项：
A: 用于判断某个城市是否是已访问过的城市
B: 用于寻找距当前城市距离最近的城市
C: 用于完整地产生一个路径
D: 上述都不是
答案: 【 用于寻找距当前城市距离最近的城市】
37、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：算法的时间复杂性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；该程序时间复杂性表达正确的是_________。
选项：
A: O(n)
B: 
C: 
D: 上述都不对
答案: 【 】
38、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：算法的时间复杂性T(n)，可以通过评估算法基本语句的执行次数来获得。分析下列算法的时间复杂性。Start of the algorithm(算法开始)
(1) 输入结点的数目n；
(2) 当前最短路径Path设为空，当前最短距离Dtemp设为最大值；
注：一个路径是n个结点的一个组合，任何一个结点在路经中不能重复出现
(3) 组合一条新路径NewPath并计算该路径的距离D；
(4) 如果D<Dtemp 则Path = NewPath，且Dtemp = D；
(5) 如果所有路径组合完毕，则结束；否则转第(3)步继续执行；
(6) 输出Path及Dtemp；
End of the algorithm(算法结束)该算法的时间复杂性表达正确的是_________。
选项：
A: 
B:
C:
D: 
答案: 【 】
39、单选题：
关于数据结构，下列说法不正确的是______________？
选项：
A: 数据结构由逻辑结构、存储结构及运算3部分组成
B: 存储结构定义了数据在存储器中的存储方式
C: 向量使用顺序存储结构，并借助元素在存储器中的相对位置来表示数据元素的逻辑关系
D: 在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针
答案: 【 在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针】
40、单选题：
数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
关于数组和存储器，下列说法不正确的是_____。
选项：
A: 和存储器一样，数组是按线性方式组织数据
B: 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个存储单元来存储，一个下标即相当于一个存储单元的地址
C: 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个存储单元的地址
D: 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个或多个存储单元的地址
答案: 【 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个存储单元的地址】
41、单选题：
堆栈(stack)是一种特殊的串行形式的数据结构，其特殊之处在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
有关堆栈数据结构的说法，不正确的是_____。
选项：
A: 堆栈按照先进先出（FIFO, First In First Out）的原理运作
B: 堆栈按照后进先出（LIFO, Last In First Out）的原理运作
C: 堆栈可以使用顺序存储结构作为存储结构
D: 堆栈可以使用链式存储结构作为存储结构
答案: 【 堆栈按照先进先出（FIFO, First In First Out）的原理运作】
42、单选题：
阅读下列算法，回答：算法执行的结果为_________。Start of the algorithm(算法开始)
(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的结果。
End of the algorithm(算法结束)
选项：
A: 24
B: 26
C: 55
D: 45
答案: 【 26】
43、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：通常从哪些方面，进行算法的模拟与分析？
选项：
A: 算法的正确性问题，即一个算法求得的解是满足问题约束的正确的解吗？
B: 算法的效果评价问题，即算法输出的是最优解还是可行解，其可行解与最优解的偏差有多大？
C: 算法的时间效率问题(时间复杂性)，即算法执行所需要的时间是多少？算法的空间效率问题(空间复杂性)，即算法执性所需要的空间是多少？
D: 上述全部。
答案: 【 上述全部。】
44、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：算法的时间复杂性T(n)，可以通过计算算法基本语句的执行次数来获得。分析下列程序的时间复杂性。(10) K = 0；
(20) I = 2；
(30) While (I<=8)
(40) { K = K + I；
(50) I = I + 2；}该程序时间复杂性表达正确的是_________。
选项：
A: O(n)
B: O(1)
C:
D: O(n!)
答案: 【 O(1)】
45、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：阅读下面的程序，其时间复杂度为_________?int index = 5;
int condition=1;
if (condition==1) then
index++;
else
index--；
for i = 1 to 100
for j = 1 to 200
index=index+2;
选项：
A: O(1)
B: O(n)
C:
D: O(n*log n)
答案: 【 O(1)】
46、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：分析下列算法的时间复杂性。Start of the Algorithm
(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。
End of the Algorithm该算法的时间复杂性表达正确的是_________。
选项：
A:
B:
C:
D:
答案: 【 】
47、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:关于TSP，下列说法不正确的是_____。
选项：
A: TSP问题的一个可能解就是n个城市的一个组合
，其中任何两个
，
都对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较
B: TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，以致于计算机不能在有限时间内完成所有的组合
C: TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合
D: 上述思想--对所有组合进行比较的思想，即是所谓的遍历算法策略，它仅仅对n值很小的TSP问题是能行的
答案: 【 TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合】
48、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:关于TSP的贪心算法的求解思想，下列说法不正确的是_____。
选项：
A: 无需对所有组合(所有可能解)进行比较，而仅需依照某种办法确定其中的一个组合即可，该组合不一定是最优解，但却是一个较优解或次优解
B: 在确定一个组合时，
是与
相连接的城市中与距离最短的城市，即是由确定的，与连接的若干城市中的特性最优的城市
C: 贪心算法确定的路径，是由局部最优(即在看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的
D: 对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的
答案: 【 贪心算法确定的路径，是由局部最优(即在看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的】
49、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:
关于下列四个数学抽象，说法正确的是_____。
选项：
A: 只有数学抽象I是TSP问题，数学抽象II和III不是
B: 数学抽象I和III可以被认为是TSP问题，数学抽象II和IV不是
C: 数学抽象I、II、III和IV都可以被认为是TSP问题
D: 上述说法都不正确
答案: 【 数学抽象I、II、III和IV都可以被认为是TSP问题】
50、单选题：
关于数据结构，下列说法不正确的是_____。
选项：
A: 数据结构是问题域数学模型中各种数据的存储结构
B: 数据结构是将逻辑上有一定语义关系的数据，转换成计算机可以存储和处理的变量，便于算法和程序进行处理
C: 数据结构是将具有一定语义关系的变量进行命名，以便隐藏数据结构内部的操作细节，便于算法按逻辑语义通过操控该名字来操控该数据结构
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
51、单选题：
堆栈(stack)是一种特殊的串行形式的数据结构，其特殊之处在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
有关堆栈数据结构的基本运算，说法不正确的是_____。
选项：
A: 推入是将数据放入堆栈的顶端，堆栈顶端指针top加一；弹出是将堆栈顶端的数据取出，堆栈顶端指针top减一
B: 如果是固定长度的堆栈，当堆栈顶端指针top与长度相等时，堆栈是满的
C: 如果堆栈顶端指针top为0，则堆栈为空
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
52、单选题：
堆栈(stack)是一种特殊的串行形式的数据结构，其特殊之处在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
假定当前堆栈顶端指针top=10，欲将栈底的元素取出，其他的元素仍然保持在栈中，则需要进行____次弹出操作，____ 次推入操作
选项：
A: 1，1
B: 2，1
C: 10，9
D: 10，0
答案: 【 10，9】
53、单选题：
观察下图I.，没有错误的流程图为_________。
选项：
A: 流程图(a)无错误
B: 流程图(b)无错误
C: 流程图(c)无错误
D: 没有无错误的流程图
答案: 【 没有无错误的流程图】
54、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：算法的时间复杂性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；该程序时间复杂性表达正确的是_________。
选项：
A: O(n)
B:
C:
D: 上述都不对
答案: 【 】
55、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：为什么要评估算法的复杂性？下列说法不正确的是_________。
选项：
A: 当算法的时间复杂性量级为多项式函数时，计算机是能够完成计算的
B: 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的
C: 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，对于大规模问题，计算机是不能够完成计算的
D: 上述说法有不正确的
答案: 【 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的】
56、单选题：
关于算法类问题的基本求解步骤，下列说法不正确的是_________。
选项：
A: 算法类问题求解首先要进行数学建模，即用数学语言对问题进行抽象
B: 一个问题，进行了数学建模后，可以通过模型的一些性质的分析判断该问题是否有解；在有解的情况下，再设计算法进行求解，否则则可能做的是无用功！
C: 一个问题，进行了数学建模后，可以依据数学的一些求解方法，设计出让计算机求解的算法。
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
第7讲测验
1、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。通常从哪些方面，进行算法的模拟与分析？
选项：
A: 其它三个选项全部
B: 算法的正确性问题，即一个算法求得的解是满足问题约束的正确的解吗？
C: 算法的效果评价问题，即算法输出的是最优解还是可行解，其可行解与最优解的偏差有多大？
D: 算法的时间效率问题(时间复杂性)，即算法执行所需要的时间是多少？算法的空间效率问题(空间复杂性)，即算法执性所需要的空间是多少？
答案: 【 其它三个选项全部】
2、单选题：
阅读下面的程序，其时间复杂度为_________?int index = 5;
int condition=1;
if (condition==1) then
index++;
else
index--；
for i = 1 to 100
for j = 1 to 200
index=index+2;
选项：
A: O(1)
B: O(n)
C:
D: O(n*log n)
答案: 【 O(1)】
3、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：算法的时间复杂性T(n)，可以通过评估算法基本语句的执行次数来获得。分析下列算法的时间复杂性。Start of the algorithm(算法开始)
(1) 输入结点的数目n；
(2) 当前最短路径Path设为空，当前最短距离Dtemp设为最大值；
注：一个路径是n个结点的一个组合，任何一个结点在路经中不能重复出现
(3) 组合一条新路径NewPath并计算该路径的距离D；
(4) 如果D<Dtemp 则Path = NewPath，且Dtemp = D；
(5) 如果所有路径组合完毕，则结束；否则转第(3)步继续执行；
(6) 输出Path及Dtemp；
End of the algorithm(算法结束)该算法的时间复杂性表达正确的是_________。
选项：
A: O(n!)
B:
C:
D:
答案: 【 O(n!)】
4、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：分析下列算法的时间复杂性。Start of the Algorithm
(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。
End of the Algorithm该算法的时间复杂性表达正确的是_________。
选项：
A:
B:
C:
D:
答案: 【 】
5、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
参见图(c)，增加哪些边，使得能够找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？
选项：
A: CG边
B: BG边
C: AG边
D: AD边
E: DE边
答案: 【 CG边】
6、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
下面所示的图(c)，能否找到走遍每一座桥，且每座桥仅走过一次、最后又回到原出发点的路径呢？
选项：
A: 一定不能找到
B: 一定能够找到
C: 不确定能不能找到
D: 其它三个选项都不正确
答案: 【 一定不能找到】
7、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:
关于下列四个数学抽象，说法正确的是_____。
选项：
A: 数学抽象I、II、III和IV都可以被认为是TSP问题
B: 只有数学抽象I是TSP问题，数学抽象II和III不是
C: 数学抽象I和III可以被认为是TSP问题，数学抽象II和IV不是
D: 其它选项的说法都不正确
答案: 【 数学抽象I、II、III和IV都可以被认为是TSP问题】
8、单选题：
数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
关于数组和存储器，下列说法不正确的是_____。
选项：
A: 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个存储单元的地址
B: 和存储器一样，数组是按线性方式组织数据
C: 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个存储单元来存储，一个下标即相当于一个存储单元的地址
D: 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个或多个存储单元的地址
答案: 【 和存储器一样，一维数组是按线性方式组织数据，一个数据元素需要一个或多个存储单元来存储，一个下标即相当于一个存储单元的地址】
9、单选题：
堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
假定当前堆栈顶端指针top=10，欲将栈底的元素取出，其他的元素仍然保持在栈中，则需要进行____次弹出操作，____ 次推入操作
选项：
A: 10，9
B: 1，1
C: 2，1
D: 10，0
E: 11，8
答案: 【 10，9】
10、单选题：
阅读下列算法，回答：算法执行的结果为_________。Start of the algorithm(算法开始)
(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的结果。
End of the algorithm(算法结束)
选项：
A: 26
B: 24
C: 55
D: 45
E: 46
答案: 【 26】
11、单选题：
算法的时间复杂性，可以表达为关于问题规模n的一个函数T(n)，T(n)可以用大O表示法来处理。问T(n)=O(f(n))是什么意思？正确的是_________。
选项：
A: T(n)是与f(n)同数量级的函数
B: T(n)是关于f(n)的一个函数
C: T(n)是将函数f(n)代入O(x)中所形成的新函数
D: T(n)是依据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；}该程序时间复杂性表达正确的是_________。
选项：
A: O(1)
B: O(n)
C:
D: O(n!)
答案: 【 O(1)】
13、单选题：
对于算法类问题求解，下列说法正确的是_________。
选项：
A: 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤
B: 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计三个基本步骤
C: 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的正确性与复杂性分析四个基本步骤
D: 其它三个选项的说法都正确
答案: 【 一般而言，算法类问题求解包括数学建模、算法策略设计、算法的数据结构与控制结构设计、算法的程序实现、算法的正确性与复杂性分析五个基本步骤】
14、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
下面所示的图(d)和图(e)，问能否找到走遍每一座桥，且每座桥仅走过一次的路径呢？
选项：
A: 图(d)一定不能找到；图(e)一定能够找到
B: 图(d)和图(e)都一定不能找到
C: 图(d)一定能够找到；图(e)一定不能找到
D: 图(d)和图(e)都一定能够找到
答案: 【 图(d)一定不能找到；图(e)一定能够找到】
15、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:关于TSP问题的遍历算法和贪心算法，下列说法正确的是_____。
选项：
A: 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些
B: 对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是贪心算法更快一些，而遍历算法更慢一些
C: 对TSP问题而言，遍历算法和贪心算法求得的解是一样的，所不同的是遍历算法更快一些，而贪心算法更慢一些
D: 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求精确解，执行更快一些，而遍历算法是求近似解，执行更慢一些
答案: 【 对TSP问题而言，遍历算法和贪心算法求得的解是不一样的，贪心算法是求近似解，执行更快一些，而遍历算法是求精确解，执行更慢一些】
16、单选题：
算法是计算系统的灵魂，为什么？不正确的是_____。
选项：
A: 问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛
B: 计算系统是执行程序的系统，而程序是用计算机语言表达的算法
C: 一个问题的求解可以通过构造算法来解决，“是否会编程序”本质上讲是“能否想出求解该问题的算法”
D: 一个算法不仅可以解决一个具体问题，它可以在变换输入输出的情况下，求解一个问题系列
答案: 【 问题求解都可以归结到算法的构造与设计，系统和算法的关系是：算法是龙，而系统是睛，画龙要点睛】
17、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：对河流隔开的m块陆地上建造的n座桥梁，能否找到走遍这n座桥且只许走过每座桥一次最后又回到原出发点的路径呢？
选项：
A: 不确定能不能找到
B: 一定能够找到
C: 一定不能找到
D: 其它三个选项都不正确
答案: 【 不确定能不能找到】
18、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
假定求解该问题的一种贪心策略是：优先选择能装下盒子中价格最高的，依据该算法策略所得到的解的总价值是_____。
选项：
A: 15
B: 16
C: 14
D: 13
答案: 【 15】
19、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
假定求解该问题的一种贪心策略是：最大程度地利用背包的容量（15kg），依据该算法策略所得到的解的总价值是_____。
选项：
A: 8
B: 15
C: 14
D: 13
答案: 【 8】
20、单选题：
关于数据结构，下列说法不正确的是_______？
选项：
A: 在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针
B: 数据结构由逻辑结构、存储结构及运算3部分组成
C: 存储结构定义了数据在存储器中的存储方式
D: 向量使用顺序存储结构，并借助元素在存储器中的相对位置来表示数据元素的逻辑关系
答案: 【 在树结构中，指针用于表达元素之间的逻辑关系——父子关系，每个元素的指针指向其父节点，因此一个元素可以有一个或多个指针】
21、单选题：
关于算法的特性，下列说法不正确的是_____。
选项：
A: 算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性
B: 算法必须有明确的结束条件，即算法应该能够结束，此即算法的有穷性
C: 算法的步骤必须要确切地定义，不能有歧义性，此即算法的确定性
D: 算法中有待执行的运算和操作必须是相当基本的，可以由机器自动完成，进一步，算法应能在有限时间内完成，此即算法的能行性
答案: 【 算法可以有零个或多个输入，也可以有零个或多个输出，此即算法的输入输出性】
22、单选题：
关于算法的命题，下列说法不正确的是_____。
选项：
A: 算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的
B: 算法规定了任务执行/问题求解的一系列、有限的步骤
C: 算法可以没有输入，但必须有输出
D: 算法的每一个步骤必须确切地定义，且其运算和操作必须相当基本，可以由机器自动完成
答案: 【 算法所规定的计算/处理步骤是有限的，但算法实际执行的计算/处理步骤可以是无限的】
23、单选题：
关于算法与程序、计算机语言之间的关系，下列说法不正确的是_____。
选项：
A: 算法只能由高级（计算机）语言实现，不能通过机器语言实现
B: 算法是解决问题的步骤，某个问题可能有多个求解算法
C: 算法不能直接由计算机执行，必须将其转换为程序才能够由计算机执行
D: 求解问题的多个算法不一定获得相同的解
答案: 【 算法只能由高级（计算机）语言实现，不能通过机器语言实现】
24、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：哥尼斯堡七桥问题的路径能够找到吗？
选项：
A: 一定不能找到
B: 一定能够找到
C: 不确定能不能找到
D: 其它三个选项都不正确
答案: 【 一定不能找到】
25、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
哥尼斯堡七桥问题，给我们的启示是_____。
选项：
A: 其它三个选项都正确
B: 一个具体问题应该进行数学抽象，基于数学抽象进行问题求解
C: 一个具体问题的求解，进行数学建模后，通过模型中的性质分析可以判断该问题是否有解，如果有解，则可以进行计算；而如果无解，则无需进行计算
D: 一个具体问题的求解方法，进行数学建模后，可反映出一类问题的求解方法，例如哥尼斯堡七桥问题的求解方法，建立“图”后，可反映任意n座桥的求解方法
答案: 【 其它三个选项都正确】
26、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
该背包问题的可能解的数量是_____。
选项：
A: 32
B: 5
C: 10
D: 64
答案: 【 32】
27、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
假定求解该问题的一种贪心策略是：优先选择能装下盒子中单位重量价值最高的，依据该算法策略所得到的解的总价值是_____。
选项：
A: 15
B: 16
C: 14
D: 13
答案: 【 15】
28、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:关于TSP，下列说法不正确的是_____。
选项：
A: TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合
B: TSP问题的一个可能解就是n个城市的一个组合
，其中任何两个
都对应不同的城市。若要求得最优解，则必须对所有的组合，即所有可能解进行比较
C: TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，以致于计算机不能在有限时间内完成所有的组合
D: 对所有组合进行比较的思想，即是所谓的遍历算法策略，它仅仅对n值很小的TSP问题是能行的
答案: 【 TSP问题的难点是当n值很大时，组合数目非常庞大(组合数目为n!)，虽如此，计算机仍然能够在有限时间内完成所有的组合】
29、单选题：
TSP-旅行商问题，是一个经典问题，如下图所示，描述为“有n个城市，任何两个城市之间的距离都是确定的，现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次，最后回到原出发城市，问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP，回答问题:关于TSP的贪心算法的求解思想，下列说法不正确的是_____。
选项：
A: 贪心算法确定的路径，是由局部最优(即在看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的
B: 无需对所有组合(所有可能解)进行比较，而仅需依照某种办法确定其中的一个组合即可，该组合不一定是最优解，但却是一个较优解或次优解
C: 在确定一个组合时，是与相连接的城市中与距离最短的城市，即是由确定的，与连接的若干城市中的特性最优的城市
D: 对一个具体的TSP问题，每次执行贪心算法，所求得的最终解可能是不同的
答案: 【 贪心算法确定的路径，是由局部最优(即在看来是最优的)组合起来的路径，该路径从全局角度也一定是最优的】
30、单选题：
数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
请对照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[4][2]元素所对应的存储单元的存储地址为_____。
选项：
A: 00000000 00001000
B: 00000000 00000101
C: 00000000 00001010
D: 其它三个选项的说法都不正确
答案: 【 00000000 00001000】
31、单选题：
堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
有关堆栈数据结构的基本运算，说法不正确的是_____。
选项：
A: 其它三个选项的说法有不正确的
B: 推入是将数据放入堆栈的顶端，堆栈顶端指针top加一
C: 弹出是将堆栈顶端的数据取出，堆栈顶端指针top减一
D: 如果堆栈顶端指针top为0，则堆栈为空
E: 如果是固定长度的堆栈，当堆栈顶端指针top与长度相等时，堆栈是满的
答案: 【 其它三个选项的说法有不正确的】
32、单选题：
关于数据结构，下列说法不正确的是_____。
选项：
A: 其它选项的说法有不正确的
B: 数据结构是问题域数学模型中各种数据的存储结构
C: 数据结构是将逻辑上有一定语义关系的数据，转换成计算机可以存储和处理的变量，便于算法和程序进行处理
D: 数据结构是将具有一定语义关系的变量进行命名，以便隐藏数据结构内部的操作细节，便于算法按逻辑语义通过操控该名字来操控该数据结构
E: 数据结构包含了数据的逻辑结构、存储结构及其操作
答案: 【 其它选项的说法有不正确的】
33、单选题：
哥尼斯堡七桥问题，是一个经典问题，如下图(a)所示，描述为“由河流隔开的四块陆地上建造了七座桥，寻找走遍这七座桥且只许走过每座桥一次最后又回到原出发点的路径”。关于哥尼斯堡七桥问题，著名数学家欧拉对该问题做了一个抽象：“顶点”为陆地，“边”为连接两块陆地的桥梁。这个抽象被称为“图”，并定义了顶点的“度”为连接一个顶点的边的数量。关于此问题回答问题：
参见下图(f)，下列说法正确的是_____。
选项：
A: 对两个顶点D和G，可以找到一条路径，从D出发 走遍每一座桥，且每座桥仅走过一次，最后终止于G
B: 对{A、B、C、D、E、F、G}中的任意两个顶点X和Y，都可以找到一条路径，从X出发 走遍每一座桥，且每座桥仅走过一次，最后终止于Y
C: 对两个顶点A和B，可以找到一条路径，从A出发 走遍每一座桥，且每座桥仅走过一次，最后终止于B
D: 对{A、B、C、D、E、F、G}中的任意两个顶点X和Y，都找不到一条路径，从X出发 走遍每一座桥，且每座桥仅走过一次，最后终止于Y
答案: 【 对两个顶点D和G，可以找到一条路径，从D出发 走遍每一座桥，且每座桥仅走过一次，最后终止于G】
34、单选题：
背包问题的定义是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重量小于或等于15 kg？其示意图如下：
使用遍历算法策略所得到的解的总价值是_____。
选项：
A: 15
B: 8
C: 14
D: 13
答案: 【 15】
35、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
关于“树”这种数据结构，下列说法不正确的是_____。
选项：
A: 其它三个选项的说法有不正确的
B: “树”既需要存储数据元素本身即数据，还需要存储数据元素之间的关系
C: “树”可以采用两个数组来组织树型数据，其中一个数组用于存储数据元素本身，另一个数组用于存储与该数据元素发生某种关系的另一个数据元素的存储位置
D: “树”可以采用三个数组来组织树型数据，其中一个数组用于存储数据元素本身，另外两个数组用于存储与该数据元素发生某种关系的另外两个数据元素的存储位置
答案: 【 其它三个选项的说法有不正确的】
36、单选题：
堆栈(stack)是一种特殊的串行形式的数据结构，其特殊支出在于只能允许在链结串行或阵列的一端（称为堆栈顶端指针，top）进行加入数据(push)或输出数据(pop)的运算。其示意图如下所示。
有关堆栈数据结构的说法，不正确的是_____。
选项：
A: 堆栈按照先进先出（FIFO, First In First Out）的原理运作
B: 堆栈按照后进先出（LIFO, Last In First Out）的原理运作
C: 堆栈可以使用顺序存储结构作为存储结构
D: 堆栈可以使用链式存储结构作为存储结构
答案: 【 堆栈按照先进先出（FIFO, First In First Out）的原理运作】
37、单选题：
程序流程图是表达算法控制结构或者说算法步骤的重要方法。观察下图I.，没有错误的流程图为_________。
选项：
A: 没有无错误的流程图
B: 流程图(a)无错误
C: 流程图(b)无错误
D: 流程图(c)无错误
答案: 【 没有无错误的流程图】
38、单选题：
TSP算法流程图如下图I.示意，回答问题：最内层循环(L变量控制的循环)的作用是_________。
选项：
A: 用于判断某个城市是否是已访问过的城市
B: 用于寻找距当前城市距离最近的城市
C: 用于完整地产生一个路径
D: 其它三个选项都不是
答案: 【 用于判断某个城市是否是已访问过的城市】
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；该程序时间复杂性表达正确的是_________。
选项：
A:
B: O(n)
C:
D: 其它三个选项都不对
答案: 【 】
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；该程序时间复杂性表达正确的是_________。
选项：
A:
B: O(n)
C:
D: 其它三个选项都不对
答案: 【 】
41、单选题：
一般而言，算法设计完成后，需要进行算法的模拟与分析。关于算法的模拟与分析回答问题：为什么要评估算法的复杂性？下列说法不正确的是_________。
选项：
A: 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的
B: 当算法的时间复杂性量级为多项式函数时，计算机是能够完成计算的
C: 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，对于大规模问题，计算机是不能够完成计算的
D: 其它三个选项的说法有不正确的
答案: 【 当算法的时间复杂性量级为非多项式函数时，如指数函数、阶乘函数时，计算机是不能够完成计算的】
42、单选题：
数据通常要存储在存储器中，存储器是按地址访问的存储单元的集合，因此存储器可被认为是按线性方式组织数据。数组是高级语言中经常使用的一种数据结构，其按照不同的下标可访问数组的不同的元素。如下图所示：
请参照上图的左子图和右子图来观察，右子图的二维数组是按左图的形式存储在存储器中。则D[i][j]元素，与对应存储单元的存储地址的转换关系正确的为_____。
选项：
A: D[i][j]元素的存储地址=数组的起始地址+((i-1)*每行的列数+j-1)*单一元素占用存储单元的数目
B: D[i][j]元素的存储地址=数组的起始地址+(i-1)*每行的列数+j-1；此公式在任何情况下都正确
C: D[i][j]元素的存储地址=数组的起始地址+((j-1)*每行的列数+i-1)*单一元素占用存储单元的数目
D: D[i][j]元素的存储地址=数组的起始地址+(j-1)*每行的列数+i-1；此公式在任何情况下都正确
答案: 【 D[i][j]元素的存储地址=数组的起始地址+((i-1)*每行的列数+j-1)*单一元素占用存储单元的数目】
43、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
参照上图(I)，下列说法不正确的是_____。
选项：
A: 当数据元素不发生变化，而只是数据元素之间的关系发生变化时，既需要调整数据元素本身，又需要调整其对应的左指针数组或右指针数组中的值来完成
B: 当数据元素不发生变化，而只是数据元素之间的关系发生变化时，可以通过调整数据元素对应的左指针数组或右指针数组中的值来完成
C: 相同的数据元素，不同的左指针和右指针可以反映数据元素之间不同的关系
D: 图(I)说明，一个数据元素最多只能有两个子元素，一个是左子元素，一个是右子元素
答案: 【 当数据元素不发生变化，而只是数据元素之间的关系发生变化时，既需要调整数据元素本身，又需要调整其对应的左指针数组或右指针数组中的值来完成】
44、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
上图(I)表示的数据的逻辑关系，下列正确的是_____。
选项：
A: 图II.(d)
B: 图II.(a)
C: 图II.(b)
D: 图II.(c)
答案: 【 图II.(d)】
45、单选题：
“树”是一种典型的数据结构，在很多算法中都应用树来组织相关的数据。树是组织层次型数据的一种存储结构，它将每一个数据称为一个数据元素。见下图I.示意，采用三个数组来存储树型数据，一个数组TreeElement[]存放数据元素本身，一个数组LeftPointer[]存放该数据元素的左侧子元素的存放地址(简称为左指针)，另一个数组RightPointer[]存放该数据元素的右侧子元素的存放地址(简称为右指针)。参照图I.，回答问题。
如想使图(I)，改变为存储下图IV所示的逻辑关系，下列四步操作都是需要的，但有些操作的内容却是不正确的。不正确的是_____。
选项：
A: 将00000000 00010010号存储单元的值修改为00000000 00000010
B: 将00000000 00001000号存储单元的值修改为00000000 01010101
C: 将00000000 00011010号存储单元的值修改为00000000 00000000(即Null)
D: 将00000000 00001010号存储单元的值修改为00000000 00001000
答案: 【 将00000000 00010010号存储单元的值修改为00000000 00000010】
46、单选题：
TSP算法流程图如下图I.示意，回答问题：中层循环(K变量控制的循环)的作用是_________。
选项：
A: 用于寻找距当前城市距离最近的城市
B: 用于判断某个城市是否是已访问过的城市
C: 用于完整地产生一个路径
D: 其它三个选项都不是
答案: 【 用于寻找距当前城市距离最近的城市】
47、单选题：
TSP算法流程图如下图I.示意，回答问题：外层循环(I变量控制的循环)的作用是_________。
选项：
A: 用于完整地产生一个路径
B: 用于判断某个城市是否是已访问过的城市
C: 用于寻找距当前城市距离最近的城市
D: 其它三个选项都不是
答案: 【 用于完整地产生一个路径】
48、单选题：
关于算法类问题的基本求解步骤，下列说法不正确的是_________。
选项：
A: 其它三个选项的说法有不正确的
B: 算法类问题求解首先要进行数学建模，即用数学语言对问题进行抽象
C: 一个问题，进行了数学建模后，可以通过模型的一些性质的分析判断该问题是否有解；在有解的情况下，再设计算法进行求解，否则则可能做的是无用功！
D: 一个问题，进行了数学建模后，可以依据数学的一些求解方法，设计出让计算机求解的算法
E: 一个问题，虽然进行了数学建模但可以不依据数学求解方法，设计出让计算机求解的算法
答案: 【 其它三个选项的说法有不正确的】
第8讲 问题-算法与环境排序算法研究示例
第8讲之模拟练习题
1、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示。如果：内存块数为
，待排序元素集合所占用磁盘块数
，采用排序-归并算法进行升序排序，下列说法正确的是_____。
选项：
A: 算法以磁盘块读写次数衡量的时间复杂性为
B: 算法以磁盘块读写次数衡量的时间复杂性为
C: 算法以磁盘块读写次数衡量的时间复杂性为
D: 算法以磁盘块读写次数衡量的时间复杂性为
答案: 【 算法以磁盘块读写次数衡量的时间复杂性为】
2、单选题：
下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。
【算法A1】
Start of algorithm A1
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。
End of algorithm A1
【算法A2】
Start of algorithm A2
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。
Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。
End of algorithm A2
【算法A3】
Start of algorithm A3
Step 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
关于三个算法的复杂性，下列说法正确的是_____。
选项：
A: 算法A1、A2和A3的时间复杂性都为O(n)
B: 算法A1和A2的时间复杂性为O(1)，算法A3的时间复杂性为O(n)
C: 算法A1的时间复杂性为O(n)，算法A2的时间复杂性为O(n/2)，算法A3的时间复杂性为O(n/4)
D: 算法A1和A2的时间复杂性为O(n)，算法A3的时间复杂性为
答案: 【 算法A1和A2的时间复杂性为O(n)，算法A3的时间复杂性为】
3、单选题：
关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。
若要在n个全文文档中(n可能很大)查找有无某个关键词的文档，为提高检索效率，最好的做法是_____。
选项：
A: 直接用给定关键词来匹配每一份文档中的每一个词汇。若该文档存在匹配成功的词汇，则输出该文档；否则，不输出该文档
B: 对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号；否则，则输出信息“没有含该关键词的文档”
C: 对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”
D: 选项(B)(C)比选项(A)的做法好，但选项(B)(C)没有效率上的差别
答案: 【 对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”】
4、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
关于“排序-归并”算法，下列说法不正确的是_____。
选项：
A: “排序-归并”算法是一个两阶段完成排序的算法，第一个阶段称为子集合排序，第二个阶段称为归并排序
B: “排序-归并”算法是在这样环境下应用的算法：待排序数据元素数目大于或远大于内存中可装入数据元素数目
C: “排序-归并”算法可以对任意大规模的数据集合进行排序；“排序-归并”算法是通过多次读写磁盘完成大规模数据集合的排序工作的
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
5、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示，内存块数为
，每块可装载
个元素，如果经过一个轮次的归并操作便能完成排序，则关于待排序元素集合的大小，下列说法正确的是_____。
选项：
A: 待排序元素数目应 
B: 待排序元素数目应 
C: 待排序元素数目应 
D: 待排序元素数目应 
答案: 【 待排序元素数目应 】
6、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示。如果：内存块数为，每块可装载个元素，待排序元素集合所占用磁盘块数
，采用排序-归并算法进行升序排序，下列说法正确的是_____。
选项：
A: 算法以磁盘块读写次数衡量的时间复杂性为
B: 算法以磁盘块读写次数衡量的时间复杂性为
C: 算法以磁盘块读写次数衡量的时间复杂性为
D: 算法以磁盘块读写次数衡量的时间复杂性为
答案: 【 算法以磁盘块读写次数衡量的时间复杂性为】
7、单选题：
下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。
【算法A1】
Start of algorithm A1
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。
End of algorithm A1
【算法A2】
Start of algorithm A2
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。
Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。
End of algorithm A2
【算法A3】
Start of algorithm A3
Step 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的快慢问题，下列说法正确的是_____。
选项：
A: 算法A1快于算法A2， 算法A2快于算法A3
B: 算法A2快于算法A1， 算法A2快于算法A3
C: 算法A3快于算法A2， 算法A2快于算法A1
D: 算法A1快于算法A3， 算法A3快于算法A2
答案: 【 算法A3快于算法A2， 算法A2快于算法A1】
8、单选题：
关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。
上图给出了一种“自动获取文档关键词”的方法，关于该方法的表述，最好的是_____。
选项：
A: 文档中出现次数最多的词汇必定是关键词
B: 文档中去掉标点符号后，出现次数最多的词汇必定是关键词
C: 文档中去掉标点符号和一些辅助词汇， 出现次数最多的词汇必定是关键词
D: 文档中去掉标点符号和一些辅助词汇， 出现次数最多且次数达到一定数值的词汇必定是关键词
答案: 【 文档中去掉标点符号和一些辅助词汇， 出现次数最多且次数达到一定数值的词汇必定是关键词】
9、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }关于排序的选择法和冒泡法，下列说法不正确的是_____。
选项：
A: “选择法”和“冒泡法”都是每一轮次找出一个最小值元素，只是寻找最小值元素的方法不一样，在效率方面没有什么差别；
B: “选择法”通过将所有未排序元素与当前轮次待寻找的最小值元素进行比较，获得当前轮次的最小值元素；而“冒泡法”通过相邻元素的两两比较，一个轮次完成也能获得一个最小值元素；
C: 虽然“选择法”和“冒泡法”都是每一轮次找出一个最小值元素，但选择法每轮次仅比较，没有交换，直至找到最小值后做一次交换；而冒泡法每一轮次是通过相邻元素比较来找最小值，如果不满足排序，则交换相邻两个元素，交换可能频繁发生。这样来看，选择法比冒泡法要快一些；
D: 上述说法有不正确的。
答案: 【 “选择法”和“冒泡法”都是每一轮次找出一个最小值元素，只是寻找最小值元素的方法不一样，在效率方面没有什么差别；】
10、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }阅读BUBBLE-SORT算法，已知N=20，下列说法正确的是_____。
选项：
A: 第5轮次，是将第1个元素至第15个元素之间的元素，相邻者进行比较
B: 第4轮次，是将第1个元素至第20个元素之间的元素，相邻者进行比较
C: 第8轮次，是将第20个元素至第12个元素之间的元素，相邻者进行比较
D: 第11轮次，是将第20个元素至第1个元素之间的元素，相邻者进行比较
答案: 【 第5轮次，是将第1个元素至第15个元素之间的元素，相邻者进行比较】
11、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
已知内存块数为
，待排序元素集合所占用磁盘块数
，设计一个“排序-归并”算法的基本思路，下列描述不正确的是_____。
选项：
A: 首先划分子集合，每个子集合最大可为块，可以划分为/个子集合。这样划分的理由：一是子集合可以全部装载入内存执行内排序，二是最大限度地利用内存产生尽可能少数目的子集合
B: 将块内存留出两块，一块作为输出数据块，一块用于待比较元素数据块。其余-2块用于装载尽可能多数目的子集合，即尽可能采用更多路的归并。这样做的理由：尽可能最大限度地利用内存，以便减少归并的次数
C: 如果子集合参与归并一次被称为一个轮次，则整个数据集的轮次是指该数据集中参与归并次数最多的子集合的轮次。归并算法应考虑以尽可能少轮次的归并为目标来衡量各种不同归并策略的好坏。也可以定义一个参数“子集合轮次累积和”，即所有子集合参与归并轮次的总和，来衡量性能好坏，即“子集合轮次累积和”越小，算法性能越好
D: 假设=6，=60，则按照上述(A)(B)(C)思想，可自动确定出：子集合数目=10，第一次将10个子集合分成3组(3个、3个和4个)并分别采用3路归并和4路归并将其归并成3个子集合；第二次对这3个集合再采用3路归并完成最终的排序。这样做的算法是最优的
答案: 【 假设=6，=60，则按照上述(A)(B)(C)思想，可自动确定出：子集合数目=10，第一次将10个子集合分成3组(3个、3个和4个)并分别采用3路归并和4路归并将其归并成3个子集合；第二次对这3个集合再采用3路归并完成最终的排序。这样做的算法是最优的】
12、单选题：
PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。
按照PageRank的思想，一个网页的重要度被定义为_____。
选项：
A: 其所拥有的所有反向链接的数目
B: 其所拥有的所有正向链接的数目
C: 其所拥有的所有链接的数目
D: 上述都不正确
答案: 【 上述都不正确】
13、单选题：
关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。
针对下列问题求解方法：对n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找次数最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”。问该方法涉及到几类算法，说法正确的是_____。
选项：
A: 涉及字符串的字母序排序算法
B: 涉及数值属性排序算法
C: 涉及字符串匹配算法及数值属性查找算法
D: 涉及上述全部算法
答案: 【 涉及上述全部算法】
14、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示。如果：内存块数为，每块可装载个元素，待排序元素集合所占用磁盘块数，则关于此集合的排序问题，下列说法正确的是_____。
选项：
A: 首先将待排序元素集合划分为2个子集合，每个子集合为12块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再一个轮次对这2个已排序子集合进行归并操作，完成最终排序
B: 首先将待排序元素集合划分为4个子集合，每个子集合为6块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再对这4个已排序子集合进行归并操作，完成最终排序
C: 首先将待排序元素集合划分为6个子集合，每个子集合为4块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再对这6个已排序子集合进行一个轮次的归并操作，完成最终排序
D: 前述(A)(B)(C)都正确
答案: 【 首先将待排序元素集合划分为4个子集合，每个子集合为6块，将每个子集合从磁盘装入内存并采用任何内排序算法进行排序后再写回磁盘；然后再对这4个已排序子集合进行归并操作，完成最终排序】
15、单选题：
PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。
PageRank将网页的链接关系，抽象为一个n ´ n的矩阵A：网页被从1到n进行编号；如果网页i有一个指向网页j的链接，则矩阵的
元素(即第i行第j列元素)值为1，否则矩阵元素值为0。然后将A做一个转置处理(即矩阵的行列互换)，形成转置矩阵
，为什么要转置，原因是_____。
选项：
A: 有利于体现反向链接的重要性
B: 有利于更好地区分反向链接与正向链接
C: 有利于计算权值矩阵(可被称为转移概率矩阵M)：将的一列中的各行除以该列中1的个数，即可形成权值矩阵M
D: 有利于由计算的权值矩阵M与网页重要度矩阵R的乘积符合网页重要度的计算方法：反向链接的加权和
答案: 【 有利于由计算的权值矩阵M与网页重要度矩阵R的乘积符合网页重要度的计算方法：反向链接的加权和】
16、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示。如果：内存块数为，待排序元素集合所占用磁盘块数，进行升序排序。如果：归并过程中，整体的数据集被从磁盘读入内存，再由内存写回磁盘，被称为一个轮次，则下列说法正确的是_____。
选项：
A: 该数据集可以经过1个轮次的2路归并完成最终排序
B: 该数据集可以经过2个轮次的2路归并完成最终排序
C: 该数据集可以经过3个轮次的2路归并完成最终排序
D: 该数据集可以经过多于3个轮次的2路归并完成最终排序
答案: 【 该数据集可以经过多于3个轮次的2路归并完成最终排序】
17、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }关于INSERTION-SORT算法的基本思想，下列说法正确的是_____。
选项：
A: 一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束
B: 一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束
C: 一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束
D: 上述说法都不正确
答案: 【 一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束】
18、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }关于三种排序算法，下列说法正确的是_____。
选项：
A: 三种算法的时间复杂度都为，所以三种算法的执行效率是一样的；
B: 尽管三种算法的时间复杂度都为，但细致比较还是有差别的，例如冒泡法排序比选择法排序要快一些；
C: 尽管细致比较三种算法的执行时间是有差别的，但这种差别对内排序问题而言是可以忽略不计的
D: 尽管细致比较三种算法的执行时间是有差别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行
答案: 【 尽管细致比较三种算法的执行时间是有差别的，这种差别对内排序问题而言是重要的，因为内排序算法可能要被频繁的执行】
19、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }阅读INSERTION-SORT算法，关于第4.行至第6.行间程序段的作用，下列说法正确的是_____。
选项：
A: 将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置
B: 将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以前的元素依次向后移动一个位置
C: 将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递增方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向前移动一个位置
D: 将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向后移动一个位置
答案: 【 将当前待处理元素，依次与已经排序的第j个元素进行比较，j采取递减方式循环，以找到当前元素所应在的位置，并将该位置以后的元素依次向后移动一个位置】
20、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }阅读SELECTION-SORT算法，关于第3.行至第4.行间程序段的作用，下列说法正确的是_____。
选项：
A: 循环地在未排序元素集合中找最小值元素的位置，该位置保存在变量k中
B: 循环地在未排序元素集合中找最小值元素，该元素保存在变量k中
C: 循环地在未排序元素集合中找最大值元素的位置，该位置保存在变量k中
D: 循环地在未排序元素集合中找最大值元素，该元素保存在变量k中
答案: 【 循环地在未排序元素集合中找最小值元素的位置，该位置保存在变量k中】
21、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示。如果：内存块数为
，待排序元素集合所占用磁盘块数
，首先，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)策略
答案: 【 前述(A)(B)(C)归并策略都可以，但性能有所不同，最好的是(A)策略】
22、单选题：
PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。
按照PageRank的思想，一个网页的重要度被定义为_____。
选项：
A: 其所拥有的所有反向链接的数目
B: 其所拥有的所有反向链接的加权和
C: 其所拥有的所有正向链接的数目
D: 其所拥有的所有正向链接的加权和
答案: 【 其所拥有的所有反向链接的加权和】
23、单选题：
PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。
按照PageRank的思想，一个网页链接的权值被定义为_____。
选项：
A: 网页重要度除以该网页所拥有的正向链接数
B: 网页重要度除以该网页所拥有的反向链接数
C: 网页重要度除以该网页所拥有的所有链接数
D: 上述都不正确
答案: 【 网页重要度除以该网页所拥有的正向链接数】
24、单选题：
PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。
前述说过 PageRank，通过不断地计算
来计算网页重要度，即由第(m-1)次的网页重要度来计算第(m)次的网页重要度，那么网页重要度的初始值
应如何获得呢?
下列说法正确的是_____。
选项：
A: 随机产生各网页重要度的一组值，该组值对最终计算结果没有影响
B: 由专家给出各网页重要度的一组值，该组值的质量好坏直接影响计算结果
C: 设定各网页重要度都是1
D: 随机产生各网页重要度的一组值，使网页重要度界于0和1之间，但该组值对最终结果没有影响
答案: 【 随机产生各网页重要度的一组值，使网页重要度界于0和1之间，但该组值对最终结果没有影响】
25、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
关于内排序和外排序算法设计的关键点，下列说法不正确的是_____。
选项：
A: 外排序算法体现了受限资源环境下的算法构造，这里内存是一种受限资源
B: 外排序算法强调尽可能少地读写磁盘，尽可能充分地利用内存来完成算法构造
C: 外排序算法体现了与内排序算法设计不一样的关注点，前者更关注磁盘读写，后者更关注CPU执行操作的步数
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
26、单选题：
PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。
关于PageRank计算网页重要度的基本思想，下列说法正确的是_____。
选项：
A: 反向链接数越多的网页越重要----被链接次数越多越重要
B: 反向链接加权和越高的网页越重要----被重要网页链接次数越多越重要
C: 正向链接数越多的网页，其链接的权值越低----正向链接数越多的网页越不重要
D: 上述全部
答案: 【 上述全部】
27、单选题：
PageRank是Google公司提出的计算网页重要度的一种方法。参见下图，简单而言，网页是由“文本”和“链接”构成的，“链接”可使用户从一个网页跳转到另一个网页。因此，所谓“链接”即是某一个网页的地址，通过网页链接的读取，可以建立起各个网页之间的链接关系。对一个网页而言，其链接到其他网页的链接被称为“正向链接”，而所有链接到该网页的链接被称为“反向链接”。关于PageRank算法，回答问题。
前述说过 PageRank网页i重要度
可以通过迭代地计算得到，即由m-1状态下各个网页的重要度
，依转移概率矩阵计算m状态下网页重要度
，参见下图。
关于网页重要度的计算过程，下列说法正确的是_____。
选项：
A: 在得到了转移概率矩阵M后，任意给出网页重要度的一组值，记为，是一向量，参见下图，继续进行(B)
B: 不断地计算
，m从0开始，为迭代次数。当
时，迭代计算终止，此时的向量R即为所求的各个网页的重要度
C: 选项(A)(B)是将状态序列，...，，，...不断迭代产生后趋于稳定的，或者说收敛的，作为最终的R，即是已知M情况下，求方程R = MR的解
D: 上述说法都正确
答案: 【 上述说法都正确】
28、单选题：
排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。
选项：
A: 大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多
B: 大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多
C: 对无序数据集合，两个算法 X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢
D: 上述说法有不正确的
答案: 【 对无序数据集合，两个算法 X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢】
29、单选题：
下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。
【算法A1】
Start of algorithm A1
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。
End of algorithm A1
【算法A2】
Start of algorithm A2
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。
Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。
End of algorithm A2
【算法A3】
Start of algorithm A3
Step 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，下列说法正确的是_____。
选项：
A: 对数据表中的任何数据，算法A3都适用
B: 对数据表中任何已排序的数据，算法A3都适用
C: 对已按成绩排序的数据表，算法A3都适用
D: 对已按成绩进行降序排列的数据表，算法A3都适用
答案: 【 对已按成绩进行降序排列的数据表，算法A3都适用】
30、单选题：
下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。
【算法A1】
Start of algorithm A1
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。
End of algorithm A1
【算法A2】
Start of algorithm A2
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。
Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。
End of algorithm A2
【算法A3】
Start of algorithm A3
Step 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，下列说法正确的是_____。
选项：
A: 如果数据表中记录数越多，则算法A3相比算法A1的优势越明显，即查找时间越短
B: 如果数据表中记录数越多，则算法A1相比算法A3的优势越明显；即查找时间越短
C: 算法A3和算法A1的执行时间差异不会随数据表中记录数多少而变化
D: 上述都不正确
答案: 【 如果数据表中记录数越多，则算法A3相比算法A1的优势越明显，即查找时间越短】
31、单选题：
下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。
【算法A1】
Start of algorithm A1
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。
End of algorithm A1
【算法A2】
Start of algorithm A2
Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。
Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。
Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。
End of algorithm A2
【算法A3】
Start of algorithm A3
Step 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，下列说法正确的是_____。
选项：
A: 算法A2在任何情况下都需要读取n条记录，才能得到结果
B: 算法A2在任何情况下都需要读取n/2条记录，才能得到结果
C: 算法A2在最好的情况下是读取1条记录，在最差的情况是读取n条记录，才能得到结果
D: 算法A2在任何数据分布情况下，平均要读取n/2条记录才能得到结果
答案: 【 算法A2在最好的情况下是读取1条记录，在最差的情况是读取n条记录，才能得到结果】
32、单选题：
关于“非结构化数据(文档)的查找与搜索”问题，参考下图，回答下列问题。注意每份文档可能包含数千数万的词汇。
若要在n个全文文档中(n可能很大)查找与某个关键词最相关的文档，为提高检索效果和检索效率，最好的做法是_____。
选项：
A: 对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”及包含该关键词的“文档编号”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则输出索引表中相对应的文档编号，否则，则输出信息“没有含该关键词的文档”
B: 对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”，并按关键词进行字母序的排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找同一关键词“次数”最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”
C: 对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找同一关键词“次数”最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”
D: 选项(B)(C)比选项(A)的做法好，但选项(B)(C)在执行效果和执行效率方面没有什么差别
答案: 【 对这n个文档，首先建立一个“关键词”索引表，该索引表记录着“关键词”，包含该关键词的“文档编号”，以及该关键词在该文档中出现的“次数”；对索引表，按关键词进行字母序的排序；如果关键词相同，则进一步按“次数”对同一关键词的若干文档进行降序排序。在此基础上，用给定关键词来匹配索引表中的关键词。如果匹配成功，则进一步寻找同一关键词“次数”最多的m个索引项，输出相对应的文档编号；否则，则输出信息“没有含该关键词的文档”】
33、单选题：
关于“内排序”算法和“外排序”算法，下列说法不正确的是_____。
选项：
A: “内排序”算法通常是内存中数据排序常用的算法，而“外排序”算法通常是大规模数据排序常用的算法
B: “内排序”算法由于内存排序应用的频繁性，所以算法要考虑用尽可能少的步骤，而“外排序”算法由于要利用磁盘保存中间结果，所以算法主要考虑尽可能少的读写磁盘
C: 无论是“内排序”算法，还是“外排序”算法，都需要考虑读写磁盘的代价问题
D: 对一组需要排序的数据，能应用“内排序”算法时，尽量不用“外排序”算法
答案: 【 无论是“内排序”算法，还是“外排序”算法，都需要考虑读写磁盘的代价问题】
34、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }关于SELECTION-SORT算法的基本思想，下列说法正确的是_____。
选项：
A: 一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束。
B: 一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。
C: 一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。
D: 上述说法都不正确。
答案: 【 一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。】
35、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }关于BUBBLE-SORT算法的基本思想，下列说法正确的是_____。
选项：
A: 一个元素一个元素的处理。每次处理一个元素，通过与当前已排序元素的比较，将该元素放入到当前正确排序的位置。直到最后一个元素则算法结束。
B: 一个轮次一个轮次的处理。将元素集合分成两个部分，已排序元素集合和未排序元素集合，开始时已排序元素集合为空。在每一轮次，从未排序元素集合中找出最小值的元素，将其移入已排序元素集合；直到未排序元素集合为空时则算法结束。
C: 一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。
D: 上述说法都不正确。
答案: 【 一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较：如不符合排序关系，则交换两个元素。直到某一轮次没有元素交换发生则结束。】
36、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }阅读BUBBLE-SORT算法，下列说法正确的是_____。
选项：
A: 该算法在N=20时，必定要执行20个轮次的内循环
B: 该算法在N=20时，必定要执行19个轮次的内循环
C: 该算法在N=20时，最多要执行20个轮次的内循环
D: 该算法在N=20时，最多要执行19个轮次的内循环
答案: 【 该算法在N=20时，最多要执行19个轮次的内循环】
37、单选题：
下列三种算法是经常应用的内排序算法：插入排序、选择排序和冒泡排序。阅读下列算法，回答问题。INSERTION-SORT(A)
1. for i=2 to N
2. { key = A[i] ;
3. j =i-1;
4. While (j>0 and A[j]>key) do
5. { A[j+1]=A[j];
6. j=j-1; }
7. A[j+1]=key;
8. }
SELECTION-SORT(A)
1. for i=1 to N-1
2. { k=i;
3． for j=i+1 to N
4. { if A[j]<A[k] then k=j; }
5. if k<>i then
6. {
7. temp =A[k];
8. A[k]=A[i];
9. A[i]=temp;
10. }
11. }
BUBBLE-SORT(A)
1. for i=1 to N-1
2. { haschange=false;
3. for j=1 to N-i
4. { if A[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) then break;
12. }阅读BUBBLE-SORT算法，其中关于haschange变量的作用，下列说法不正确的是_____。
选项：
A: haschange用于标记每个轮次的相邻元素比较中，是否有“交换”发生
B: haschange用于判断至某个轮次时是否已完成排序，以便提前结束算法
C: haschange需要在每轮次之前置初始值为假，表示没有“交换”发生
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
38、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示。如果：内存块数为，每块可装载个元素，待排序元素集合所占用磁盘块数，进行升序排序，此集合已被划分为4个子集合并对每个子集合元素已进行升序排序并写回磁盘，则关于归并问题，下列说法不正确的是_____。
选项：
A: 内存共有6块，其使用分配如下：4块内存中的每一块分别用于装载4个子集合中的一块；剩余2块，一块用于装载输出数据块，另一块用于存放待比较元素数据块，该块中的元素分别来自于4个子集合中
B: 待比较元素数据块中的最小者，被送到输出数据块中；同时，再从其对应的子集合数据块中依次补充进一个元素
C: 当某子集合在内存的数据被处理完时，则再从磁盘上将该子集合的下一块读入到内存中，直到该子集合的所有块都已经被处理完为止；当输出数据块被装满时，则将输出数据块依次写回到磁盘上
D: 上述说法有不正确的
答案: 【 上述说法有不正确的】
39、单选题：
外排序是需要使用硬盘等外部存储设备进行大数据集合排序的过程或算法，其中一种策略是“排序-归并”，如下图所示。仔细理解该图所表达的基本思想，回答问题。
参见图示。如果：内存块数为，待排序元素集合所占用磁盘块数，进行升序排序。如果：从磁盘装入内存，再从内存写回磁盘，被称为内存利用了一次，则下列说法正确的是_____。
选项：
A: 该数据集基于“排序-归并”策略完成最终排序，需要利用内存19次
B: 该数据集基于“排序-归并”策略完成最终排序，需要利用内存9次
C: 该数据集基于“排序-归并”策略完成最终排序，需要利用内存10次
D: 该数据集基于“排序-归并”策略完成最终排序，需要利用内存5次
答案: 【 该数据集基于“排序-归并”策略完成最终排序，需要利用内存19次】