算法分析与设计20春在线作业1【东北师范大学答案51037】

东北师范大学
在线作业
参考答案
试读一页
Java程序设计20春在线作业1-0002
试卷总分:100
一、单选题 (共 10 道试题,共 30 分)
1.下列说法中错误的一项是（）。

A.Java语言提供了检测与避免死锁的机制
B.在Java语言中，要避免死锁，只能通过程序进行控制
C.释放锁的时候，应该按照死锁顺序的逆序进行
D.在编写程序的时候，可以对所有共享数据设汁一个统一的加锁顺序正确答案:A
2.在编写Java Applet程序时，需要在程序的开头写上( )语句。

A.import java.awt.* ;
B.import java.applet.* ;
C.import java.io.* ;
D.import java.awt.event.* ;
正确答案:B
3.以下哪项可能包含菜单条（）。

算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。

2.程序：程序是算法⽤某种程序设计语⾔的具体实现。

⼆、简答题：1.算法需要满⾜哪些性质？简述之。

答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。

（2）输出：算法产⽣⾄少⼀个量作为输出。

（3）确定性：组成算法的每条指令清晰、⽆歧义。

（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。

2.简要分析分治法能解决的问题具有的特征。

答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。

3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。

答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。

该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。

（2）⽤递推来实现递归函数。

（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。

后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。

三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。

答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。

（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。

A.错误
B.正确
【答案】A
139. strcmp（）函数用来（）。
A.求字符串长度
B.比较字符
C.求子串
D.字符串拷贝
【答案】B
140.对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。
A.错误
B.正确
【答案】A
141.采用简单选择排序，比较次数与移动次数分别为()。
A. O(n),O(logn)
A.对象
B.符号
C.标识符
D.命名规则
【答案】C
12.一个算法的评价主要从时间复杂度和()来考虑。
A.空间复杂度
B.算法有效性
C.算法有穷性
D.算法可读性
【答案】A
13. ()是一个开放源代码的、基于Java的可扩展开发平台。
A. VS
B. Dev-C++
C. Eclipse
D. JDK
【答案】C
14.十六进制的213，1的位权是（）。
A. 8,9,7,4,1,2
B. 1,9,7,4,8,2
C. 8,7,4,1,2,9
D. 1,2,8,9,7,4
【答案】B
131.字符数组通过（）来引用其中的某个元素。
A.数组名
B.下标
C.数组名和下标
D.字符串名
【答案】C
132.统计字符串长度时包括字符串结束标志。
A.错误
B.正确
【答案】A
133.字符数组要求其最后一个元素是‘\0’。
A.错误
B.正确
【答案】B
136.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。
A.选择排序法
B.插入排序法

【奥鹏】-[东北师范大学]数据结构20春在线作业1试卷总分:100 得分:100第1题,数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( )A、线性表B、广义表C、树形结构D、图结构正确答案:A第2题,插入、删除只能在同一端进行的线性表，称为 ( )。

A、队列B、循环队列C、栈D、循环栈正确答案:C第3题,任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。

A、不发生改变B、发生改变C、稍有改变D、不能确定正确答案:A第4题,在k叉树中，度为0的结点称为 ( )。

A、根B、叶C、祖先D、子孙正确答案:B第5题,在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。

A、直接插入排序B、冒泡排序C、快速排序D、直接选择排序正确答案:D第6题,下面哪些方法可以判断出一个有向图是否有环（回路）? ()A、广(宽)度优先遍历B、拓扑排序C、求最短路径D、求关键路径正确答案:B第7题,串是一种特殊的线性表，其特殊性体现在 ( )。

A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符正确答案:B第8题,head指向的带表头结点的单链表为空的判定条件是 ( )。

A、head = = NULLB、head-next = = headC、head ! = NULLD、head-next = = NULL正确答案:D第9题,二叉树在线索化后，仍不能有效求解的问题是 ( )。

A、前序线索二叉树中求前序后继B、中序线索二叉树中求中序前驱C、中序线索二叉树中求中序后继D、后序线索二叉树中求后序后继正确答案:D第10题,算法分析的两个主要方面是 ( )。

