您所在位置：主题：2008年下半年程序员下午试卷试题1至3（答案）
csai007
[专家分：0] 发布于 2009-06-01 14:42:00
试题一(共15分)
阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是：在已知字符串A 中查找特定字符串B，如果存在，则输出B串首字符在 A 串中的位置，否则输出-1。设串 A 由 n 个字符 A(0)、A(1)、…、A(n-1)组成，串B由m个字符B(0)、B(1)、…、B(m-1)组成，其中n≥m>0。在串A中查找串B的基本算法如下：从串A 的首字符A(0)开始，取子串A(0)A(1)…A(m-1)与串B比较;若不同，则再取子串A(1)A(2)…A(m)与串B 比较，依次类推。
例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出3)，不存在字符子串“RFD”(输出-1)。
在流程图中，i用于访问串A中的字符(i=0，1，…，n-1)，j用于访问串B 中的字符(j=0，1，…，m-1)。在比较 A(i)A(i+1)…A(i+m-1)与 B(0)B(1)…B(m-1)时，需要对A(i)与B(0)、A(i+1)与B(1)、…、A(i+j)与B(j)、…逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。
[流程图]
试题二(共15分)
阅读以下说明和C 程序代码，将应填入 (n) 处的字句写在答题纸的对应栏内。
[说明]
下面C 程序代码的功能是：对于输入的一个正整数n(100≤n<1000)，先判断其是否是回文数(正读反读都一样的数)。若不是，则将 n 与其反序数相加，再判断得到的和数是否为回文数，若还不是，再将该和数与其反序数相加并进行判断，依此类推，直到得到一个回文数为止。例如，278 不是回文数，其反序数为 872，相加后得到的 1150还不是回文数，再将1150与其反序数511相加，得到的1661是回文数。
函数int isPalm(long m)的功能是：将正整数m的各位数字取出存入数组中，然后判断其是否为回文数。若m是回文数则返回1，否则返回0。
[C 程序代码]
#include
#include
int isPalm(long m)
{
int i = 0, k = 0;
char str[32];
while (m > 0) {
str[k++] = (1) + '0';
m = m / 10;
}
for(i = 0; i < k/2; i++)
if ( str[i] != str[ (2) ] ) return 0;
return 1;
}
int main( )
{
long n, a, t;
printf("input a positive integer:"); scanf("%ld",&n);
if (n < 100 || n > =1000) return -1 ;
while( (3) ) {
printf("%ld -> ", n);
for(a = 0, t = n; t > 0; ) {
a = (4) *10 + t % 10; t = t / 10;
}
n = (5) ;
}
printf("%ld\n",n);
system("pause"); return 0;
}
试题三(共15 分)
阅读以下说明和C 函数，将应填入 (n) 处的字句写在答题纸的对应栏内。
[说明]
已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组 Ht中。结点结构及数组Ht的定义如下：
#define MAXLEAFNUM 30
struct node{
char ch;
char *pstr;
int parent;
int lchild,rchild;
};
struct node Ht[2 * MAXLEAFNUM];
该二叉树的n个叶子结点存储在下标为1～n的Ht数组元素中。例如，某二叉树如图3-1所示，其存储结构如图3-2所示，其中，与叶子结点a对应的数组元素下标为1，a 的父结点存储在 Ht[5]，表示为 Ht[1].parent=5。Ht[7].parent=0 表示 7 号结点是树根，Ht[7].lchild=3、Ht[7].rchild=6 分别表示 7 号结点的左孩子是 3号结点、右孩子是 6 号结点。
如果用“0”或“1”分别标识二叉树的左分支和右分支(如图 3-1 所示)，从根结点开始到叶子结点为止，按所经过分支的次序将相应标识依次排列，可得到一个 0、1序列，称之为对应叶子结点的编码。例如，图3-1中a、b、c、d的编码分别是100、101、0、11。
函数LeafCode(Ht[],n)的功能是：求解存储在Ht中的二叉树中所有叶子结点(n个)的编码，叶子结点存储在Ht[1]～Ht[n]中，求出的编码存储区由对应的数组元素pstr域指示。
函数LeafCode从叶子到根逆向求叶子结点的编码。例如，对图3-1中叶子结点a求编码的过程如图3-3所示。
图3-3从叶子到根求结点编码示意图
typedef enum Status {ERROR, OK} Status;
[函数]
Status LeafCode(struct node Ht[], int n)
{
int pc, pf;
int i,start;
char tstr[31] = {'\0'};
for(i=1;(1) ; i++) {
start = 29;
pc = i; pf = Ht[i].parent;
while (pf != (2) ) {
if ( (3) .lchild == pc )
tstr[--start] = '0';
else
tstr[--start] = '1';
pc = (4) ; pf = Ht[pf].parent;
}
Ht[i].pstr = (char *) malloc(31-start);
if (!Ht[i].pstr) return ERROR;
strcpy(Ht[i].pstr, (5) );
}
return OK;
}
选自http://www.educity.cn/rk/prog/200812221043571962.htm
答案参考http://www.educity.cn/user/xch/from.asp?id=140&wh=20095603 （注册有分才能看到）
阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是：在已知字符串A 中查找特定字符串B，如果存在，则输出B串首字符在 A 串中的位置，否则输出-1。设串 A 由 n 个字符 A(0)、A(1)、…、A(n-1)组成，串B由m个字符B(0)、B(1)、…、B(m-1)组成，其中n≥m>0。在串A中查找串B的基本算法如下：从串A 的首字符A(0)开始，取子串A(0)A(1)…A(m-1)与串B比较;若不同，则再取子串A(1)A(2)…A(m)与串B 比较，依次类推。
例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出3)，不存在字符子串“RFD”(输出-1)。
在流程图中，i用于访问串A中的字符(i=0，1，…，n-1)，j用于访问串B 中的字符(j=0，1，…，m-1)。在比较 A(i)A(i+1)…A(i+m-1)与 B(0)B(1)…B(m-1)时，需要对A(i)与B(0)、A(i+1)与B(1)、…、A(i+j)与B(j)、…逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。
[流程图]
试题二(共15分)
阅读以下说明和C 程序代码，将应填入 (n) 处的字句写在答题纸的对应栏内。
[说明]
下面C 程序代码的功能是：对于输入的一个正整数n(100≤n<1000)，先判断其是否是回文数(正读反读都一样的数)。若不是，则将 n 与其反序数相加，再判断得到的和数是否为回文数，若还不是，再将该和数与其反序数相加并进行判断，依此类推，直到得到一个回文数为止。例如，278 不是回文数，其反序数为 872，相加后得到的 1150还不是回文数，再将1150与其反序数511相加，得到的1661是回文数。
函数int isPalm(long m)的功能是：将正整数m的各位数字取出存入数组中，然后判断其是否为回文数。若m是回文数则返回1，否则返回0。
[C 程序代码]
#include
#include
int isPalm(long m)
{
int i = 0, k = 0;
char str[32];
while (m > 0) {
str[k++] = (1) + '0';
m = m / 10;
}
for(i = 0; i < k/2; i++)
if ( str[i] != str[ (2) ] ) return 0;
return 1;
}
int main( )
{
long n, a, t;
printf("input a positive integer:"); scanf("%ld",&n);
if (n < 100 || n > =1000) return -1 ;
while( (3) ) {
printf("%ld -> ", n);
for(a = 0, t = n; t > 0; ) {
a = (4) *10 + t % 10; t = t / 10;
}
n = (5) ;
}
printf("%ld\n",n);
system("pause"); return 0;
}
试题三(共15 分)
阅读以下说明和C 函数，将应填入 (n) 处的字句写在答题纸的对应栏内。
[说明]
已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组 Ht中。结点结构及数组Ht的定义如下：
#define MAXLEAFNUM 30
struct node{
char ch;
char *pstr;
int parent;
int lchild,rchild;
};
struct node Ht[2 * MAXLEAFNUM];
该二叉树的n个叶子结点存储在下标为1～n的Ht数组元素中。例如，某二叉树如图3-1所示，其存储结构如图3-2所示，其中，与叶子结点a对应的数组元素下标为1，a 的父结点存储在 Ht[5]，表示为 Ht[1].parent=5。Ht[7].parent=0 表示 7 号结点是树根，Ht[7].lchild=3、Ht[7].rchild=6 分别表示 7 号结点的左孩子是 3号结点、右孩子是 6 号结点。
如果用“0”或“1”分别标识二叉树的左分支和右分支(如图 3-1 所示)，从根结点开始到叶子结点为止，按所经过分支的次序将相应标识依次排列，可得到一个 0、1序列，称之为对应叶子结点的编码。例如，图3-1中a、b、c、d的编码分别是100、101、0、11。
函数LeafCode(Ht[],n)的功能是：求解存储在Ht中的二叉树中所有叶子结点(n个)的编码，叶子结点存储在Ht[1]～Ht[n]中，求出的编码存储区由对应的数组元素pstr域指示。
函数LeafCode从叶子到根逆向求叶子结点的编码。例如，对图3-1中叶子结点a求编码的过程如图3-3所示。
图3-3从叶子到根求结点编码示意图
typedef enum Status {ERROR, OK} Status;
[函数]
Status LeafCode(struct node Ht[], int n)
{
int pc, pf;
int i,start;
char tstr[31] = {'\0'};
for(i=1;(1) ; i++) {
start = 29;
pc = i; pf = Ht[i].parent;
while (pf != (2) ) {
if ( (3) .lchild == pc )
tstr[--start] = '0';
else
tstr[--start] = '1';
pc = (4) ; pf = Ht[pf].parent;
}
Ht[i].pstr = (char *) malloc(31-start);
if (!Ht[i].pstr) return ERROR;
strcpy(Ht[i].pstr, (5) );
}
return OK;
}
选自http://www.educity.cn/rk/prog/200812221043571962.htm
答案参考http://www.educity.cn/user/xch/from.asp?id=140&wh=20095603 （注册有分才能看到）