数据结构期末题型归纳测试.docVIP

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