A、正确性与健壮性B、可读性与可用性C、时间复杂度与空间复杂度D、数据复杂性与程序复杂性正确答案:C第11题,下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。

【奥鹏】-[东北师范大学]算法分析与设计20春在线作业1试卷总分:100 得分:100第1题,按F5开始调试，程序便会直接运行到断点处。

接下来可以逐行来运行程序，查看各个变量的值，也可以直接运行到下一个断点或程序结束，这样过程被称作()。

A、设置断点B、单步调试C、程序编译D、程序调试正确答案:B第2题,()主要是用来显示当前目录的名称或更改当前的目录。

A、dirB、cdC、typeD、fc正确答案:B第3题,输出一个字符串时使用（）格式符。

A、%cB、%sC、%dD、%e正确答案:B第4题,动态规划是一种在数学和计算机科学中使用的，用于求解包含()的最优化问题的方法。

A、重叠子问题B、相似子问题C、互斥子问题D、有序子问题正确答案:A第5题,如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为()。

A、编写程序B、调试程序C、执行程序D、编译程序正确答案:B第6题,对于循环队列，下列叙述中正确的是（）A、队头指针是固定不变的B、队头指针一定大于队尾指针C、队头指针一定小于队尾指针D、队头指针可以大于队尾指针，也可以小于队尾指针正确答案:D第7题,下列对队列的叙述正确的是（）。

A、队列属于非线性表B、队列按“先进后出”原则组织数据C、队列在队尾删除数据D、队列按“先进先出”原则组织数据正确答案:D第8题,以C语言为例，下列四个选项中，均是不合法的用户标识符的是()。

A、BA、x_0、doB、float、1a0、_YC、x-y、goto、123D、_123、tmp、CHAR正确答案:C第9题,()命令用来显示ASCII码文件的内容。

A、dirB、cdC、typeD、fc正确答案:C第10题,下列排序算法中，其中()是稳定的。

A、堆排序，冒泡排序B、快速排序，堆排序C、直接选择排序，归并排序D、归并排序，冒泡排序正确答案:D第11题,strlen(str)是用来（）。

A、求字符串长度B、比较字符C、求子串D、字符串拷贝正确答案:A第12题,批处理，也称为批处理脚本，其文件扩展名为()。

C程序设计19春在线作业1-0003试卷总分:100 得分:100一、单选题(共20 道试题,共60 分)1.以下的for 循环for(x=0,y=0;(y!=123)&&(x<4);x++) ; （）A.执行3 次B.执行4 次C.循环次数不定D.是无限循环答案:B2.以下不属于算法基本特征的是（）A.有穷性B.有效性C.可靠性D.有一个或多个输出答案:C3.以下程序：main( ) { char s1[40]="country",s2[20]="side"; int i=0,j=0; while(s1[i]!='\0') i++; while(s2[j]!='\0') s1[i++]=s2[j++]; s1[i]=0; printf("%s\n",s1); } 的输出结果为（）A.sideB.countryC.sidetryD.countryside答案:D4.要把高级语言编写的源程序转换为目标程序,需要使用（）A.编辑程序B.驱动程序C.诊断程序D.编译程序答案:D5.当把以下四个表达式用作if语句的控制表达式时，有一个选项与其它三个选项含义不同，这个选项是（）A.k%2B.k%2==1C.(k%2)!=0D.!k%2==1答案:D6.下面的选项中正确的赋值语句是（char a[5],*p=a;）（）A.p=“abcd”;B.a=“abcd”;C.*p=“abcd”;D.*a=“abcd”;答案:A7.设a为整型变量,初值为12,执行完语句a+=a-=a*a后,a的值是（）A.552B.144C.264D.-264答案:D8.能正确表示a≥10或a≤0的关系表达式是（）A.a>=10 or a<=0B.a>=10│a<=0C.a>=10||a<=0D.a>=10&&a<=0答案:C9.下列不能实现赋值操作的是（）A.a++B.a== bC.a+=bD.a=1答案:B10.有以下程序段: int m=0,n=0; char c=‘a’; scanf("%d%c%d",&m,&c,&n); printf("%d,%c,%d\n",m,c,n); 若从键盘上输入：10A10<回车>，则输出结果是（）A.10,A,10B.10,a,10C.10,a,0D.10,A,0答案:A11.当说明一个结构体变量时，系统分配它的内存是（）A.各成员所需内存容量的总和B.结构体中第一个成员所需内存C.各成员所需内存容量的最大值D.结构体中最后一个成员所需内存答案:A12.设有以下宏定义：#define H 30 #define LEN H+20 则执行赋值语句v=LEN*10;后，v的值是（）A.60B.230C.500。

