江开江苏开放大学算法设计与分析形考作业2最新答案

试题列表
单选题
题型：单选题客观题分值2分难度：简单得分：2
1
采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。
A
n/2
B
n
C
(n-1)/2
D
(n+1)/2
学生答案：D
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
2
对于顺序存储的有序表（5,12,20,26,37,42,46,50,64），若采用折半查找元素26的比较次数为（）。
A
3
B
5
C
2
D
4
学生答案：D
老师点评：
题型：单选题客观题分值2分难度：中等得分：2
3
用冒泡排序对4,5,6,3,2,1进行从小到大排序，第三趟排序后的状态为（）
A
2 1 3 4 5 6
B
3 2 1 4 5 6
C
4 3 2 1 5 6
D
4 5 3 2 1 6
学生答案：B
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
4
当待排序序列基本有序时，以下排序方法中，（）最不利于其优势的发挥。
A
快速排序
B
直接选择排序
C
直接插入排序
D
冒泡排序
学生答案：A
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
5
数据序列（8,9,10,4,5,6,20,1,2）只能是下列排序算法中的（ ）两趟排序后的结构。
A
堆排序
B
冒泡排序
C
选择排序
D
插入排序
学生答案：D
老师点评：
题型：单选题客观题分值2分难度：简单得分：2
6
就平均性能而言，目前最好的内排序方法是（ ）排序法。
A
希尔插入
B
快速
C
冒泡
D
交换
题型：单选题客观题分值2分难度：简单得分：2
7
在对一组关键字序列{70,55,100,15,33,65,50,40,95}，进行直接插入排序时，把65插入，需要 比较（）次。
A
6
B
8
C
4
D
2
题型：单选题客观题分值2分难度：简单得分：2
8
穷举法的适用范围（）。
A
解的个数极多的问题
B
一切问题
C
不适合设计算法
D
解的个数有限且可一一列举
题型：单选题客观题分值2分难度：一般得分：2
9
在待排序序列局部有序时，效率最高的排序算法是（）。
A
快速排序
B
归并排序
C
直接选择排序
D
直接插入排序
题型：单选题客观题分值2分难度：一般得分：2
10
在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（）。
A
直接插入排序
B
直接选择排序
C
快速排序
D
冒泡排序
题型：单选题客观题分值2分难度：中等得分：2
11
用冒泡排序法对数据7,6,3,9,2从小到大排序，共需经过（）趟排序已可以得到正确结果？
A
3
B
5
C
2
D
4
题型：单选题客观题分值2分难度：一般得分：2
12
递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A
栈
B
队列
C
线性表
D
多维数组
题型：单选题客观题分值2分难度：简单得分：2
13
线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
A
必须是连续的
B
部分地址必须是连续的
C
连续或不连续都可以
D
一定是不连续的
题型：单选题客观题分值2分难度：简单得分：2
14
算法分析中，记号O表示（ ）。
A
紧渐进界
B
非紧上界
C
渐进下界
D
渐进上界
题型：单选题客观题分值2分难度：简单得分：2
15
穷举法的适用范围是（）。
A
不适合设计算法
B
一切问题
C
解的个数有限且可一一列举
D
解的个数极多的问题
填空题
题型：填空题客观题答案不允许乱序分值2分难度：一般得分：2
1
.以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为 。
第1空分值：2分
2
在对一组记录序列{50,40,95,20,15，70,60,45,80}进行直接选择排序时，第4次交换和选择后，未排序记录为 。
3
在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用 。
4
在对一组记录序列{50,40,95,20,15，70,60,45,80}进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较 次。
5
在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的是 。
6
对n个结点进行快速排序，最大的比较次数是 。
7
n个记录的冒泡排序算法所需的最大移动次数为 ，最小移动次数为 。
8
以折半查找方法在一个查找表上进行查找时，该查找表必须组织成 存储的 表。
9
从有序表（12,18,30,43,56,78,82,95）中分别折半查找43和56元素时，其比较次数分别为 和 。
第1空分值：2分
第2空分值：2分
正确答案：1；3
10
下列是基于分治策略的快速排序算法的部分代码，请补全空格中缺失的代码。
template< class Type >
void QuickSort( Type a[], int p, int r )
{   if ( p < r )
{   int q = Partition( a, p, r );
; // 对左半段排序
; // 对右半段排序
}
}
第1空分值：2分
第2空分值：2分
简答题
1
什么是递归算法，递归算法的特点是什么。
2
【算法设计题】使用欧几里得公式写一个递归函数gcd(m,n)，用来计算m与n的最大公约数。
请给出具体实现代码。
3
【算法设计题】试打印出2~100中的所有素数。