大学MOOC 数据结构与算法(西华大学)1456404166 最新慕课完整章节测试答案
第一章绪论
文章目录
绪论测验
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)
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; while(i>=1) { if(x<L->data[i]){L->data[i+1]=L->data[i];--i;} else {L->data[i]=x;break;} } 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(x<L->data[i]){L->data[i+1]=L->data[i];--i;} L->data[i]=x; } }
答案: 【 //L是顺序存储结构void insert(list *L,elemtype x){ int i=L->length; while(i>=1) { if(x<L->data[i]){L->data[i+1]=L->data[i];--i;} else {L->data[i]=x;break;} } 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) { if(x==L.data[i])L.data[i]=-1; i++; }}
C: void del(SqList L,elemtype x){ int i=L.length; 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++; }}
答案: 【 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++; }}】
8、单选题：
已知不带头结点的单链表L，下面用函数实现的在第一个元素前面插入值为x的元素结点的算法错误的是（ ）
选项：
A: void insert(List *L,elemtype x){ ptr p=*L; node d=new node(x); ptr q=&d; q->next=p; L=&q;}
B: List * insert(List *L,elemtype x){ ptr p=*L; node d=new node(x); ptr q=&d; q->next=p; L=&q; 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){ ptr p=*L; node d=new node(x); ptr q=&d; q->next=p; return &q;}
答案: 【 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: 取决于表递增还是递减
答案: 【 大部分情况下快】
第二章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) &nb