东师算法分析与设计17春在线作业答案
东师算法分析与设计17春在线作业1一、单选题：
1.一个算法的评价主要从时间复杂度和( )来考虑。 (满分:2)
A. 空间复杂度
B. 算法有效性
C. 算法有穷性
D. 算法可读性
2.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个( )。 (满分:2)
A. 导数
B. 指数
C. 对数
D. 函数
3.下列排序算法中，其中( )是稳定的。 (满分:2)
A. 堆排序，冒泡排序
B. 快速排序，堆排序
C. 直接选择排序，归并排序
D. 归并排序，冒泡排序
4.八进制，就表示某一位置上的数运算时是逢( )进一位。 (满分:2)
A. 2
B. 8
C. 9
D. 10
5.设有如下函数定义int fun(int k){ if(k<1) return 0; else if(k==1) return 1; else return fun(k-1)+1; } 若执行调用语句：n=fun(3);，则函数fun 总共被调用的次数是( )。 (满分:2)
A. 2
B. 3
C. 4
D. 5
6.计算机能直接执行的语言是( )。 (满分:2)
A. 机器语言
B. 汇编语言
C. 高级语言
D. 目标语言
7.数制是人们利用( )进行计数的一种科学方法。 (满分:2)
A. 数字
B. 符号
C. 字母
D. 图形
8.伪代码是用介于( )和计算机语言之间的文字和符号来描述算法。 (满分:2)
A. 自然语言
B. 面向对象语言
C. 编程语言
D. 面向过程语言
9.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为( )。 (满分:2)
A. n+1
B. n-1
C. 2n
D. n/2
10.九进制，就表示某一位置上的数运算时是逢( )进一位。 (满分:2)
A. 2
B. 8
C. 9
D. 10
11.图中有关路径的定义是( )。 (满分:2)
A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
12.strcmp( )函数用来( )。 (满分:2)
A. 求字符串长度
B. 比较字符
C. 求子串
D. 字符串拷贝
13.字符数组在初始化时若数据个数少于数组长度,多余元素自动为( )。 (满分:2)
A. 空
B. 0
C. null
D. 随机
14.用计算机解决问题的过程可以分成哪三个阶段( )。 (满分:2)
A. 输入、算法设计和输出
B. 输入、测试和输出
C. 分析问题、设计算法和实现算法
D. 分析问题、测试和实现
15.strlen(str)是用来( )。 (满分:2)
A. 求字符串长度
B. 比较字符
C. 求子串
D. 字符串拷贝
16.从平均性能考虑，目前最好的内排序方法是( )排序法。 (满分:2)
A. 冒泡
B. 希尔插入
C. 交换
D. 快速
17.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )。 (满分:2)
A. （N+1）/2
B. N/2
C. N
D. [（1+N）*N ]/2
18.遗传算法主要模拟生物中的( )。 (满分:2)
A. 遗传、复制、传递和分裂
B. 遗传、突变、选择和杂交
C. 遗传、突变、传递和转录
D. 遗传、复制、转录和逆转录
19.对于长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为( )。 (满分:2)
A. log2n
B. n/2
C. n
D. n+1
20.( )主要是用来显示当前目录的名称或更改当前的目录。 (满分:2)
A. dir
B. cd
C. type
D. fc
二、多选题：
1.字符串有关的格式字符有( )。 (满分:4)
A. "%c"
B. "%d"
C. "%f"
D. "%s"
2.高精度运算主要解决( )。 (满分:4)
A.
B. 加数
C. 减数
D. 运算结果的输入
E. 运算结果的存储
3.递归算法的执行过程分( )和( )两个阶段。 (满分:4)
A. 递归
B. 递推
C. 回归
D. 回溯
4.设计递归算法有两点最为关键( )和( )。 (满分:4)
A. 确定递推公式
B. 确定边界（终了）条件（递归出口）
C. 每次递归调用，都必须向基本条件前进
D. 如果结果已知，那么，不用再重复调用递归
5.顺序结构、选择结构、循环结构三种结构共同特点是( ) (满分:4)
A. 只有一个入口
B. 只有一个出口
C. 结构内的每一部分都有机会被执行到（不存在死语句）
D. 结构内不存在死循环（永远执行不完的循环）。
三、判断题：
1.在任何情况下，顺序表中进行结点的插入操作时都不需要移动结点。 (满分:2)
A. 错误
B. 正确
2.归并排序在任何情况下都比所有简单排序速度快。 (满分:2)
A. 错误
B. 正确
3.gets( )函数一次可以输入多个字符串。 (满分:2)
A. 错误
B. 正确
4.设变量定义为char s[]=“hello”，则数组s中有6个元素。 (满分:2)
A. 错误
B. 正确
5.归并排序辅助存储为O（1）。 (满分:2)
A. 错误
B. 正确
6.int a; 说明整型数组a，有10个元素。 (满分:2)
A. 错误
B. 正确
7.某二叉树由5个度为2的结点以及3个度为1的结点，则该二叉树中共有15个结点。 (满分:2)
A. 错误
B. 正确
8.float b；定义b为5×6(5行6列)的数组。 (满分:2)
A. 错误
B. 正确
9.顺序查找法适合于存储结构为散列存储的线性表 (满分:2)
A. 错误
B. 正确
10.高精度计算时可以用数组来存储运算结果。 (满分:2)
A. 错误
B. 正确
11.折半查找的先决条件：表中结点按关键字有序，且顺序（一维数组）存储。 (满分:2)
A. 错误
B. 正确
12.字符串的结束标记在输出时也会被输出。 (满分:2)
A. 错误
B. 正确
13.scanf("%s",&str)这种用法是错误的。 (满分:2)
A. 错误
B. 正确
14.简单选择排序和冒泡排序都是一种不稳定排序方法。 (满分:2)
A. 错误
B. 正确
15.一个scanf函数输入多个字符串，输入时以“空格”键作为字符串间的分隔。 (满分:2)
A. 错误
B. 正确
16.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 (满分:2)
A. 错误
B. 正确
17.简单选择排序算法在最好情况下的时间复杂度为O（N）。 (满分:2)
A. 错误
B. 正确
18.为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。 (满分:2)
A. 错误
B. 正确
19.在任何情况下，归并排序都比简单插入排序快。 (满分:2)
A. 错误
B. 正确
20.字符数组不可用字符串来初始化 (满分:2)
A. 错误
B. 正确算法分析与设计17春在线作业2
一、单选题：
1.十六进制的基数是( )。 (满分:2)
A. 2
B. 8
C. 10
D. 16
2.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为( )。 (满分:2)
A. 63
B. 64
C. 6
D. 7
3.十进制数2024等值于十六制数为( )。 (满分:2)
A. 7E8
B. 6F7
C. 7AB
D. 3DF
4.下面关于二分查找的叙述正确的是( ) (满分:2)
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序，而且只能从小到大排列
C. 表必须有序且表中数据必须是整型，实型或字符型
D. 表必须有序，且表只能以顺序方式存储
5.下列数据结构中，能用二分法进行查找的是( )。 (满分:2)
A. 顺序存储的有序线性表
B. 线性链表
C. 二叉链表
D. 有序线性链表
6.深度优先搜索的搜索策略是( )。 (满分:2)
A. 尽可能“深”地搜索图
B. 尽可能“深”地搜索树
C. 尽可能“深”地搜索表
D. 尽可能“深”地搜索队列
7.一个算法中的语句的( )被称为语句频度或时间频度。 (满分:2)
A. 执行时间
B. 执行顺序
C. 执行速度
D. 执行次数
8.十进制算术表达式：3*512+7*64＋4*8＋5的运算结果，用二进制表示为( )。 (满分:2)
A. 10111100101
B. 11111100101
C. 11110100101
D. 11111101101
9.伪代码是用介于( )和计算机语言之间的文字和符号来描述算法。 (满分:2)
A. 自然语言
B. 面向对象语言
C. 编程语言
D. 面向过程语言
10.十六进制中最大的数码是( )。 (满分:2)
A. 16
B. 15
C. F
D. E
11.支持子程序调用的数据结构是( ) (满分:2)
A. 栈
B. 树
C. 队列
D. 二叉树
12.递归函数f(n)=f(n-1)+n(n>1)的递归出口是( )。 (满分:2)
A. f(1)=0
B. f(1)=1
C. f(0)=1
D. f(n)=n
13.C语言中，一般不能采用的命名规则为( )。 (满分:2)
A. 匈牙利命名法
B. 骆驼命名法
C. 下划线命名法
D. 图灵命名法
14.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树的总结点数为( )。 (满分:2)
A. 219
B. 221
C. 229
D. 231
15.字符串比较的函数是( )。 (满分:2)
A. strlen( )
B. strcpy( )
C. strcmp( )
D. strcat( )
16.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。 (满分:2)
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
17.有以下程序#includevoid fun(int x) { if(x/2>1) fun(x/2); printf("%d", x); } main( ){ fun(7); printf("\n"); } 程序运行后的输出结果是( )。 (满分:2)
A. 1 3 7
B. 7 3 1
C. 7 3
D. 3 7
18.九进制，就表示某一位置上的数运算时是逢( )进一位。 (满分:2)
A. 2
B. 8
C. 9
D. 10
19.十进制数2014等值于八进制数( )。 (满分:2)
A. 4028
B. 3736
C. 2726
D. 2014
20.数制是人们利用( )进行计数的一种科学方法。 (满分:2)
A. 数字
B. 符号
C. 字母
D. 图形
二、多选题：
1.顺序结构、选择结构、循环结构三种结构共同特点是( ) (满分:4)
A. 只有一个入口
B. 只有一个出口
C. 结构内的每一部分都有机会被执行到（不存在死语句）
D. 结构内不存在死循环（永远执行不完的循环）。
2.递归算法的执行过程分( )和( )两个阶段。 (满分:4)
A. 递归
B. 递推
C. 回归
D. 回溯
3.字符串有关的格式字符有( )。 (满分:4)
A. "%c"
B. "%d"
C. "%f"
D. "%s"
4.高精度运算主要解决( )。 (满分:4)
A.
B. 加数
C. 减数
D. 运算结果的输入
E. 运算结果的存储
5.设计递归算法有两点最为关键( )和( )。 (满分:4)
A. 确定递推公式
B. 确定边界（终了）条件（递归出口）
C. 每次递归调用，都必须向基本条件前进
D. 如果结果已知，那么，不用再重复调用递归
三、判断题：
1.简单选择排序的时间复杂度为n*n。 (满分:2)
A. 错误
B. 正确
2.有一组数据{6，202，100，301，38，8，1}，使用简单选择排序需要进行6趟比较。 (满分:2)
A. 错误
B. 正确
3.二叉树第i(i>=1)层上至多有2^(i-1)个结点。 (满分:2)
A. 错误
B. 正确
4.排序速度，进行外排序时，必须选用最快的内排序算法。 (满分:2)
A. 错误
B. 正确
5.在任何情况下，归并排序都比简单插入排序快。 (满分:2)
A. 错误
B. 正确
6.puts( )函数一次可以输出多个字符串。 (满分:2)
A. 错误
B. 正确
7.归并排序在任何情况下都比所有简单排序速度快。 (满分:2)
A. 错误
B. 正确
8.C语言允许对数组的大小作动态定义，即定义行中的数组长度能包括变量。 (满分:2)
A. 错误
B. 正确
9.当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为上溢。 (满分:2)
A. 错误
B. 正确
10.一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为ABCDEF54321。 (满分:2)
A. 错误
B. 正确
11.一棵二叉树第6层（根结点为第一层）的结点数最多为31个。 (满分:2)
A. 错误
B. 正确
12.一个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为54321ABCDEF。 (满分:2)
A. 错误
B. 正确
13.很多递归问题可转为递推，比如阶乘、 Fibonacci数列等。 (满分:2)
A. 错误
B. 正确
14.已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有12个叶子结点。 (满分:2)
A. 错误
B. 正确
15.puts不需要格式控制符，且自动换行。 (满分:2)
A. 错误
B. 正确
16.函数atoi("1234")的函数返回值是1234。 (满分:2)
A. 错误
B. 正确
17.在程序中关键字和变量名之间不需要加空格。 (满分:2)
A. 错误
B. 正确
18.高精度计算时可以用数组来存储运算结果。 (满分:2)
A. 错误
B. 正确
19.C程序执行的入口是main( )函数，所以main函数必须放在程序的开头。 (满分:2)
A. 错误
B. 正确
20.两个字符串中的字符个数相同时才能进行字符串大小的比较。 (满分:2)
A. 错误
B. 正确
页:
[1]