2008年下半年程序员下午试卷

试题二（共 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 <stdio.h>
#include <stdlib.h>
int isPalm(long m)
{  /*判断 m 是否为回文数*/
int i = 0, k = 0;
char str[32];
while (m > 0) {    /*从个位数开始逐个取出 m 的各位数字并存入字符数组 str*/
str[k++] =  （1）  + '0';
m = m / 10;
}
for(i = 0; i < k/2; i++)  /*判断 str 中的 k 个数字字符序列是否是回文*/
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）  ) {            /*n 不是回文数时执行循环*/
printf("%ld -> ", n);
for(a = 0, t = n; t > 0; ) {    /*计算 n 的反序数并存入 a*/
a =  （4）  *10 + t % 10;      t = t / 10;
} /*end of for*/
n =  （5）  ;          /*与反序数求和*/
} /*end of while*/
printf("%ld\n",n);
system("pause");        return 0;
}

试题三（共15分）
    阅读以下说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。[说明]
    已知某二叉树的非叶子结点都有两个孩子结点，现将该二叉树存储在结构数组 Ht中。结点结构及数组Ht的定义如下：
    #define MAXLEAFNUM  30
    struct node{
    char ch;        /*当前结点表示的字符，对于非叶子结点，此域不用*/
    char *pstr;      /*当前结点的编码指针，非叶子结点不用*/
    int parent;      /*当前结点的父结点，为0时表示无父结点*/
    int lchild,rchild;
    /*当前结点的左、右孩子结点，为0时表示无对应的孩子结点*/
    }；
    struct node Ht[2*MAXLEAFNUM];  /*数组元素Ht[0]不用*/
    该二叉树的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 所示。 
    
typedef enum Status {ERROR, OK} Status;
[C函数]
Status LeafCode(struct node Ht[], int n)
{
int pc, pf;  /*pc 用于指出树中的结点，pf 则指出 pc 所对应结点的父结点*/
int i,start;
char tstr[31] = {'\0'}; /*临时存储给定叶子结点的编码，从高下标开始存入*/
for(i = 1;  （1）  ; i++) { /*对所有叶子结点求编码，i 表示叶结点在 HT 数组中的下标*/
start = 29;
pc = i;    pf = Ht[i].parent;
while (pf !=  （2）  ) {        /*没有到达树根时，继续求编码*/
if (  （3）  .lchild == pc )  /*pc 所表示的结点是其父结点的左孩子*/
tstr[--start] = '0';
else
tstr[--start] = '1';
pc =  （4）  ;  pf = Ht[pf].parent; /*pc 和 pf 分别向根方向回退一层*/
}/* end of while */
Ht[i].pstr = (char *) malloc(31-start);
if (!Ht[i].pstr)  return ERROR;
strcpy(Ht[i].pstr,  （5）  );
}/* end of for */
return OK;
}/* end of LeafCode */

试题四（共15分）
    阅读以下说明和C函数代码，回答问题并将解答写在答题纸的对应栏内。[说明]
    著名的菲波那契数列定义式为
    f1 = 1  f2 = 1  fn = fn-1+ fn-2    （n= 3,4,…）
    因此，从第1项开始的该数列为1,1,2,3,5,8,13,21,…。函数fib1和fib2分别用递归方式和迭代方式求解菲波那契数列的第n项（调用fib1、fib2时可确保参数n获得一个正整数）。
[C函数代码]
   
[问题1]（6分）
    函数fib1和fib2存在错误，只需分别修改其中的一行代码即可改正错误。
    （1）函数fib1不能通过编译，请写出fib1中错误所在行修改正确后的完整代码；
    （2）函数fib2在n≤2时不能获得正确结果，请写出fib2中错误所在行修改正确后的完整代码。
[问题2]（3分）
    将函数fib1和fib2改正后进行测试，发现前46项都正确，而第47项的值是一个负数，请说明原因。
[问题3]（6分）
    函数fib1、fib2求得菲波那契数列第n项（n>40）的速度并不相同，请指出速度慢的函数名，并简要说明原因。

试题五（共15分）
    阅读以下应用说明、属性设置以及Visual Basic程序代码，将解答写在答题纸的对应栏内。
[应用说明]
    本应用运行时，由用户输入一个正整数n后自动产生n个正整数，然后按照用户的指定要求对该组数进行处理。该应用的运行界面如下图所示：
    
    1. 窗体中有两个文本框（txtSrc，txtObj）、两个标签（lblSrc，lblObj）、三个命令按钮（cmdGendat，cmdProc，cmdQuit）和一个弹出式菜单（procMenu，初始时不可见）。
    2．文本框txtSrc（由标签lblSrc提示）用于显示产生的数据，文本框txtObj（由标签lblObj提示）用于显示处理结果，要求每行显示一个整数。
    3. 程序启动时，命令按钮cmdProc（运算要求）不可用。点击命令按钮cmdGendat（产生数据）后，提示用户输入一个n的值并生成n个正整数存入数组元素a(1)～a(n)，然后将数据逐行显示在txtSrc中，并设置命令按钮cmdProc可用。
    4. 点击命令按钮cmdProc（运算要求）后弹出菜单。选择菜单项并单击后，进行相应处理并将结果显示在txtObj中，同时将lblObj的标题改为该菜单项表示的处理命令。
  弹出式菜单“运算要求”的结构如下表所示：
    
    一个整数序列的中位数指对该序列进行非递减（增）排列后最中间位置上的元素。若序列长度为偶数，则取中间两个元素的平均值为其中位数。
