东师《算法分析与设计》2023年春学期在线作业2[答案][答案]

《算法分析与设计》2023年春学期在线作业2题目

正确答案:B

试卷总分:100  得分:100

一、单选题 (共 20 道试题,共 40 分)

1.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（C）。

A.39

B.52

C.111

D.119

正确答案:A

2.strlen(str)是用来（）。

A.求字符串长度

B.比较字符

C.求子串

D.字符串拷贝

正确答案:B

3.八进制中最大的数码是（）。

A.6

B.7

C.8

D.9

正确答案:C

4.字符串的结束标记是（）。

A.0'

B.' '

C.'\0'

D.' '

正确答案:B

5.下列叙述中正确的是（）

A.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化

B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化

C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化

D.上述三种说法都不对

正确答案:B

6.一般情况下，程序中所有注释的行数占到整个源程序的()比较适宜。

A.1/2到2/3

B.1/3

C.1/3到1/2

D.1/2

正确答案:B

7.一个递归算法必须包括()。

A.递归部分

B.终止条件和递归部分

C.循环部分

D.终止条件和循环部分

正确答案:B

8.十六进制数C1B转换为二进制数是（）。

A.1100101101011

B.110000011011

C.10110101010

D.11101001011

正确答案:B

9.采用简单选择排序，比较次数与移动次数分别为()。

A.O(n),O(logn)

B.O(logn),0(n*n)

C.0(n*n),0(n)

D.0(nlogn),0(n)

正确答案:D

10.十六进制数38A.11转换为十进制数是（）。

A.960.06

B.916.0364

C.906.0664

D.902.0563

正确答案:B

11.下列数据结构中，能用二分法进行查找的是()。

A.顺序存储的有序线性表

B.线性链表

C.二叉链表

D.有序线性链表

正确答案:B

12.例如“camelCase”和“printEmployeePaychecks()” 这样的命名规则是()。

正确答案:B

A.匈牙利命名法

B.骆驼命名法

C.下划线命名法

D.帕斯卡命名法

正确答案:A

13.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。

A.选择排序法

B.插入排序法

C.快速排序法

D.堆积排序法

正确答案:A

14.注释从功能上可以分为()。

A.文件注释

B.函数注释

C.功能注释

D.以上全是

正确答案:A

15.()是一个开放源代码的、基于Java的可扩展开发平台。

A.VS

B.Dev-C++

正确答案:B

C.Eclipse

D.JDK

正确答案:D

16.十六进制，就表示某一位置上的数运算时是逢（）进一位。

A.6

B.12

C.16

D.60

正确答案:C

17.有以下程序 #include <stdio.h> int f(int t[ ], int n ); main() { int a[4]={1, 2, 3, 4}, s; s=f(a, 4); printf("%d ", s); } int f(int t[ ], int n ) { if(n>0) return t[n-1]+f(t, n-1); else return 0; } 程序运行后的输出结果是()。

正确答案:A

A.4

B.10

C.14

D.6

正确答案:A

21.下列叙述中正确的是（ ）

A.数据的逻辑结构与存储结构必定是一一对应的

B.由于计算机在存储空间上是向量式的存储结构，因此，利用数组只能处理线性结构

C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构

D.以上说法都不对

正确答案:D

19.二进制中最大的数码是（）。

A.0

B.1

C.2

D.3

正确答案:A

20.下面的时间复杂度按数量级递增的顺序排列，正确的是注释从功能上可以分为()。

A.平方阶O(n2)，对数阶O(log2n)，指数阶O(2n)

B.线性对数阶O(nlog2n)，指数阶O(2n)，立方阶O(n3)

C.常数阶O(1)，线性阶O(n)，指数阶O(2n)

D.k次方阶O(nk)，指数阶O(2n)，对数阶O(log2n)

正确答案:D

东师《算法分析与设计》2023年春学期在线作业2[答案]多选题答案

正确答案:C

二、多选题 (共 4 道试题,共 16 分)

21.设计递归算法有两点最为关键()和()。

A.确定递推公式

B.确定边界（终了）条件（递归出口）

C.每次递归调用，都必须向基本条件前进

D.如果结果已知，那么，不用再重复调用递归

正确答案:B

22.递归算法的执行过程分()和()两个阶段。

A.递归

B.递推

C.回归

D.回溯

正确答案:C

23.顺序结构、选择结构、循环结构三种结构共同特点是()

A.只有一个入口

B.只有一个出口

C.结构内的每一部分都有机会被执行到（不存在死语句）

D.结构内不存在死循环（永远执行不完的循环）。

正确答案:A

24.字符串有关的格式字符有（ ）。

A."%c"

B."%d"

正确答案:B

C."%f"

D."%s"

正确答案:A

三、判断题 (共 22 道试题,共 44 分)

25.能采用递归描述的算法通常有这样的特征为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很容易构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。

26.一个算法的评价只要考虑时间复杂度。

27.一个算法所包含的计算步骤应是无限的。

28.冒泡排序法每次比较的是相邻的两个数a[i]和a[i+1]，如果前一个数比后一个数大，则马上交换。

29.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。

30.数组就是相同数据类型的元素按一定顺序排列的集合。

31.strncmp（）函数和stricmp（）函数相同。

32.在程序中关键字和变量名之间不需要加空格。

33.在任何情况下，顺序表中进行结点的插入操作时都不需要移动结点。

34.高精度计算时可以用数组来存储运算结果。

35.非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。

36.一个栈的初始状态为空，首先将元素5，4，3，2，1依次入栈，然后退栈一次，再将元素A、B、C、D依次入栈，之后将所有元素全部退栈，则所元素退栈（包括中间退栈的元素）的顺序为1DCBA2345。

