山东科技大学425数据结构试卷2004考研试题研究生入学考试试题考研真题
● 摘要
科目代码：425 请在答题纸（本）上做题，在此试卷及草稿纸上做题无效！ 山东科技大学2004年招收硕士学位研究生入学考试
数据结构试卷
（共3页）
注意事项
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分）设有上三角矩阵(a ij ) n ×n ，将其上三角元素逐行存于数组B [m ]中（m 充分大）
，使得B [k ]=a ij 且k =f 1(i ) +f 2(j ) +c 。试推导出函数f 1，f 2和常数c （要求f 1和f 2中不含常数
项）。
第1页
6、（8分）设有三对角矩阵(a ij ) n ×n ，将其三条对角线上的元素逐行地存在于数组B [3n −2]中，使得B [k ]=a ij ，求：
（1）用i , j 表示k 的下标变换公式： （2）用k 表示i , j 的下标变换公式。
7、（7分）己知一棵度为k 的树中有n 1个度为1的结点，n 2个度为2的结点，……，n k 个度为
k 的结点，问该树中有多少个叶子结点？
8、（7分）试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态：并对所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 9、（8分）试证明求最短路径的Dijkstra 算法的正确性。 二、（15分）试基于图的广度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点v i 到顶点v j 的路径(i ≠j ) 。注意：算法中涉及的图的基本操作必须在此存储结构上实现。
三、（15）假设在算法描述语言中引入指针的二元运算“异或”（用“⊕”表示），若a 和b 为指针，则a ⊕b 的运算结果仍为原指针类型，且
a ⊕(a ⊕b ) =(a ⊕a ) ⊕b =b
(a ⊕b ) ⊕b =a ⊕(b ⊕b ) =a
则可利用一个指针域来实现双向链表L 0链表L 中的每个结点只含两个域：data 域和LRPtr 域，其中LRPtr 域存放该结点的左邻与右邻结点指针（不存在时为NULL ）的异或。若设指针L.left 指向链表中的最左结点，L.Right 指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。
第2页
相关内容
相关标签