2016年上半年程序员下午试卷案例

【说明】
设整型数组A[1：N]每个元素的值都是1到N之间的正整数。一般来说，其中会有一些元素的值是重复的，也有些数未出现在数组中。下面流程图的功能是查缺查重，即找出A[1：N]中所有缺失的或重复的整数，并计算其出现的次数（出现次数为0时表示缺）。流程图中采用的算法思想是将数组A的下标与值看作是整数集[1：N]上的一个映射，用数组C[1：N]依次记录各整数k出现的次数c[k]，并输出所有缺失的或重复的数及其出现的次数。
【流程图】

如果数组A[1：5]的元素分别为{3，2，5，5，1}，则算法流程结束后输出结果为：（5）。
输出格式为：缺失或重复的数，次数（0表示缺少）。

问题：1.1 阅读说明和流程图，填补流程图和问题中的空缺（1）〜（5），将解答填入答题纸的对应栏内。

【说明1】
递归函数is_elem（char ch，char*set）的功能是判断ch中的字符是否在set表示的字符集合中，若是，则返回1，否则返回0。
【C代码1】

【说明2】
函数char*combine（char*setA，char*setB）的功能是将字符集合A（元素互异，由setA表示）和字符集合B（元素互异，由setB表示）合并，并返回合并后的字符集合。
【C代码2】

问题：2.1

阅读说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏中。

【说明】
某文本文件中保存了若干个日期数据，格式如下（年/月/曰）：
2005/12/1
2013/2/29
1997/10/11
1980/5/1
……
但是其中有些日期是非法的，例如2013/2/29是非法日期，闰年（即能被400整除或者能被4整除而不能被100整除的年份）的2月份有29天，2013年不是闰年。现要求将其中自1985/1/1开始、至2010/12/31结束的合法日期挑选出来并输出。
下面的C代码用于完成上述要求。

问题：3.1 阅读说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。

【说明】
二叉查找树又称为二叉排序树，它或者是一棵空树，或者是具有如下性质的二叉树。
(1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值。
(2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值。
(3)左、右子树本身就是两棵二叉查找树。
二叉查找树是通过依次输入数据元素并把它们插入到二叉树的适当位置上构造起来的，具体的过程是：每读入一个元素，建立一个新结点，若二叉查找树非空，则将新结点的值与根结点的值相比较，如果小于根结点的值，则插入到左子树中，否则插入到右子树中；若二叉查找树为空，则新结点作为二叉查找树的根结点。
根据关键码序列{46，25，54，13，29，91}构造一个二叉查找树的过程如图4-1所示。