东北师范大学
在线作业
参考答案
试读一页
C 程序设计20春在线作业1-0005
试卷总分:100
一、单选题 (共 20 道试题,共 60 分)
1.已知：类A中一个成员函数说明如下：void Set(A&a);其中，A&的含义是()。

A.指向类A的指针为a
B.将a的地址值赋给变量Set
C.a是类A对象的引用，用来作函数Set()的参数
D.变量A与a按位与作为函数Set( )的参数
正确答案:C
2.下面关于运算符重载的描述错误的是()。

A.重载不能改变操作数的个数、运算符的优先级、运算符的结合性和运算符的语法结构
B.不是所有的运算符都可以进行重载
C.运算符函数的调用必须使用关键字operator
D.在C++语言中不可通过运算符重载创造出新的运算符
正确答案:C
3.在函数定义前加上关键字"inline"，表示该函数被定义为()。

C栈
D循环栈
【答案】：C栈|
3.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序( )。
【选项】：
A不发生改变
B发生改变
C稍有改变
D不能确定
【答案】：A
4.在k叉树中，度为0的结点称为( )。
【选项】：
A根
B叶
C祖先
D子孙
【答案】：B叶|
5.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关()。
【选项】：
A空或只有一个结点
B高度等于其结点数
C任一结点无左子女
D任一结点无右子女
【答案】：B
14. n个结点的线索二叉树上含有的线索数为( )。
【选项】：
A n-1
B n
C n +1
D 2n
【答案】：C
15.广义表(( a , b , c , d ) )的表头是()。
【选项】：
A a
B ( )
C ( a , b , c , d )
东北师范大学
东师远程教育
数据结构20春在线作业1
参考答案
试读一页
数据结构20春在线作业1
1个后继，该数据结构是( )
【选项】：
A线性表
B广义表
C树形结构
D图结构
【答案】：A线性表|
2.插入、删除只能在同一端进行的线性表，称为( )。
【选项】：
A队列
B循环队列
C可以链接存储
D数据元素可以是多个字符
【答案】：B
8. head指向的带表头结点的单链表为空的判定条件是( )。
【选项】：
A head = = NULL
B head-&gt;next = = head

(单选题)1: 图中有关路径的定义是（）。

A: 由顶点和相邻顶点序偶构成的边所形成的序列
B: 由不同顶点所形成的序列
C: 由不同边所形成的序列
D: 上述定义都不是
正确答案: A
(单选题)2: ()是一个基本完整的开发工具集，它包括了整个软件生命周期中所需要的大部分工具，如UML工具、代码管控工具、集成开发环境等等。

A: VS
B: VM
C: Dev-C++
D: IDE
正确答案: A
(单选题)3: 下列数据结构中，属于非线性结构的是（）。

A: 循环队列
B: 带链队列
C: 二叉树
D: 带链栈
正确答案: C
(单选题)4: 下列叙述中正确的是（）。

A: 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
B: 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
C: 顺序存储结构能存储有序表，链式存储结构不能存储有序表
D: 链式存储结构比顺序存储结构节省存储空间
正确答案: A
(单选题)5: 十六进制中最大的数码是（）。

