资源描述：
《数据结构期末题型归纳测试.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、编写算法实现单链表的就地逆置，即要求利用原单链表的节点空间，把数据元素序列(a0，a1,…,an-1)逆置为（an-1,…,a1,a0）。（15分）typedefintDataType;typedefstructNode{DataTypdedata;structNode*next;}SLNode;voidConverse(SLNode*head){SLNode*p,*q;p=head->next;head->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=head->next
2、;head->next=q;}}二、对于一个堆栈，（15分）（1）如果输入序列有A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。（2）设有n个数据元素的序列顺序进栈，试给出可能的输出序列个数。（3）设有n个数据元素的序列顺序进栈，试给出不可能的输出序列个数。（4）以n=4为例，用（2）和（3）中得出的公式验证（1）的结论。(1)队列有：ABCD,ABDC,ACBD,ACDB,ADCB,BACD,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA不可能的输出队列有：DABC,ADBC
3、,DACB,DBAC,BDAC,DBCA,DCAB,CDAB,CADB,CABD(2)可能的输出序列个数为：（3）对有n个数据元素的序列，全部可能的排列个数，所以，不可能的输出序列个数为：（4）当n=4时，有，与（1）中得出的结论个数相符，说明（1）中得出的结论是正确的。一、给出采用设置标志位的方法解决“假溢出”问题的顺序循环队列的初始化操作、入队列操作和出队列操作的算法思想。（15分）设MaxSize为顺序循环队列的数组最大个数，front为对头指针，rear为队尾指针，tag为标志。初始化操作算法思想：置对头指针fron
4、t=0，队尾指针rear=0，标志tag=0；入队列操作算法思想：（1）判断是否为满队列，对满时推出，对满的条件为rear==front并且tag=1（2）当队列不满时，把要入队列的数据元素插入到队尾（3）修改队尾指针，rear=（rear+1）%MaxSize;（4）判断并标记是否对满，当rear=front时置tag=1。出队列操作算法思想：（1）判断队列是否为空，队空时推出，对空的条件为rear==front并且tag==0（2）当队列不空时，把当前对头元素从对头删除；（3）修改对头指针，front==(front+1
5、)%MaxSize；（4）置标记tag为非满状态，即置tag=0。二、对于如下所示的稀疏矩阵A：（20分）（1）写出该稀疏矩阵的三元组线性表（2）画出稀疏矩阵A的三元组顺序表结构（3）画出稀疏矩阵A的带头节点单链表结构（4）画出稀疏矩阵A的行指针数组链表结构（5）画出稀疏矩阵A的三元组十字链表结构。五、给定如图所示的数，请完成下述操作：（20分）（1）给出书的先根遍历和后根遍历得到的节点序列（2）将该树转换为二叉树（3）给出该二叉树的先序、后序、中序遍历结果。（4）给出该二叉树的前序、中序、后序线索二叉树。六、若一棵树有m1
6、个度为1的结点，有m2个度为2的结点…有mk个度为k的结点，问：树中共有多少个叶结点。（15分）假设初始时该树只存在一个根节点，该根节点的度为0，此时该树的叶节点个数为1.每加一个度为1的节点时，均产生一个新叶节点，同时占去原先一个叶节点，故叶节点数不变，即此时增加了（1-1）*m1=0个节点。每增加一个度为2的节点时，均产生两个新叶节点，同时占去原先一个叶节点，故在原先叶节点数上加2-1个叶节点；又存在m2个度为2的节点，故此时增加了（2-1）*m2个叶节点。以此类推，每增加一个度为k的节点时，均产生k个新叶节点，同时占去
7、原先一个叶节点，故在原先叶节点数上加k-1个叶节点；又存在mk个度为k的节点，故此时增加了（k-1）*mk个叶节点。所以，总的叶节点数N为：
