2008-年硕士研究生入学考试数据结构与-C-语言程序设计试题与答案

12008年硕士研究生入学考试数据结构与C语言程序设计(991)试题与答案一、简答题（本题共20分，每小题各5分）1．一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理。2．若5个元素A,B,C,D,E按此先后次序进入一个初始为空的堆栈，则在所有可能的出栈序列中，第一个元素为C、且第二个元素为D的出栈序列是哪几个？3．设散列函数为H(key)=keyMOD7，散列地址范围为[0..7]，采用线性探测再散列法处理冲突。依次将序列(20,11,13,21,34)中各关键字值插入初始为空的散列表以后，查找关键字值34，需要依次与散列表中哪些关键字值进行比较？（符号MOD表示求模运算）4．在设计快速排序法的非递归算法时，能否不用堆栈保存当前尚未参加排序的子序列的首、尾位置，而改为其他机制？如队列。请说明理由。二、综合题（本题共20分，每小题各5分）1．已知在非空双向循环链表中由指针q指的那个链结点的前面插入一个由指针p指的链结点的过程的前3个动作对应的赋值语句依次为“p-rlink=q;p-llink=q-llink;q-llink=p;”，请写出第4个动作对应的语句。2．请证明具有n0个叶结点的满二叉树的分支数为2(n0-1)。3．已知有向图G=(V,E)，其中，顶点的集合为V={v1,v2,v3,v4,v5}，弧的集合为E={v1,v2,v1,v3,v1,v4,v2,v5,v3,v4,v4,v5}，请写出G的所有拓扑序列。4．请画出依次插入关键字序列(6,7,10,14,9,2,13,5,4,11)中各关键字值以后的4阶B-树。三、算法设计题（本题15分）请写一算法，依次输出通过键盘输入的一组整型数据中的最后k个元素。约定：以Ctrl+z作为键盘输入的结束，并假设k≤输入的数据元素的个数。限制：算法中不允许使用数组，也不允许有计算输入数据个数的过程。四、算法设计题（本题20分）已知二叉树采用二叉链表存储结构，链结点构造为lchilddatarchild，根结点指针为T，请写一非递归算法，判断该二叉树是否为二叉排序树。若是二叉排序树，算法返回1，否则，返回0。五、单项选择题（本题共20分，每小题各2分）1．在下面给出的四个选项中，值为1的表达式是。A．1-‘\0’B．1-‘0’C．‘1’-0D．‘\0’-‘0’2．对于条件表达式(E)?(x++):(x--)，其中的表达式E等价于。A．E==0B．E==1C．E!=0D．E!=13．以下语句中存在语法错误的是。A．char*S[]={“right?”};B．charS[][20]={“right?”};2C．char*S[6];S[1]=“right?”;D．charS[6][20];S[1]=“right?”;4．若变量a,b已经正确定义并赋值，以下符合C语言语法规则的表达式是。A．a+1=yB．++a,b=a--C．a=a+10=a+bD．double(a)/105．设已有定义“intx;floaty;”，执行语句“scanf(“%2d%f”,&x,&y);”时，若从键盘输入数据876543.0CR，x和y的值分别是。(CR表示回车)A．876和543.000000B．87和543.000000C．87和6.000000D．76和543.0000006．下面关于宏的四个描述中，错误的是。A．进行宏替换时是先求出实参表达式的值，然后代入形参数，运算求值B．宏不存在类型问题，宏名无类型，它的参数也无类型C．宏替换不占用运行时间D．实际上，宏替换只不过是字符替代而已7．若有以下程序intADD(intx,inty){returnx+y;}main(){intk,(*f)(),x=5,y=10;f=ADD;…}则下面给出的四个函数调用语句中，有错误的是。A．k=(*f)(x,y);B．k=ADD(x,y);C．k=*f(x,y);D．k=f(x,y);8．若变量已经正确定义，则下面能够正确计算f=n!的程序段是。A．f=0;B．f=1;for(i=1;i=n;i++)for(i=1;in;i++)f*=i;f*=i;C．f=1;D．f=1;for(i=n;i1;i++)for(i=n;i=2;i--)f*=i;f*=i;9．对于以下程序，#includestring.hmain(){chars1[]={‘x’,‘y’,‘z’},s2[10]={‘x’,‘y’,‘z’};printf(“%d%d\n”,strlen(s1),strlen(s2));}下面给出的四个叙述中，正确的是。A．在给s1和s2数组置初值时，系统会自动添加字符串结束符，故输出的长度都为3。B．由于s1数组中无字符串结束符，长度不能确定；但s2数组中字符串长度为3。C．由于s2数组中无字符串结束符，长度不能确定；但s1数组中字符串长度为3。D．由于s1和s2数组中都没有字符串结束符，长度都不能确定。310．若需要打开一个已经存在的非空文件“FILE”，并对其进行修改操作，则正确的打开语句是。A．fp=fopen(“FILE”,“r”);B．fp=fopen(“FILE”,“ab+”);C．fp=fopen(“FILE”,“w+”);D．fp=fopen(“FILE”,“r+”);六、填空题（本题共20分，每小题各2分）1．在C语言中，表示逻辑“真”值用。2．若有a=1,b=2,c=3，则表达式(ab?a:b)==c++的值是。3．如果已经有如下定义“floata=123.4567;”，那么，执行输出语句“printf(“%f\n”,(int)(a*100+0.5)/100.0);”的输出结果是。4．若有定义“doublex[4][6];”，则数组x中行下标的下限与列下标的上限分别是。5．若有以下宏定义：#defineWIDTH80#defineLENGTHWIDTH+40则执行赋值语句“x=LENGTH*20;（设x为int类型变量）”后，x的值是。6．若for循环语句用以下形式表示：for(表达式1，表达式2，表达式3)循环体语句则执行语句“for(i=0;i4;i++)printf(“*”);”时，表达式3执行了次。7．执行以下程序段的输出结果是。inta=3;do{printf(“%3d”,a-=2);}while(!(--a));8．若已经定义：structnum{intx;inty;}n={1,3};structnum*p=&n;则表达式p-y/n.x*++p-y的值是。9．以下程序的输出结果是。#includestdio.hintA[3][3]={1,2,3,4,5,6,7,8,9},*p;main(){p=(int*)malloc(sizeof(int));FUN(p,A);printf(“%d\n”,*p);}FUN(int*r,intp[][3]){*r=p[1][1];}10．若下面给出的程序是输出如右下所示形式的一个方阵，则在程序中的空白处(横线4上)需要填入内容。main(){inti,j,x;for(j=4;j;j--){for(i=1;i=4;i++){x=(j-1)*4+i;printf(“%4d”,x);}printf(“\n”);}}七、程序设计题（本题15分）请编写一程序，将一字符串的第k个字符开始的全部字符复制成为另外一个字符串。要求：1．将复制过程单独编写为一个函数，并且采用指针完成；2．在主函数中输入字符串和k的值，并且在主函数中输出复制结果。八、程序设计题（本题20分）请使用命令行参数形式编写程序，该程序将指定文本文件中所有某个单词的出现均替换为另一个单词，经过替换后的文件信息存放于另一个文本文件中。设命令行格式为replaceoldfilenewfileoldwordnewword其中，replace为命令名，oldfile、newfile、oldword和newword为命令行参数。例如，执行命令creplacefile1file2oldnewCR的结果是将文本文件file1中的所有单词“old”替换为“new”，替换后的文件信息存放于文本文件file2中。(CR表示回车)要求：程序中必须有命令行的正确性检查。答案一、简答题1．答：一般情况下，线性表可以采用顺序存储结构与链式存储结构。顺序存储结构是按照表中元素之间的逻辑结构依次将元素存放在一组地址连续的存储空间里，数据元素之间的逻辑结构通过元素的地址直接反映出来。而链式存储结构则是将表中元素依次存放与一组地址任意的存储空间中，数据元素之间的逻辑结构通过指针间接反映出来。因此，在链式存储结构中，除了存储每一个数据元素的信息之外，还要存储指针信息，以反映元素之间的逻辑结构。2．答：这样的序列一共有三个，它们分别是C,D,B,A,E，C,D,E,B,A和C,D,B,E,A。3．答：20,13,21,344．答：可以不用设置堆栈，而采用其它机制。因为快速排序法经过一次划分(一趟排序)以后，基准元素将当前参加排序的那些元素分成前后两个部分，如果这两个部分的长度都超过1，下一次划分(排序)先处理其中哪一个部分，后处理哪一个部分，与先后次序无关紧要，而设置何种机制只是决定处理的先后次序而已。131415169101112567812345二、综合题1．p-llink-rlink=p;2．证明：假设满二叉树的结点总数为n，分支数为B，有n=n0+n2B=n-1由二叉树的性质(四)得到n2=n0-1，于是，n=2n0-1由此得到结论B=2n0-1-1=2(n0-1)证毕3．v1,v2,v3,v4,v5，v1,v3,v2,v4,v5，v1,v3,v4,v2,v54．三、算法设计题voidPRINTELE(intk){LinkkListlist,p,r;inti,a;list=(LinkList)malloc(sizeof(LNode));/*建立第一个结点*/r=list;for(i=1;ik;i++){p=(LinkList)malloc(sizeof(LNode));r-link=p;r=p;}r-link=list;/*建立循环链表*/p=list;while(scanf(“%d”,&a)0){p-data=a;p=p-link;}/*将数据依次读入链表*/r=p;do{printf(“%d”,p-data);p=p-link;}while(p!=r);/*依次打印所有元素*/}四、算法设计题#defineNodeNum100intTESTSORTTREE(BTREET){BTREESTACK[NodeNum],p=T;inttop=-1;datatypelast=MinValue;/*最小值*/if(T!=NULL){do{while(p!=NULL){STACK[++top]=p;p=p-lchild;}471011131456296p=STACK[top--];if(p-datalast)return0;/*不是二叉排序树*/last=p-data;p=p-rchild;}while(p!=NULL||top!=-1);}return1;/*是二叉排序树*/}五、单项选择题1．A2．C3．D4．B5．C6．A7．C8．D9．B10．D六、填空题1．非0的数字2．03．123.46或123.4600004．0和55．8806．47．1-28．129．510．=1或0或!=0七、程序设计题#includestdio.h#includestring.hmain(){intk;charstr1[80],str2[80];printf(“\nInputastring:\n”);gets(str1);printf(“Inputk:\n”);scanf(“%d”,&k);if(k=0||strlen(str1)k)printf(“Errorinput!\n”);/*若str1的长度