东师算法分析与设计秋在线作业.doc

东北师范大学东师算法分析与设计16秋在线作业1

一、单选题（共 20 道试题，共 40 分。）

1. n个结点的完全有向图具有边的数目（）。
A. n*n
B. n（n＋１）
C. n／2
D. n*（n－l）
对的答案：
2. 在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A. 1/2
B. 2
C. 1
D. 4
对的答案：
3. 将递归算法转换成相应的非递归算法时，通常需要使用()。
A. 栈
B. 队列
C. 链表
D. 树
对的答案：
4. 分治法是把一个复杂的问题提成相似的子问题，再把子问题提成更小的子问题……直到最后子问题可以简朴的直接求解，原问题的解即子问题解的()
A. 合并
B. 最大值
C. 最小值
D. 平均值
对的答案：
5. strcmp("a","b")返回的值是（）
A. 2
B. 1
C. 0
D. -1
对的答案：
6. 一个算法中的语句的()被称为语句频度或时间频度。
A. 执行时间
B. 占用空间
C. 执行速度
D. 执行次数
对的答案：
7. 与二进制数101.01011等值的十六进制数为( )。
A. A.B
B. 5.51
C. A.51
D. 5.58
对的答案：
8. 下面选项中比较著名的命名规则有()。
A. 匈牙利命名法
B. 匈牙利命名法和骆驼命名法
C. 有匈牙利命名法、骆驼命名法和帕斯卡命名法
D. 匈牙利命名法、骆驼命名法、帕斯卡命名法以及下划线命名法
对的答案：
9. 数制中表达基本数值大小的不同数字符号称为（）。
A. 进制
B. 基数
C. 位权
D. 数码
对的答案：
10. ()是用户在程序中使用的名字，它是一种用于命名一些具有特定含义的对象的符号，通常用来标记程序中的变量，常量，函数，语句块。
A. 对象
B. 标记符
C. 符号
D. 命名规则
对的答案：
11. IDE的全程是()。
A. 集成开发环境
B. 集成环境
C. 开发软件
D. 调试过程
对的答案：
12. 有以下程序，程序的运营结果是()。 #include <stdio.h> int f(int x ) { int y; if (x==0||x==1) return (3); y=x*x- f(x-2); return y; } main() { int z; z=f(3); printf(“%d\n”,z); }
A. 0
B. 9
C. 6
D. 8
对的答案：
13. ()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，由于程序自身就是怎么做。
A. 文献注释
B. 函数注释
C. 功能注释
D. 程序注释
对的答案：
14. 下列叙述中，对的的是()。
A. 对长度为n 的有序链表进行查找，最坏情况下需要的比较次数为n
B. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(n/2)
C. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(log2n)
D. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为(nlog2n)
对的答案：
15. 图中有关途径的定义是（）。
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
对的答案：
16. ()是一个开放源代码的、基于Java的可扩展开发平台。
A. VS
B. Dev-C++
C. Eclipse
D. JDK
对的答案：
17. 设无向图的顶点个数为n，则该图最多有（）条边。
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. n2
对的答案：
18. 九进制，就表达某一位置上的数运算时是逢（）进一位。
A. 2
B. 8
C. 9
D. 10
对的答案：
19. 某内排序方法的稳定性是指()。
A. 该排序算法不允许有相同的关键字记录
B. 该排序算法允许有相同的关键字记录
C. 平均时间为0（n log n）的排序方法
D. 以上都不对
对的答案：
20. 递归算法是()。
A. 简朴方程
B. 标准方程
C. 简朴公式
D. 标准公式
对的答案：

算法分析与设计16秋在线作业1

二、多选题（共 5 道试题，共 20 分。）

1. 字符串有关的格式字符有（ ）。
A. "%c"
B. "%d"
C. "%f"
D. "%s"
对的答案：
2. 高精度运算重要解决（）。
A.
B. 加数
C. 减数
D. 运算结果的输入
E. 运算结果的存储
对的答案：
3. 设计递归算法有两点最为关键()和()。
A. 拟定递推公式
B. 拟定边界（终了）条件（递归出口）
C. 每次递归调用，都必须向基本条件前进
D. 假如结果已知，那么，不用再反复调用递归
对的答案：
4. 递归算法的执行过程分()和()两个阶段。
A. 递归
B. 递推
C. 回归
D. 回溯
对的答案：
5. 顺序结构、选择结构、循环结构三种结构共同特点是()
A. 只有一个入口
B. 只有一个出口
C. 结构内的每一部分都有机会被执行到（不存在死语句）
D. 结构内不存在死循环（永远执行不完的循环）。
对的答案：

