MOOC 数据结构与算法(戴波)(电子科技大学)1461031175 最新慕课完整章节测试答案
第一章 绪论
绪论测验
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)
答案: 【 O(n*m)】
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的平方
答案: 【 O(sqrt(n)) 注释:sqrt(n)表示对n开方】
5、单选题:
下面程序段的时间复杂度是( )i=1;while(i<=n) i=i*3;
选项:
A: O(n)
B: O(3*n)
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.3 排序
讨论归并排序问题
1、单选题:
3,1,34,25,51,2,11采用迭代法,第一趟排序后的序列是( )
选项:
A: 1,3,25,34,2,11,51
B: 1,3,25,34,2,51,11
C: 1,3,34,2,11,25,51
D: 1,3,34,25,51,2,11
答案: 【 1,3,25,34,2,51,11】
2、单选题:
3,1,34,25,51,2,11采用归并排序的分治方法,第一趟划分的位置是( )
选项:
A: (3,1,34),(25,51,2,11)
B: (3,1,34,25),(51,2,11)
C: (3,1),(34,25),(51,2),(11)
D: (3),(1),(34),(25),(51),(2),(11)
答案: 【 (3,1,34,25),(51,2,11)】
讨论快速排序问题
1、单选题:
13,27,9,5,89,72,4的枢纽是( )
选项:
A: 13
B: 4
C: 5
D: 以上都可以,看选择枢纽的方法
答案: 【 以上都可以,看选择枢纽的方法】
2、单选题:
13,27,9,5,89,72,4进行快速排序,13为枢纽,第一次快排后的序列为( )
选项:
A: 5,4,9,13,89,72,27
B: 4,5,9,13,89,72,27
C: 4,5,9,13,89,72,27
D: 以上都对,快速排序将比枢纽小的数据放到枢纽前面,比枢纽大的放到枢纽大的数据放到后面的具体方法不同,可能得到不同的序列。
答案: 【 以上都对,快速排序将比枢纽小的数据放到枢纽前面,比枢纽大的放到枢纽大的数据放到后面的具体方法不同,可能得到不同的序列。】
第二章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(x<L->data[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) &nbs