资源描述：
《数据结构基础-南理工泰州科技学院》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、习题一绪论1简要回答术语：数据，数据元素，数据结构，数据类型。2数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？3数据结构的主要运算包括哪些？4算法分析的目的是什么？算法分析的主要方面是什么？5分析以下程序段的时间复杂度，请说明分析的理由或原因。⑴Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}⑵Sum2(intn){intsum=0,m,t;for(m=1;m<=n;m++){p=1;for(t=1;t
2、<=m;t++)p*=t;sum+=p;}return(sum);}⑶递归函数fact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}13习题二线性表1简述下列术语：线性表，顺序表，链表。2何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?3在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?4链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又
3、如何理解?5设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。5写一求单链表的结点数目ListLength(L)的算法。6写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。7设线性表中的元素按值递增有序，以带头结点head的单链表作存储结构，写一算法删除表中大于等于min且小于等于max的元素（若表中存在这样的元素），同时释放被删结点的空间。8写一算法将带有头结点head的单链表逆置。9写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的
4、参数，可以和表中的元素相同，也可以不同)。10设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。13习题三栈和队列1设有一个栈，元素进栈的次序为a,b,c。问经过栈操作后可以得到哪些输出序列？2循环队列的优点是什么?如何判断它的空和满?3设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？4设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？5利用栈的基本操作，写一个返回栈S中结点个数
5、的算法intStackSize(SeqStackS)，并说明S为何不作为指针参数的算法?6一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S)，入栈Push(S,i,x)，出栈Pop(S,i,x)算法，其中i为0或1，用以表示栈号。7设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。a,b,c,d入队a,b,c出队i,j,k,l,m入队d,
6、i出队n,o,p,q,r入队8假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。d,e,b,g,h入队13d,e出队i,j,k,l,m入队b出队n,o,p,q,r入队13习题六树和二叉树⑴假设在树中，结点x是结点y的双亲时，用(x,y)来表示树边。已知一棵树的树边集合为{(e,i),(b,e),(b,d),(a,b),(g,j),(c,g),(c,f),(h,l),(c,h),(a,c)}，用树型表示法表示该树，
7、并回答下列问题：①哪个是根结点?哪些是叶子结点?哪个是g的双亲?哪些是g的祖先?哪些是g的孩子?那些是e的子孙?哪些是e的兄弟?哪些是f的兄弟?②b和n的层次各是多少?树的深度是多少?以结点c为根的子树的深度是多少?⑵一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：①各层的结点数是多少?②编号为i的结点的双亲结点(若存在)的编号是多少?③编号为i的结点的第j个孩子结点(若存在)的编号是多少?④编号为i的结点的有
8、右兄弟的条件是什么?其右兄弟的编号是多少?⑶设有如图6-27所示的二叉树。①分别用顺序存储方法和链接存储方法画出该二叉树的存储结构。②写出该二叉树的先序、中序、后序遍历序列。⑷已知一棵二叉树的先序遍历序列和中序遍历序列分别为ABDGHCEFI和GDHBAECIF13，请画出这棵二叉树，然后给出该树的后序遍历序列。⑸设一棵二叉树的中序遍历序列和后
