大学MOOC 数据结构(厦门理工学院)1206512803 最新慕课完整章节测试答案
第一章 概论
第一章 概论 测验
1、单选题：
算法分析的两个主要方面是（ ）。
选项：
A: 空间复杂度和时间复杂度
B: 正确性和简单性
C: 可读性和文档性
D: 数据复杂性和程序复杂性
答案: 【 空间复杂度和时间复杂度】
2、单选题：
具有线性结构的数据结构是（ ）。
选项：
A: 图
B: 树
C: 广义表（线性表的推广）
D: 栈
答案: 【 栈】
3、单选题：
下面程序段的时间复杂度是（ ）。 for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]=i*j;
选项：
A: O(m^2) (注：m的平方)
B: O(n^2) (注：n的平方)
C: O(m*n)
D: O(m+n)
答案: 【 O(m*n)】
4、单选题：
抽象数据类型的三个组成部分分别为（ ）。
选项：
A: 数据对象、数据关系和基本操作
B: 数据元素、逻辑结构和存储结构
C: 数据项、数据元素和数据类型
D: 数据元素、数据结构和数据类型
答案: 【 数据对象、数据关系和基本操作】
5、单选题：
某算法的语句执行频度为（3n+nlog2n+n^2+8），其时间复杂度表示（ ）。
选项：
A: O(n)
B: O(nlog2n) （注：2是底）
C: O(n^2)（注：n的平方）
D: O(log2n)（注：2是底）
答案: 【 O(n^2)（注：n的平方）】
第二章 线性表
第二章 线性表 测验
1、单选题：
在线性表的下列存储结构中，读取元素花费的时间最少的是（ ）。
选项：
A: 单链表
B: 双链表
C: 循环链表
D: 顺序表
答案: 【 顺序表】
2、单选题：
在一个单链表中，若删除p所指向结点的后续结点，则执行（ ）。
选项：
A: p->next = p->next->next;
B: p = p->next; p->next = p->next->next;
C: p = p->next;
D: p = p->next->next;
答案: 【 p->next = p->next->next;】
3、单选题：
已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
选项：
A: q->next=s->next；s->next=p；
B: s->next=p；q->next=s->next；
C: p->next=s->next；s->next=q；
D: s->next=q；p->next=s->next；
答案: 【 q->next=s->next；s->next=p；】
4、单选题：
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（ ）。
选项：
A: s->next=p->next; p->next=s;
B: p->next=s->next;s->next=p;
C: q->next=s;s->next=p;
D: p->next=s;s->next=q;
答案: 【 q->next=s;s->next=p;】
5、单选题：
线性表L=(a1,a2,……,an)，下列说法正确的是（ ）。
选项：
A: 每个元素都有一个直接前驱和一个直接后继
B: 线性表中至少要有一个元素
C: 表中诸元素的排列顺序必须是由小到大或由大到小
D: 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继
答案: 【 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继】
6、填空题：
1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。int GetElem(LinkList L,int i,Elemtype *e){ LinkList p；int j； p=L->next; j=1; while(p&&j<i) { ; ++j; } if(!p||j>i) return ERROR; *e = p-data; return OK;}
答案: 【 p=p->next】
7、填空题：
函数实现单链表的插入算法，请在空格处将算法补充完整。int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s;int j; p=L;j=0; while((p!=NULL)&&(j<i-1)) { p=p->next;j++; } if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e; ; p-next=s; return OK;}
答案: 【 s-next=p-next】
8、填空题：
函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L, int i){ int k; if(i<1||i>L->length) return ERROR; for(k=i-1;k<L->length-1;k++) L->slist[k] = ; --L->Length ; return OK;}
答案: 【 L->slist[k+1]】
9、填空题：
函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q; int j; p=L;j=0; while((p-next!=null)&&(j<i-1)) { p=p->next; j++; } if(p->next==NULL||j>i-1) return ERROR; q=p->next; ; *s=q->data; free(q); return OK;}
答案: 【 p-next=q-next】
10、填空题：
下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedef struct node{ int data; struct node *next;}lklist; void lklistcreate(lklist &head){ for (i=1; i<=n; i++) { p=(lklist *)malloc(sizeof(lklist)); scanf("%d", &(p->data)); p->next=NULL; if(i==1) head=q=p; else { q->next=p; ; } } }/*lklistcreate*/
答案: 【 q=p】
第三章 栈与队列
第三章 栈和队列 测验
1、单选题：
设计一个判别表达式中括号是否配对的算法，采用（ ）数据结构最佳。
选项：
A: 顺序表
B: 链表
C: 队列
D: 栈
答案: 【 栈】
2、单选题：
判断一个循环队列Q（最多n个元素）为满的条件是（ ）。
选项：
A: Q->rear==Q->front
B: Q->rear==Q->front+1
C: Q->front==(Q->rear+1)%n
D: Q->front==(Q->rear-1)%n
答案: 【 Q->front==(Q->rear+1)%n】
3、单选题：
一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（ ）。
选项：
A: *S->top=e;S->top++;
B: S->top++;*S->top=e;
C: *S->top=e
D: S->top=e;
答案: 【 *S->top=e;S->top++; 】
4、单选题：
在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。
选项：
A: front=front->next;
B: s->next=rear;rear=s;
C: rear->next=s;rear=s;
D: s->next=front;front=s;
答案: 【 rear->next=s;rear=s;】
5、单选题：
在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。
选项：
A: 堆栈
B: 队列
C: 数组
D: 线性表
答案: 【 队列】
6、单选题：
栈和队列都是（ ）。
选项：
A: 链式存储的线性结构
B: 链式存储的非线性结构
C: 限制存取点的线性结构
D: 限制存取点的非线性结构
答案: 【 限制存取点的线性结构】
7、填空题：
已知栈的4个基本操作函数： (a) int InitStack(SqStack *S); //构造空栈 (b) int StackEmpty(SqStack *S); //判断栈空 (c) int Push(SqStack *S,ElemType e); //入栈 (d) int Pop(SqStack *S,ElemType *e); //出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。void conversion( ){ InitStack(S); scanf("%d", &N); //N为输入的十进制数 while(N) { ; N=N/8; } while(!StackEmpty(S)) { Pop(S, &e); //获取栈S中八进制的数字，赋值给e printf("%d", e); }}/*conversion*/
答案: 【 Push(S,N%8)】
8、填空题：
一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，则循环队列中元素的个数为( )。
答案: 【 (rear-front+M)%M】
9、填空题：
3、阅读算法f1, 设队列Q=(1,3,5,2,4,6)。写出执行算法f1后的队列Q;注, 答案如：1,2,3,4,5,6void f1(Queue *Q){ DataType e; if (!QueueEmpty(Q)) { e=DeQueue(Q); f1(Q); EnQueue(Q,e); }}
答案: 【 6,4,2,5,3,1】
10、填空题：
正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是top= 。
答案: 【 top-1】
第五章 二叉树
第五章 二叉树前半部分（5.1~5.4）测验
1、多选题：
下列关于二叉树性质的说法正确的有：（多选）Which sentences of the followings are right about a binary tree's characterization:（There are more than one correct answers）
选项：
A: 非空满二叉树的结点个数一定为奇数个。 The amount of nodes of a full binary tree with at least one node must be odd.
B: 非完全二叉树也可以用像完全二叉树那样使用顺序存储结构进行存储。Sequential storing structure can also be used to store an incomplete binary tree just like to store a complete binary tree.
C: 当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。If a complete binary tree is a full binary tree, it will be possible that leaf nodes is no t on the nethermost layer.
D: 完全二叉树最多只有最下面的一层结点度数可以小于2。For a complete binary tree, only the degrees of nodes on the nethermost layer could be less than 2.
E: 一棵非空二叉树的为空的外部结点数目等于其结点数加1。The amount of external null nodes in a binary tree with at least one node equals to its amount of nodes plus 1.
F: 满二叉树的所有结点的度均为2。All degrees of nodes in a full binary tree are 2.
答案: 【 非空满二叉树的结点个数一定为奇数个。 The amount of nodes of a full binary tree with at least one node must be odd.;
当一棵完全二叉树是满二叉树时，叶子结点不一定集中在最下面一层。If a complete binary tree is a full binary tree, it will be possible that leaf nodes is no t on the nethermost layer.;
一棵非空二叉树的为空的外部结点数目等于其结点数加1。The amount of external null nodes in a binary tree with at least one node equals to its amount of nodes plus 1.】
2、多选题：
下列关于二叉树遍历的说法正确的有:Which sentences of the followings are right about traversal of a binary tree:
选项：
A: 前序和中序遍历的顺序恰好一样的二叉树，只能是空二叉树或者独根二叉树这两种情况。Only the sequences of preorder and infix order of the binary tree with no nodes or only one node are the same.
B: 所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without left child tree are the same.
C: 所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without right child tree are the same.
D: 只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Only the sequences of preorder and post order of the binary tree with no nodes or only one node are the same.
E: 所有结点左子树为空的二叉树的前序和后序遍历顺序恰好一样。The sequences of preorder and post order of a binary tree with all nodes without left child tree are the same.
F: 所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。The sequences of preorder and post order of a binary tree with all nodes without left child tree are the same.
G: 只有空二叉树和一个根结点的二叉树这两种二叉树的中序和后序遍历的顺序恰好一样。Only the sequences of infix order and post order of the binary tree with no nodes or only one node are the same.
H: 所有结点左子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without left child tree are the same.
I: 所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without right child tree are the same.
J: 存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。There exists a binary tree with at least one node, whose preorder, infix order and post order are all the same.
答案: 【 所有结点左子树为空的二叉树的前序和中序遍历顺序恰好一样。The sequences of preorder and infix order of a binary tree with all nodes without left child tree are the same.;
只有空二叉树和一个根结点的二叉树这两种二叉树的前序和后序遍历的顺序恰好一样。Only the sequences of preorder and post order of the binary tree with no nodes or only one node are the same.;
所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。The sequences of infix order and post order of a binary tree with all nodes without right child tree are the same.;
存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。There exists a binary tree with at least one node, whose preorder, infix order and post order are all the same.】
3、填空题：
一棵有510个结点的完全二叉树的高度为多少？（独根树高度为1)What is the height of a complete binary tree with 510 nodes? (the height of a tree with only a root is 1)
答案: 【 9】
4、填空题：
一棵有512个结点的完全二叉树的高度为多少？（独根树高度为1）What is the height of a complete binary tree with 512 nodes? (the height of a tree with only a root is 1)
答案: 【 10】
5、填空题：
在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=________ (系统根据字符串匹配来判定答案