奥鹏作业网算法分析与设计2022年秋学期在线作业2
共46道题 总分：100分
一、单选题(共20题，40分)
1.用计算机解决问题的过程可以分成哪三个阶段()。
A、输入、测试和输出
B、分析问题、设计算法和实现算法
C、输入、算法设计和输出
D、分析问题、测试和实现
2.()命令主要用来查看磁盘中文件的命令。
A、dir
B、cd
C、type
D、fc
3.cd 目录名的功能是()。
A、退回到根目录
B、退回到上一级目录
C、进入特定的目录
D、显示出文本文件的内容
4.IDE的全程是()。
A、集成开发环境
B、集成环境
C、开发软件
D、调试过程
5.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是()。
A、选择
B、冒泡
C、插入
D、堆
6.在下列排序算法中,哪一个算法的时间复杂度与初始排序无关()。
A、直接插入排序
B、冒泡排序
C、快速排序
D、直接选择排序
7.下列叙述中，正确的是()。
A、对长度为n 的有序链表进行查找，最坏情况下需要的比较次数为n
B、对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)
C、对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
D、对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)
8.按F5开始调试，程序便会直接运行到断点处。接下来可以逐行来运行程序，查看各个变量的值，也可以直接运行到下一个断点或程序结束，这样过程被称作()。
A、设置断点
B、单步调试
C、程序编译
D、程序调试
9.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）
A、acbed
B、deabc
C、decab
D、cedba
10.对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。
A、35/11
B、34/11
C、33/11
D、32/11
11.某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（）
A、10
B、8
C、6东师答案请进：opzy.net或请联系微信：1095258436
D、4
12.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。
A、起泡排序
B、归并排序
C、Shell排序
D、直接插入排序
13.在程序代码编辑框外（一般都是程序代码的最左侧）双击，就成功设置了一个断点，设置成功后会在该行的最前面显示一个圆点，这样的过程称作()。
A、设置断点
B、单步调试
C、程序编译
D、程序调试
14.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为()。
A、编写程序
B、调试程序
C、执行程序
D、编译程序
15.变量名=属性 + 类型 + 对象描述，其中每个对象的名称都要有明确含义，可以取对象的名字全称或名字的一部分，这种命名规则是()。
A、匈牙利命名法
B、骆驼命名法
C、下划线命名法
D、帕斯卡命名法
16.支持子程序调用的数据结构是（ ）
A、栈
B、树
C、队列
D、二叉树
17.下列数据结果中，能够按照“先进后出”原则存取数据的是（ ）
A、循环队列
B、栈
C、队列
D、二叉树
18.十进制中最小的数码是（）。
A、10
B、9
C、1
D、0
19.在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。
A、O(n)
B、O(n2)
C、O(log2n)
D、O(nlog2n)
20.strchr（）函数用来（）。
A、字符串连接
B、比较字符
C、求字符位置
D、求子串位置
二、多选题(共4题，16分)
1.递归算法的执行过程分()和()两个阶段。
A、递归
B、递推
C、回归
D、回溯
2.设计递归算法有两点最为关键()和()。
A、确定递推公式
B、确定边界（终了）条件（递归出口）
C、每次递归调用，都必须向基本条件前进
D、如果结果已知，那么，不用再重复调用递归
3.顺序结构、选择结构、循环结构三种结构共同特点是()
A、只有一个入口
B、只有一个出口
C、结构内的每一部分都有机会被执行到（不存在死语句）
D、结构内不存在死循环（永远执行不完的循环）。
4.字符串有关的格式字符有（ ）。
A、”%c”
B、”%d”
C、”%f”
D、”%s”
三、判断题(共22题，44分)
1.在查找其关键字等于给定值的过程中，需要和给定值进行比较的关键字个数的期望值称为查找成功时的平均查找长度，则称为平均查找长度ASL。
A、错误
B、正确
2.puts不需要格式控制符，且自动换行。
A、错误
B、正确
3.已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有12个叶子结点。
A、错误
B、正确
4.对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。
A、错误
B、正确
5.冒泡排序是一种不稳定排序方法。
A、错误
B、正确
6.二分法插入排序所需比较次数与待排序记录的初始排列状态相关。
A、错误
B、正确
7.在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。
A、错误
B、正确
8.递归算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。
A、错误
B、正确
9.gets()函数一次可以输入多个字符串。
A、错误
B、正确
10.递推就是在函数里调用自身。
A、错误
B、正确
11.一个函数直接或间接调用自己本身，这种函数叫递归函数。
A、错误
B、正确
12.字符串的结束标记在输出时也会被输出。
A、错误
B、正确
13.内排序要求数据一定要以顺序方式存储。
A、错误
B、正确
14.有一组数据{6，202，100，301，38，8，1}，使用简单选择排序需要进行6趟比较。
A、错误
B、正确
15.长度不同的字符串一定不会相等。
A、错误
B、正确
16.在待排数据基本有序的情况下，快速排序效果最好。
A、错误
B、正确
17.在顺序表中进行结点的删除操作平均须移动一半结点。
A、错误
B、正确
18.一棵二叉树第6层（根结点为第一层）的结点数最多为31个。
A、错误
B、正确
19.顺序查找法适合于存储结构为散列存储的线性表
A、错误
B、正确
20.字符数组的初始化可以逐个元素进行初始化。
A、错误
B、正确
21.线性表需要为表示结点间的逻辑关系而增加额外的存储空间。
A、错误
B、正确
22.快速排序的时间复杂度为O(n*n)。
A、错误
B、正确
算法分析与设计2022年秋学期在线作业2
共46道题 总分：100分
一、单选题(共20题，40分)
1.十进制中最大的数码是（）。
A、6
B、7
C、8
D、9
2.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：()。
A、直接插入排序
B、快速排序
C、直接选择排序
D、堆排序
3.二进制的基数是（）。
A、2
B、8
C、10
D、16
4.下列说法错误的是()
A、使用高级计算机语言，如C、C++、Java，编写的程序，都需要经过编译器编译或解释，才能转化成机器能够识别并能执行的二进制代码。
B、如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为调试程序。
C、自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做调试器。
D、调试器并能解决程序中出现的问题。
5.下面说法不是断点特点是()。
A、它是调试器的功能之一
B、程序运行到这一行就会停住，然后你可以一步一步往下调试
C、调试过程中可以看各个变量当前的值，出错的话，调试到出错的代码行即显示错误停下
D、调试过程中不可以看各个变量当前的值，出错的话，调试到出错的代码行即显示错误停下
6.八进制的基数是（）。
A、2
B、8
C、10
D、16
7.一个有n个结点的图，最多有（）个连通分量。
A、0
B、1
C、n-1
D、n
8.十进制的基数是（）。
A、2
B、8
C、10
D、16
9.下面命名规则中，哪项不是现在比较常用的命名规则()。
A、匈牙利命名法
B、骆驼命名法
C、下划线命名法
D、图灵命名法
10.判断 c 是否是数字字符的函数是（）。
A、isalpha(int c)
B、isalnum(int c)
C、islower(int c)
D、isdigit(int c)
11.十六进制数5A.8转换为十进制数是（）。
A、89.6
B、90.1
C、90.5
D、96.8
12.排序算法是按照某个或某些关键字的()，递增或递减的排列起来的操作
A、类别
B、属性
C、名称
D、大小
13.isalnum（）函数用来（）。
A、判断字符串
B、判断大写
C、判断数字或字母
D、判断小写
14.字符串的结束标记是（）。
A、0′
B、’ ‘
C、’\0′
D、’\n’
15.字符串”China Beijing”的长度是（）
A、12
B、13
C、14
D、15
16.对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（）。
A、log2n
B、n/2
C、n
D、n+1
17.某内排序方法的稳定性是指()。
A、该排序算法不允许有相同的关键字记录
B、该排序算法允许有相同的关键字记录
C、平均时间为0（n log n）的排序方法
D、以上都不对
18.执行memset(s,’a’,4)后，s的值为（）。
A、”aaaa”
B、”a4″
C、”4a”
D、”eeee”
19.isdigit（）函数用来（）。
A、判断字母
B、判断数字
C、判断大写
D、判断小写
20.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为()次。
A、n/2
B、(n+1)/2
C、(n-1)/2
D、n
二、多选题(共4题，16分)
1.顺序结构、选择结构、循环结构三种结构共同特点是()
A、只有一个入口
B、只有一个出口
C、结构内的每一部分都有机会被执行到（不存在死语句）
D、结构内不存在死循环（永远执行不完的循环）。
2.字符串有关的格式字符有（ ）。
A、”%c”
B、”%d”
C、”%f”
D、”%s”
3.递归算法的执行过程分()和()两个阶段。
A、递归
B、递推
C、回归
D、回溯
4.设计递归算法有两点最为关键()和()。
A、确定递推公式
B、确定边界（终了）条件（递归出口）
C、每次递归调用，都必须向基本条件前进
D、如果结果已知，那么，不用再重复调用递归
三、判断题(共22题，44分)
1.快速排序是一种不稳定排序方法。
A、错误
B、正确
2.puts()函数一次可以输出多个字符串。
A、错误
B、正确
3.按“先进后出”原则组织数据的数据结构是队列。
A、错误
B、正确
4.折半查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存储。
A、错误
B、正确
5.注释内容太多会影响程序的执行效率。
A、错误
B、正确
6.设变量定义为char s[]=“hello”，则数组s中有6个元素。
A、错误
B、正确
7.任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为n-2m+1个。
A、错误
B、正确
8.两个字符串中的字符个数相同时才能进行字符串大小的比较。
A、错误
B、正确
9.非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。
A、错误
B、正确
10.scanf()、printf()可以输入输出几个字符串。
A、错误
B、正确
11.在递归算法所体现的“重复”中要求每次调用在规模上都有所缩小。
A、错误
B、正确
12.确定性是指算法的每一个步骤必须要确切地定义。
A、错误
B、正确
13.简单选择排序和冒泡排序都是一种不稳定排序方法。
A、错误
B、正确
14.统计字符串长度时包括字符串结束标志。
A、错误
B、正确
15.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。
A、错误
B、正确
16.在计算机上中有符号整数和无符号整数表示的数值范围是相同的。
A、错误
B、正确
17.函数atoi(“1234”)的函数返回值是1234。
A、错误
B、正确
18.插入排序是一种稳定排序方法。
A、错误
B、正确
19.穷举法，也称辗转法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。
A、错误
B、正确
20.在深度为7的满二叉树中，度为2的结点个数为64。
A、错误
B、正确
21.冒泡排序是一种不稳定排序方法。
A、错误
B、正确
22.对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
A、错误
B、正确
算法分析与设计2022年秋学期在线作业2
共46道题 总分：100分
一、单选题(共20题，40分)
1.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（C）。
A、39
B、52
C、111
D、119
2.strlen(str)是用来（）。
A、求字符串长度
B、比较字符
C、求子串
D、字符串拷贝
3.八进制中最大的数码是（）。
A、6
B、7
C、8
D、9
4.字符串的结束标记是（）。
A、0′
B、’ ‘
C、’\0′
D、’\n’
5.下列叙述中正确的是（）
A、在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B、在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C、在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D、上述三种说法都不对
6.一般情况下，程序中所有注释的行数占到整个源程序的()比较适宜。
A、1/2到2/3
B、1/3
C、1/3到1/2
D、1/2
7.一个递归算法必须包括()。
A、递归部分
B、终止条件和递归部分
C、循环部分
D、终止条件和循环部分
8.十六进制数C1B转换为二进制数是（）。
A、1100101101011
B、110000011011
C、10110101010
D、11101001011
9.采用简单选择排序，比较次数与移动次数分别为()。
A、O(n),O(logn)
B、O(logn),0(n*n)
C、0(n*n),0(n)
D、0(nlogn),0(n)
10.十六进制数38A.11转换为十进制数是（）。
A、960.06
B、916.0364
C、906.0664
D、902.0563
11.下列数据结构中，能用二分法进行查找的是()。
A、顺序存储的有序线性表
B、线性链表
C、二叉链表
D、有序线性链表
12.例如“camelCase”和“printEmployeePaychecks()” 这样的命名规则是()。
A、匈牙利命名法
B、骆驼命名法
C、下划线命名法
D、帕斯卡命名法
13.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。
A、选择排序法
B、插入排序法
C、快速排序法
D、堆积排序法
14.注释从功能上可以分为()。
A、文件注释
B、函数注释
C、功能注释
D、以上全是
15.()是一个开放源代码的、基于Java的可扩展开发平台。
A、VS
B、Dev-C++
C、Eclipse
D、JDK
16.十六进制，就表示某一位置上的数运算时是逢（）进一位。
A、6
B、12
C、16
D、60
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\n”, s); } int f(int t[ ], int n ) { if(n>0) return t[n-1]+f(t, n-1); else return 0; }程序运行后的输出结果是()。
A、4
B、10
C、14
D、6
18.下列叙述中正确的是（ ）
A、数据的逻辑结构与存储结构必定是一一对应的
B、由于计算机在存储空间上是向量式的存储结构，因此，利用数组只能处理线性结构
C、程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构
D、以上说法都不对
19.二进制中最大的数码是（）。
A、0
B、1
C、2
D、3
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)
二、多选题(共4题，16分)
1.设计递归算法有两点最为关键()和()。
A、确定递推公式
B、确定边界（终了）条件（递归出口）
C、每次递归调用，都必须向基本条件前进
D、如果结果已知，那么，不用再重复调用递归
2.递归算法的执行过程分()和()两个阶段。
A、递归
B、递推
C、回归
D、回溯
3.顺序结构、选择结构、循环结构三种结构共同特点是()
A、只有一个入口
B、只有一个出口
C、结构内的每一部分都有机会被执行到（不存在死语句）
D、结构内不存在死循环（永远执行不完的循环）。
4.字符串有关的格式字符有（ ）。
A、”%c”
B、”%d”
C、”%f”
D、”%s”
三、判断题(共22题，44分)
1.能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很容易构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
A、错误
B、正确
2.一个算法的评价只要考虑时间复杂度。
A、错误
B、正确
3.一个算法所包含的计算步骤应是无限的。
A、错误
B、正确
4.冒泡排序法每次比较的是相邻的两个数：a[i]和a[i+1]，如果前一个数比后一个数大，则马上交换。
A、错误
B、正确
5.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。
A、错误
B、正确
6.数组就是相同数据类型的元素按一定顺序排列的集合。
A、错误
B、正确
7.strncmp（）函数和stricmp（）函数相同。
A、错误
B、正确
8.在程序中关键字和变量名之间不需要加空格。
A、错误
B、正确
9.在任何情况下，顺序表中进行结点的插入操作时都不需要移动结点。
A、错误
B、正确
10.高精度计算时可以用数组来存储运算结果。
A、错误
B、正确
11.非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。
A、错误
B、正确
12.一个栈的初始状态为空，首先将元素5，4，3，2，1依次入栈，然后退栈一次，再将元素A、B、C、D依次入栈，之后将所有元素全部退栈，则所元素退栈（包括中间退栈的元素）的顺序为1DCBA2345。
A、错误
B、正确
13.任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为n-2m+1个。
A、错误
B、正确
14.深度为k(k>=1)的二叉树至多有2^k-1个结点。
A、错误
B、正确
15.关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，称为主关键字。
A、错误
B、正确
16.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
A、错误
B、正确
17.以特定的图形符号加上说明表示算法的图，称为框图。
A、错误
B、正确
18.假如A=”Jinlin changchun”，B=”changchun”,则B是A的子串。
A、错误
B、正确
19.简单选择排序的时间复杂度为n*n。
A、错误
B、正确
20.线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的顺序存储结构。
A、错误
B、正确
21.树中所有结点度的最大值就是树的深度。
A、错误
B、正确
22.归并排序辅助存储为O（1）。
A、错误
B、正确
