下载文档原格式
数据结构期中考试试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序3. 在二叉树中，度为2的节点最多有多少个子节点？A. 1B. 2C. 3D. 44. 哈希表解决冲突的方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 树形结构法5. 以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 动态规划D. 克鲁斯卡尔算法6. 栈的特点是？A. 后进先出B. 先进后出C. 先进先出D. 后进后出7. 以下哪个不是二叉搜索树的性质？A. 左子树上所有节点的值小于它的根节点的值B. 右子树上所有节点的值大于它的根节点的值C. 左子树和右子树都是二叉搜索树D. 所有节点的值都相等8. 在数据库中，索引的作用是什么？A. 增加数据存储空间B. 提高数据检索效率C. 降低数据插入速度D. 减少数据存储量9. 以下哪个不是图的存储结构？A. 邻接矩阵B. 邻接表C. 树形结构D. 边列表10. 递归算法的基本思想是什么？A. 将问题分解为更小的子问题B. 重复执行相同的操作C. 将问题转化为非递归形式D. 避免使用循环结构二、填空题（每题2分，共20分）1. 在数据结构中，______是一种特殊的线性表，只允许在一端进行插入和删除操作。
2. 排序算法中，______排序的时间复杂度为O(n^2)，适用于小规模数据的排序。
3. 在图的表示中，______矩阵可以有效地表示稠密图。
4. 哈希表中，______是指两个关键字通过哈希函数得到同一个哈希地址。
5. 栈和队列的主要区别在于，栈是______，而队列是先进先出。
6. 二叉树的遍历方式包括前序遍历、中序遍历和______遍历。
第页/共 页 《数据结构》期中考试试卷一、选择题（每题2分，共40分）1．组成数据的基本单位是【 】。
A ．数据项B ．数据类型C ．数据元素D ．数据变量 2．线性表采用链式存储时，结点的存储地址【 】。
A ．必须是不连续的 B ．连续与否均可C ．必须是连续的D ．和头结点的存储地址相连续3. 有一个含头结点的单链表，头指针为head ，判断其是否为空的条件为【 】。
A ．head==NULL B ． head->next==NULL C ．head->next==head D ．head!=NULL 4．算法分析的目的是【 】。
A ．辨别数据结构的合理性B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性5．已知指针p 所指结点不是尾结点，若在*p 之后插入结点*s ，则应执行下列哪一个操作？【 】。
A. s->next = p ； p-> next = s ；B. s-> next = p-> next ； p-> next = s ；C. s-> next = p-> next ； p = s ；D. p-> next = s ； s-> next = p ； 6．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可 能出现的出栈序列为【 】。
A ．3，2，6，1，4，5B ．5，6，4，2，3，1C ．1，2，5，3，4，6D ．3，4，2，1，6，5 7．一个元素进入队列的时间复杂度是【 】。
A O(1)B O(n)C O(n 2)D O(log 2n) 8．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为【 】。
A 1140 B 1145 C 1120 D 1125 9．链表不具有的特点是【 】。
11-12学年2学期电⼦信息⼯程《数据结构》期中试卷11-12学年2学期电⼦信息⼯程《数据结构》期中试卷答题纸上只写班级姓名学号及每题答案。
1、单项选择题(本⼤题共30⼩题，每⼩题1分，共30分)在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的，请将其代码填写在题后的括号内。
错选、多选或未选均⽆分。
1.数据的不可分割的最⼩标识单位是（）A.数据项B.数据记录C.数据元素D.数据变量2.for(i=0;ifor(j=0;jc[i][j]=0;for(i=0;ifor(j=0;jfor(k=0;kc[i][j]=c[i][j]+a[i][k]*b[k][j];上列程序的时间复杂度为（）A.O(m+n×t)B.O(m+n+t)C.O(m×n×t)D.O(m×t+n)3.若线性表最常⽤的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储⽅式是（）A.单链表B.双链表C.单循环链表D.顺序表4.设单链表中指针p指向结点A，要删除A之后的结点(若存在)，则修改指针的操作为（）A.p—>next=p—>next—>nextB.p=p—>nextC.p=p—>next—>nextD.p—>next=p5.向⼀个栈顶指针为hs的链栈中插⼊⼀个*s结点时，应执⾏的操作为（）A.hs—>next=s;B.s—>next=hs;hs=s;C.s—>next=hs—>next;hs—>next=s;D.s—>next=hs;hs=hs—>next;6.设循环队列的元素存放在⼀维数组Q[0‥30]中，队列⾮空时，front指⽰队头元素的前⼀个位置，rear指⽰队尾元素。
如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（）A.Q[4]D.Q[15]7.定义⼆维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以⾏序为主序的存储⽅式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储⽅式下，该元素的存储地址为（）A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L8.具有n个结点的⼆叉树，拥有指向孩⼦结点的分⽀数⽬是（）A.n-1B.nC.n+1D.2n9.对⼀棵有100个结点的完全⼆叉树按层序编号，则编号为49的结点，它的左孩⼦的编号为（）A.99B.98C.97D.5010.有m个叶⼦结点的哈夫曼树，其结点总数是（）A.2m-1B.2mC.2m+1D.2(m+1)11.有n个结点的⽆向图的边数最多为（）A.n+1B.n(n-1)/2C.n(n+1)D.2n(n+1)12.设图的邻接矩阵为，则该图为（）A.有向图B.⽆向图C.强连通图D.完全图13.⼆分查找算法的时间复杂度是（）B.O(nlog2n)C.O(n)14.已知8个元素(34，76，45，18，26，54，92，65)，按照依次插⼊结点的⽅法⽣成⼀棵⼆叉排序树，则该树的深度为（）A.4B.5C.6D.715.采⽤排序算法对n个元素进⾏排序，其排序趟数肯定为n-1趟的排序⽅法是（）A.插⼊和快速B.冒泡和快速C.选择和插⼊D.选择和冒泡16.从逻辑上可以把数据结构分为（）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、⾮线性结构D.初等结构、构造型结构17.关于算法的描述，不正确的是（）A.算法最终必须由计算机程序实现B.所谓时间复杂度是指最坏情况下，估算算法执⾏时间的⼀个上界C.健壮的算法不会因⾮法的输⼊数据⽽出现莫名其妙的状态D.算法的优劣与算法描述语⾔⽆关18.在单链表中，存储每个结点需要有两个域，⼀个是数据域，另⼀个是指针域，指针域指向该结点的（）A.直接前趋B.直接后继C.开始结点D.终端结点19.将两个各有n个元素的有序表合并成⼀个有序表，其最少的⽐较次数为（）A.nB.2n-1C.2nD.n220.栈和队列共同具有的特点是（）A.都是先进后出B.都是先进先出C.只允许在端点进⾏操作运算D.既能先进先出，也能先进后出21.若⽤⼀个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。
一、单项选择题(本题总分 20分，每题 2分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母。
1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) 。
A.顺序表 B.链表 C.索引表 D.散列表采用排除法，顺序表存储位置表示数据元素的顺序关系，跟关键字无法；链表的地址是动态分配的；索引表是 按数据元素的关键字排序所得，它的数据元素是没有规律的2.在长度为 n 的顺序表的第 i(1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( A ) 。
A.n -i+1B.n -iC.iD.i -1代入计算法，我们知道在 i=n+1 时不需要移动元素3.若一棵二叉树的先序遍历序列为 a,b,c ，则由 abc 三个结点构成的二叉树个数为( B ) 。
A.4B.5C.6D.74.三维数组 A[4][5][6]按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存 储地址为 130，则元素 A[3][4][5]的存储地址为(B A.370B .368C .366) 。
D.372Loc(3,4,5)=loc(0,0,0)+(3*5*6+4*6+5)*2=130+119*2=368;5.高度为 h 的二叉树（仅含根结点的二叉树高度为 1）的结点最少是多少( D) 。
A. h+1B. 2hC. 2h －1D. h二叉树性质 26. 将两个各有 n 个元素的有序表归并成一个有序表，其最多的比较次数是( A. nB.n+1 C. 2n-1D. n-17. 已知一算术表达式的中缀形式为 A ＋B *C -D/E ，后缀形式为 ABC *+DE/-，其前缀形式为( C) 。
A )。
A. -+A*BC/DE C. -+*ABC/DEB. –A+B*CD/E D. –A+B*C/DE根据中缀和后缀表达式可画出表达树如下：- + /A* D EBC故前缀表达式为：-+A*BC/DE数据结构期中考试8．下面图示的顺序存储结构表示的二叉树是（ A ）。
数据结构期中试卷答案（信计11）嘉兴学院试卷2012 —2013学年第2学期期中考试试卷课程名称：数据结构使⽤班级：信计11级考试形式：闭卷在题⼲的括号内。
每个选择1分，共10分)1．抽象数据类型可⽤三元组（D，R，P）表⽰，其中R是 D 的有限集。
A．算法B．数据元素C．数据操作D．数据关系2．数据结构的研究包含三个⽅⾯的内容，它们分别是数据的 B 、数据的存储结构和数据运算。
A．数据元素B．逻辑结构C．存储结构D．计算⽅法3．线性结构的顺序存储结构是⼀种随机存取的存储结构，⽽链式存储结构是⼀种 A 的存储结构。
A．顺序存取 B．随机存取 C．索引存取 D．散列存取4．线性表L在 B 情况下，最适合使⽤链接结构实现算法。
A．不需经常对L进⾏修改 B．需经常对L进⾏删除和插⼊C．需经常修改L中结点值 D．L中结点结构复杂5．⼀个队列的⼊列序列是a，b，c，d，则队列的输出序列是 A 。
A．a，b，c，d B．a，d，c，b C．c，b，d，a D．d，c，b，a6．循环队列Q中的数据元素值存放在长度为m的数组中，且此数组最多只能存放m-1个数据元素。
已知头尾指针分别是Q．front和Q．rear, 则判断Q为满队列的条件是 B 。
A．Q．front= =Q．rear B．Q．front= =(Q．rear+1) %mC．Q．front!=Q．rear D．Q．front!= (Q．rear+1) %m7．⼀个栈的⼊栈序列是a, b, c, d, e, 则栈的不可能的输出序列是D 。
A．abcde B．decba C．edcba D．dceab8．判定⼀个顺序栈S（最多存放元素个数是m）为空栈的条件是 C 。
(顺序栈类型定义为：typedef struct {Selemtype *base;Selemtype *top;Int stacksize; } Sqstack；) A．S．top= =0 B．S．top= =m C．S．top= = S．base D．S．base= =0 9．从数据结构来看，串是⼀种特殊的线性表，其特殊性体现中 B 。
一、选择题（每小题2分，共30分）1. 数据结构是（ D ）。
A．一种数据类型 B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．以下与数据的存储结构无关的术语是（ D ）。
A．链队列 B. 链表 C. 顺序表 D. 栈3．以下数据结构中，（ A ）是非线性数据结构A．树 B．字符串 C．队 D．栈4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。
A．98 B．100 C．102 D．1065．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。
A．插入 B．删除 C．排序 D．查找6．线性表采用链式存储时，其地址(D )。
A．必须是连续的 B．一定是不连续的C．部分地址必须连续 D．连续与否均可以7．线性表是(A )。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空C．一个无限序列，可以为空 D．一个无限序列，不可以为空8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。
A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，19. 若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C ）。
A．k B．n-k-1 C．n-k+1 D．不确定10.对于队列操作数据的原则是（ A ）。
A. 先进先出B. 后进先出C. 先进后出D. 不分顺序11. 栈和队列的共同点是（ C ）。
A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。
A．front=front->next B．rear=rear->nextC．rear->next=front D．front->next＝rear13. 空串与空格串（ B ）。
《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。
数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。
2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。
3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。
在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。
顺序表中逻辑上相邻的元素的物理位置相邻。
单链表中逻辑上相邻的元素的物理位置不一定相邻。
单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。
在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。
4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。
在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。
给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。
5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
在p所指结点后插入s所指结点：4、1。
在p所指结点前插入s所指结点：7、11、8、4、1。
在表首插入s所指结点：5、12。
在表尾插入s所指结点：11、9、1、6。
1)p->next=s;2)p->next=p->next->next;3)p->next=s->next;4)s->next=p->next;5)s->next=L;6)s->next=NULL;7)q=p;8)while(p->next!=q) p=p->next;9)while(p->next!=NULL) p=p->next;10)p=q;11)p=L;12)L=s;13)L=p;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。
数据结构期中试卷及答案解析考试说明考试说明：考察前五章小题，难度接近真题。
满分100分，共20道选择题，每题5分。
请在60分钟内完成。
C T(n)=n3+5000nD T(n)=2nlogn-1000n参考答案：C本题考察时间复杂度，多个项相加时，只保留最高阶项由于巴啦啦能量——“常<对<幂<指<阶”，因此T(n)=logn+5000n=O(n)T(n)=n2-8000n=O(n2)T(n)=n3+5000n=O(n3)T(n)=2nlogn-1000n=O(nlogn)所以O(n3)复杂度最大，选C。
3.下列叙述中正确的是（）①线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比②线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关③线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比A. 仅①B. 仅②C. 仅③D. ①②③参考答案：A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比。
线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。
A. 单链表B. 双向链表C. 单循环链表D. 顺序表参考答案：D注意到，题目要求存取第i个元素及其前驱和后继，ABC三个选项找到第i个元素的时间复杂度均为O(n)，而D选项对于这3个位置的存取的时间复杂度均为O(1)，故选D。
5.静态链表中next域表示的是（）A 下一个元素的地址B 下一个元素的值C 当前元素的值D 下一个元素在数组中的位置参考答案：D静态链表一般保存在数组中，它和链表最大的区别是静态链表占用一段固定的区间，所以next域只需要表示下一个元素在数组中的下标即可而不是表示下一个元素的地址，选D。
6.对于不带头结点的链栈L（next域表示该结点下一个元素），top指针指向栈顶元素（栈顶在链头方向），则x结点进栈操作为A top->next=x;top=x;B top=x;top-next=x;C top=x;x->next=top;D x->next=top;top=x;参考答案：D本题考察链栈的操作x入栈之后x下一个元素为原来的top，所以先把x->next=top，然后更新top，栈顶元素指向x。
嘉兴学院试卷2012—2013 学年第1 学期期中考试试卷课程名称：数据结构使用班级：信息11级考试形式：开卷试卷代码：班级：姓名：学号：一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。
每小题1分，共10分)1．数据的逻辑结构从形式上可用二元组（D，R）表示，其中R是（ D ）的有限集。
A．算法B．数据元素C．数据操作D．数据关系2．数据结构课程研究的内容涉及到三个方面的内容，它们分别是数据的逻辑结构、数据的（C）和数据的操作。
A．数据元素B．逻辑结构C．存储结构D．计算方法3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种（ A ）的存储结构。
A．顺序存取 B．随机存取 C．索引存取 D．散列存取4．线性表L在（ B ）情况下，最适合采用链式存储结构来实现算法。
A．不需经常对L进行修改 B．需经常对L进行删除和插入操作C．需经常修改L中结点值 D．L中结点结构复杂5．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。
A.O(1)B. O(log2n)C. O(n)D. O(n2)6．在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（ A ）。
A．front==rear B. front= =rear && num==0C. front= =rear && num>0D. num= =maxSize7．一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的出栈序列是（ D ）。
A．abcde B．decba C．edcba D．dceab 8．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。
则顺序栈的判满的条件是（ C ）。
A．top = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-19．设线性表有n个元素，严格说来，以下操作中，（ B ）在顺序表上实现比链表上实现比链表上实现效率更高。
Ⅰ输出第i个（0≤i≤n-1）数据元素的值Ⅱ交换第3个数据元素与第4个数据元素的值Ⅲ顺序输出这n个数据元素的值A．Ⅰ B．Ⅰ、Ⅱ C．Ⅰ、Ⅲ D．Ⅱ、Ⅲ10. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列是（ D ）。
A．s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p);C. q.setNext(s.getNext()); s.setNext(p);D. p.setNext(s); s.setNext(q);二、填空题（20分，每空1分）1．算法的复杂度通常体现为时间复杂度和空间复杂度两个指标。
2．设有函数T (n)=3n2-n+4，T (n)=O ( n²)。
3．要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，会引起n-1-i个数据元素的移动。
4．队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。
队列具有先进先出的特点。
5．在一个单链表中删除p所指结点时，可执行如下操作：q=p.getNext(); p.setData(q.getData());p.setNext( q.getNext() );6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是3。
7．若双向链表的结点类描述为：public class DuLNode {pvivate Object data;private DuLNode piror;private DuLNode next;……}则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是：1）p.getPiror().setNext(s);2）s.setPiror(p.gettPiror());3）s.setNext(p);4）p.setPiror(s);8．在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为：class Node {命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：private Object data;private Node next:…… }则将一个新结点p入栈时修改链的两个对应语句是：1）p.setNext(top);2）top=p;9．如果循环顺序队列类的描述如下：class CircleSqQueeu {pvivate Object[ ] queueElem; //队列的存储空间pvivate int front;pvivate int rear;……}假设以少用一个存储单元的方法来区分队列判满和判空的条件，其中front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是(rear-front+queueElem.length)%queueElem.length。
10．在顺序存储、链式存储、索引存储和散列存储这4种存储方式中，最基本、最常用的两种存储结构是顺序存储和链式存储。
11．按数据元素的逻辑关系来系，数据结构可分为四种：线性表、集合、树和图。
其中图型结构中的数据元素之间存在“多对多”的关系。
12. 栈元素存储在数组stackElem中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top= =0；栈顶元素的访问形式是stackElem[top-1]。
三、判断题（共10分，2分1题，对的打“√”，错的打“×”）1. 线性表中数据元素的逻辑顺序与存储顺序总是一致的。
（×）2．链式存储时，存储区域可以连续，也可以不连续。
（√）3．删除顺序表中第0个数据元素a0的时间复杂度是O(n)。
（√）4．判断一个链栈为空的条件件是表达式的值为真。
（√）5．双向循环链表中，任意一结点的后继指针均指向其逻辑后继。
（×）四、应用与计算题（共26分）1．求下列程序段的时间复杂度。
（9分）（1）for (i=0; i<n; i++)for (j=0; j<i; j++)A[i][j]=0;时间复杂度是：O(n²)（2）a=0;b=1;for (i=0;i<=n; i++){ s=a+b;b=a;a=s;}时间复杂度是：O(n)（3）a=1; m=1;while(a<n){m+=a; a*=3;}时间复杂度是：O(log3n)2.设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a0,a1,…,a n-1}，R={<a i,a i+1>| i=0,1,…，n-2}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。
(共6分)3．对线性表A=（11, 22, 33, 44,55），画出下列存储结构的示意图：（共6分）（1）带表头结点的单链表；（2）不带表头结点的单向循环链表；（3）带表结点的双向循环链表。
命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：命题人或命题小组负责人签名： 所（室、教研部）负责人签名： 分院（部）领导签名：4. 建立链栈的基本思想是从空栈开始依次将入栈元素结点插入到栈顶。
假设依次入栈的元素为23、17、28、69、11，请画出将各元素结点分别入栈后的链栈示意图。
（5分）五、 根据以下各题的要求，分别写出相应的算法（用Java 语言描述）。
（共34分）1． 编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。
（8分） 已知顺序表类的描述为：class SqList {private Object[ ] listElem; privat int curLen;……}[参考答案]：（方法不唯一） public void nizhi(SqList L){ Object temp;for(int i=0;i<curLen/2;i++){ temp=listElem[i];listElem[i]=listElem[curLen-i-1]; listElem[curLen-i-1]=temp; } } 2．编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个整数值为x 的数据元素，并使单链表仍保持有序的操作。
（8分）已知单链表中的结点类和单链表类分别描述如下： class Node { //链表中的结点类 private Object data; private Node next;public Node(Object data){ //构造函数：构造一个数据域值为data 为结点this.data=data; this.next=null; } …… }clsss LinkList(){ //单链表类 private Node head; ……} [参考答案]：（方法不唯一）public void charu(int x){ Node p=head.getNext(); Node q=head; int temp;while (p!=null ){temp=((Integer)p.getData()).intValue(); if (temp<x) {q=p;p=p.getNext(); } elsebreak ; }Node s=new Node(x); s.setNext(p); q.setNext(s); }3．编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列，例、如：abba 和abdba 均是回文序列。
要求只借助栈来实现。
[参考答案]：（方法不唯一）public Boolean isPalindSeq(String str){ LinkStack s=new LinkStack;for(int i=0;i<str.length();i++) s.push(str.charAt(i));for(int i=0;i<str.length();i++){char c=((Character)S.pop()).charValue(); if(c!=str.charAt(i)) return false;}Return true;}4.假设采用带头结点的循环链表来表示队列，并且只设一个指向队尾元素的指针（不设队首指针），试编写相应的队列置空、队列判空、入队和出队操作的成员函数。