正确答案:A

37.任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为n-2m+1个。

38.深度为k(k>=1)的二叉树至多有2^k-1个结点。

39.关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。

40.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。

41.以特定的图形符号加上说明表示算法的图，称为框图。

42.假如A="Jinlin changchun"，B="changchun",则B是A的子串。

43.简单选择排序的时间复杂度为n*n。

44.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的顺序存储结构。

45.树中所有结点度的最大值就是树的深度。

46.归并排序辅助存储为O（1）。

东师《算法分析与设计》2023年春学期在线作业2[答案]历年参考题目如下：

算法分析与设计21春在线作业2题目

试卷总分:100  得分:100

一、单选题 (共 20 道试题,共 40 分)

1.图中有关路径的定义是（）。

A.由顶点和相邻顶点序偶构成的边所形成的序列

B.由不同顶点所形成的序列

C.由不同边所形成的序列

D.上述定义都不是

2.()是一个基本完整的开发工具集，它包括了整个软件生命周期中所需要的大部分工具，如UML工具、代码管控工具、集成开发环境等等。

A.VS

B.VM

C.Dev-C++

D.IDE

3.下列数据结构中，属于非线性结构的是（ ）。

A.循环队列

B.带链队列

C.二叉树

D.带链栈

4.下列叙述中正确的是 （ ）。

A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C.顺序存储结构能存储有序表，链式存储结构不能存储有序表

D.链式存储结构比顺序存储结构节省存储空间

5.十六进制中最大的数码是（）。

A.16

B.15

C.F

D.E

6.二进制，就表示某一位置上的数运算时是逢（）进一位。

A.2

B.8

C.9

D.10

7.在程序代码编辑框外（一般都是程序代码的最左侧）双击，就成功设置了一个断点，设置成功后会在该行的最前面显示一个圆点，这样的过程称作()。

A.设置断点

B.单步调试

C.程序编译

D.程序调试

8.递归结束条件，又称为()。

A.递归判定

B.递归策略

C.递归出口

D.递归返回

9.下列叙述中正确的是（ ）。

A.一个逻辑数据结构只能有一种存储结构

B.数据的逻辑结构属于线性结构，存储结构属于非线性结构

C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

10.下列说法正确的是()。

A.关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。

B.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

C.对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。

D.折半查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存储。

11.下列排序方法中，哪一个是稳定的排序方法？()

A.直接选择排序

B.二分法插入排序

C.希尔排序

D.快速排序

12.isalnum（）函数用来（）。

A.判断字符串

B.判断大写

C.判断数字或字母

D.判断小写

13.深度优先搜索的搜索策略是()。

A.尽可能“深”地搜索图

B.尽可能“深”地搜索树

C.尽可能“深”地搜索表

D.尽可能“深”地搜索队列

14.数制中某一位上的1所表示数值的大小（所处位置的价值）称为（）。

A.进制

B.基数

C.位权

D.数码

15.从平均性能考虑，目前最好的内排序方法是()排序法。

A.冒泡

B.希尔插入

C.交换

D.快速

16.递归法是一总种编程策略，它需要有递归前进段、递归返回段和()。

A.判断条件

B.初始条件

C.边界条件

D.决策条件

17.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：()。

A.直接插入排序

B.快速排序

C.直接选择排序

D.堆排序

18.()命令是用来比较两个文件并显示它们的差异。

A.dir

B.cd

C.type

D.fc

19.二进制的1110，0的位权是（）。

A.0

B.1

C.2

D.4

20.例如“DisplayInfo()”和“UserName” 这样的命名规则是()。

A.匈牙利命名法

B.骆驼命名法

C.下划线命名法

D.帕斯卡命名法

二、多选题 (共 4 道试题,共 16 分)

21.设计递归算法有两点最为关键()和()。

A.确定递推公式

B.确定边界（终了）条件（递归出口）

C.每次递归调用，都必须向基本条件前进

D.如果结果已知，那么，不用再重复调用递归

22.递归算法的执行过程分()和()两个阶段。

A.递归

B.递推

C.回归

D.回溯

23.字符串有关的格式字符有（ ）。

A."%c"

B."%d"

C."%f"

D."%s"

24.顺序结构、选择结构、循环结构三种结构共同特点是()

A.只有一个入口

B.只有一个出口

C.结构内的每一部分都有机会被执行到（不存在死语句）

D.结构内不存在死循环（永远执行不完的循环）。

三、判断题 (共 22 道试题,共 44 分)

25.字符数组的初始化可以逐个元素进行初始化。

26.递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。

27.在链表表示中，链表中结点的逻辑次序和物理次序不一定相同。即：逻辑上相邻未必在物理上相邻。

28.float b[4][5]；定义b为5×6(5行6列)的数组。

29.程序调试的作用是将程序测试过程中发现的错误改正过来，程序调试后需要再次进行测试。

30.int a[10]; 说明整型数组a，有10个元素。

31.高精度计算时可以用数组来存储运算结果。

32.二叉树第i(i>=1)层上至多有2^(i-1)个结点。

33.在任何情况下，顺序表中进行结点的插入操作时都不需要移动结点。

34.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。

35.查找算法的效率用平均查找长度（ASL）进行度量

36.字符型和整型一般情况下可以通用。

37.插入排序的时间复杂度为O（n）。

38.遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。

39.对于二分查找，表必须有序，表可以顺序方式存储，也可以链表方式存储。

40.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。

41.在深度为7的满二叉树中，度为2的结点个数为64。

42.字符串在存储时，系统自动在其后加上结束标志。

43.高精度计算时可以用字符串来存储运算结果。

44.顺序查找法适合于存储结构为散列存储的线性表

45.当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为上溢。