《北京航空航天大学-991-2014-真题.pdf》由会员分享，可在线阅读，更多相关《北京航空航天大学-991-2014-真题.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、北京航空航天大学2014年硕士研究生入学考试试题科目代码：991数据结构与C语言程序设计-.（共8页）少，考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效（本题单不参与阅卷）。一、填空（本题共20分，每小题各2分）1.设带有头结点的非空单向循环链表的链结点构造为尸rear为指向链尾结点的指针。删除链表头结点后面那个结点应该依次执行的语句是霞_,_o.2.为了增加空间的利用率和减少溢出的可能性，在两个堆栈共享一片连续空间时通常将两个堆栈的栈底位置分别设置在这片空间的两端，当一时才会产生上溢。3.如果一棵二叉树有1024个结点，其中465个是叶结点，那么，该二叉树中度为
2、1的结点的个数是4.已知在一棵二叉树中，a是b的祖先结点，若要通过遍历操作找到从年到b的路径，则在前序遍历、中序遍历、后序遍历和按层次遍历这4种遍历方法中，应该选择一一5.如果从无向图中的任意一个顶点出发进行1次深度优先搜索便可以访问到图中的所有顶点，这样的图一定是一_o6.在顺序表(b,c,d,e,f,g,q,r,s,t)中采用折半查找法查找元素b的过程中，被比较过的元素依次为7.所谓m阶B-对中的m是指一一,.,_,o、,.睿;、8.若n个关键字互为同义词，并且采用线性探测再散列法处理冲突，则将这组关键字散列到一个散列空间中，需要进行的探测次数为-:.9.在插入排序法、选择排序法、泡排序法
3、和快速排序法这4种排序方法中有一种方法，若初始时最小值元素位于待排序序列的最后，则在最后一趟排序开始之前，所有元第991-1页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研素都不在其最终位置上，这种排序方法是10.若采用泡排序法对序列(tang;d吐g,an,wang,shi,bai,fang,liu)中元素按值从小到大进行排序，则第2趟排序结束时的结果是.,-.,.o 二、简答（本题共20分，
4、每小题各5分）1.一个完整的算法通常应该具备哪5个最基本的特性？（可以不对各特性的具体意义进行解释）2.对于长度为n的线性表，下面给出的4种操作中，在顺序表上实现比在链表上实现效率更高的是哪一种？请分别用大O符号表示的时间复杂度形式说明你的理由。(1)输出线性表中第i个数据元素的值(1三i立）；(2)交换线性表中第 1 个数据元素与第 2 个数据元素的值；(3)依次输出线性表的n个数据元素；(4)输出线性表中与给定值x相匹配的数据元素在线性表中的序号。I3.具有n个结点且深度也为n的二叉树一共有多少种？请具体说明你的结论。4.为什么在建立散列表时若采用线性探测再散列法处理散列冲突容易产生聚集(
5、clustering)?采用其他什么方法可以减少这种聚集？三、问题求解（本题共20分，每小题各5分）1.设有编号分别为1,2,3的三辆列车顺序进入一个栈式结构的车站站台，请分别写出这三辆列车开出车站所有可能的顺序。2.已知对某二叉排序树进行前序遍历得到的前序遍历序列为C60,45,35,40,50,65,75,70),请画出该二叉排序树。3.若某无向图一共有16条边，并且有3个度为4的顶点，4个度为3的顶点，其余顶点的度均小于3,则该无向图至少有多少个顶点？（请写出结论的求解过程）4.在设计快速排序法的非递归算法时，通常利用了一个堆栈来记录待排序区间的首、尾两个端点的位置，而实际上也可以利用其
6、他数据结构（如队列）来代替这个堆栈。请说明其中的理由。第991-2页-r,各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研四、算法设计（本题15分）已知某具有n个顶点的有向图采用邻接表方法存储，其中，用以存储有向边信息的边结点类型为typedef struct edge int adjvex;存放某有向边的终止顶点在顶点结点中的位置struct edge*next;/*指向下一个边结点ELink;
7、用以存储顶点信息的顶点结点类型为typedef struct ver 存放某顶点的度存放一个顶点的数据信息int degree;vertype vertex;ELink*link;指向以该顶点为出发点的第一个边结点VLink;并且n个顶点结点构成一个数组GO.n-1。请写一个算法，该算法依次求出图中各顶点的度，并分别存放在相应的顶点结点的degree域中。五、单项选择（本题共20分，每小题各2分）1.下列关千C语言的自增和自减运算符的使用中，正确的是A.15+;B.(x+y)-;C.+(a-b);D.s+-i+t+u+。2.若有intx=lO;,则执行y=(2*8,x+=S)以后，x和y的值分
8、别是A.15和16;B.15禾日15;C.16和15;,.D.16和16。3.对于下列4种输入函数，当用户要输入的字符串中含有空格字符时，应该使用-A.scanf();B.getchar(.):C.gets();D.getc()。4.对于char sl=abed;2=a,b,c,d;,下列叙述中，正确的是一_o，A.数组sl与数组s2等价；、又二于;B.数组sl的长度与数组s2的长度相等；，C.数组sl的长度大于数组s2的长度；D.数组sl的长度小于数组s2的长度。第991-3页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k
9、 y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研5.设已有如下定义和语句：int a=4,b=3,*ptr,*qtr,*t;ptr=&a;qtr=&b;t=qtr;qtr=NULL;下列4条赋值语句中，错误的是_oA.*qtr=O;B.t=ptr;:C.*ptr=a;6.若从键盘上输入abc def,则下列程序的输出结果是。#include#include void main()char*ptr,*qtr;ptr=(char*)malloc(sizeof(ch杠）*20);qtr=ptr;scanf(%s%s,
10、ptr,qtr);printf(%s%s,ptr,qtr);A.defabc;7.已知变量定义如下：struct float x,y;char slO;point,*ptr=&point;B.defdef;下列4个表达式中，错误的是.C.abcdef;D.*ptr=*t;。D.abcabc。A.ptr-x=:2,0;B.(*ptr).3.0;C.poin.x=2.0:D.p忙s=str。8.若有宏定义#defmeAREA(a,b)a*b,则下列“宏调用”中，正确的是_oA.s=A邸A(r*r);C.s=c*AREA(x=3.5),(y+4.l);B.s=AREA(x*y);D.s=AREA。9
11、.设下列程序经编译链接后生成的可执行文件是test.exe。若运行该程序时输入带参数的命令行为test abed efg h3 k44回车，则程序执行后的输出结果是。#include#include void main(int argc,char*argv)第991-4页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研.!int i,len=O;for(i=l;i逛gc;i+:=2)len+=st
12、rlen(argvi);printfC%drr,len);A.6;B.8;r?.!、.蟠 -l;:C.12;10.下列程序的功能是-。#include void main()FILE*fp;fp=fopen(file.dat,r+);-while(!feof(fp)if(fgetc(fp)=*)fse.1c(fp,-lL,SEEK_C);fputc(节，fp);fseek(fp,ftell(fp),SEEK_SET);.心.、.气.-，.:.D.14。.-,.，.fclose(fp);A.将文件file.dat中的所有字符都换成；B,将文件file.dat中所有的都换成；C.查找文件file.
13、dat中所有的；D.查找文件file.,dat中所有的。六、简答（本题共20分，每小题各4分）,.i 1.在C语言中，intalO;a+;是否正确？为什么？2.在C语言中，strlen与sizeof的区别是什么？3.使用函数strcpy(char*s 1,char*s2)应该注意哪些问题？.4.在C语言中，什么是函数指针？什么是指针函数？（飞上5.递归程序在进行递归调用时通常用到递归工作栈，请问：通常情况下，该递归栈、,.中需要保存哪些信息？第991:-5页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o
14、 y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研噜七、程序阅读填空（本题共20分，每小题各4分）L若已有定义int alO);,则下列函数FUNC()的功能是在第一个循环中给数组的10个元素依次赋予1,2,3,4,5,6,7,8,9,10:在第二个循环中使数组a的后5个元素的值为前5个元素的逆序，即数组变成1,2,3,4,5,5,4,3,2,I。为了使该函数正确、完整，请写出函数的空白处（方框内）应该填入的内容；FUNC(int a)int k;for(k=l;k=IO;k+)亡k;for(k=O;k5;k+)亡ak;2.下列函数i
15、nt MINPRIME(int num)的功能是返回大千num的最小素数。例如：若nurn.=13,则函数返回素数17;若nurn.=29,则函数返回素数31。为了使该函数正确、完整，请写出函数的空白处（方框内）应该填入的内容。#include intM爪PRIME(int num)int k,j;k=n:um+l;while(l)forG=2;jk-1)return k;else k+;，,.-.人 力了,如果K不是素数、-.3.下列函数int INDEX(char str,.char substr)的功能是返回子串substr在主串str中的位置；若主串str中不存在子串substr,则函
16、数返回0。.提示：所谓一个子串在包含它的主串中的位置是指主串中首次出现的这个子串的第1第,991-6页金一，各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研扩3 个字符在主串中的位置。例如;i若-sBe,ijig and,.Nanjil?-g,substr=jg,则亚bstr在str中的位置为4。,为了使该函数正确、完整，请写出函数的空臼处:方框内）应该填入的内容。#include int INQ
17、Ei(9par str,char汜pstr)inti,j,k;for(i=O;stri;i+)forG=i,k=O;str(j=substrk;j+,k+)ifcr=可若主串中存在该子串return/*返回子串在主串的位置亡；return O;若主串中不存在该子串 ，4.下列函数的功能是用字符串str2替换字符串olds中所有出现的子串strL olds串中的其他字符丕变，并且将形成的新字符串存放在news中。例如：若olds=I23abl23x,strl=123,str2=45.,则news=45ab45x。为了使该函数正确、完整，请写出函数的空白处（方框内）应该填入的内容。void REP
18、LACE(char*olds,char*strl,char*str2,char*news)char*p,*q;while(*olds!=O)for(p=olds,q=strl;*p!=O&*q!=O&琏二二卫p+,q+);在olds中查找与strl相匹配的子串if(*q!=O)若在olds中未找到与怼strl相匹配的子串.it 、，*news+二；若在o、1c1s中找到与strl相匹配的子串 .else,4.-，for(q=str2;*q!=O;q+)为*news+=*q,l、.1.j气;_;、olds=p;.;-;_:个,.,气.,.,.t.,J.子俨,I.,令.:、-:、心.:,:.i(:
19、-.仁；，,.:七,:，r,今 J.，矿拿.,第991.:.7页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研、A t 宅全 -.5.下列程序的功能是找出由数字字符组成的文本文件钳e:.dat中的所有不同整数，并且分别将这些整数存放于一维数组a中。约定：该文本文件中的各整数之间以空格字符或者Tab(制表符）或者回车符分隔，并,.;!.,.且假定文件中的不同整数不超过1000个。为了使该程序正确、
20、完整，请写出程序的空白处（方框内）应该填入的内容。,.卢#include#define N 1000 void main()FILEfp，血aN,i,num,count;if(fp二Nl!LL)printf(Can not openfile!n);exit(O);.:,.-.-,打开文本文件*I count=O;while(fscan叽二二二b=l)a count=n;for(i=O;ai!=num;i+);.;.1.,.t:if1勹息count+;fclose(fp);，八、程序设计（本题15分）.-.（又.1 从文件中读一个整数-.、:.,.,.累计不同整数的个数:.f.俨，寸、.请编写一
21、程序，该程序的功能是计算并输出某子串substr在主串str中出现的次数。要求：-.,i.(1)把求子串在主串中出现次数的过程编写为一个独立的函数：int STRCOUNT(char*str,char*substr)，(2)若主串str中未出现子串substr,则函数STRCOUNT(char*str,char*substr)返回0。(3)在主函数中通过键盘输入方式分别给str与substr赋值，并且所有涉及到字符串的操作均通过指针完成。第991-8_1.页各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研