A: 16
B: 15
C: F
D: E
正确答案: C
(单选题)6: 二进制，就表示某一位置上的数运算时是逢（）进一位。

A: 2
B: 8
C: 9
D: 10
正确答案: A
(单选题)7: 在程序代码编辑框外（一般都是程序代码的最左侧）双击，就成功设置了一个断。

(单选题)1: 下列叙述中正确的是（）
A: 在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B: 在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C: 在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D: 上述三种说法都不对
正确答案: C
(单选题)2: 十进制算术表达式：3*512+7*64＋4*8＋5的运算结果，用二进制表示为（）。

A: 10111100101
B: 11111100101
C: 11110100101
D: 11111101101
正确答案: B
(单选题)3: 十进制数2014等值于八进制数（）。

A: 4028
B: 3736
C: 2726
D: 2014
正确答案: B
(单选题)4: 下面命名规则中，哪项不是现在比较常用的命名规则()。

A: 匈牙利命名法
B: 骆驼命名法
C: 下划线命名法
D: 图灵命名法
正确答案: D
(单选题)5: 下列叙述中正确的是（）。

A: 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B: 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C: 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D: 上述三种说法都不对
正确答案: B
(单选题)6: 在程序调试中，我们需要借助于()来中断程序的运行，查看变量的值。

A: 变量名
B: 断点
C: 设置断点函数
D: 程序段
正确答案: B
(单选题)7: 十六进制数C1B转换为二进制数是（）。

A: 1100101101011。

2020智慧树知到《算法分析与设计》章节测试完整答案智慧树知到《算法分析与设计》章节测试答案第一章1、给定一个实例，如果一个算法能得到正确解答，称这个算法解答了该问题。

答案: 错2、一个问题的同一实例可以有不同的表示形式答案: 对3、同一数学模型使用不同的数据结构会有不同的算法，有效性有很大差别。

答案: 对4、问题的两个要素是输入和实例。

答案: 错5、算法与程序的区别是()A:输入B:输出C:确定性D:有穷性答案: 有穷性6、解决问题的基本步骤是()。

(1)算法设计(2)算法实现(3)数学建模(4)算法分析(5)正确性证明A:(3)(1)(4)(5)(2)B:(3)(4)(1)(5)(2)C:(3)(1)(5)(4)(2)D:(1)(2)(3)(4)(5)答案: (3)(1)(5)(4)(2)7、下面说法关于算法与问题的说法错误的是()。

A:如果一个算法能应用于问题的任意实例，并保证得到正确解答，称这个算法解答了该问题。

B:算法是一种计算方法，对问题的每个实例计算都能得到正确答案。

C:同一问题可能有几种不同的算法，解题思路和解题速度也会显著不同。

D:证明算法不正确，需要证明对任意实例算法都不能正确处理。

答案: 证明算法不正确，需要证明对任意实例算法都不能正确处理。

8、下面关于程序和算法的说法正确的是()。

A:算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。

B:程序是算法用某种程序设计语言的具体实现。

C:程序总是在有穷步的运算后终止。

D:算法是一个过程，计算机每次求解是针对问题的一个实例求解。

答案: 算法的每一步骤必须要有确切的含义，必须是清楚的、无二义的。

,程序是算法用某种程序设计语言的具体实现。

,算法是一个过程，计算机每次求解是针对问题的一个实例求解。

9、最大独立集问题和()问题等价。

A: 最大团B:最小顶点覆盖C:区间调度问题D:稳定匹配问题答案: 最大团,最小顶点覆盖10、给定两张喜欢列表，稳定匹配问题的输出是( ) 。

《算法分析与设计》练习题一答案1.程序书写格式应该遵循哪四个原则？参考答案：（1）正确使用缩进：一定要有缩进，否则代码的层次不明显。

（2）在一行内只写一条语句。

（3）, '}'位置不可随意放置。

（4）变量和运算符之间最好加1个空格2.什么是算法？参考答案：用计算机解决问题的过程可以分成三个阶段：分析问题、设计算法和实现算法。

