- —四川最大高校综合门户网
注意事项 1、答案一律写在答题纸上； 2、答卷应字迹清楚，语义确切； 3、算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释； 4、算法用C语言或自然语言编写。 一、解答下列问题（共70分） 1、（8分）描述以下三个
注意事项
1、答案一律写在答题纸上；
2、答卷应字迹清楚，语义确切；
3、算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清晰、简明易懂，应加上必要的注释；
4、算法用C语言或自然语言编写。
一、解答下列问题（共70分）
1、（8分）描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
2、（8分）试写出一算法，对单链表实现就地逆置。
3、（8分）假设以S和X分别表示入栈和出栈的操作，则初态和终态均为栈空的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
4、（8分）若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列：
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列：
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列：
5、（8分）设有上三角矩阵 ，将其上三角元素逐行存于数组 中（m充分大），使得 且 。试推导出函数 ， 和常数c（要求 和 中不含常数项）。
第1页
6、（8分）设有三对角矩阵 ，将其三条对角线上的元素逐行地存在于数组 中，使得 ，求：
（1）用 表示 的下标变换公式：
（2）用 表示 的下标变换公式。
7、（7分）己知一棵度为 的树中有 个度为1的结点， 个度为2的结点，……， 个度为 的结点，问该树中有多少个叶子结点？
8、（7分）试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态：并对所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
9、（8分）试证明求最短路径的Dijkstra算法的正确性。
二、（15分）试基于图的广度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点 到顶点 的路径 。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
三、（15）假设在算法描述语言中引入指针的二元运算“异或”（用“ ”表示），若a和b为指针，则a b的运算结果仍为原指针类型，且
则可利用一个指针域来实现双向链表 链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。
第2页
四、（15分）编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应添上。
五、（20分）若在DAG图中存在一个顶点r，在r和图中所有其他顶点之间均存在由r出发的有向路径，则称该DAG图有限。试编写求DAG图的根算法。
六、（15分）己知两个有序序列 和 ，并且其中一个序列的记录个数少于S，且 。试写一个算法，用 时间和 附加空间完成这两个有序序列的归并。