算法和程序设计分析及试题附答案_08-算法和程序设计
选修1：算法与程序设计
第一单元算法
一、知识内容
（一）使用计算机解决问题的一般过程
考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。
1．一般过程
（1）分析问题确定要使用计算机来“做什么”，即确定解题的任务。
（2）寻求解决问题的途径和方法。
（3）用计算机进行处理。
2．确定解决问题的方法及步骤化
确定了解决问题的方法后，必须把解决问题的方法步骤化，即用某种方式告诉计算机每个需做什么。
计算机开始计算之前，需把解决问题的程序存储在内存中。通常一个程序包括指令和数据两部分。
（1）指令部分：指令是对计算机操作类型和操作数地址做出规定的一组符号。
（2）数据部分：计算所需的原始数据、计算的中间结果或最终结果。
3．设计程序时需要考虑的问题
（1）数据的存储：计算所需要的原始数据、计算产生的中间结果需要存储在不同的变量中。
（2）计算的过程：把解决问题的方法步骤化，并用计算机能执行的指令来有序地实现对应的步骤。
（3）典型的指令类型有输入指令、输出指令、算术运算指令、逻辑运算指令和控制转移指令。（二）算法及算法的表示方法
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．算法的特征
（1）有穷性。一个算法必须保证它的执行步骤是有限的，即它是能终止的。
（2）确定性。算法中的每个步骤必须有确切的含义，不应当有模棱两可的。
（3）能行性。算法中的每一个步骤都要足够简单，能实际能作的，而且在能在有限的时间内完成。
（4）有0个或多个输入。
（5）有一个或多个输出。
（三）用自然语言、流程图、伪代码表示算法
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．自然语言
就像写文章时所列的提纲一样，可以有序地用简洁的自然语言加数学符号来描述算法。
2．流程图
用国家颁布的标准（GB1526-89，ISO5807-1985）中规定的图示及方法来画流程图，常用的构件有如图所示。
3．伪代码
使用某些程序设计语言中控制结构，来描述算法中各步骤地执行次序和模式；使用自然语言、数学符号或其他符号，来表示计算步骤要完成的处理或需要涉及的数据。
（四）顺序、选择和循环三种基本模式
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．顺序模式就是按指令的先后顺序依次执行
2．分支模式就是根据分支条件，判断条件成立情况，选择某一条路径中的指令执行
3．循环模式就是首先判断条件是否成立，如果不成立则直接执行循环体外的第一条指令，如果条件成立则执行循环体内的指令，然后再次判断条件是否成立，如果条件成立再次执行循环体内的指令，直至条件不成立跳出循环体为止。
三种基本模式流程示意图如下图所示。
二、例题分析
1．下面关于算法的描述，正确的是
(A) 一个算法只能有一个输入
(B) 算法只能用框图来表示
(C) 一个算法的执行步骤可以是无限的
(D) 一个完整的算法，不管用什么方法来表示，都至少有一个输出结果
参考答案：D 所考知识点：算法的特征
2．算法描述可以有多种表达方法，下面哪些方法不可以描述“闰年问题”的算法
(A) 自然语言(B) 流程图(C) 伪代码(D) 机器语言
参考答案：D 所考知识点：算法的描述
3．算法与程序的关系
(A) 算法是对程序的描述(B) 算法决定程序，是程序设计的核心
(C) 算法与程序之间无关系(D) 程序决定算法，是算法设计的核心
参考答案：B 所考知识点：算法的概念
4．人们利用计算机解决问题的基本过程一般有如下四个步骤（①～④），请按各步骤的先后顺序在下列选项中选择正确的答案
①调试程序②分析问题③设计算法④编写程序
(A) ①②③④(B) ②③④①(C) ③②④①(D) ②③①④
参考答案：B 所考知识点：用计算机解决问题的过程
5．在一次电视选秀活动中，有三个评位为每位选手打分。如果三个评委都亮绿灯，则进入下一轮；如果两个评委亮绿灯，则进入待定席；如果红灯数超过二盏则淘汰。最适合用到的程序结构是
(A) 循环(B) 赋值(C) 分支(D) 顺序
参考答案：C 所考知识点：算法的基本模式
6．下列流程图符号属于判断框的是
(A) (B) (C) (D)
参考答案：D 所考知识点：算法的表示、流程图
第二单元VB程序设计
一、知识内容
（一）面向对象程序设计的基本思想与方法
考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。
1．面向对象程序设计（object oriented programming，缩写OOP）方法：在进行程序设计是从分析问题领域中各种客观事物本体的属性和行为，以及它们之间的相互关系着手，在计算机中建立起这些客体的映象——对象，用对象对应于问题领域中的客体，用对象间的消息传递来表示客体的相互作用、相互关系。
（二）属性、类、事件和事件处理的概念
考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。
1．对象是客观存在的事物或概念。它有两个特点：状态和行为。
2．一个对象的状态是通过若干个属性（property）来描述的；行为是指对属性进行操作和处理的方法（method）。在面向对象的程序设计中，一个对象是由一组对象状态的数据和一组描述处理对象属性的方法的代码构成的。对象的属性定义其外观，方法定义其行为，事件定义其与用户的交互。
3．类（class）是对相同性质的对象的一种抽象，而一个对象则是类的一个“实例”。
4．事件（event）就是发生在对象上的事情，通常是由用户在对象上激发的一种动作。一个事件的发生，可以引起某个对象上某个方法（事件处理过程）的执行，即由某个事件驱动了相应的事件处理过程的执行。这就是面向对象程序设计中的事件驱动概念。
（二） VB应用程序的界面设计与调式
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．VB应用程序的界面设计
（1）VB程序设计语言：基于Basic语言的可视化程序设计环境，采用面向对象的程序设计方法（OOP）。
（2）VB应用程序设计环境的的窗口主要由对象窗口、控件工具箱、属性窗口、工程窗口组成。
（3）控件工具箱集中了常用的基本控件：标签label、文本框TextBox、命令按钮Command Button、列表框ListBox等。
(4)窗体（Form）是VB应用程序的基本结构。窗体可以看作是一个“容器”，其中放置着各种各样在应用程序中必须用到的对象。
2．VB应用程序的运行和保存
运行：单击工具栏中“运行”选项中的启动按钮，运行应用程序。
保存：在“文件”菜单中选“工程另存为”，该应用程序的窗体和工程分别存储到文件中，其相应的文件扩展名分别是“.frm”和“.vbp”。也可以选“文件”菜单中的“生成工程xxx.exe”，这样，就可在Windows环境中直接运行这个应用程序了。
（四）事件处理代码的编制方法考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
对于对象而言，事件就是发生在该对象上的事情，通常是由用户在对象上激发的一种动作。一个事件的发生，可以引起某个对象上某个方法的执行，即由某个事件驱动了相应的事件处理过程的行为。
在事件处理过程中，可以按预定设计好的方式，改变某个对象的相关属性值，因此是这个对象的状态得到相应的改变。
（五）VB基本数据类型、常量、变量和数组
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．数据：数据是信息的一种记录形式。在VB中，常用的基本数据类型有以下几种：Integer(整数型)、Long(长整数型)、Single(单精度实数型)、Double(双精度实数型)、String(字符串型)、Boolean(逻辑型)、Date(日期型)。
2．常量：常量是在程序执行过程中其值不变的存储单元或数据。在VB中，常量有整数常量、实数常量、字符串常量和逻辑常量这几种类型。
3．变量：变量用来表示数据的存储区，在程序运行过程中，这些存储区中的值是可以改变的。变量名由字母、数字和下划线等字符组成，但必须以字母开头，在变量名中对大小写字母是不加区分的。
变量说明语句的常用形式为：Dim 变量名As 变量的类型。
4．数组：数组是由一批同类型的变量构成的一个序列，组成数组的每一个变量被称为数组的元素，也称为下标变量，下标是一个整数，用来指出某个元素在数组中的位置。
一维数组的常用形式为：Dim 数组变量名(A1 To A2) As 元素的类型。
二维数组的常用形式为：Dim 数组变量名(A1 To A2，B1 To B2) As 元素的类型。
（六）VB各类表达式与标准函数
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．VB中的常用标准函数
（1）常用数学函数：Abs(X)、Int(X)、Sqr(X)、Rnd（）、 Exp(X)、Log(X)、Sin(X)、Cos(X)、Tan(X)。
（2）常用类型转换函数和字符串函数：Asc(X)、Chr(X)、Val(X)、Str(X)、Len(X)、Mid(X,n,k)、Fix(X)。
2．基本运算与表达式
（1）VB的基本运算：VB的基本运算包括算术运算、关系运算和逻辑运算三大类。
算术类基本运算有：＾、-、*、/、\、Mod、+、-
关系类基本运算有：=、<>、<、>、<=、>=
逻辑类基本运算有：Not 、And 、Or
（2）表达式：表达式主要用来规定值的计算过程，以及对于某些情况或条件的判断。一个表达式中可能包括算术运算、关系运算和逻辑运算等多种基本运算，以及这些基本运算所涉及的数据（变量和常量）。
（3）基本运算的优先级从高到低为：＾（1级），-（指负号，2级），﹡、/（3级），\（4级），Mod（5级），+、-（6级），=、<>、<、>、<=、>=（7级），Not（8级），And（9级），Or（10级）。（七）常用的VB语句
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
（八）使用VB实现顺序、选择、循环三种控制结构
考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．赋值语句：变量名 = 表达式
或对象名.属性名 = 表达式
2．选择语句：
行If语句：If 条件表达式Then 语句1 Else 语句2
或If 条件表达式Then 语句
块If语句：
If 条件表达式1 Then
语句块 1
ElseIf 条件表达式2 Then
语句块 2
……
ElseIf 条件表达式n Then
语句块 n
Else
语句块 0
End If
3．循环语句：
For 语句 For 循环变量 = 初值To 终值Step 步长
语句块
Next 循环变量
Do 语句 Do While 条件表达式
语句块
Loop
4．注释：注释是以单引号（'）开头的一串文字，可以出现在程序中需要说明的位置上，通过这一串文字，对附近的程序段进行简要的说明，增加程序的可读性。注释对程序的执行效果没有任何影响，程序运行时自动跳过注释。
（九）过程、事件处理过程、自定义函数考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．VB应用程序是按模块化的方式组成的，一个程序模块是程序的一部分，每个模块负责解决整个应用问题的一部分任务。程序模块分为过程和函数两种。
2．过程：将程序划分成一个个较小的逻辑单元，每个逻辑单元构成一个过程。过程中的代码可以被重复调用。过程分成两类，一类是事件处理过程，另一类是通用过程。
3．事件处理过程： Sub 事件处理过程名（参数表）
语句块
End Sub
其中，事件处理过程名必须符合下面的规则：对象名_事件的标准名。
VB的一些常用对象上的常见事件的标准名有：
文本框Text：Text_Click、Text_DblClick、Text_KeyPress
命令按钮Command：Command_Click、Command_DblClick
标签Label：KeyPress
4．函数：函数是类似于过程的另一个程序模块，不同之处是函数执行完成后，函数的计算结果被送到函数的调用点上，供程序的后继部分继续进行处理。
自定义函数： Function 函数名（参数表） As 类型名
语句块
End Function
二、例题分析
1．对于对象及其特征的错误理解是()。
(A) 对象都具有一个标识自己以区别其他对象的名字。
(B) 对象都具有自身的属性及其属性值。
(C) 对象一般只用数据表示属性，但不用代码表示行为。
(D) 对象都具有自身的行为（操作）。
参考答案：C 所考知识点：对象的概念。
2．下列控件中可用于接受用户输入文本，又可用于显示文本的是
(A) Label 控件 (B) TextBox 控件(C) Timer 控件(D) CommandButton 控件
参考答案：B 所考知识点：VB的界面设计。
3．VB中保存工程文件的文件扩展名为
(A) vbp (B) frm (C) doc (D) pas
参考答案：A 所考知识点：VB应用程序的运行和保存
4．VB语言中，下列各种基本数据类型说明符中表示单精度实型数的是
(A) Integer (B) Boolean (C) Single (D) String
参考答案：C 所考知识点：基本数据类型
5．在Visual Basic中，下列属于字符串常量的是
(A) Abs(100) (B) "100" (C) Val("100") (D) 1/2
参考答案：B 所考知识点：数据、标准函数的应用。
解此题需要了解各函数返回值的数据类型，以及数值和字符串的表示方法。题中Abs()函数求的是数值的绝对值，返回的是数值；Val()函数是将数字字符串转换为数值；返回值是数值，1/2本身就是数值；而数字字符串的表示需要加引号。
6．下列可以作为Visual Basic的变量名的是
(A) sqr (B) 2pai (C) cj1 (D) a+b
参考答案：C 所考知识点：变量的命名。
解此题需要了解变量的命名规则。变量名是由字母、数字和下划线等字符的任意字符组成，但必须以字母开头，另外值得一提的是变量名不能使用VB中的保留字。题中sqr属于VB的保留字；5pai不是字母开头；a+b中“+”号是非法字符。
7．函数Sqr(X)功能是
(A) 求X的算术平方根(B) 求X的绝对值
(C) 求不大于X的最大整数(D) 数值X转换成字串X
参考答案：A 所考知识点：标准函数。
8．下列运算结果中，值最大的是
(A) 3\4 (B) 3/4 (C) 4 mod 3 (D) 3 mod 4
参考答案：D 所考知识点：算术类基本运算符
此题考生需注意“/”、“\”、“mod”三个有关除的运算符的区别
9．3 mod 2 + 3 \ 2的执行结果为
(A) -1 (B) 3 (C) 2 (D) 0
参考答案：C 所考知识点：算术类基本运算
10．a=5，b=7，c=-2，d=1时，下列结果为False的是
(A) a + b > c + d And a >= 5 Or Not c > 0 Or d < 0
(B) c + d > a + b And a >= 5 Or Not c > 0 Or d > 0
(C) a + b > c + d And a < 5 Or Not c > 0 Or d < 0
(D) a + d < b + c And a >= 5 Or Not c < 0 Or d < 0
参考答案：D 所考知识点：逻辑类基本运算
11．下列属于正确的Visual Basic表达式是
(A) a+|b| (B) 3b-2a (C) 2?b (D) b+5
参考答案：D 所考知识点：算术表达式
题中a+|b|和3b-2a均属数学表达式，在VB中表达为a+abs(b)和3*b-2*a，而2?b中“?”不属于基本运算符
12．在Visual Basic中，"20"+"08"的运算结果是
(A) "28" (B) False (C) "20+08" (D) "2008"
参考答案：D 所考知识点：字符串表达式
“+”运算符两边的操作数如果均为数值型，则进行算术运算；如果均为字符串，则它的作用是将两个字符串连接起来。题中两边均为字符串，帮结果为D。值得一提的是，“+”两头的操作数的数据类型必须是同一类型的，否则会提示错误
13．以下哪项是Visual Basic合法数组元素的表示法
(A) X9 (B) X[9] (C) X(I+9) (D) X{9}
参考答案：D 所考知识点：数组
延伸：在VB的表达式中，一般只出现小括号，其它括号只能出现在字符串当中。
14．下列属于正确的赋值语句是
(A) a+b=5 (B) a=2+3 (C) 2+3=a (D) a+b=2+3
参考答案：B 所考知识点：赋值语句
赋值语句首先要计算赋值号右边的表达式的值，然后将此值赋给赋值号左边的变量或对象属性。题中A、C、D的左边均不是变量也不是对象属性，只有B符合赋值语句的要求
15．下列语句中正确是
(A) txt3.text=txt1.text+txt2.text (B) https://www.wendangku.net/doc/649492202.html,=cmdOK
(C) 12label.Caption=1234 (D) A=InputBox(Hello)
参考答案：A 所考知识点：赋值语句、对象属性
在对象属性的赋值语句当中，一切要注意赋值号两边的数据类型是否一致，且书写语句是否规范。题中B、C选项https://www.wendangku.net/doc/649492202.html,与12label.Caption均是字符串类型，故“=”均需加引号；而D项中InputBox的输入值需是字符串，所以Hello需加引号；A选项要理解两点：一是txt1、txt2、txt3均表示文本框的名称，二是“+”代表的是连接符的功能，题中只是将txt1和txt2中的字符串连接后赋给txt3。
16．下列程序段中，可以实现变量X、Y的值交换的是
(A) y=x: x=y (B) z=x: y=z: x=y (C) z=x: x=y: y=z (D) z=x: w=y: y=z: x=y
参考答案：C 所考知识点：赋值语句的运用
X，Y的值的交换需要一个中间值Z，先将X保存在Z中，如此X的值就可以保存Y的值，再将Z中的值赋值给Y，这时候实现了X与Y的值的交换。
17．有如下程序段：
x=5: y=-20
if Not x>0 then x=y-3 Else y=x+3
y的值是__________
(A) 2 (B) -23 (C) 8 (D) -17
参考答案：C 所考知识点：选择语句
18．循环语句For i=1 To 10 step 2 的循环次数是
(A) 5 (B) 9 (C) 8 (D) 10
参考答案：A 所考知识点：循环语句的运用
19．有如下程序段：
x=2
For I=1 To 3
If x< I Then
x = x + I
End If
Next I
该程序段运行后，x的值为
(A) 2 (B) 4 (C) 5 (D) 7
参考答案：C 所考知识点：选择语句与循环语句的嵌套运用
20．下列程序段的执行结果为
n=1: s=0
Do while s<20
s=s+n
n=n+2
Loop
Print n; s
(A) 9 16 (B) 11 25 (C) 11 20 (D) 9 24
参考答案：B 所考知识点：Do循环语句的运用
第三单元算法的程序实现
一、知识内容
（一）枚举算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
枚举算法的基本思想是根据问题的本身性质，一一列举出该问题所有可能的情况，并根据题目的条件逐个作出判断，从中挑选出符合条件的解答。
枚举算法属于搜索策略，适用于那些解变量确定的连续值域的问题。设置枚举算法要列举出所有可能的情况，不能遗漏，也不能重复。
（二）解析算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
解析算法的基本思想是用解析的方法找出表示问题的前提条件与所求结果之间关系的数学表达式，并通过数学表达式的计算来实现问题的求解。
（三）排序算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．冒泡排序
冒泡排序的基本思想是在待排序的数据中，先找到最小（大）的数据将它放到最前面，再从第二个数据开始，找到第二小（大）的数据将它放到第二个位置，以此类推，直到只剩下最后一个数据为止。
2．选择排序
选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。（四）查找算法及程序实现考试要求：对所列知识要理解其确切含义及与其它知识的联系，能够用所学的信息技术知识和操作方法解决实际问题，熟练应用信息技术进行信息的处理。
1．顺序查找
顺序查找的基本思想是从第一个数据开始，按数据的顺序逐个将数据与给定的值进行比较，若某个数据和给定值相等，则查找成功，找到所查数据的位置；反之，查找不成功。
2．对分查找
对分查找的基本思想是在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，使查找成功，或直到子表不存在，查找不成功。
对分查找的条件是被查找的数据必须是有序的。
（五）递归算法
考试要求：对所列知识要知道其内容及含义，并能用自己的语言或动作进行表达、判断和直接运用。
函数或过程调用它本身，称为递归。递归算法的基本思想是把规模较大的、较难解决的问题变成规模较小的、容易解决的同一问题，规模较小的问题又变成规模更小的问题，当问题小到一定程度时，可以直接得出它的解，从而得到原来问题的解。即采用“大事化小、小事化了”的基本思想。
采用递归算法的条件：（1）每一步骤解决问题的方法要一致；（2）有边界条件。
二、例题分析
1．有5位运动员100米成绩依次为13.8，12.5，13.0，13.2，13.4，
若采用选择排序算法对其进行从小到大排序，则第二趟的排序结果是
(A) 12.5 13.8 13.2 13.4 13.0 (B) 12.5 13.4 13.2 13.8 13.0
(C) 12.5 13.0 13.8 13.2 13.4 (D) 12.5 13.2 13.8 13.4 13.0
参考答案：C 所考知识点：选择排序
选择排序的基本思想是在所有的记录中选出最小（大）的数据，把它与第一个数据交换，然后在其余的记录中再选出最小（大）的数据与第二个数据交换，依此类推，直至所有数据排序完成。此题中要从小到大排序，并且已经实现第一趟排序，故在后面4个数据当中找出最小的数据“13.0”与第2个数据“13.8”交换，所以结果选C
2．数列1，4，7，10，13，……的递推公式为( )。
(A) f(1)=1;f(n)=n+3 (B) f(1)=1;f(n)=n*2-1
(C) f(1)=1;f(n)=n*2+1 (D) f(1)=1;f(n)=f(n-1)+3
参考答案：D 所考知识点：递归算法
由数列可推出规律，从第二项开始，每一项跟前一项的差为3，故得出递推公式
3．用选择排序法对数据7，6，3，9，2从大到小排序，共需经过多少次数据对调。
(A) 3 (B) 4 (C) 5 (D) 10
参考答案：A 所考知识点：选择排序
此题只能根据选择排序的思路，共需进行四趟比较，具体过程如下：
4．要从n个数据元素中顺序查找一个元素，最多查找次数是
(A) 1 (B) n (C) n/2 (D) lgn
参考答案：B 所考知识点：顺序查找
此题稍简单，只要稍理解顺序查找的概念，就能选择答案
5．对分查找算法的前提是
(A)被查找数据元素个数是奇数(B)被查找数据元素个数是偶数
(C)被查找数据元素是有序的(D)被查找数据元素是无序的
参考答案：C 所考知识点：对分查找的概念
此题稍简单，只要稍理解对分查找的概念，就能选择答案
6．用对分查找法从数列3，6，7，10，12，16，25，30，75中找到数据10的最少查找次数是
(A) 2 (B) 3 (C) 4 (D) 7
参考答案：B 所考知识点：对分查找
用对分查找的方法需分别对上列数据进行编号，共9个数，依次序号为1~9。按照对分查找的思路，依次查找的数据为12、6、10，所以查找次数为3次。
强化练习（综合题）
1．有如下Visual Basic程序段：
a="How"
b=" are you"
c=a+b
该程序段运行后，变量c的值是
参考答案：How are you
本题是读程序写结果题，属于基础题，是主要是考核字符串数据类型中“+”（字符串连接）含义的理解
2．有如下程序段：
x=3
y=4
z=5
If x+y<=z Or y+z<=x Or x+z<=y then a="False" Else a="True"
该程序段运行后，a的值是
参考答案： "True"
本题是读程序写结果题，属于基础题，主要是考核分支If语句以及逻辑类运算符“or”的理解3．有如下VB程序段：
Dim n As Integer
Dim m As Integer
m = 0
For n = 1 To 15
m = m + n mod 5
Next n
该程序段运行后，变量m的值是
参考答案：30
本题是基础题本题是读程序写结果题，属于基础题，主要是考核循环For语句以及运算符“Mod”的理解
4．有如下VB程序段：n=3 s=3;n=6 s=9;n=9 s=18;n=12 s=30;n=15 s=45;n=18 s= n = 0
s = 0
Do While n <=30
n = n+3
s = s + n
Loop
执行该程序段后，变量s的值是
参考答案：198
本题是读程序写结果题，属于基础题，主要是考核循环Do while语句的理解，尤其要注意循环的终止条件
5．下面程序用来计算：
Private Sub Command1_Click()
Dim x, y As Single
x = Val(Text1.Text)
If x>=0 (1) Then
If x >= 7 Then y = Sqr(x ) Else y = x ^ 2
Else
If x < -10 Then y = Abs(x) Else y = 3 x + 2(2)
End If
Text2.Text = Str(y)
End Sub
参考答案：(1) x>0 (2)y=3*x +2
本题是改错题，属于基础题，主要考核算术表达式以及分支结构的条件语句
6．下面程序的功能是：计算表达式2+4+6+…+2n的值，在文本框Text1中输入n的值，结果在文本框Text2中输出。则程序中划线处的语句应更正为（1）（2）
Private Sub Command1_Click()
Dim sum As Long, , i As Integer , n As Integer
sum = 0
n = Val(Text1.Text)
For I = 2 To 2 * n Step 2
sum = sum + 2 *i (1)
Next I
Text2.Text=Val (sum) (2)
End Sub
参考答案：(1)sum=sum+i (2) Text2.Text=Str (sum)
本题是改错题，属于基础题，只要是考核FOR语句的步长step的作用，以及Val函数和Str函数作用的区别
7．下面程序的功能是：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一（鸡雏三三买之）。百钱买百鸡，问鸡翁、母、雏各几何？则程序中划线处的语句应更正为（1）
（2）
Private Sub Form_Click()
Dim x, y, z As Integer
For x = 0 To 20
For y = 0 To 33
z = 100 - x - y
If 5 * x + 3 * y + z \ 3 = 100 or z Mod 3=0 (1) Then
Print x; y; z
End If
Next Z
Next x
End Sub
参考答案：(1) Next Y (2)5 * x + 3 * y + z \ 3 = 100 or z Mod 3=0
本题是改错题，属于基础题，只要是考核FOR语句的结构，以及逻辑类运算符“or”和“and”
的不同含义
8．下面程序的功能是：求的值，直至最后一项的值≤0.0001。则程序中划线
处的语句应更正为（1）（2）
Private Sub Form_Click()
N = 1: Sum = 0 (1)
Do
N = N + 2
Term = 1 / (N ^ 2)
Sum = Sum + Term
Loop Until term>=0.0001 (2)
Print "运算结果为："; Sum
Print "最后一项的值为："; Term
End Sub
参考答案：(1)sum=1 (2) term<=0.0001
本题是改错题，属于稍难题，只要是考核Do Until语句的理解，尤其注意在循环中累加器的初值设置以及循环终止条件，不要产生死循环。
9．完成程序中的空格，打印显示如图片所示的九九乘法表：
解决上述问题的Visual Basic程序如下，为了实现这一目标，在划线处，填入合适的语句或表达式是
（1）（2）
Private Sub Form_Load()
Form1.Show
For a = 1 To 9
For = 1 To (1)
Print a; "×"; b; "="; (2)
Next b
Next a
End Sub
参考答案：(1) 30-man-woman (2)s=500 或者500=s
本题是程序填空题，属于容易题，主要考核解析算法的程序实现。
10．下面是一个元旦文艺会演评分程序。10位评委，除去一个最高分和一个最低分，计算平均分（评满分为10分）。
解决上述问题的Visual Basic程序如下，为了实现这一目标，在划线处，填入合适的语句或表达式是
（1）（2）
Max=0:Min=10
For I=1 to 10
N=Val(InputBox("请输入分数"))
If (1) Then Max=N
If N < Min Then Min = N
S=S+N
Next I
(2)
P=S/8
Print "最高分";Max;"最低分";Min;"最后得分";P
参考答案：(1) N>Max (2) S=S-Max-Min
本题是程序填空题，属于容易题，主要考核解析算法的程序实现。
11.有30个人，其中有男人、女人和小孩。他们在一家饭馆里花去500元。已知，每个男人花30元，每个女人花20元，每个小孩花10元。问男人、女人、小孩各为多少人？解决上述问题的Visual Basic程序如下，为了实现这一目标，在划线处，填入合适的语句或表达式是
（1）（2）
Sub command1_click()
Dim man, woman, child, s As Integer
For man = 1 To 15
For woman = 1 To 23
child = (1)
s = 30 * man + 20 * woman + 10 * child
If (2) Then
list1.AddItem Str(man) + Str(woman) + Str(child)
End If
Next woman
Next man
End Sub
参考答案：(1) 30-man-woman (2)s=500 或者500=s
本题是程序填空题，属于稍难题，主要考核枚举算法的程序实现。
12. 如果一个三位数等于它的每个数字的立方和，则此数称为“水仙花”数。如：
153＝1３＋5３＋3３故153是水仙花数。下面程序用于求出100～999之间的全部水仙花数解决上述问题的Visual Basic程序如下，为了实现这一目标，在划线处，填入合适的语句或表达式是（1）（2）
sub command1_click()
for m=100 to 999
a=int(m/100)
b=int((m-100*a)/10)
c=m-100*a-10*b
n=
if then list1.additem str(m)
next m
end sub
参考答案：（1） a*a*a+b*b*b+c*c*c （2） m=n
本题是程序填空题，属于稍难题，主要考核枚举算法的程序实现。
13．如下程序段的功能是：随机产生8个1-100之间的正整数，按升序将10个数据排序输出。
为了实现这一目标，在划线处，填入合适的语句或表达式是
（1）
（2）
（3）
Const n=8
Dim a(1 to n) As Integer
Dim I , j , t , k as integer
For i = 1 To n
（1）
Next i
For i = 1 To n-1
For j =（2）To n
If （3）Then
t = d(i): d(i) = d(k): d(k) = t
End If
Next j
Next I
参考答案：(1) a(i) = Int(100 * Rnd + 1)或a(I) = Int(100 * Rnd() + 1)
(2)I+1
(3)a(i) > a(j)或a(i) > = a(j)
本题是程序填空题，属于稍难题，主要考核冒泡排序的程序实现，同时也考核函数Rnd和Int 的正确使用。
14．下列程序的功能是：在一个有序的序列中查找数值50，同时统计查找的次数并显示查找次数。
为了实现这一目标，在划线处，填入合适的语句或表达式是
（1）
（2）
（3）
Dim a(1 to 8) As Integer（定义在通用里，数组元素通过另一事件产生）
Private Sub Command1_Click()
Dim m As Integer, I As Integer, j As Integer, x As Integer, total As Integer
Dim f As Boolean
f = False: x = 30: i = 1: j = 8: total = 0
Do While （1）And (f = False)
total = total + 1
m = （2）)
If a(m) = x hen
f = True
Else
If x < a(m) Then
j = m - 1
Else
i = m + 1
End If
End If
Loop
If f = True Then
Label1.Caption = （3）
Else
Label1.Caption = "找不到该数值"
End If
End Sub
参考答案：(1) i<=j
(2)Fix(I+j)/2+1
(3)a(i) > a(j)或a(i) > = a(j)
本题是程序填空题，属于稍难题，主要考核对分查找的程序实现。
15．下列程序的功能是：某班级45名学生，每位学生中文姓名均不相同，并且都有一个英文名。下面程序的功能是根据学生的中文姓名查找相应的英文名，其中学号存储在数组sno中，英文名存储在数组sname中，中文姓名存储在数组ch中。在文本框text1中输入要查找的中文姓名，单击"开始查找"按钮，如果查找成功，则在文本框Text2中输出该学生的学号、中文姓名和英文名，否则在文本框Text2中输出"查无此人！"。
为了实现这一目标，在划线处，填入合适的语句或表达式是
（1）
（2）
（3）
Private Sub Command1_Click()
Dim key As String, i As Integer
Dim n As Integer, found As Boolean
found = False
n = 0 : i = 1
(1)
Do While i <= 45 And Not found
If ch(i) = key Then n = i: (2)
i = i + 1
Loop
If (3) Then
Text2.Text = "查无此人！"
Else
Text2.Text = Str(sno(n)) + "号:" + ch(n) + "的英文名是" + sname(n)
End If
End Sub
参考答案：(1) key=text1.text
(2)found=true
(3)not found
本题是程序填空题，属于稍难题，主要考核顺序查找的程序实现。
16．下列程序的功能是：求两个正整数的最大公约数。求两个正整数的最大公约数可以采用辗转相除法求解。在文本框text1、text2中获取两个数据m、n，将结果显示在文本框text3上。
以下是辗转相除法的算法：分别用m , n , r表示被除数、除数、余数
①求m/n的余数
②若r=0。则n为最大公约数。若r<>0，执行第3步
③将n的值放在m中，将r的值放在n中。
④返回重新执行第①步
为了实现这一目标，在划线处，填入合适的语句或表达式是
（1）
（2）
（3）
Private Sub Command1_Click()
Dim m , n , i As Integer
m=Val(text1.text)
n=Val(text2.text)
(1)
Do While r<>0
m=n
(2)
r=m mod n
Loop
Text3.text= (3)
End Sub
参考答案：(1) r=m mod n
(2)n=r
(3)str(r)
本题是程序填空题，属于稍难题，主要考核实现给出算法的相关程序的能力。
17．已知四位数3025有一个特殊的性质：她的前两位数字30和后两位数字25的和是55，而55的平方和刚好等于该数（552=3025）。下面程序求具有这种性质的所有四位数。
其中，上述界面中“开始处理”按钮的名称是“Command1”，布尔型函数special(x)作用判断x 是否具有这种性质的四位数，若x是具有这种性质的四位数，其值为True，否则为False。
请在下列程序代码的基础上按照要求设计该程序。
Dim n As Integer, a As Integer
Function special(x as integer) As Boolean
End Function
Private Sub Command1_Click()
For a = 1000 To 9999
If special(a) Then List1.AddItem (Str(a))
Next a
End Sub
操作要求：
（1）完善程序中的Function special (x)部分
(2)在子程序Private Sub Command1_Click()中，主要采用的算法是：__________。
参考答案：(1) Dim a, b As Integer
a = x Mod 100
b = x \ 100
a = a + b
If a ^ 2 = x Then special = True Else specail = flase
(2)枚举
本题是补充一段程序，属于难题，主要考核自定义函数的能力。
18．下面程序求2到1000之间的平方数对，在文本框text1中输入的自然数N，找出所有小于N且
满足下述条件的数对（X，Y）：X+Y和X-Y都是完全平方数。例如：当X=10，Y=6时，有10+6=16=42 10-6 =4=22
其中，上述界面中“开始处理”按钮的名称是
“Command1”，布尔型函数numbert(x,y)作用判断x,y是否
为平方数对，若x,y是平方数对，其值为True，否则为False。
请在下列程序代码的基础上按照要求设计该程序。
Dim n As Integer, x, y As Integer
Function number(x, y As Integer) As Boolean
End Function
Private Sub Command1_Click()
For x = 2 To 1000
For y = x + 1 To 1000
If number(x, y) Then List1.AddItem (Str(x) + "与" +
Str(y))
Next y
Next x
End Sub
操作要求：
（1）完善程序中的Function number(x,y)部分
（2）在子程序Private Sub Command1_Click()中，主要采用的算法是：__________。
参考答案：（1）Dim a, b As Integer
a = x + y
b = y - x
If Sqr(a) = Int(Sqr(a)) And Sqr(b) = Int(Sqr(b)) Then number = True Else number = False
（2）枚举
本题是补充一段程序，属于难题，主要考核自定义函数的能力。
19．下面程序求2到1000之间的亲密数对，找出所有小于1000且满足下述条件的数对（A，B）：如果A的约数之和等于B，B的约数之和等于A，A和B
称为亲密数对。如220的所有约数（即能被它整除）为：
1、2、4、5、10、11、20、22、44、55、110，而
1+2+4+5+10+11+20+22+44+55+110=284；284的所有
约数为：1、2、4、71、142，而1+2+4+71+142=220。所
以220和284就是亲密数对
其中，上述界面中“开始处理”按钮的名称是
“Command1”，布尔型函数numbert(x,y)作用判断x,y是
否为亲密数对，若x,y是亲密数对，其值为True，否则为
False。
请在下列程序代码的基础上按照要求设计该程序。
Dim n As Integer, x, y As Integer
Function number(x, y As Integer) As Boolean
End Function
Private Sub Command1_Click()
For x = 2 To 1000
For y = x + 1 To 1000
If number(x, y) Then List1.AddItem (Str(x) + "" + Str(y))
Next y
Next x
End Sub操作要求：
（1）完善程序中的Function numbertwo(x,y)部分
（2）在子程序Private Sub Command1_Click()中，主要采用的算法是：__________。
参考答案：（1）Dim a, b, i As Integer
a = 1:
b = 1
For i = 2 To x \ 2
If x Mod i = 0 Then a = a + i
Next i
For i = 2 To y \ 2
If y Mod i = 0 Then b = b + i
Next i
If a = y And b = x Then number = True Else number = False
（2）枚举
本题是补充一段程序，属于难题，主要考核自定义函数的能力。
20．数学黑洞数6174。已知：一个任意的四位正整数（四位数字完全相同的除外）。将数字重新组合成一个最大的数和最小的数相减，重复这个过程，最多七步，必得6174。即7614-1467=6174。从文本框text1中输入一个任意的数字不完全相同的四位正整数，在文本框text2中输出掉进黑洞的步数。
Private Sub Command1_Click()
Dim a(1 To 4) As Integer
Dim x, y, i, j As Integer
x = Val(Text1.Text)
st = 0
Do While x <> 6174
For i = 1 To 4
a(i) = x Mod 10
x = x \ 10
Next i
x = a(1) * 1000 + a(2) * 100 + a(3) * 10 + a(4)
y = a(1) + a(2) * 10 + a(3) * 100 + a(4) * 1000
x = x - y
st = st + 1
Loop
高中信息技术《算法与程序设计》试题
高中信息技术《算法与程序设计》试题 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C
《计算机算法设计与分析》习题及答案
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
算法分析与设计试卷
《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。
算法设计与分析考试题及答案
算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】
一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj
《算法与程序设计》试题带答案
《算法与程序设计》试题 学校：_____________ 班级：____________ 学号：____________ 姓名：____________ 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C
算法设计与分析试卷A及答案
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 ---------------------------------------------------------
参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x =
算法设计与分析考试题及答案
1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。
算法与程序设计试题带答案
高一第二学期《算法与程序设计》学分认定试题 学校：_____________ 班级：____________ 学号：____________ 姓名：____________ 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么”，然后再确定程序“如何做”请问“如何做”是属于用计算机解决问题的哪一个步骤（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、 D、 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式A+B+C
算法设计与分析考试题及答案
算法设计与分析考试题及 答案 It was last revised on January 2, 2021
一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算， 此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多 个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些 子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造 最优解； 2.流水作业调度问题的johnson算法的思想。 ①令N 1={i|a i =b i }；②将N 1 中作业按a i 的非减序排序得到N 1 ’，将N 2 中作业按b i 的非增序排序得到N 2’；③N 1 ’中作业接N 2 ’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i 和b i ，且 (a 1,a 2 ,a 3 ,a 4 )=(4,5,12,10)，(b 1 ,b 2 ,b 3 ,b 4 )=(8,2,15,9)求4个作业的最优调度方案，并计算最优 值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2 ’={4，2}； 最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0）
5.《算法设计与分析》试题库
《算法分析与设计》试题库 （一） 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上，并 D.动态规划算法
3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质
D.预排序与递归调用 4. 算法分析中，记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有：(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题，一般具有的重要性质为：(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中，按(D)策略，从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先
算法设计与分析试卷(2010)
内部资料，转载请注明出处，谢谢合作。 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T
2014山东省信息技术学考算法与程序设计试题答案附后讲解
2014山东省信息技术学考算法与程序设计试题答案附后讲解
山东省学考算法与程序设计试题 选择题 1、下列VB表达式中： ⑴Sqr(x) ⑵Text1.text ⑶Command1.caption ⑷"45"+"34" ⑸45+34值为字符串类型的是（） A⑴⑵⑶ B⑵⑶⑷ C ⑴⑶⑸ D⑵⑷⑸ 2、如果给出三条线段的长分别为a、b、c，且已知a≤b≤c，要问这三条线段能否构成三角形，仅需下列选项中的哪个判定条件即可？（） A 其他选项都不对 B a+c>b C a+b>c D b+c>a 3、VB程序中“Dim n As Integer”这条语句的作用是（） A 定义一个事件过程 B 定义一个数据输入方法 C 定义一个变量 D 定义一个数据处理方法 4、关于算法的描述，下列选项中正确的是（） A 算法的每一步骤必须有确切的含义 B 算法必须有输入 C 算法的步骤可以是无穷的 D 算法本身就是一种程序设计语言 5、关于算法的描述，正确的是（） A同一种算法只能用一种程序语言实现 B算法就是数值计算的方法 C描述算法的方法只有流程图 D算法是描述解决问题的方法和步骤 6、算法的描述方法有多种，下列选项中不适合描述算法的是（） A机器语言 B自然语言 C流程图 D伪代码 7、长度分别为a、b、c的三条线段，能够组成三角形的条件是（） A a+b>c Or a+c>b Or b+c>a B a+b>c or a+c>b And b+c>a C a+b>c Or a+c>b And b+c>a D a+b>c And a+c>b And b+c>a 8、已知海伦公式：()()() p p a p b p c ---p=1 2 （a+b+c），a、b、c分别为三角形的三条 边长。利用海伦公式求三角形面积的算法属于（） A 排序法 B 解析法 C 穷举法 D 查找法 9、以下程序段中循环体执行的次数是（） s=0 i=0 Do While s<10 i=i+1 s=s+i*i Loop A 1 B 3 C 2 D 4 10、下列VB表达式中，能正确表达不等式方程|x|>1的解的是（） A x>-1 and x<1 B x>-1 or x<1 C x<-1 and x>1 D x<-1 or x>1 11、一元二次方程ax2+bx+c=0(a≠0)的两个实数根分别为： x 1 24 b b ac -+- 2 24 b b ac ---下列表达式正确的是（） A x 2=-b-sqr(b^2-4*a*c)/(2*a) B x 1 =(-b+sqr(b^2-4ac))/(2*a)
算法设计与分析试卷及答案
湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:1２０分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分，共计30 分) １、用O、Ω与θ表示函数f与g之间得关系＿__________＿__＿_＿_＿＿_＿__＿___＿＿。 2、算法得时间复杂性为,则算法得时间复杂性得阶为_＿__＿＿____＿_＿_＿____＿＿_＿__＿。 3、快速排序算法得性能取决于_＿_____＿_______＿__＿__＿_＿___＿__。 4、算法就是__＿_＿______＿＿_＿＿__＿________＿___＿___＿___＿___＿_＿_＿_＿＿_＿__。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是＿_______＿__＿____________＿。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是__＿_＿情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越__＿________,结果就越有价值。。 8、_＿_＿__＿_＿____＿________＿_____就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指_＿____________＿______＿_＿__＿__＿______＿________________＿__＿_____＿____＿____＿_＿______＿__＿__＿___＿_＿__＿___＿_＿＿＿________＿__。 1０、回溯法在问题得解空间树中,按______＿＿＿_＿__＿策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计3０分) １、试述回溯法得基本思想及用回溯法解题得步骤。 2、有８个作业{１,２,…,8}要在由2台机器M1与Ｍ２组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M１与M2加工作业ｉ所需得时间分别为: M１10 2 8 12 6 ９４14
最新高中信息技术《算法与程序设计》试题精品版
2020年高中信息技术《算法与程序设计》 试题精品版
新课标高中信息技术《算法与程序设计》试题一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（ ） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C
算法分析与设计复习题及答案
算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do
计算机算法设计与分析期末考试复习题
1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。
算法与程序设计试题
算法与程序设计试题 一、选择题（每题两分，共１４分每题2分） １、要进行元旦晚会比赛，学校请你设计一个能够对元旦晚会节目分数自动排序的软件，你接到任务后，准备开始设计此软件，比较好的方法和步骤是（） Ａ、设计算法，编写程序，提出问题，调试程序 Ｂ、分析问题，编写程序，设计算法，调试程序 Ｃ、分析问题，设计算法，编写程序，调试程序 Ｄ、设计算法，提出问题，编写程序，调试程序 2、数值型数据包括两种。 A、整型和长整型 B、整型和浮点型 C、单精度型和双精度型 D、整型、实型和货币型 3、具有输出数据功能的控件是：（） Ａ、窗体控件和标签控件 Ｂ、复选框控件和文本框控件 Ｃ、标签控件和文本框控件 Ｄ、选项框按钮控件和复选框控件 4、要使循环体至少执行一次，应使用循环。 ５、下列程序段是计算公式的： s=0;t=1 for I =1 to 10 t:=t*I s:=s+t Next I A、s=1+2+3＋......１０Ｂ、s=1*2*3* (10) C、s=1!+2!+3! ......10! D、s=1+2*3+3*4+4*5+......９*10 6、在窗体（Name属性为Formal）上画两个文本框（其Name属性分别为Text1和Text2）和一个命令按钮（Name属性为Command1），然后编写如下两个事件过程： Private Sub Command1_Click() A = Text１Text + Text2.Text Print a End Sub Private Sub Formal_Load() Text1.Text = " " Text2.Text = " " End Sub 程序运行后，在第一个文本框（Text1）和第二个文本框（Text2）中分别输入123和321，然后单击命令按钮，则输出结果为（）。 A、444 B、321123 C、123321 D、132231 ７、使用函数与过程是为了。 A、使程序模块化Ｂ、使程序易于阅读
计算机算法设计与分析习题及答案
计算机算法设计与分析习 题及答案 Prepared on 24 November 2020
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先
10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。