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

1、WORD格式一、编写算法实现单链表的就地逆置，即要求利用原单链表的节点空间，把数据元素序列 (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-&

2、gt;next;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,BDA

3、C,DBCA,DCAB,CDAB,CADB,CABD(2) 可能的输出序列个数为：C n1( 2n)!n*1 (n! ) 23对有 n 个数据元素的序列，全部可能的排列个数Pn n! ，所以，不可能的输出序列个数为： Pn C n4当 n=4 时，有C414, P4C 4 24 14 10 ，与1中得出的结论个数相符，说明专业资料整理WORD格式1中得出的结论是正确的。专业资料整理WORD格式三、给出采用设置标志位的方法解决队列操作和出队列操作的算法思想。“假溢出 问题的顺序循环队列的初始化操作、15 分入专业资料整理WORD格式设 MaxSize 为顺序循环队列的数组最大个数，front 为

4、对头指针， rear 为队尾指针，为标志。初始化操作算法思想：置对头指针front=0 ，队尾指针rear=0，标志 tag=0；入队列操作算法思想：1判断是否为满队列，对满时推出，对满的条件为rear=front 并且 tag=1tag专业资料整理WORD格式（ 2 当队列不满时，把要入队列的数据元素插入到队尾（ 3 修改队尾指针， rear= rear+1 %MaxSize;（ 4 判断并标记是否对满，当 rear=front 时置 tag=1。出队列操作算法思想：1判断队列是否为空，队空时推出，对空的条件为rear=front 并且 tag=0（ 2 当队列不空时，把当前对头元素从对头删

5、除；（ 3 修改对头指针， front=(front+1)%MaxSize ；（ 4 置标记 tag 为非满状态，即置 tag=0。四、对于如下所示的稀疏矩阵A ： 20 分（ 1 写出该稀疏矩阵的三元组线性表（ 2 画出稀疏矩阵 A 的三元组顺序表构造（ 3 画出稀疏矩阵 A 的带头节点单链表构造（ 4 画出稀疏矩阵 A 的行指针数组链表构造（ 5 画出稀疏矩阵 A 的三元组十字链表构造。五、给定如下列图的数，请完成下述操作：20 分（ 1给出书的先根遍历和后根遍历得到的节点序列（ 2将该树转换为二叉树（ 3给出该二叉树的先序、后序、中序遍历结果。（ 4给出该二叉树的前序、中序、后序线索二叉

6、树。六、假设一棵树有m1 个度为 1 的结点，有m2 个度为 2 的结点有 mk 个度为 k 的结点，问：专业资料整理WORD格式树中共有多少个叶结点。15 分假设初始时该树只存在一个根节点，该根节点的度为0，此时该树的叶节点个数为1.每加一个度为1 的节点时， 均产生一个新叶节点，同时占去原先一个叶节点，故叶节点数不变，即此时增加了1-1 *m1=0 个节点。每增加一个度为2 的节点时， 均产生两个新叶节点，同时占去原先一个叶节点，故在原先叶节点数上加2-1 个叶节点；又存在m2 个度为 2 的节点，故此时增加了2-1*m2 个叶节点。以此类推， 每增加一个度为k 的节点时， 均产生 k 个新叶节点， 同时占去原先一个叶节点，故在原先叶节点数上加k-1 个叶节点； 又存在 mk 个度为 k 的节点， 故此时增加了