2020 数据结构(厦门理工学院)1462111450 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-10-07到2021-01-30
本篇答案更新状态:已完结

第一章 概论 第一章 概论 测验

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]=ij;
选项：
A:O(m^2)  (注：m的平方)
B:O(n^2)  (注：n的平方)
C:O(mn)
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、 问题:针对教材（注：数据结构(c语言版)，清华大学出版社，严蔚敏， ISBN：9787302147510）中的算法2.9和算法2.10，写程序主函数，调用ListInsert_L和ListDelete_L函数。要求：（1）提交pdf文档；（2）文档中有主函数，有对算法2.9和算法2.10的演示截图结果。
评分规则: 【 提交的文档格式为pdf
有主函数，且程序能够运行
有运行结果截图
代码风格良好
】

第三章 栈与队列 第三章 栈和队列 测验

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.】