算法可以理解为冇基本运算及规定的运算顺序所构成的完整的解题步骤，它是求解问题类的、机械的、统一的方法，它由有限多个步骤组成，对于问题类屮每个给定的具体问题，机械地执行这些步骤就可以得到问题的解答。

或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

3.什么是线性结构？什么是非线性结构？参考答案：线性结构：数据逻辑结构屮的一类。

它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所冇结点都冇R只冇一个直接前趋和一个直接后继。

线性表就是一个典型的线性结构。

栈、队列、串等都是线性结构。

非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接而趋和直接后继。

数组、广义表、树和图等数据结构都是非线性结构。

4.已知二叉树后序遍丿力序列是DABEC,屮序遍丿力序列是DEBAC,则前序遍历序列是什么？参考答案：前序遍历序列是CEDBA5.什么是数制？参考答案：数制是人们利用符号进行计数的一种科学方法。

数制也称计数制，是用一组固定的符号和统一的规则來表示数值的方法。

6.如果将十进制数106转换为八进制数，结果是多少？参考答案：1527.请问查找算法的效率用什么进行度量？参考答案：平均查找长度ASL：在查找其关键字等于给定值的过程小，需要和给定值进行比较的关键字个数的期望值称为查找成功吋的平均查找长度。

AS厶=£皿/=1其屮，n是结点的个数；是杳找第i个结点的概率,是找到第i个结点所需要的比较次数。

算法分析与设计教程习题解答第1章 算法引论1. 解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。

频率计数是指计算机执行程序中的某一条语句的执行次数。

多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。

指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。

2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。

3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。

4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。

5. 解：①n=11； ②n=12； ③n=982； ④n=39。

第2章 递归算法与分治算法1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。

2． 解：通过分治算法的一般设计步骤进行说明。