[属性设置]
    为实现单击命令按钮cmdProc 后弹出“运算要求”菜单（procMenu），设计时需将procMenu的 （1） 属性设置成false。
    供（1）选择的属性： Default  Enabled  ScaleMode  Style  Visible
[Visual Basic程序代码]
    Dim a() As Integer, n As Integer
    Private Sub Form_Load()
    txtSrc.Text = "":    txtObj.Text = "":      （2）  = False
    End Sub
    Private Sub cmdGendat_Click()  '生成正整数序列并存入数组a
    On Error GoTo Error_handler
    n = InputBox$("请输入数组元素个数：", "输入序列长度")
    If (n < 1) Then
    MsgBox "输入数据错误！", vbOKOnly, "提示："
    GoTo Error_handler:
    End If
    ReDim a(n) As Integer
    s = ""
    For i = 1 To n          '将生成的正整数存入a(1)~a(n)中
    a(i) = Int(Rnd * 10000) :  s = s & Str$(a(i)) & vbCrLf
    Next
    txtSrc.Text = s
    （3）          '设置运算要求命令按钮可用
    Error_handler:
    End Sub
    Private Sub cmdProc_Click()
    PopupMenu procMenu
    End Sub
    Private Sub MidNum_Click()      '求中位数
    lblObj.Caption = MidNum.Caption & ":"
    For i = 1  To  round((n + 1)/2)  '用选择排序法对数组a进行部分排序
    a(0) = a(i):k = i      ' a(0)用作临时变量，暂存第i次选出的最小元素
    For j = i + 1  To  n
    If a(j) < a(0) Then
    a(0) = a(j): k =  （4）
    End If
    Next
    If k <> i Then
    a(k) = a(i): a(i) = a(0)
    End If
    Next
    If  n / 2 - n \ 2 > 0 Then        'n为奇数时，取中间一个数
    txtObj.Text = Str$(a( （5） ))
    Else                        'n为偶数时，取中间两个数的平均值
    txtObj.Text = Str$(Int((a(n \ 2) + a(n \ 2 + 1)) / 2))
    End If
    End Sub
    '其他代码略

试题六（共15分）
    阅读以下说明和C++代码，将应填入 （n） 处的字句写在答题纸的对应栏内。[说明]
    C++标准模板库中提供了vector模板类，可作为动态数组使用，并可容纳任意数据类型，其所属的命名空间为std。vector模板类的部分方法说明如下表所示：
   
[C++代码]
#include <iostream>
#include <vector>
using namespace  （1） ;
typedef vector< （2） > INTVECTOR;
const int ARRAY_SIZE = 6;
void ShowVector(INTVECTOR &theVector);
int main(){
    INTVECTOR theVector;
    // 初始化theVector，将theVector的元素依次设置为0至5
    for (int cEachItem = 0; cEachItem < ARRAY_SIZE; cEachItem++)
    theVector.push_back( （3） );
    ShowVector(theVector);  // 依次输出theVector中的元素
    theVector.erase(theVector.begin() + 3);
    ShowVector(theVector);
}
void ShowVector(INTVECTOR &theVector) {
    if (theVector.empty())  {
    cout << "theVector is empty." << endl;    return;
    }
    INTVECTOR::iterator  （4） ;
    for (theIterator = theVector.begin(); theIterator != theVector.end(); theIterator++){
    cout << *theIterator;
    if (theIterator != theVector.end()-1)  cout << ", ";
    }
    cout << endl;
}
该程序运行后的输出结果为：
0, 1, 2, 3, 4, 5
（5）

试题七（共15分）
    阅读以下说明和Java代码，将应填入 （n） 处的字句写在答题纸的对应栏内。[说明]
    java.util库中提供了Vector模板类，可作为动态数组使用，并可容纳任意数据类型。该类的部分方法说明如下表所示：
   
[Java代码]
    import  （1） ;
    public class JavaMain {
    static private final int  （2）  = 6;
    public static void  main(String[] args){
    Vector<Integer> theVector = new Vector< （3） >();
    // 初始化theVector，将theVector的元素设置为0至5
    for (int cEachItem = 0; cEachItem < ARRAY_SIZE; cEachItem++)
    theVector.add( （4） );
    showVector(theVector);  // 依次输出theVector中的元素
    theVector.removeElementAt(3);
    showVector(theVector);
    }
    public static void showVector(Vector<Integer> theVector){
    if (theVector.isEmpty()) {
    System.out.println("theVector is empty.");
    return;
    }
    for (int loop = 0; loop < theVector.size(); loop++) {
    System.out.print(theVector.get(loop));
    System.out.print(", ");
    }
    System.out.println();
    }
    }
该程序运行后的输出结果为：
0, 1, 2, 3, 4, 5
（5）