算法分析与设计16秋在线作业1

三、判断题（共 20 道试题，共 40 分。）

1. C语言中，字符串作为字符数组来解决。
A. 错误
B. 对的
对的答案：
2. 有n个数存放在一维数组A[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
A. 错误
B. 对的
对的答案：
3. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为n次。
A. 错误
B. 对的
对的答案：
4. C语言允许对数组的大小作动态定义，即定义行中的数组长度能涉及变量。
A. 错误
B. 对的
对的答案：
5. 递推就是在函数里调用自身。
A. 错误
B. 对的
对的答案：
6. 一个函数直接或间接调用自己自身，这种函数叫递归函数。
A. 错误
B. 对的
对的答案：
7. 使用冒泡排序法对n个数进行排序必须要进行n趟比较。
A. 错误
B. 对的
对的答案：
8. 一个算法的评价只要考虑时间复杂度。
A. 错误
B. 对的
对的答案：
9. 求n的阶乘的表达方法n!=n*(n-1)! ，其中0!=1，相应的是递归的思想。
A. 错误
B. 对的
对的答案：
10. 在计算机上中有符号整数和无符号整数表达的数值范围是相同的。
A. 错误
B. 对的
对的答案：
11. 在待排数据基本有序的情况下，快速排序效果最佳。
A. 错误
B. 对的
对的答案：
12. 高精度计算时可以用数组来存储运算结果。
A. 错误
B. 对的
对的答案：
13. 按“先进后出”原则组织数据的数据结构是队列。
A. 错误
B. 对的
对的答案：
14. 注释内容太多会影响程序的执行效率。
A. 错误
B. 对的
对的答案：
15. 深度为k(k>=1)的二叉树至多有2^k-1个结点。
A. 错误
B. 对的
对的答案：
16. 一个scanf函数输入多个字符串，输入时以“空格”键作为字符串间的分隔。
A. 错误
B. 对的
对的答案：
17. 在顺序表中进行结点的删除操作平均须移动一半结点。
A. 错误
B. 对的
对的答案：
18. 为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。
A. 错误
B. 对的
对的答案：
19. 能采用递归描述的算法通常有这样的特性：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解很容易构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
A. 错误
B. 对的
对的答案：
20. 字符串的结束标记在输出时也会被输出。
A. 错误
B. 对的
对的答案：

算法分析与设计16秋在线作业1

一、单选题（共 20 道试题，共 40 分。）

1. 下列数据结构中，属于非线性结构的是（ ）。
A. 循环队列
B. 带链队列
C. 二叉树
D. 带链栈
对的答案：
2. tolower（）函数用来（）。
A. 小写字母转换为大写字母
B. 大写字母转换为小写字母
C. 小写字母转换为大写字母，同时大写字母转换为小写字母
D. 判断大小写
对的答案：
3. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是()。
A. 选择排序法
B. 插入排序法
C. 快速排序法
D. 堆积排序法
对的答案：
4. 排序算法是按照某个或某些关键字的()，递增或递减的排列起来的操作
A. 类别
B. 属性
C. 名称
D. 大小
对的答案：
5. 伪代码是用介于自然语言和()之间的文字和符号来描述算法。
A. 面向过程语言
B. 面向对象语言
C. 编程语言
D. 计算机语言
对的答案：
6. ()是一个开放源代码的、基于Java的可扩展开发平台。
A. VS
B. Dev-C++
C. Eclipse
D. JDK
对的答案：
7. 变量名=属性 + 类型 + 对象描述，其中每个对象的名称都要有明确含义，可以取对象的名字全称或名字的一部分，这种命名规则是()。
A. 匈牙利命名法
B. 骆驼命名法
C. 下划线命名法
D. 帕斯卡命名法
对的答案：
8. 注释从功能上可以分为文献注释、函数注释和()。
A. 程序员注释
B. 功能注释
C. 时间注释
D. 版权注释
对的答案：
9. 二进制的1110，0的位权是（）。
A. 0
B. 1
C. 2
D. 4
对的答案：
10. 广度优先搜索的原则()。
A. 准时间遍历解空间
B. 按代价遍历解空间
C. 按层遍历解空间
D. 按速度遍历解空间
对的答案：
11. 字符数组在初始化时若数据个数少于数组长度,多余元素自动为（）。
A. 空
B. 0
C. null
D. 随机
对的答案：
12. 十六进制数C1B转换为二进制数是（）。
A. 1
B.
C.
D.
对的答案：
13. 一般情况下，程序中所有注释的行数占到整个源程序的()比较适宜。
A. 1/2到2/3
B. 1/3
C. 1/3到1/2
D. 1/2
对的答案：
14. 下面不是批解决文献的特点是()。
A. 批解决，也称为批解决脚本，其文献扩展名为.bat
B. 它是无格式的文本文献，每一行可视为一个命令，每个命令里可以含多条子命令，从第一行开始执行，直到最后一行结束，它运营的平台是DOS。
C. 在命令提醒下键入批解决文献的名称，或者单击该批解决文献，系统就会调用cmd.exe按照该文献中各个命令出现的顺序来逐个运营它们。
D. 使用批解决文献，可以简化平常或反复性任务，使用方便、灵活，功能强大，自动化限度高
对的答案：
15. 在深度为7的满二叉树中，叶子结点的个数为（）。
A. 32
B. 31
C. 64
D. 63
对的答案：
16. 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。
A. 35/11
B. 34/11
C. 33/11
D. 32/11
对的答案：
17. 十进制的123，1的位权是（）。
A. 1
B. 2
C. 10
D. 100
对的答案：
18. 使用简朴选择排序法对n个数进行排序要进行()趟比较。
A. n
B. n-1
C. n+1
D. 不一定
对的答案：
19. 假如待排序序列中两个数据元素具有相同的值，在排序前后它们的互相位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。
A. 起泡排序
B. 归并排序
C. Shell排序
D. 直接插入排序
对的答案：
20. 递归函数f(n)=f(n-1)+n(n>1)的递归出口是()。
A. f(1)=0
B. f(1)=1
C. f(0)=1
D. f(n)=n
对的答案：

算法分析与设计16秋在线作业1

二、多选题（共 5 道试题，共 20 分。）

1. 设计递归算法有两点最为关键()和()。
A. 拟定递推公式
B. 拟定边界（终了）条件（递归出口）
C. 每次递归调用，都必须向基本条件前进
D. 假如结果已知，那么，不用再反复调用递归
对的答案：
2. 高精度运算重要解决（）。
A.
B. 加数
C. 减数
D. 运算结果的输入
E. 运算结果的存储
对的答案：
3. 顺序结构、选择结构、循环结构三种结构共同特点是()
A. 只有一个入口
B. 只有一个出口
C. 结构内的每一部分都有机会被执行到（不存在死语句）
D. 结构内不存在死循环（永远执行不完的循环）。
对的答案：
4. 递归算法的执行过程分()和()两个阶段。
A. 递归
B. 递推
C. 回归
D. 回溯
对的答案：
5. 字符串有关的格式字符有（ ）。
A. "%c"
B. "%d"
C. "%f"
D. "%s"
对的答案：

算法分析与设计16秋在线作业1

三、判断题（共 20 道试题，共 40 分。）

1. 下列程序段实现的是顺序查找功能（） int Search(int array[], int n, int key) { int i; array[n] = key; for(i=0;key!=array[i];i++); return(i<n?i:-1); }
A. 错误
B. 对的
对的答案：
2. 当待排序的元素很大时，为了互换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的重要因素。
A. 错误
B. 对的
对的答案：
3. 字符型和整型一般情况下可以通用。
A. 错误
B. 对的
对的答案：
4. 高精度计算时可以用字符串来存储运算结果。
A. 错误
B. 对的
对的答案：
5. 查找就是根据给定的某个值，在查找表中拟定一个其关键字等于给定值的记录或数据元素。
A. 错误
B. 对的
对的答案：
6. 快速排序是一种不稳定排序方法。
A. 错误
B. 对的
对的答案：
7. 在C语言中字符串的头文献是string.h。
A. 错误
B. 对的
对的答案：
8. 某二叉树中度为2的结点有18个，则该二叉树中有19个叶子结点。
A. 错误
B. 对的
对的答案：
9. 快速排序总比简朴排序快。
A. 错误
B. 对的
对的答案：
10. 使用冒泡排序法对n个数进行排序必须要进行n趟比较。
A. 错误
B. 对的
对的答案：
11. 互换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行互换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n） ，而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。
A. 错误
B. 对的
对的答案：
12. 在后序遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。
A. 错误
B. 对的
对的答案：
13. 外部排序是把外存文献调入内存,可运用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。
A. 错误
B. 对的
对的答案：
14. 假如用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，假如bottom=49,top=30（数组下标），则栈中具有19个元素。
A. 错误
B. 对的
对的答案：
15. 插入排序是一种稳定排序方法。
A. 错误
B. 对的
对的答案：
16. puts不需要格式控制符，且自动换行。
A. 错误
B. 对的
对的答案：
17. 假如A="Jinlin changchun"，B="changchun",则B是A的子串。
A. 错误
B. 对的
对的答案：
18. 一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有24个结点。
A. 错误
B. 对的
对的答案：
19. 当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为上溢。
A. 错误
B. 对的
对的答案：
20. 程序调试的作用是将程序测试过程中发现的错误改正过来，程序调试后需要再次进行测试。
A. 错误
B. 对的
对的答案：

算法分析与设计16秋在线作业1

一、单选题（共 20 道试题，共 40 分。）

1. 十进制，就表达某一位置上的数运算时是逢（）进一位。
A. 2
B. 8
C. 9
D. 10
对的答案：
2. 假如待排序序列中两个数据元素具有相同的值，在排序前后它们的互相位置发生颠倒，则称该排序算法是不稳定的。()就是不稳定的排序方法。
A. 起泡排序
B. 归并排序
C. Shell排序
D. 直接插入排序
对的答案：
3. 下面关于二分查找的叙述对的的是()
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，并且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
对的答案：
4. 注释从功能上可以分为()。
A. 文献注释
B. 函数注释
C. 功能注释
D. 以上全是
对的答案：
5. 在下面的排序方法中，辅助空间为O（n）的是() 。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
对的答案：
6. 下面叙述中对的的是（ ）
A. 栈是“先进先出”的线性表
B. 队列是“先进后出”的线性表
C. 循环队列是非线性结构
D. 有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
对的答案：
7. int atoi(char *s)函数的作用是（）。
A. 整数转换为字符串
B. 字符串转换为整数
C. 字符转换为字符串
D. 获取字符个数
对的答案：
8. 下列数据结构中，能用二分法进行查找的是（）。
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表
对的答案：
9. 语句 printf("%d\n",strlen("ATS\n012\1\\"));的输出结果是（）。
A. 11
B. 10
C. 9
D. 8
对的答案：
10. char c[6] = "China";哪个语句能输出该字符串（）。
A. printf("%s",c);
B. printf("%c",c[0]);
C. printf("%s",c[0]);
D. printf("%d",c);
对的答案：
11. isdigit（）函数用来（）。
A. 判断字母
B. 判断数字
C. 判断大写
D. 判断小写
对的答案：
12. 一个算法中的语句的()被称为语句频度或时间频度。
A. 执行时间
B. 占用空间
C. 执行速度
D. 执行次数
对的答案：
13. ()是用户在程序中使用的名字，它是一种用于命名一些具有特定含义的对象的符号，通常用来标记程序中的变量，常量，函数，语句块。
A. 对象
B. 符号
C. 标记符
D. 命名规则
对的答案：
14. ()嵌在源程序体中，用于描述其后的语句或程序段做什么工作，也就是解释下面要做什么，或是执行了下面的语句会怎么样。而不要解释下面怎么做，由于程序自身就是怎么做。
A. 文献注释
B. 函数注释
C. 功能注释
D. 程序注释
对的答案：
15. isalpha（）函数用来（）。
A. 判断字母
B. 判断数字
C. 判断大写
D. 判断小写
对的答案：
16. 字符数组在进行指定初值时，若未指定数组长度，则长度（）初值个数。
A. 小于
B. 等于
C. 大于
D. 不等于
对的答案：
17. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是()。
A. 选择
B. 冒泡
C. 插入
D. 堆
对的答案：
18. 下面选项中比较著名的命名规则有()。
A. 匈牙利命名法
B. 匈牙利命名法和骆驼命名法
C. 有匈牙利命名法、骆驼命名法和帕斯卡命名法
D. 匈牙利命名法、骆驼命名法、帕斯卡命名法以及下划线命名法
对的答案：
19. 二进制数10110.101转换为十进制数是（）。
A. 22.625
B. 20.625
C. 22.725#20.725
对的答案：
20. ()重要是用来显示当前目录的名称或更改当前的目录。
A. dir
B. cd
C. type
D. fc
对的答案：

算法分析与设计16秋在线作业1

二、多选题（共 5 道试题，共 20 分。）

1. 字符串有关的格式字符有（ ）。
A. "%c"
B. "%d"
C. "%f"
D. "%s"
对的答案：
2. 顺序结构、选择结构、循环结构三种结构共同特点是()
A. 只有一个入口
B. 只有一个出口
C. 结构内的每一部分都有机会被执行到（不存在死语句）
D. 结构内不存在死循环（永远执行不完的循环）。
对的答案：
3. 递归算法的执行过程分()和()两个阶段。
A. 递归
B. 递推
C. 回归
D. 回溯
对的答案：
4. 高精度运算重要解决（）。
A.
B. 加数
C. 减数
D. 运算结果的输入
E. 运算结果的存储
对的答案：
5. 设计递归算法有两点最为关键()和()。
A. 拟定递推公式
B. 拟定边界（终了）条件（递归出口）
C. 每次递归调用，都必须向基本条件前进
D. 假如结果已知，那么，不用再反复调用递归
对的答案：

算法分析与设计16秋在线作业1

三、判断题（共 20 道试题，共 40 分。）

1. 快速排序是一种不稳定排序方法。
A. 错误
B. 对的
对的答案：
2. 顺序查找是从线性表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某元素关键字与K相等，则查找成功；若所有元素都比较完毕，仍找不到关键字为K的元素，则查找失败。
A. 错误
B. 对的
对的答案：
3. 求n的阶乘的表达方法n!=n*(n-1)! ，其中0!=1，相应的是递归的思想。
A. 错误
B. 对的
对的答案：
4. 深度为k(k>=1)的二叉树至多有2^k-1个结点。
A. 错误
B. 对的
对的答案：
5. 在使用递归策略时，必须有一个明确的递归结束条件，称为递归入口。
A. 错误
B. 对的
对的答案：
6. 在深度为7的满二叉树中，度为2的结点个数为64。
A. 错误
B. 对的
对的答案：
7. 冒泡排序是一种不稳定排序方法。
A. 错误
B. 对的
对的答案：
8. 下列程序段实现的是顺序查找功能（） int Search(int array[], int n, int key) { int i; array[n] = key; for(i=0;key!=array[i];i++); return(i<n?i:-1); }
A. 错误
B. 对的
对的答案：
9. 递推分倒推法和顺推法两种形式。
A. 错误
B. 对的
对的答案：
10. 简朴选择排序和冒泡排序都是一种不稳定排序方法。
A. 错误
B. 对的
对的答案：
11. 归并排序是一种稳定的排序方法。
A. 错误
B. 对的
对的答案：
12. 函数atoi("1234")的函数返回值是1234。
A. 错误
B. 对的
对的答案：
13. 对长度为n 的有序链表进行对分查找，最坏情况下需要的比较次数为log2n。
A. 错误
B. 对的
对的答案：
14. 高精度计算时可以用字符串来存储运算结果。
A. 错误
B. 对的
对的答案：
15. 在深度为7的满二叉树中，度为2的结点个数为63。
A. 错误
B. 对的
对的答案：
16. scanf()、printf()可以输入输出几个字符串。
A. 错误
B. 对的
对的答案：
17. 对于任意一棵二叉树，假如度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。
A. 错误
B. 对的
对的答案：
18. 快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。
A. 错误
B. 对的
对的答案：
19. 某二叉树中度为2的结点有18个，则该二叉树中有20个叶子结点。
A. 错误
B. 对的
对的答案：
20. 在计算机上中有符号整数和无符号整数表达的数值范围是相同的。
A. 错误
B. 对的
对的答案：

算法分析与设计16秋在线作业1

一、单选题（共 20 道试题，共 40 分。）

1. 十进制的123，1的位权是（）。
A. 1
B. 2
C. 10
D. 100
对的答案：
2. 用计算机解决问题的过程可以提成哪三个阶段（）。
A. 输入、算法设计和输出
B. 输入、测试和输出
C. 分析问题、设计算法和实现算法
D. 分析问题、测试和实现
对的答案：
3. 二进制，就表达某一位置上的数运算时是逢（）进一位。
A. 2
B. 8