软考中级
试题七（共 15 分）阅读以下说明和C程序，将应填入 （n） 处的字句写在答题纸的对应栏内。【说明】现有 n（n < 1000）节火车车厢，顺序编号为 1,2,3,...,n，按编号连续依次从 A方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 7-1所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。下面的 C 程序判断能否从 B 方向驶出预先指定的车厢序列，程序中使用了栈类S
题目
试题七（共 15 分）
阅读以下说明和C程序，将应填入 （n） 处的字句写在答题纸的对应栏内。
【说明】
现有 n（n < 1000）节火车车厢，顺序编号为 1,2,3,...,n，按编号连续依次从 A方向的铁轨驶入，从 B 方向铁轨驶出，一旦车厢进入车站（Station）就不能再回到 A方向的铁轨上；一旦车厢驶入 B 方向铁轨就不能再回到车站，如图 7-1所示，其中 Station 为栈结构，初始为空且最多能停放 1000 节车厢。
下面的 C 程序判断能否从 B 方向驶出预先指定的车厢序列，程序中使用了栈类
STACK,关于栈基本操作的函数原型说明如下：
void InitStack(STACK *s)：初始化栈。
void Push(STACK *s,int e): 将一个整数压栈，栈中元素数目增 1。
void Pop(STACK *s)：栈顶元素出栈，栈中元素数目减 1。
int Top(STACK s)：返回非空栈的栈顶元素值，栈中元素数目不变。
int IsEmpty(STACK s)：若是空栈则返回 1，否则返回 0。
【C 程序】
include<stdio.h>
/*此处为栈类型及其基本操作的定义，省略*/
int main( ){
STACK station;
int state[1000];
int n; /*车厢数*/
int begin, i, j, maxNo; /*maxNo 为 A端正待入栈的车厢编号*/
printf("请输入车厢数： ");
scanf("%d",&n);
printf("请输入需要判断的车厢编号序列（以空格分隔） ： ");
if (n < 1) return -1;
for (i = 0; i<n; i++) /* 读入需要驶出的车厢编号序列,存入数组 state[] */
scanf("%d",&state[i]);
（1） ; /*初始化栈*/
maxNo = 1;
for(i = 0; i < n; ){/*检查输出序列中的每个车厢号 state[i]是否能从栈中获取*/
if ( （2） ){/*当栈不为空时*/
if (state[i] == Top(station)){ /*栈顶车厢号等于被检查车厢号*/
printf("%d ",Top(station));
Pop(&station); i++;
}
else
if ( （3） ){
printf("error\n");
return 1;
}
else {
begin = （4） ;
for(j = begin+1; j<=state[i]; j++) {
Push(&station, j);
}
}
}
else { /*当栈为空时*/
begin = maxNo;
for(j = begin; j<=state[i]; j++){
Push(&station, j);
}
maxNo = （5） ;
}
}
printf("OK");
return 0;
}
相似问题和答案
第1题：
●试题二
阅读下列程序或函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【函数2．1说明】
函数strcmp()是比较两个字符串s和t的大小。若s＜t函数返回负数；若s=t函数返回0；若s＞t，函数返回正数。
【函数2．1】
int strcmp(char *s，char *t)
{ while(*s && *t && (1) ){
s++；t++；
}
return (2) ；
}
【程序2．2说明】
在n行n列的矩阵中，每行都有最大的数，本程序求这n个最大数中的最小一个。
【程序2．2】
#includestdio．h
#define N 100
int a［N］［N］；
void main()
{ int row ，col，max，min，n；
/*输入合法n(＜100)，和输入n×n个整数到数组a的代码略*/
for (row=0；row＜n；row++){
for(max=a［row］［0］，col=1；col＜n；col++)
if( (3) )max=a［row］［col］；
if( (4) )min=max；
else if( (5) )min=max；
}
printf ("The min of max numbers is %d＼n"，min)；
}
●试题二
【答案】(1)*s == *t(2) *s - *t
【解析】*s 和 *t相等才执行循环体。返回二者差值，恰好符合题目要求。
【答案】(3) a［row］［col］>max (4) row == 0(5) max<min
【解析】当前值比max大，则把它赋给max。max是本行最大值。初始化min为第一行的max。该行的max比min小，则将max赋给min。
第2题：
试题二（共 15 分）
阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。
[说明]
下面的程序按照以下规则输出给定名词的复数形式：
a. 若名词以“y”结尾，则删除 y 并添加“ies” ；
b. 若名词以“s” 、 “ch”或“sh”结尾，则添加“es” ；
c. 其他所有情况，直接添加“s” 。
[C 程序]
#include <stdio.h>
#include <string.h>
char *plural(char *word)
{
int n;
char *pstr;
n = strlen(word); /*求给定单词的长度*/
pstr = (char *)malloc(n+3); /*申请给定单词的复数形式存储空间*/
if (!pstr || n < 2)
return NULL;
strcpy(pstr,word); /*复制给定单词*/
if ( (1) )
{
pstr[n-1] = 'i'; pstr[n] = 'e'; pstr[n+1] = 's'; (2) ;
}
else
if(pstr[n-1]=='s'||pstr[n-1]== 'h' && ( (3) ))
{
pstr[n] = 'e'; pstr[n+1] = 's'; pstr[n+2] = '\0';
}
else
{ pstr[n] = 's'; pstr[n+1] = '\0'; }
(4) ;
}
main( )
{ int i; char *ps;
char wc[9][10] =
{"chair","dairy","boss","circus","fly","dog","church","clue","dish"}
for(i = 0; i < 9; i++) {
ps = (5) ;
printf("%s: %s\n",wc[i],ps); /*输出单词及其复数形式*/
free(ps); /*释放空间*/
}
system("pause");
}
第3题：
●试题四
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数QuickSort是在一维数组A［n］上进行快速排序的递归算法。
【函数】
void QuickSort(int A［］，int s，int t)
{int i=s，j=t+1，temp；
int x=A［s］；
do{
do i＋＋；while (1) ；
do j--；while(A［j］>x)；
if(i<j){temp=A［i］； (2) ； (3) ；}
}while(i<j)；
A［a］=A［j］；A［j］=x；
if(s<i-1) (4) ；
if(j+1<t) (5) ；
}
●试题四
【答案】(1)A［i］<x(2)A［i］=A［j］(3)A［j］=temp(4)QuickSort(A，s，j-1)
(5)QuickSort(A，j+1，t)；
【解析】快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。
第4题：
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。
【说明】
有n个整数，使其前面各数顺序向后移m个位置，最后m个数变成最前面的m个数。
【函数】
main()
{
int number[20],n,m,i;
printf("the total numbers is:");
scanf("%d",&n);
printf("back m:");
scanf("%d",&m);
for(i=0;i＜=n-1;i)
scanf("%d,",&number[i]);
(1);
for(i=0;i＜=n-1;i)
printf("%d,",number[i]);
}
move(array,n,m)
int n,m,array[20];
{
int *p,array_end;
array_end=(2);
for(p=array[n-1];(3);p--)
*p=(4);
*array=array_end;
m--;
if(m＞0) (5);
}
(1)move(number,n,m) (2)*(array[n-1]) (3)p＞array (4)*(p-1) (5)move(array,n,m) 解析：本题考查数字顺序移动和数组的相关知识。
从数据结构的角度出发，数字在数组中顺序移动，就是将数字一个一个往后搬，例如，将n-1位置的数字移到n位置，然后再把n-2位置的数字移到n-1位置，其实这是一个简单的数字移动。我们只需要取出第n个位置的数字并保存在一个临时变量中，然后，其他的就按顺序依次移动即可，直到一次整体移动完成，我们再从临时变量中取回数字并将其放在数组的第一个位置中。重复这个过程m次，整个数组就往后移动了m个位置。
首先，我们来看一下主函数，在主函数里面声明了一个容量为20的整型数组 number[20]和其余3个整型变量，数组用来存储我们输入的待处理的数，而变量m、n分别用于存放我们要移动位置的个数和输入整数的个数。第一个循环语句用于n个整数的输入，第二个循环语句用于n个整数的输出，在这中间应该还有一个处理来完成将n个整数顺序向后移m个位置，并让最后m个数变成最前面的m个数这个功能，从下面的程序段我们知道，这里是调用函数muve(number,n,m)来完成的。因此，第(1)空填 move(nurnber,n,m)，在调用时我们需要注意参数的传递。
再来看move(array,n,m)函数，在此函数中，同样声明了一个容量为20的整型数组和 2个整型变量，另外还声明了一个指针变量p。由*array=array_end，结合第(2)空来看，这里是把数组中最后位置的数取出存放在array_end变量当中。因此，第(2)空应填 *(array[n-1])。
第(3)空是常见的在循环语句中表示判断的语句，由于“p=array[n-1]”把数组最末的地址赋给了指针p，只要p的值大于数组的起始地址循环就可以继续，因此，第(3)空应填p＞array。
第(4)空要完成的任务是将数字后移，因此，第(4)空为*p-1。从程序来分析，数组每移动完成一次，m的值就减一，而现在只有移动m次的功能没有实现，因此，只要m值大于0，就调用函数自身来实现再次移动。因此，第(5)空填写move(array,n,m)进行递归调用。
第5题：
阅读以下说明和流程图，将应填入(n)处的字句写在对应栏内。
[说明]
设学生某次考试的成绩按学号顺序逐行存放于某文件中，文件以单行句点“.”为结束符。下面的流程图读取该文件，统计出全部成绩中的最高分max和最低分min。
(1) max←a (2) min←a (3) a="." (4) a＞max或amax或maxa或max≤a (5) amin或a≤min或min＞a或mina 解析：本题用到的三个变量及其作用分别为：a，存放读入的一行数据；max存放最高分；min存放最低分。算法首先读入文件的第一行数据a，若a为文件结束符“.”，则算法提前结束；否则为max和min赋初值a，循环读入文件其余部分，直至文件末尾。循环过程中，当某行数据a大于max时，更新max的值；当某行数据a小于min时，更新min的值。
第6题：
阅读下列程序说明和C代码，把应填入其中n处的字句写在答卷的对应栏内。
【说明】
程序利用选择排序算法对数组a中的N个整数按照从小到大的顺序排列，并将排序结果显示出来。
【程序】
define N 10
main()
{
void (1)；
int i，a[N]；
for(i=0；i＜10，i++) /*输入*/
scanf(“%d”，&a[i])；
(2)；
for(i=0；i＜N，i++) /*输出*/
printf(“%3d”，a[i])；
}
void selectSon(int x[]，int n)
{
int i，j，k，t；
for(int i=0； (3)；i++)
{
k=i；
for(j=i+1；j＜n；j++)
if (4) k=j；
if (5)
{t=x[i]；x[i]=x[k]；x[k] =t；}
}
}
(1)selectSort() 解析：main函数中对selectSort函数的调用在定义之前，所以要进行说明。
第7题：
阅读以下说明和流程图，将应填入(n)处的字句写在对应栏内。
【说明】
已知头指针分别为La和lb的有序单链表，其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc，使得Lc中的元素按值非递减排列。程序流程图如下所示：
(1)pa-＞data=pb-＞data (2)pc-＞next=pa (3)pc=pb (4)pb=pb-＞next (5)pc-＞next=pa?pa:pb 解析：本题考查程序流程图和有序链表的归并。
题目要求我们归并头指针分别为La和Lb的有序单链表，组成一个新的有序单链表 Lc，而Lc又是指向La的。首先，我们来了解一下单链表的结构。单链表中一般有两个域，一个是数据域，用来存放链表中的数据；另一个是指针域，用来存放指向下个结点的指针。其归并的过程应该是先比较链表La和Lb中第一个元素，将较小的从其链表中取出放到k中，再取下一个结点的值去比较，重复这个过程，直到一个链表被全部取完，再将另一个链表剩下的部分连接到Lc后面即可。
下面，我们来看程序流程图的内容。首先是用两个指针变量pa和pb分别指向La和Lb的当前待比较插入的结点，而pc指向Lc表中当前最后一个结点。再下面是一个条件判断语句，其作用是判断链表La和Lb是否为空，如果有一个为空，只要将另一个链表剩下的部分连接到Lc后面，程序应该就可以结束了。
第(1)空是条件判断语句的条件，根据我们上面的分析，再结合流程图下面的内容，我们可以知道，这个条件语句的作用是比较当前待插入的两个值的大小，而指针变量pa和pb分别指向La和Lb的当前待比较插入的结点，因此，此空的答案为 pa-＞data=pb-＞data。
第(2)空是在条件为真的情况下执行的语句，如果条件判断为真，应该将pa所指结点连接到pc所指结点后面，因此，pc所指结点的指针域应该存放pa所指结点的地址。所以，此空的答案为pc-＞next=pa。
第(3)空和第(4)空都是在条件为假的情况下执行的语句，如果条件为假，说明 pb所指结点的值小于pa所指结点的值，应该将pb所指结点连接到pc所指结点后面，图中已经实现这一功能，要我们完成的是在插入后的后继工作。由于pc指向的是Lc表中当前最后一个结点，在插入一个结点后，要修改pc的值。在将pb所指结点插入后，链表中的最后一个结点就是pb所指结点，第(3)空的答案应该为pc=pb。执行完这些功能后，指针pb应该要往后移动，即指向下一个结点，第(4)用来完成这个功能，所以答案为pb=pb-＞next。
在前面，我们已经讲到如果链表La和Lb有一个为空，只要将另一个链表剩下的部分连接到Lc后面即可。第(5)空就是用来完成这个功能的，但我们不知道具体是哪个链表为空，还需要判断，因此，此空答案为pc-＞next=pa?pa:pb。
第8题：
●试题八
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
以下程序的功能是：从键盘上输入一个字符串，把该字符串中的小写字母转换为大写字母，输出到文件test．txt中，然后从该文件读出字符串并显示出来。
【程序】
#include<stdio．h>
main()
{FILE*fp；
charstr［100］；inti=0；
if((fp=fopen("text．txt" (1) ))==NULL)
{printf("can't open this file．＼n")；exit(0)；}
printf("input astring:＼n")；gest(str)；
while(str［i］)
{if(str［i］>=′a′ ＆＆ str［i］<=′z′)
str［i］= (2) ；
fputc(str［i］， (3) )；
i＋＋；
}
fclose(fp)；
fp=fopen("test．txt"， (4) )；
fgets(str，100，fp)；
printf("％s＼n"，str)；
(5) ；
}
●试题八
【答案】(1)W
(2)str［i］-′a′+′A′
(3)fp
(4)r
(5)fclose(fp)
【解析】程序运行后，首先打开文件test.txt用于写入，因此(1)空填w。
程序从键盘读入字符串到变量str中，对str中每个字符，如是小写字母，则将其转换成大写字母。(2)空是小写字母转换大写字母的操作。(3)空是将str中的字符写入文件text.txt中。
str中所有字符处理完后，关闭文件test.txt(对应语句是fclose(fp))，然后重新以读方式打开，因此(4)空填r，将test.txt中的内容读到str中并显示输出后，关闭文件test.txt，即(5)空填fclose(fp)。
第9题：
阅读下列说明和流程图，将应填入(n)的字句写在对应栏内。
【说明】
下列流程图(如图4所示)用泰勒(Taylor)展开式
sinx=x-x3/3!+x5/5!-x7/7!+…+(-1)n×x2n+1/(2n+1)!+…
【流程图】
计算并打印sinx的近似值。其中用ε(＞0)表示误差要求。
(1)x*x (2)x-＞t (3)│t│:ε (4)s+2-＞s (5)(-1) * t* x2/(s* (s-1)) 解析：该题的关键是搞清楚几个变量的含义。很显然变量t是用来保存多项式各项的值，变量s和变量x2的作用是什么呢?从流程图的功能上看，需要计算11、3!、5!，……，又从变量s的初值置为1可知，变量s主要用来计算这此数的阶乘的，但没有其他变量用于整数自增，这样就以判断s用来存储奇数的，即s值依次为1、3、5，……。但x2的功能还不明确，现在可以不用管它。
(2)空的作用是给t赋初值，即给它多项式的第一项，因此应填写“x-＞t”。(3)空处需填写循环条件，显然当t的绝对值小于ε(＞0)就表示已经达到误差要求，因此(3)空应填入“│t│:ε”。由变量s的功能可知，(4)空应当实现变量s的增加，因此(4)空应填入“s+2-＞s”。 (5)空应当是求多项式下一项的值，根据多项式连续两项的关系可知，当前一项为t时，后一项的值为(-1)*t*x*x/(s*(s-1))。但这样的话，每次循环都需要计算一次x*x，计算效率受到影响，联想到变量x2还没用，这时就可以判断x2就是用来存储x*x的值，使得每次循环者少进行一次乘法运算。因此(1)空处应填入“x*x”，(5)空处应填入“(-1)*t*x2/(s*(s-1))”。
第10题：
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。
【函数2.1说明】
递归函数sum(int a[], int n)的返回值是数组a[]的前n个元素之和。
【函数2.1】
int sum (int a[],int n)
{
if(n＞0) return (1);
else (2);
}
【函数2.2说明】
有3个整数，设计函数compare(int a，int b，int c)求其中最大的数。
【函数2.2】
int compare (int a, int b, int c )
{ int temp, max;
(3) a:b;
(4) temp:c;
}
【函数2.3说明】
递归函数dec(int a[]，int n)判断数组a[]的前n个元素是否是不递增的。不递增返回 1，否则返回0。
【函数2.3】
int dec( int a[], int n )
{
if(n＜=1) return 1;
if(a[0]＜a[1]) return 0;
return (5);
}
(1)a[n-1]+sum(a，n-1)或者a[0]+sum(a+1，n-1)； (2)return 0； (3)temp=(a>b)? (4)max=(temp＞c)? (5)dec(a+1,n-1)； 解析：本题考查C语言函数和一些基本运算。
下面我们分别来分析这几个函数。在函数2.1中，题目要求用此递归函数求数组前 n个元素之和。递归函数的特点是在函数体中不停地调用函数本身，只是将其函数的参数范围改变。题目中要求我们求数组前n个元素之和，我们可以这样理解，即前n个元素之和等于第n个元素加上前n-1个元素之和，现在的问题转化成如何求前n-1个元素之和。同样的道理，可以将求前n-1个元素之和转化成求前n-2个元素之和，直到这个数小于0。从函数2.1的代码中可以知道，在计算以前，首先判断n与0的关系，如果n小于0，说明数组中无元素，因此，返回0值；如果n大于等于0，说明数组中有元素，应该返回的结果是第n个元素加上前n-1个元素之和，而前n-1个元素之和是调用函数本身来计算的。因此，第(1)空和第(2)空的答案分别是a[n-1)+sum(a，n-1)，return()。
在函数2.2中，题目要求我们在三个数中取最大数，在数学中，我们从三个数中取最大数时，一般是首先拿其中两个数比较，取较大的数再与第三个数比较，再取其较大的数，这个数就是三个数中的最大数。从函数2.2的代码中知道，三个数a、b、c，两个整型变量temp与max。根据求三个数中最大数的数学过程和函数中已给出的代码可知，第(3)空处语句应该为temp=(a＞b)?a:b，求得a、b中较大数并存放在变量temp中。第(4)空处语句为max=(temp＞c)?temp:c。
在函数2.3中，题目要求判断数组a[]的前n个元素是否是不递增的。不递增返回1，否则返回0。要判断前n个元素是否是不递增的，需要判断前n-1个元素是否是不递增的，以及第n个元素与第n-1个元素的关系。此处与函数2.1一样，用的都是递归函数，只是出口不同，在函数2.1中，只要数组中没有元素了，递归结束，这里只要第n个元素大于第n-1个元素，则返回0，递归结束。又由if(a[0]a[1])语句可知，在每次调用函数时，都将其数组中的第一个元素与第二个元素比较来作为递归的出口，如果结果为假，就说明数组的前面两项的关系是不递增的，在下次调用中不用再考虑第一项。因此第(5)空应该是dec(a+1,n-1)。