资源描述：
《数据结构_王翠茹_数据结构习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题一1.简述下列术语：数据、数据元素、数据对象、数据结构、逻辑结构、存储结构、基本运算、运算实现和数据类型。2.设有数据结构(D,R）,其中D={d1,d2,d3,d4},R={r},r={(d1,d2),(d2,d3),(d3,d4)}.试按图论中图的画法惯例画出其逻辑结构图。3.函数f（M，n）按下式定义（m，n为≥0的整数）：f（m，n）=﹛m+n+1当m*n=0时f（m-1，（m，n-1））当m*n≠0时（1）试写出计算该函数的递归过程；（2）写出递归过程转换成非递归过程的转换规则。4.把数组A[1…n]按递减顺序排序,并分析其最坏情况时间复杂性量级。5.为了用计
2、算机实现学生档案管理,需要经过哪些主要步骤?每个步骤的主要工作是什么?试用本章讲到的从“具体到抽象”、再“从抽象到具体”的观点加以分析。6.试设定若干n值,比较两函数n2和50nlog2n的增长趋势,并确定n在什么范围内,函数n2值大于50nlog2n的值。习题二1.设线性表存于a（1：n）的前elenum个分量中,且递增有序。试写一算法,将X插入到线性表的适当位置上,以保持线性表的有序性。2.写一个逆置线性表的算法。即由A[1：n]产生B[1：n],使得B[1]=A[n],B[2]=A[n-1],…B[n]=A[1]。要求用最少的附加空间。3.设有编号为1,2,3,4的四
3、辆列车,顺序进入一个栈式结构的站台,试写出这四辆列车开出车站的所有可能顺序。4.设有六辆火车编号为1，2，3，4，5，6利用栈,将它们重新编成3，2，5，6，4，1的顺序。请写出操作序列，设X表示将一列火车从栈中开出；S表示将一列火车从输入端开入栈中。161.假设栈中每个数据项占K个空间位置,试改写入栈和出栈的算法。2.假设有两个栈如图所示共享空间[1..m]。试写一个对任一栈作入栈push（s,x，i）和出栈pop（s,i）。（i=1，2）的算法,只有在整个[1…m]空间均满时才产生溢出。6题图两个栈共享一个数组示意图3.按照四则运算加、减、乘、除和幂运算优先关系的惯例，
4、画出对下列算术表达式求值时操作数栈和运算符栈的变化过程。A-BXC/D+E↑F4.假设以数组cycque（0…m-1）存放循环队列的元素,同时设变量rear和quelen分别表示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满条件。并写出相应的入队列和出队列算法。（在出队列的算法中要返回队头元素）。5.已知Ackerman函数的定义如下：（1）试写出递归算法并画出m，n取值时工作栈状态变化情况。（2）写出非递归算法10.联系现实生活理解限制存取点的线性表。限制存取点的线性表有（1）栈和队列：本章中巳介绍.（2）双端队列：对所有的插入和删除都限定在表的两端进行的
5、线性表。10题图（1）双端队列(3〉双栈：规定从端1插入的元素只能从端1端删除,而从端2插入的元素只能从端2端删除。它是一种加限制的双端队列。好象两个底部相连的栈。1610题图(2)双栈习题三1.描述以下三个概念的区别：头指针、头结点、首元结点。2.试编写在无头结点的单链表上实现线性表基本运算LOCATE（L,X）、INSERT（L、X、i）和DELETE（L、i）的算法,并和在带头结点的单链表上实现相同运算的算法进行比较。3.试写出在不带头结点的单链表上实现线性表基本运算LENGTU（L）的算法。4.试写出一个把不带头结点的单链表逆转的算法。即将链表X=（a1,a2,…,
6、an）变成(an,an-1,…a2,a1),且将原来指向a1的头指针改为指向an。（要求用修改指针的方法来实现）。5.假设两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构.编写算法将A和B表归并成一个按元素值递减有序〈允许值相同〉排列的线性表C,并要求利用原表〈EPA和B表〉结点空间存放表C。6.设有两个线性表x=(x1,x2,…,xm)和y=〈y1,y2,…,yn〉.均以单链表为存储结构。写出一个将x,y合并为线性表z〈也是用链表方式存储〉的算法,使得Z={(x1,y1,x2,y2,…xmymym+1,…yn)当m≤n;(x1,y1,x2,y2,…xnynxn
7、+1,…xm）当m>n要求:z表利用单链表x，y的结点空间7.已知单链表L中的结点是按值非递减有序排列的,试写一算法将值为x的结点插入表L中,使得L仍然有序8.假设分别以两个元素值递增有序的线性表A、B表示两个集合〈即同一个线性表中的元素各不相同〉,现要求构成一个新的线性表C,C表示集合A与B的交,且C中元素也递增有序.试以单链表为存储结构,编写实现上述运算的算法9.已知A、B和C为三个元素值递增有序的线性表,现要求对表A作如下运算删除那些既在16表B中出现又在表C中出现的元素.试以链式存储结构,编写实现上述运算的
