苇市呻炕凯泄柿惜你澈温纫惫
第一章 绪论 绪论测验
1、 问题:下面（ ）术语与数据的存储结构无关
选项：
A:顺序表
B:链表
C:队列
D:顺序队列
答案: 【队列】
2、 问题:算法分析的目的是（ ）
选项：
A:找出数据结构的合理性
B:研究算法的输入与输出的关系
C:分析算法的效率以求改进
D:分析算法的易懂性和文档性
答案: 【分析算法的效率以求改进】
3、 问题:下面程序段的时间复杂度是（ ）for(i=0;i<n;i++) for(j=”0;j<m;j++)” a[i][j]=”0;” 选项：=”” a:=”” o(n*m)=”” b:o(n)=”” c:o(m)=”” d:o(n+m)=”” 答案:=”” 【<span=””> O(n*m)】</n;i++)>
4、 问题:下面程序段的时间复杂度是（ ）i=s=0;while(s<n){i++;s+=i;} 选项：=”” a:o(n)=”” b:o(s)=”” c:o(sqrt(n))=”” 注释：sqrt(n)表示对n开方=”” d:o(n^2)=”” 注释：n^2表示求n的平方=”” 答案:=”” 【<span=””>O(sqrt(n)) 注释：sqrt(n)表示对n开方】</n){i++;s+=i;}>
5、 问题:下面程序段的时间复杂度是（ ）i=1;while(i<=n) i=i3;
选项：
A:O(n)
B:O(3n)
C:O(n^3) 注释：n的立方的复杂度
D:O(logn) 注释：对数复杂度
答案: 【O(logn) 注释：对数复杂度】
6、 问题:数据的关系有逻辑关系和存储关系。其中逻辑关系是进行算法分析和设计需要考虑与使用的，而存储关系是编程实现的时候需要考虑的，逻辑关系和存储关系之间并没有关系
选项：
A:正确
B:错误
答案: 【错误】
7、 问题:下面的递归函数时间复杂度是O(1)int fact(int n){ if(n<=1)return 1; else return n*fact(n-1);}
选项：
A:正确
B:错误
答案: 【错误】
8、 问题:算法和程序都不能无穷的，否则会进入死循环
选项：
A:正确
B:错误
答案: 【错误】
9、 问题:数据包含数据对象，数据对象包含数据元素，数据元素包含数据项。
选项：
A:正确
B:错误
答案: 【正确】
10、 问题:算法可以用不同的语言描述，比如C或者java，所以算法实际上就是程序。
选项：
A:正确
B:错误
答案: 【错误】
第二章2.1 线性表 （本章内容比较多，需要2周的学习时间） 线性表测验
1、 问题:双向链表中有2个指针域pre和next，分别指向直接前驱和直接后继，假设有指针p指向链表中的一个结点，指针q指向一个待插入的结点，现在要求在p的前面插入q所指结点，则正确的插入语句为（ ）
选项：
A:p->pre=q;q->next=p;p->pre->next=q;q->pre=p->pre;
B:q->pre=p->pre;p->pre->next=q;q->next=p;p->pre=q->next;
C:q->next=p;p->next=q;p->pre->next=q;q->next=p;
D:p->pre->next=q; q->next=p; q->pre=p->pre;p->pre=q;
答案: 【p->pre->next=q; q->next=p; q->pre=p->pre;p->pre=q;】
2、 问题:在一个具有n个链结点的线性链表中，按数据内容查找某一个结点，如果查找成功，需要平均比较（ ）个结点。
选项：
A:n
B:n/2
C:(n+1)/2
D:(n-1)/2
答案: 【(n+1)/2】
3、 问题:假设按照行优先存储整数数组A[9][8]，第一个元素a11的首字节地址是100，每个整数占4个字节，则元素a32的存储地址是（ ）提示：数组大小是9行8列，第一个位置是1，不是0
选项：
A:164
B:168
C:144
D:172
答案: 【168】
4、 问题:一个栈的入栈序列是a,b,c,d,e,则不可能的出栈输出序列是（ ）
选项：
A:edcba
B:decba
C:dceab
D:abcde
答案: 【dceab】
5、 问题:当对一个线性表经常进行存取而很少进行插入及删除操作时，采用（ ）存储结构最节省时间；如果经常进行插入，删除操作时，则采用（ ）存储结构最节省时间。
选项：
A:顺序，顺序
B:顺序，链式
C:链式，链式
D:链式，顺序
答案: 【顺序，链式】
6、 问题:设顺序表L是一个非递减的有序表，下面的哪个算法，能够将元素x插入L中，并使L仍然有序。
选项：
A://L是顺序存储结构void insert(list L,elemtype x){ int i=1; while(i<=L->length) { if(x>L->data[i])i++; else L->data[i]=x; } }
B://L是顺序存储结构void insert(list L,elemtype x){ int i=L->length-1; while(i>=0) { if(xdata[i]){L->data[i+1]=L->data[i];–i;} } L->data[i]=x； L->length+=1;}
C://L是顺序存储结构void insert(list L,elemtype x){ int i=1; while(i<=L->length) { if(x>L->data[i]){L->data[i+1]=L->data[i];i++;} else {L->data[i]=x;break;} } }
D://L是顺序存储结构void insert(list L,elemtype x){ int i=L->length; while(i>=1) { if(xdata[i]){L->data[i+1]=L->data[i];–i;} L->data[i]=x; } }
答案: 【//L是顺序存储结构void insert(list *L,elemtype x){ int i=L->length-1; while(i>=0) { if(xdata[i]){L->data[i+1]=L->data[i];–i;} } L->data[i]=x； L->length+=1;}】
7、 问题:已知数据3,4,-2,0,8存储在顺序存储结构中，编程实现删除x的操作为（ ）提示：数据从顺序存储结构的第0个位置开始存储
选项：
A:void del(SqList L,elemtype x){ int i=0; while(i<l.length) {=”” if(x=”=L.data[i])L.data[i]=0;” i++;=”” }}=”” b:void=”” del(sqlist=”” l,elemtype=”” x){=”” int=”” i=”0;” while(i<l.length)=”” c:void=”” while(i=””>0 ) { if(x!=L.data[i])L.data[i-1]=L.data[i]; i–; }}
D:void del(SqList L,elemtype x){ int i=0,bfind=0; while(i<l.length-1) {=”” if(bfind=”=0″ &&=”” x=”=L.data[i])bfind=1;” if(bfind){l.data[i]=”L.data[i+1];}” i++;=”” }}=”” e:void=”” del(sqlist=”” l,elemtype=”” x){=”” int=”” i=”0;” while(i<l.length)=”” if(l.data[i]!=”x){” }=”” else=”” break;=”” while(i<l.length-1)=”” l.data[i]=”L.data[i+1];” i++;}=”” l.length–;}=”” 答案:=”” 【<span=””>void del(SqList L,elemtype x){ int i=0; while(i<l.length) {=”” if(l.data[i]!=”x){” i++;=”” }=”” else=”” break;=”” while(i<l.length-1)=”” l.data[i]=”L.data[i+1];” i++;}=”” l.length–;}<=”” span=””>】</l.length)></l.length-1)></l.length)>
8、 问题:已知不带头结点的单链表L，下面用函数实现的在第一个元素前面插入值为x的元素结点的算法错误的是（ ）
选项：
A:void insert(List L,elemtype x){ node d=new node(x); d.next=L; L=&d;}
B:List * insert(List L,elemtype x){ node d=new node(x); d.next=L; L=&d; return L;}
C:void insert(List L,elemtype x){ ptr p=L; node d=new node(x); ptr q=&d; p->next=q; L=&q;}
D:List insert(List L,elemtype x){ node d=new node(x); d.next=L; return &d;}
答案: 【void insert(List L,elemtype x){ ptr p=L; node d=new node(x); ptr q=&d; p->next=q; L=&q;}】
9、 问题:下面程序段的输出结果是（ ）void main(){ Queue Q; InitQueue(Q); char x=’e’,y=’c’; EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y); DeQueue(Q,x); EnQueue(Q,x); DeQueue(Q,x); EnQueue(Q,’a‘); while(!QueueEmpty(Q)){ DeQueue(Q,y); printf(y);} printf(x);
选项：
A:hrcha
B:rchah
C:rcha
D:char
答案: 【char】
10、 问题:当在一个有序的顺序存储表上查找一个数据时，可用折半查找，也可用顺序查找，但前者比后者的查找速度( )
选项：
A:一定快
B:不一定快
C:大部分情况下快
D:取决于表递增还是递减
答案: 【大部分情况下快】
11、 问题:已知有一系列输入数据为32,14,78,2,62,5,需要得到5,2,2,7,4,2，请问用什么数据结构支撑算法？
选项：
A:用栈将数据全部入栈，再出栈，出栈的数据取个位，就得到需要的输出序列。
B:用队列将数据全部入队，再全部出队，出队的时候取该数据的个位，就得到需要的输出序列。
C:用一个整数变量空间，把输入的数据依次存储，存储之后取个位，输出个位，再读入下一个数据。这样的空间利用率最高。
D:用数组存储输入的数据，再逆向输出所有数据。
答案: 【用栈将数据全部入栈，再出栈，出栈的数据取个位，就得到需要的输出序列。】
12、 问题:关键字越大，优先级越高。为了更好的为优先级高的顾客服务，银行应该采用什么存储结构支撑算法？
选项：
A:顺序存储结构
B:链式存储结构
C:有序数组
D:有序链表
答案: 【有序链表】
第二章 2.2 查找 查找测验
1、 问题:已知在长度为n的线性表中采用顺序查找，查找成功最好的比较次数是（ ），查找成功的最坏比较次数是（ ），查找失败的比较次数是（ ）
选项：
A:1，n,n
B:0，n,n+1
C:1,n,n+1
D:1,n+1,n+1
答案: 【1，n,n】
2、 问题:长度为n的有序顺序表采用折半查找，查找成功的最少次数为（ ），查找成功的最大次数为（ ），查找失败的最大次数为（ ），所以折半查找的最坏时间复杂度为（ ）
选项：
A:1,logn,logn,O(logn)
B:1,n,n,O(n)
C:1,n,logn,O(logn)
D:1,logn,n,O(n)
答案: 【1,logn,logn,O(logn)】
3、 问题:查找表如下分组(3,7,1,8,15),(22,43,18,45),(60,58,82,77,62),(90,88,99,100)，则索引表为（ ）,查找58需要比较（ ）次
选项：
A:(22,1),(60,6),(88,10),(101,15) 7
B:(15,1),(45,6),(82,10),(100,15),(NULL,19) 5
C:(15,1),(45,6),(82,10),(100,15) 5
D:(15,1),(45,6),(82,10),(100,15) 7
答案: 【(15,1),(45,6),(82,10),(100,15),(NULL,19) 5】
4、 问题:查找表32,45,18,77,5,23,44,19,7,3,哈希函数为H(key)=key %5,采用链地址法解决冲突的ASL(成功）=（ ），采用表长为11的线性探测再散列开放地址法的ASL(成功）=（ ），
选项：
A:18/10，32/10
B:18/5，31/10
C:18/10，31/10
D:18/5，32/10
答案: 【18/10，32/10】
5、 问题:哈希函数H(k)=k %11,采用开放地址法的平方探测再散列（di=1,4,9,16,……)解决冲突，输入关键字（9,31,26,19,1,13,2,11,27,16,21)，表长为13，建立的哈希表为（ ），ASL(成功）=（ ）
选项：
A:地址0123456789101112关键字1111322627161993121 查找次数11121121112 ASL(成功）=15/11
B:地址0123456789101112关键字1111322627161993121 查找次数11121121122 ASL（成功）=15/11
C:地址0123456789101112关键字1111322627161993121 查找次数11121121122 ASL(成功)=15/12
D:地址0123456789101112关键字1111322627161993121 查找次数11121121112 ASL(成功)=15/12
答案: 【地址0123456789101112关键字1111322627161993121 查找次数11121121122 ASL（成功）=15/11】
第二章 2.3 排序 排序测验
1、 问题:请对下列数据13，24，7，1，8，9，11，56，34，51，2，77，5，进行简单插入排序，冒泡排序（每趟大数冒到后面）和选择排序，2趟后的排序结果为：（ ）
选项：
A:2趟后的简单插入排序序列为：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：1，7，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5
B:2趟后的简单插入排序序列为：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：1，7，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，5，7，13，8，9，11，56，34，51，24，77
C:2趟后的简单插入排序序列为：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：7，1，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5
D:2趟后的简单插入排序序列为：7,13，1，24，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：1，7，8，9，11，13，24，34，2，5，51，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5
答案: 【2趟后的简单插入排序序列为：7,13，24，1，8，9，11，56，34，51，2，77，52趟后的冒泡排序为：7，1，8，9，11，13，24，34，2，51，5，56，772趟后的选择排序为：1，2，7，13，8，9，11，56，34，51，24，77，5】
2、 问题:已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，请采用2路归并递归排序算法进行排序，2趟排序后的结果为（ ）
选项：
A:13，7，24，1，8，9，11，56，34，51，2，5，77
B:1，7，13，24，8，9，11，34，51，56，2，5，77
C:7，13，24，1，8，9，11，34，51，56，2，5，77
D:13，24，1，7，8，9，11，34，56，51，2，77，5
答案: 【1，7，13，24，8，9，11，34，51，56，2，5，77】
3、 问题:已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，请采用快速归排序算法进行排序，其中枢纽采用3者取中法，2趟排序后的结果为（ ）注意：答案中的括号表示快排中的分组
选项：
A:（（2，5，1），（7，8），9）），11，（（13，34，24），51，（77，56））
B:（（1，2），5，（7，8，9，11）），13，（（24），34，（56，77，51））
C:（（1，2），5，（13，8，9，7）），11，（（24），34，（51，77，56））
D:（（2，5，1），7，（8，9）），11，（（13，34，24），51，（77，56））
答案: 【（（2，5，1），7，（8，9）），11，（（13，34，24），51，（77，56））】
4、 问题:已知输入数据13，24，7，1，8，9，11，56，34，51，2，77，5，增量序列d=5,3,1,请采用希尔排序算法进行排序，2趟排序后的结果为（ ）
选项：
A:1，7，5，2，8，9，24，11，34，51，13，77，56
B:1，7，8，9，13，24，11，34，51，2，5，56，77
C:2，11，5，1，8，9，24，7，34，51，13，77，56
D:2，5，11，1，8，9，7，24，34，13，51，77，56
答案: 【1，7，5，2，8，9，24，11，34，51，13，77，56】
5、 问题:已知输入数据1，2，8，5，9，11，34，56，51，77，请分析数据，采用（ ）排序算法效率最低
选项：
A:冒泡排序
B:简单插入排序
C:选择排序
D:三者取中法作为枢纽的快速排序
答案: 【选择排序】
第三章 递归与分治 递归与分治测验
1、 问题:已知某递归算法的复杂度为：T(n)=2T(n/2)+4,则求解该递归式的解为：（ ）
选项：
A:T(n)=O(1)
B:T(n)=O(n)
C:T(n)=O(n^2)
D:T(n)=O(nlogn)
答案: 【T(n)=O(n)】
2、 问题:分治法所能解决的问题一般具有以下几个特征:1.该问题的规模缩小到一定的程度就可以容易地解决；2. ______3. 利用该问题分解出的子问题的解可以合并为该问题的解；4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
选项：
A:最佳答案
B:最优解
C:最优子结构
D:最优值
E:最优方法
答案: 【最优子结构】
3、 问题:求一个数据序列的逆序数量不可以通过 ______排序中增加1个计数器实现。提示: 一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。
选项：
A:归并
B:简单插入
C:冒泡
D:堆排序
E:树形选择排序
答案: 【堆排序;
树形选择排序】
4、 问题:下面（ ）说法是正确的
选项：
A:所有问题都可以写递归程序
B:大部分递归程序可以转换为非递归程序，非递归程序运行速度更快。
C:所有递归程序都可以转换为非递归程序，且递归程序运行速度更快
D:递归程序可以把递归出口写在递归关系的后面
E:尾递归可以转换为循环
答案: 【大部分递归程序可以转换为非递归程序，非递归程序运行速度更快。;
尾递归可以转换为循环】
5、 问题:已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度，请完成下面分治法求解的代码： /**********/ /* 分治法 最大和子数组有三种情况： 1)A[1…mid] 2)A[mid+1…N] 3)A[i..mid..j] /**********/ //find max crossing left and right int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high) { const int infinite = -9999; int left_sum = infinite; int right_sum = infinite; int max_left = -1, max_right = -1; int sum = 0; //from mid to left; for (int i = mid; i >= low; i –) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } sum = 0; //from mid to right for (int j = mid + 1; j <= high; j ++) { sum += arr[j]; if (sum > right_sum) { right_sum = sum; max_right = j; } } return (left_sum + right_sum); } int Find_Maximum_Subarray(int arr[], int low, int high) { if (high == low) //only one element; return arr[low]; else { int mid = (low + high)/2; int leftSum = Find_Maximum_Subarray(arr, low, mid); int rightSum = Find_Maximum_Subarray(arr, mid+1, high); int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high); ——————————完成这里的代码—————————————————— } }
选项：
A:int tmp=(leftSum>rightSum?leftSum:rightSum;return (tmp>crossSum?tmp:crossSum);
B:if(leftSum>rightSum){ if(leftSum>crossSum)return leftSum;}else{ if(rightSum>crossSum)return rightSum;}
C:if(leftSum>rightSum>crossSum） return leftSum;if(rightSum>leftSum>crossSum) return rightSum;if(crossSum>leftSum>rightSum)return crossSum;
D:if(leftSum>rightSum && leftSum>crossSum） return leftSum;if(rightSum>leftSum && rightSum>crossSum) return rightSum;if(crossSum>leftSum && crossSum>rightSum)return crossSum;
答案: 【int tmp=(leftSum>rightSum?leftSum:rightSum;return (tmp>crossSum?tmp:crossSum);】
6、 问题:已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度，请完成下面分治法求解的代码： /**********/ /* 分治法 最大和子数组有三种情况： 1)A[1…mid] 2)A[mid+1…N] 3)A[i..mid..j] /**********/ //find max crossing left and right int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high) { const int infinite = -9999; int left_sum = infinite; int right_sum = infinite; int max_left = -1, max_right = -1; int sum = 0; //from mid to left; for (int i = mid; i >= low; i –) { sum += arr[i]; if (sum > left_sum) { left_sum = sum; max_left = i; } } sum = 0; //from mid to right for (int j = mid + 1; j <= high; j ++) { sum += arr[j]; if (sum > right_sum) { right_sum = sum; max_right = j; } } return (left_sum + right_sum); } int Find_Maximum_Subarray(int arr[], int low, int high) { if (high == low) //only one element; return arr[low]; else { int mid = (low + high)/2; int leftSum = Find_Maximum_Subarray(arr, low, mid); int rightSum = Find_Maximum_Subarray(arr, mid+1, high); int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high); ——————————完成这里的代码—————————————————— } }注意为了尽量减少答案的多样性，本次编程代码请通过>而不是<符号进行数据的比较。按照leftSum,rightSum,crossSum的顺序进行比较。运算符和操作数之间需要一个空格（括号除外）。如果造成困惑请见谅！
答案: 【(以下答案任选其一都对)if (leftSum >= rightSum && leftSum >= crossSum)
return leftSum;
else if (rightSum >= leftSum && rightSum >= crossSum)
return rightSum;
else
return crossSum;;
if(leftSum > rightSum){if(leftsum > crossSum)return left sum;else return crossSum;}
else if(rightSum > crossSum)return rightSum;
else return crossSum;;
return ((leftSum > rightSum ? leftSum : rightSum) > crossSum ? (leftSum > rightSum ? leftSum : rightSum) : crossSum;;
return ((leftSum > corssSum ? leftSum : corssSum) > rightSum ? (leftSum > corssSum ? leftSum : corssSum) : rightSum;】
7、 问题:已知某递归算法的复杂度为：T(n)=2T(n/2)+4,则求解该递归式的解为：（ ）
答案: 【O(n)】
8、 问题:分治法所能解决的问题一般具有以下几个特征:1.该问题的规模缩小到一定的程度就可以容易地解决；2. ______3. 利用该问题分解出的子问题的解可以合并为该问题的解；4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
答案: 【最优子结构】
9、 问题:求一个数据序列的逆序数量可以通过 ______排序中增加1个计数器实现。提示: 一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。
答案: 【(以下答案任选其一都对)归并;
简单插入;
冒泡】
10、 问题:大部分递归程序可以转换为非递归程序，____程序运行速度更快。
答案: 【非递归】
如需购买完整答案，请点击下方红字：
为了方便下次阅读，建议在浏览器添加书签收藏本网页
添加书签方法：
1.电脑按键盘的Ctrl键+D键即可收藏本网页
2.手机浏览器可以添加书签收藏本网页
获取更多慕课答案，欢迎在浏览器访问我们的网站：http://mooc.mengmianren.com
注：请切换至英文输入法输入域名，如果没有成功进入网站，请输入完整域名：http://mooc.mengmianren.com/
我们的公众号
打开手机微信，扫一扫下方二维码，关注微信公众号：萌面人APP
本公众号可查看各种网课答案，还可免费查看大学教材答案
点击这里，可查看公众号功能介绍
APP下载
APP功能说明
1.可查看各种网课答案
点击【萌面人官网】，可查看知到智慧树，超星尔雅学习通，学堂在线等网课答案
点击【中国大学慕课答案】，可查看mooc慕课答案
2.可一键领取淘宝/天猫/京东/拼多多无门槛优惠券
如图所示，点击对应图标即可领取淘宝/天猫/京东/拼多多无门槛优惠券
朵伞握柬锹凄漏山计遂妮惮我