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

1、精选文档一、 编写算法实现单链表的就地逆置，即要求利用原单链表的节点空间，把数据元素序列(a0，a1,an-1) 逆置为（an-1,a1,a0）。（15分） typedef int DataType;typedef struct NodeDataTypde 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->n

2、ext;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,DACB,DBAC,BDAC,DBCA,DCA

3、B,CDAB,CADB,CABD(2) 可能的输出序列个数为：（3）对有n个数据元素的序列，全部可能的排列个数，所以，不可能的输出序列个数为：（4）当n=4时，有，与（1）中得出的结论个数相符，说明（1）中得出的结论是正确的。三、 给出采用设置标志位的方法解决“假溢出”问题的顺序循环队列的初始化操作、入队列操作和出队列操作的算法思想。（15分）设MaxSize为顺序循环队列的数组最大个数，front为对头指针，rear为队尾指针，tag为标志。初始化操作算法思想：置对头指针front=0，队尾指针rear=0，标志tag=0；入队列操作算法思想：（1） 判断是否为满队列，对满时推出，对满的条件

4、为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)%MaxSize；（4） 置标记tag为非满状态，即置tag=0。四、 对于如下所示的稀疏矩阵A：（20分）（1） 写出该稀疏矩阵的三元组线性表（2） 画出稀疏矩阵A的三元组顺

5、序表结构（3） 画出稀疏矩阵A的带头节点单链表结构（4） 画出稀疏矩阵A的行指针数组链表结构（5） 画出稀疏矩阵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的节点时，