当前位置: 首页 > >

2014年安徽省C++语言版摘要

发布时间:

1、有一种简单的排序算法,叫做计数排序(count

sorting) 。这种排序算法对一个待排序

的表(用数组表示)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所 有待排序的关键码互不相同,计数排序算法针对表中的每个记录,扫描待排序的表一趟,统 计表中有多少个记录的关键码比该记录的关键码小,假设针对某一个记录,统计出的计数值 为 c,那么,这个记录在新的有序表中的合适的存放位置即为 c。 (1) (3 分)给出适用于计数排序的数据表定义; (2) (7 分)使用 Pascal 或 C 语言编写实现计数排序的算法; (3) (4 分)对于有 n 个记录的表,关键码比较次数是多少? (4) (3 分)与简单选择排序相比较,这种方法是否更好?为什么? 2、证明由二叉树的中序序列和后序序列,也可以唯一确定一棵二叉树。 当 n=1 时,只有一个根结点,由中序序列和后序序列可以确定这棵二叉树。 设当 n=m-1 时结论成立,现证明当 n=m 时结论成立。 设中序序列为 S1 , S2, ?, Sm, 后序序列是 P1,P2,?, Pm。 因后序序列最后一个元素 Pm 是根, 则在中序序列中可找到与 Pm 相等的结点(设二叉树中各结点互不相同)Si(1 ≤i≤m) ,因中 序序列是由中序遍历而得,所以 Si 是根结点,S1,S2 ,?,Si-1 是左子树的中序序列,而 Si+1,Si+2, ?,Sm 是右子树的中序序列。 若 i=1,则 S1 是根,这时二叉树的左子树为空,右子树的结点数是 m-1, 则{S2,S3,?,Sm} 和{P1,P2,?,Pm-1}可以唯一确定右子树,从而也确定了二叉树。 若 i=m,则 Sm 是根, 这时二叉树的右子树为空, 左子树的结点数是 m-1, 则 {S1 , S2, ?, Sm-1} 和{P1,P2,?,Pm-1}唯一确定左子树,从而也确定了二叉树。 最后,当 1<i<m 时,Si 把中序序列分成{S1 ,S2,?,Si-1} 和{Si+1,Si+2,?,Sm}。由于后 序遍历是“左子树—右子树—根结点” ,所以{P1,P2,?,Pi-1}和{Pi,Pi+1,? Pm-1}是二叉树 的左子树和右子树的后序遍历序列。因而由{S1, S2,?, Si-1}和{P1,P2,?,Pi-1} 可唯一确定二叉树的左子树,由{Si+1,Si+2,?, Sm}和 {Pi,Pi+1,?,Pm-1} 可唯一确定二叉树的右子树 。




友情链接: