2020 数据结构(中国海洋大学)1450374441 最新满分章节测试答案

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

第1章 绪论 第1章测验

1、 问题:图书馆的数目检索系统采用 关系的数据结构
选项：
A:集合
B:线性
C:树形
D:图状
答案: 【线性】

2、 问题: 是相互之间存在一种或多种特定关系的数据元素的集合。
选项：
A:数据
B:数据元素
C:数据项
D:数据结构
答案: 【数据结构】

3、 问题: 是一个值的集合和定义在这个值集上的一组操作的总称。
选项：
A:数据类型
B:数据元素
C:数据项
D:数据结构
答案: 【数据类型】

4、 问题:算法的确定性是指（ ）
选项：
A:当输入数据非法时，算法也能作出反应或进行处理
B:在任何情况下，算法不会出现死循环
C:算法中的每一条指令必须有确切的含义
D:算法中没有逻辑错误
答案: 【算法中的每一条指令必须有确切的含义】

【作业】第1章 绪论 第1章作业

1、 问题:说说数据结构和程序设计的关系
评分规则: 【 能说出关键点，且语句通顺
】

2、 问题:数据的逻辑关系，数据的存储结构及数据的运算之间存在着怎样的关系？
评分规则: 【 能正确地说出三者之间的关系
】

3、 问题:当你为解决某一问题而选择数据结构时，应从哪些方面考虑？在编辑管理通讯录时，什么样的数据结构合适？为什么？
评分规则: 【 要点基本回答正确
】

第3章 栈和队列 第3章测验

1、 问题:在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（ ）
选项：
A:front==rear
B:(front+1)%m==rear
C:rear+1==front
D:(rear+1)%m==front
答案: 【(rear+1)%m==front】

2、 问题:若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（ ）
选项：
A:SXSSXXXX
B:SXXSXSSX
C:SXSXXSSX
D:SSSXXSXX
答案: 【SSSXXSXX】

3、 问题:设计一个迷宫求解的算法，采用 数据结构最佳。
选项：
A:线性表的顺序存储结构
B:栈
C:队列
D:线性表的链式存储结构
答案: 【栈】

4、 问题:循环队列存储在数组A[0..m-1],则出队时的操作为（ ）
选项：
A:front=front+1
B:front=(front+1)mod (m-1)
C:ront=(front+1)mod m
D:front=(front mod m)+1
答案: 【ront=(front+1)mod m】

5、 问题:试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。BOOL Symmetry(char a[]){ int i=0; Stack s; InitStack(s); ElemType x; while(a[i]!=’&’ && a[i]){ ; i++; } if(a[i]) return FALSE; i++; while(a[i]){ Pop(s,x); if(x!=a[i]){ DestroyStack(s); return FALSE; } i++; } return TRUE;}
答案: 【Push(s,a[i])】

6、 问题:假设称正度和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。Status SymmetryString(char p){ Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(p){ Push(s,p); ; p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK;}
答案: 【EnQueue(q,p)】

【作业】第2章 线性表 第2章作业

1、 问题:设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
评分规则: 【 算法基本思路正确
逻辑无错误
算法整体可行
】

2、 问题:已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
评分规则: 【 算法基本思路正确
逻辑无错误，算法整体可行
算法能实现题目中的所有要求，并分析出算法的时间复杂度
】

【作业】第3章 栈和队列 第3章 作业

1、 问题:假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列
评分规则: 【 给出区分给定序列为合法序列或非法序列的一般准则
写出合理正确的证明过程
】

2、 问题:试证明：若借助栈由输入序列12…n得到的输出序列为P1P2…PN(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着i 写出合理正确的证明过程
】

3、 问题:若按教科书3.1.1节中图3.1(b)所示铁道进行车道(注意:两侧铁道均为单向行驶道)，则请回答：（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？（2）如果进站的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到(即写出‘S’表示进栈和以‘X’表示出栈的栈操作序列)
评分规则: 【 第一问回答正确
第二问回答正确，能说出合理的理由
】

4、 问题:简述线性表，栈和队列的相同点和不同点
评分规则: 【 能够准确的说清楚三者的异同点
】

第2章 线性表 第2章测验

1、 问题:用顺序结构存储，删除最后一个结点时（ ）
选项：
A:会移动其它结点位置
B:一定不会移动其它结点位置
C:可能会移动其它结点位置
D:其它
答案: 【一定不会移动其它结点位置】

2、 问题:链表中逻辑上相邻的元素的物理地址 相邻。
选项：
A:必定
B:不一定
C:一定不
D:其它
答案: 【不一定】

3、 问题:线性表中的数据元素有一个前驱多个后继
选项：
A:正确
B:错误
答案: 【错误】

4、 问题:假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。// 将合并逆置后的结果放在C表中，并删除B表Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C){ LinkList pa,pb,qa,qb; pa=A; pb=B; qa=pa; // 保存pa的前驱指针 qb=pb; // 保存pb的前驱指针 pa=pa->next; pb=pb->next; A->next=NULL; C=A; while(pa&&pb){ if(pa->datadata){ qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; } else{ qb=pb; pb=pb->next; //将当前最小结点插入A表表头 A->next=qb; } } while(pa){ qa=pa; pa=pa->next; qa->next=A->next; A->next=qa; } while(pb){ qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; } pb=B; free(pb); return OK;}
答案: 【qb->next=A->next;】

5、 问题:假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。Status ListDelete_CL(LinkList &S){ LinkList p,q; if(S==S->next)return ERROR; q=S; p=S->next; while( ){ q=p; p=p->next; } q->next=p->next; free(p)； return OK;}
答案: 【p->next!=s】

第4章 串 第四章测验

1、 问题:设s=’I AM A STUDENT’ , t=’GOOD’ , q=’WORKER’则Concat(Substring(s,6,2),Concat(t,Replace(s,’STUDENT’,q)))=( )
选项：
A:A GOOD I AM A WORKER
B:ST GOODSTUDENT
C:A GOOD STUDENT
D:A GOOD WORKER
答案: 【A GOOD I AM A WORKER】

2、 问题:设串sl=″Data Structures with Java″,s2=“it″，则子串定位函数index(s1,s2)的值为（　　）
选项：
A:15
B:16
C:17
D:18
答案: 【18】

3、 问题:空串与空格串是相同的。
选项：
A:正确
B:错误
答案: 【错误】

第5章 数组和广义表 第5章测验

1、 问题:数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是____。
选项：
A:80
B:100
C:240
D:270