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