数据结构精选考研试题(4)

7．下图是带

权的有向图G的邻接表表示法。给出从结点V1到结点V8的最短路径。

8．在后序线索树中，要找出X结点的前趋结点，请写出相关语句 Ltag Lc Data Rtag Rc

四．编写程序，实现在链式存储方式下的模式匹配。

设主串s和子串t分别以单链表存储，t和s 中每个字符均用一结点表示： data Next

实现在链式存储方式下的模式匹配，即求子串t在主串s中第一次出现的位置指

针。[12分]

五、编写算法：

已知二叉树采用二叉链表方式存放，其中要求对二叉树从1开始进行连续编号，要求每个结点v的编号等于其左子树上最小编号加1，结点v的编号等于其右子树结点中最大编号加1，请回答采用什么次序的遍历方式实现编号？并给出在二叉树中结点的数据域部分填写实现如上要求编号的非递归算法。[13分]

六、编写算法：

已知深度为h的二叉树采用顺序存储结构已存放于数组BT〔1：2h－1〕中，请写一算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为

根结点所在链结点的指针由BT给出。[13分]

七、编写程序：

已知全省有m个学生参加计算机等级考试，其成绩值均为界于0～100之间的整数值，且成绩中有许多值重复出现多次，请按下列方法进行排序：另设数组num[0:100]，且令num[i]计算统计整数i在成绩数组中重复出现的次数，之后按num重排成绩数组，以达成绩数组递增有序。编写程序实现上述要求。[12分]

（2） 写一个判别给定的二叉树是否是完全二叉树的算法。