2004年上半年软件水平考试（初级）程序员下午（应用技术）试题真题试卷 (题后含答案及解析)
题型有：1. 必答题 2. 选答题
必答题（共4道大题，每道大题15分）
1． 阅读下列说明、流程图和算法，将应填入______处。  [流程图说明]  下面的流程图用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，大于基准数的元素向高下标端移动。当划分结束时，基准数定位于A[i]，并且数组中下标小于i的元素的值均小于基准数，下标大于i的元素的值均大于基准数。设数组A的下界为low，上界为high，数组中的元素互不相同。例如，对数组(4，2，8，3，6)，以4为基准数的划分过程如下：  [流程图]      [算法说明]  将上述划分的思想进一步用于被划分出的数组的2部分，就可以对整个数组实现递增排序。设函数int p(intA[]，int low，int high)实现了上述流程图的划分过程并返回基准数在数组A中的下标。递归函数void sort(int A[]，int L，int H)的功能是实现数组A中元素的递增排序。  [算法]  void sort(int A[]，int L，int H){  if(L＜H){      k=p(A，L，H)；      /*p(  )返回基准数所在数组A中的下标 */      sort( (4)
)；      /*小于基准数的元素排序 */      sort( (5) )；      /*大于基准数的元素排序 */  }； }
正确答案：(1)j--(2)i++(3)A[i]←pivot或A[j]←pivot(4)A，L，k-1(5)A，k+1，H
解析：题目考查快速排序算法。  快速排序采用了一种分治的策略，通常称为分治法。其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。  快速排序的具体过程为：  第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为基准，将所有记录分成2组，第一组各记录的排序码都小于等于该排序码，第二组各记录的排序码都大于该排序码，并把该记录排在这2组中间，这个过程称为一次划分。  第二步，采用同样的方法，对划分出来的2组元素分别进行快速排序，直到所有记录都排到相应的位置为止。  在进行一次划分时，若选定以第一个元素为基准，就可将第一个元素备份在变量 pivot中，如图中的第①步所示。如此以来，基准元素在数组中占据的位置就空闲出来了，因此下一步就从后向前扫描，如图中的第②步所示，到一个比基准元素小的元素时为止，将其前移，如图中的第③步所示。然后再从前向后扫描，如图中的第④步所示，到一个比基准元素大的元素时为止，将其后移，如图中的第⑤步所示。这样，从后向前扫描和从前向后扫描交替进行，直到扫描到同一个位置
为止，如图中的第⑥步所示。  由题目中给出的流程图可知，以第一个元素作为基准数，并将A[loW]备份至pivot，i用于从前向后扫描的位置指示器，其初值为low，j用于从后往前扫描的位置指示器，其初值为high。当i＜j时进行循环：  (1)从后向前扫描数组A，在i＜j的情况下，如果被扫描的元素A[j]＞pivot，就继续向前扫描(j--)，如果被扫描的元素A[j]＜pivot就停止扫描，并将此元素的值赋给目前空闲着的A[i]；  (2)这时，再从前向后扫描，在i＜j的情况下，如果被扫描的元素A[j]＜pivot，就继续向后扫描(i++)；如果被扫描的元素A[j]＞pivot就停止扫描，并将此元素的值赋给目前空闲着的A[j]；  (3)这时，又接第(1)步，直到i≥j时退出循环。退出循环时，将pivot赋给当前的A [i](A[i]←pivot)。  递归函数的目的是执行一系列调用，直到到达某一点时递归终止。为了保证递归函数正常执行，应该遵守下面的规则：  (1)每当一个递归函数被调用时，程序首先应该检查一些基本的条件是否满足，例如，某个参数的值等于零，如果是这种情形，函数应停止递归。  (2)每次当函数被递归调用时，传递给函数一个或多个参数，应该以某种方式变得“更简单”，即这些参数应该逐渐靠近上述基本条件。例如，一个正整数在每次递归调用时会逐渐变小，以至最终其值到达零。  本题中，递归函数sort(int A[]，int L，int H)有3个参数，分别表示数组A及其下界和上界。根据流程图可知，这里的L相当于流程图中的i，这里的H相当于流程图中的j。因为p(  )返回基准数所在数
组A中的下标，也就是流程图中最后的“A[i]←pivot”中的i。  根据快速排序算法，在第一趟排序后出了基准数所在数组A中的下标，然后以该基准数为界(基准数在数组中的下标为k)，把数组A分成2组，分别是A[L，...，k-1)和 A[k+1，...，H]，最后对这2组中的元素再使用同样的方法进行快速排序。 
2． 阅读下列函数说明和C函数，将应填入______处的语句写在答题纸的对应栏内。  [函数2.1说明]  函数palindrome(char s[])的功能是：判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样，称该字符串是回文字符串，例如，“LEVEL”是回文字符串，而“LEVAL”不是。  [函数2.1]  int palindrome(char s[])  {        char *pi， *pj；        pi=s；pj=s+strlen(s)-1；        while(pi＜pj&&  (1)  ) { pi++；pj--；        }        if(  (2)  ) return-1；        else return 0；  }  [函数2.2说明]  函数f(char *str，char del)的功能是：将非空字符串str分割成若干个子字符串并输出，del表示分割时的标志字符。  例如，若str的值为“33123333435”，del的值为“3”，调用此函数后，将输出3个子字符串，分别为“12”，“4”和“5”。  [函数2.2]  void f(char *str，char del)  {        int i，j，len；        len=strlen(str)；        i=0；        While(i＜len){ While(  (3)  )i++；  /* 忽略连续的标志字符 *//* 寻从str[i]开始直到标志字符出现的一个子字符串 */ j＝i+1； while(str[j]!=del &&str[j]!’\0’)j+
+；  (4) =‘\0’；      /* 给到的字符序列置字符串结束标志 */ printf(“%s\t”，&str[i])；  (5)；        }    }
正确答案：(1)*pi==*pj(2)pi＜pj或 *pi != * pj，及其等价形式(3)str[i]==del(4)str[j](5)i=j+1
解析：[函数2.1]  若一个字符串顺读和倒读都一样，称该字符串是回文字符串。如果使用数组s[n]来存储一个字符串，则根据这个定义，要判断一个串是否是回文字符串，需要循环比较：  (1)该字符串的第一个元素s[0]和最后一个元素s[n-1]比较，如果s[0]不等于 s[n-1]，则s不是回文字符串。  (2)如果s[0]等于s[n-1]，则第二个元素s[1]和倒数第二个元素s[n-2]比较，如果s[1]不等于s[n-2]，则s不是回文字符串。  (3)依次类推，直到最中间的2个元素也比较完毕(如果s有偶数个元素)，或者只剩下中间的1个元素(如果s有奇数个元素)。  当上述循环结束时，如果最中间的元素没有进行比较，就说明s不是回文字符串，如果进行了比较，则s是回文字符串。  在函数2.1中，pi和pj是2个指向字符的指针，程序首先将s的首地址赋给pi(即 pi=&a[0])，将元素s[strlen(s)-1)的地址赋给pj(即pj=&s[strlen(s)-1])，当pi＜pj并且pi和pj所指向的字符相等时进行循环：pi自增，pj自减。  退出循环后，如果pi≥pj，则s是回文字符串(如果s有偶数个元素，则为pi＞pj，如果 s有奇数个元素，则为pi=pj)；如果pi＜pj，则s不是回文
字符串。  [函数2.2]  由函数2.2说明可知，此函数对给定的字符串进行从左至右的扫描，出不包含标志字符的子字符串。  在函数2.2中，i的初值为0，len表示字符串的长度。当i＜len时进行循环：如果当前字符是标志字符，则不做处理，继续扫描以处理标志字符连成一串的情况。当退出该循环时，当前字符str[i]不是标志字符，这时开始寻从str[i]开始，直到标志字符出现的一个子字符串(i保持不变，用j标记寻的过程)，给到的字符序列置字符串结束标志，以便于后面语句的输出。  输出语句结束后，就要继续寻后面的不包含标志字符的子字符串，这时需要把指针 i移动j的后面，继续扫描。 
3． 阅读下列函数说明和C函数，将应填入______处的语句写在答题纸的对应栏内。  [函数6说明]  函数DelA_InsB(LinkedList La，LinkedList Lb，int key1，int key2，int len)的功能是：将线性表A中关键码为key1的结点开始的len个结点，按原顺序移至线性表B中关键码为key2的结点之前，若移动成功，则返回0；否则返回-1。线性表的存储结构为带头结点的单链表，La为表A的头指针，Lb为表B的头指针。单链表结点的类型定义为：  typedef struct node {int key；struct node * next；  } * LinkedList；  [函数6]  int DelA InsB(LinkedList La，LinkedList Lb，int key1，int key2，int len)  { LinkedListp，q，s，prep，pres；  int k；  if(! La-＞next‖! Lb-＞next‖-＞next‖len＜＝0)return－1；  p=La-＞next；prep=La；  while(p&&
p-＞key!=key1){/ * 查表A中键值为key1的结点 * /  prep=p；p=p-＞next；  }  if(! p)return -1；      / * 表A中不存在键值为key1的结点 * /  q＝p；k=1；  while(q&&  (1)  ){      / * 在表A中出待删除的len个结点 * /      (2)；k++；  }  if(! q)return-1：      / * 表A中不存在要被删除的len个结点 * /  s=Lb-＞next；  (3)；  while(s s && s-＞key!=key2){      / * 查表B中键值为key2的结点 * /        pres=s；s=s-＞next；  }  if(! s)return-1；      / * 表B中不存在键值为key2的结点 * /    (4)=q-＞next；      / * 将表A中的len个结点删除 * /  q-＞next=(5)；  pres-＞next=p；/ * 将len个结点移至表B * /  return 0；  }
正确答案：(1)k＜len(2)q=q-＞next(3)pres=Lb(4)prep-＞next(5)s或pres-＞next
解析：本题是在链表插入和删除单个结点的基础上进行扩展，一次性插入多个结点和删除多个结点其原理和插入、删除一个结点的运算是一致的。首先在A链表中查键值为key1的结点，使用了下列循环：  While(p&&p-＞key!=key1) {        / * 查表A中键值为key1的结点 * /      Prep=p；p=p-＞next；  }因此，当到键值为key1的结点时，p指向该结点，prep指向p的前驱。然后看在p的后面是否有len个结点，使用了下列语句：  q＝p；k=1；  while(q&&(1)) {  / * 在表A中出待删除的len个结点 * /    (2)；k++；  }显然，首先把q指向p，k为计数器，
所以该循环的结束条件有2个，一个是p的后面没有 len个结点，这时q为空，所以(2)空应填写q＝q-＞next，使q的指针往后移动；另一个是 p的后面有len个结点，这时k＝len。所以(1)空应填写k＜len。  根据上面的语句，如果p的后面有len个结点，则q指向第len个结点。如图2-2所示(虚线表示省略了中间若干个结点)。      同样，在表B中查键值为key2的结点，使用了下列循环：  s=Lb-＞next；(3)；  while(s&&s-＞key!=key2){ / * 查表B中键值为key2的结点 * /      pres=s；s=s-＞next；  }首先，s指向第一个结点，然后进行循环，循环的结束条件也是2个，要么s为空(这时说明从头到尾都没有到键值为key2的结点)，要么到了，s指向该结点，pres指向s的前驱。但是，如果第一个结点的键值就是key2的话，根据循环条件，循环中的语句不执行，则pres没有值，所以(3)空应该填写pres＝Lb，使pres始终指向s的前驱。如图2-3所示 (虚线表示省略了中间若干个结点)。  最后将p到q的连续len个结点从A表中删除，在B表中插入，如图2-4所示。  程序中使用的语句如下：        (4)=q-＞next； / * 将表A中的len个结点删除 * /  q-＞next=(5)；  pres-＞next=p；  / * 将len个结点移至表B * /  要把p到q的连续len个结点从A表中删除，就要把p的前驱(prep)的next指向q的next，因此，(4)空应填写prep-＞next。然后把q的next指向B表中s，把s的前驱 (pres)的next指向p，所以，(5)空应填写s。 
2015年初级会计真题