3． 解：int fibonacci(int n) {if(n<=1) return 1;return fibonacci(n-1)+fibonacci(n-2); }4. 解：void hanoi(int n,int a,int b,int c) {if(n>0) {hanoi(n-1,a,c,b); move(a,b);hanoi(n-1,c,b,a); } } 5. 解：①22*2)(−−=n n f n② )log *()(n n n f O =6． 解：算法略。

《算法分析与设计》作业（一）本课程作业由两部分组成。

第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。

第二部分为“主观题部分”，由简答题和论述题组成，共15分。

作业总分30分，将作为平时成绩记入课程总成绩。

客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（ A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。

东师-C程序设计20春在线作业1-0003注：每科有多套试卷，请核实本套与您的试卷是否一致，本资料只做学习使用！！！一、单选题 (共 20 道试题,共 60 分)1.以下的 for 循环 for(x=0,y=0;(y!=123)&&(x<4);x++) ; （）[A]--执行 3 次[B]--执行 4 次[C]--循环次数不定[D]--是无限循环[提示]--请认真阅读以上题目，运用所学知识，并作出正确选择解析参考选择:B2.以下不属于算法基本特征的是（）[A]--有穷性[B]--有效性[C]--可靠性[D]--有一个或多个输出[提示]--请认真阅读以上题目，运用所学知识，并作出正确选择解析参考选择:C3.以下程序：main( ) { char s1[40]="country",s2[20]="side"; int i=0,j=0; while(s1[i]!='\0') i++; while(s2[j]!='\0') s1[i++]=s2[j++]; s1[i]=0; printf("%s\n",s1); } 的输出结果为（）[A]--side[B]--country[C]--sidetry[D]--countryside[提示]--请认真阅读以上题目，运用所学知识，并作出正确选择解析参考选择:D4.要把高级语言编写的源程序转换为目标程序,需要使用（）[A]--编辑程序[B]--驱动程序[C]--诊断程序[D]--编译程序[提示]--请认真阅读以上题目，运用所学知识，并作出正确选择解析参考选择:D5.当把以下四个表达式用作if语句的控制表达式时，有一个选项与其它三个选项含义不同，这个选项是（）[A]--k%2[B]--k%2==1。

《算法设计与分析》试卷1一、多项选择题（每空2分, 共20分）:1.以下关于算法设计问题的叙述中正确的是__________。

A.计算机与数值问题的求解——方程式求根、插值问题、数值积分、函数逼近等有关B.利用计算机无法解决非数值问题C.计算机在解决分类、语言翻译、图形识别、解决高等代数和组合分析等方面的数学问题、定理证明、公式推导乃至日常生活中各种过程的模拟等问题中, 主要进行的是判断、比较, 而不是算术运算D、算法设计与分析主要研究对象是非数值问题, 当然也包含某些数值问题2.算法的特征包括_________。

A.有穷性B、确定性C.输入和输出D.能行性或可行性3、以下描述是有关算法设计的基本步骤:①问题的陈述②算法分析③模型的拟制④算法的实现⑤算法的详细设计⑥文档的编制, 应与其它环节交织在一起其中正确的顺序是__________。

A.①②③④⑤⑥B.①③⑤②④⑥C.②④①③⑤⑥D.⑥①③⑤②④4.以下说法正确的是__________。

A.数学归纳法可以证明算法终止性B.良序原则是证明算法的正确性的有力工具C. x = 小于或等于x的最大整数（x的低限）D. x = 小于或等于x的最大整数（x的高限）5、汉诺塔（Hanoi）问题中令h（n）为从A移动n个金片到C上所用的次数, 则递归方程为__________, 其初始条件为__________, 将n个金片从A柱移到C柱上的移动次数是__________；设菲波那契（Fibonacci）数列中Fn为第n个月时兔子的对数, 则有递归方程为__________, 其中F1=F2=__________。

A.Fn=Fn-1+Fn-2 B、h（n）= 2h（n-1）+1C.1 D、h（1）= 1E、h（n）=2n-1F、06.在一个有向连通图中（如下图所示）, 找出点A到点B的一条最短路为____ ______。

A.最短路: 1→3→5→8→10, 耗费: 20B、最短路：1→4→6→9→10, 耗费：16C.最短路: 1→4→6→9, 耗费: 12D.最短路: 4→6→9→10, 耗费: 13二、填空（每空2分, 共20分）:1.快速排序法的基本思想是重新排列关键字, 把一个文件分成两个文件, 使得第一个文件中所有元素均小于第二个文件中的元素；然后再对两个子文件进行同样的处理。

单选题1.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是()。

A.快速排序B.堆排序C.归并排序D.直接插入排序答案: C2.十进制的123，1的位权是（）。

A.1B.2C.10D.100答案: D3.下列叙述中正确的是（）A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机在存储空间上是向量式的存储结构，因此，利用数组只能处理线性结构C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D.以上说法都不对答案: D4.按F5开始调试，程序便会直接运行到断点处。

接下来可以逐行来运行程序，查看各个变量的值，也可以直接运行到下一个断点或程序结束，这样过程被称作()。

A.设置断点B.单步调试C.程序编译D.程序调试答案: B5.注释从功能上可以分为文件注释、函数注释和()。

A.程序员注释B.功能注释C.时间注释D.版权注释答案: B6.()是用户在程序中使用的名字，它是一种用于命名一些具有特定含义的对象的符号，通常用来标识程序中的变量，常量，函数，语句块。

A.对象B.符号C.标识符D.命名规则答案: C7.一个算法的评价主要从时间复杂度和()来考虑。

A.空间复杂度B.算法有效性C.算法有穷性D.算法可读性答案: A8.()是一个开放源代码的、基于Java的可扩展开发平台。

A.VSB.Dev-C++C.EclipseD.JDK答案: C9.十六进制的213，1的位权是（）。

A.0B.1C.8D.16答案: D10.一般情况下，算法中基本操作重复执行的次数是()的某个函数。

A.问题类型B.问题难度C.问题结构D.问题规模答案: D11.下列叙述中正确的是（）A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D.循环队列中元素的个数是由队头指针和队尾指针共同决定答案: D12.二进制，就表示某一位置上的数运算时是逢（）进一位。