《北京航空航天大学-991-2016-真题.pdf》由会员分享，可在线阅读，更多相关《北京航空航天大学-991-2016-真题.pdf（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、北京航空航天大学2016年硕士研究生招生考试初试试题科目代码991数据结构与C语言程序设计（共8页）考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效（本题单不参与阅卷）。一、单项选择题（本题共20分，每小题各2分）L若listl和list2分别为一个指向单向链表与指向双向链表的指针变量则下列叙述中，正确的是A.list2比listl占用更多的存储单元；B.Iistl与list2占用相同多的存储单元；C.listl和list2应该是相同类型的指针变量；D.双向链表比单向链表占用更多的存储单元。2.下列关于队列的叙述中，错误的是A.队列是一种插入和删除位置受到限制的特殊
2、线性表；B.做删除操作时要先判断队列是否为空，做插入操作时要先判断队列是否已满；C.采用循环链表作为存储结构的队列称为循环队列；D.通常情况下，循环队列比非循环的队列的空间使用率要高。3.若push和pop分别表示对堆栈进行一次进栈操作和一次出栈操作，则将输入序列1,2,3转换为输出序列2,3,1所经过的操作依次为。A.push,push,pop,push,pop,pop;C.push,push,push,pop,pop,pop;B.push,pop,push,push,pop,pop;D.push,pop,push,pop,push,pop。4.若某完全二叉树的第6层有24个叶结点，则该完全
3、二叉树的结点总数最大为-一A.78;B.79:C.80;D.81。5.若某二叉排序树的后序遍历序列为10,20,40,60,50,30,则其前序遍历序列为。A.30,20,so;10,40,60;C.10,20,30,40,50,60;B.30,50,60,40,20,10;D.30,20,10,50,40,60。第991-1页0 各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研；,6.下列四种图
4、中，其对应的邻接矩阵为对称矩阵的是A.有向图；B.无向图；C.AOV网；D.AOE网。7令下列关千带权连通图的最小生成树的叙述中令正确的是一。A.最小生成树的代价不一定比该图其他任何一棵生成树的代价小；B.若图中出现权值相同的边时，则该图的最小生成树不是惟一的；c.若图中边上的权值各不相同，则该图的最小生成树是惟一的；D.该图的最小生成树的权值之和不一定是惟一的。8.下列关千查找操作的ASL(平均查找长度）的叙述中，错误的是一。A.查找成功的ASL是指找到指定元素所需要进行的关键字比较次数的期望值；B.查找失败的ASL是指没有找到指定元素，但找到该元素的插入位置所需要进行的关键字比较次数的期望
5、值；C.ASL与元素在结构中的分布状况有关；D.ASL与元素的查找概率无关。9.下列关于m阶B-树的叙述中，错误的是。A根结点至少有两棵子树；B.根结点至多有m棵子树；C.每个分支结点至少有侐121棵子树；D.所有叶结点都在同一层上。（说明：符号xl表示不小于x的最小整数）10.下列四种排序方法中，在一趟排序结束时不一定能够确定某一个元素的最终位置的是。.A,选择排序法；B泡排序法；C.堆积排序法；D.二路归并排序法口二、简答题（本题共20分，每小题各4分）1.线性表可以采用顺序存储结构，也可以采用链式存储结构。若在某应用中，对线性表的操作主要是插入和删除，则该线性表应该采用这两种存储结构中的
6、哪一种？为什么？2.如果二叉排序树的定义如下：二叉排序树或者为空，或者为具有以下特点的二叉树：对千任意分支结点，若其左孩子存在，则左孩子的值小于该分支结点的值；若其右孩子存在，则右孩子的值大于或者等千该分支结点的值。这种定义正确吗？如果你认为不正确，请举一个简单例子（画出一棵二叉树）说明你的结论，第991-2页-心巫.,、.易.各个学校计算机/软件专业考研真题 免费分享 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.对于一个有向图，除
7、了采用拓扑排序，还可以采用什么方法判断图中是否存在环（即回路）？请简要加以说明。4.若采用二叉树形式表示一个堆积(Heap),则这棵二叉树与二叉排序树的不同在哪里？（以大顶堆积为例）5.在排序方法中，若长度为n的顺序表初始时表中元素已经按值大小有序排列，则采用泡排序法的时间效率最高，采用快速排序法的时间效率最低。为什么？三、综合题（本题共20分，每小题各4分）1.已知非空双向链表的链结点定义如下：typedef struct nodeElem Type data;struct node*Hink,*rlink;*DLinkList;结点的数据域*I指向直接前驱、直接后继结点的指针域*!下面是删
8、除该链表中指针p所指结点的直接后继结点的算法。为了使该算法正确、完整，请写出算法的空白处（横线上方）应该填入的内容。DELETE(DLinkList list,DLinkList p)DLinkLi戏q;q可-:rlink;(1)(2)free(q);一条语句一条语句释放被删除结点的空间2.设非空满m叉树的定义如下：最下面一层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。若假设叶结点数目为助，分支结点数目为Um,则有结论：n。=(m-l)xnm+1 请写出该结论的推导过程。3.设G为具有n个项点的无向连通图，请采用数学归纳法证明G中至少含有n-1条边。4.在元素按值大小有序排列的顺序
9、表中进行折半查找，其查找过程可用一棵称之为判第991-3页,各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研定树”的二叉树来描述。请画出在长度为19的顺序表中进行折半查找所对应的“判定树”。s.若采用快速排序法对序列(49,38,65,97,76,13,27.49)的元素按值从小到大进行排序，请写出第一趟排序结束（即确定了序列的第一个元素49的最终位置）时序列的状态。四、算法设计题（本题15分）在
10、二叉树中，结点的祖先被定义为从根结点到该结点的所有分支上经过的结点。已知非空二叉树采用二叉链表存储结构，链结点定义如下：typedef struct node int data;结点的数据域struct node*lchild,*rchild;指向左、右孩子的指针域*BTREE;设根结点指针为T,请写一非递归算法，依次打印数据信息为item的结点的祖先结点。设该二叉树中数据信息为item的结点有且仅有一个，且该结点的祖先结点存在。五、填空题（本题共20分，每小题各4分）1.下面的函数atof是模拟C语言中同名库函数的实现，该函数的功能是将一个字符串转换为一个浮点数（为了简化问题，不考虑字符串格
11、式错误）。为了使该函数正确、完整，请写出函数的空白处（横线上方）应该填入的内容。血lude double atof(char s)double value=O.O,power=l.0;int i=O:si驴；/*sign表示数据的符号位，一1表示负数，1表示正数for(;isspace(si);i+);/*跳过前面的所有空白字符*Isign气(1)?一1:1;if(si;=十llsi一)i+;for(;isdigit(si);i+)value=1 O.O*value+(si一0);if(si=.)i+;for(;isdigit(si);i+)value=l O.O*value+(si-O);(
12、2);第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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 return sign*value/power;2.下面的函数min_ave函乒用来计算一个N*N的二维数组中每一行最小的数的平均值。为了使该函数正确、完整，请写出函数的空白处（横线上方）应该填入的内容。#defineN 4 double min_average(double aNN)double min,avemge=O
13、.O;int i,j;for(i=O;iN;i+)(1);forintj=l;jaifj)roinaii;(2);returnaverage/N;3.斐波那契数列是由斐波那契函数生成的一组数据序列，该函数定义为：f(n)=l 当n=l或者n=2时f(n一l)+f(n-2)当n2时在下面的C语言代码中，函数f为斐波那契函数的实现，函数print_丘bonacci用于打印n个斐波那契数列。为了使该函数正确、完整，请写出函数的空白处（横线上方）应该填入的内容。intf(int n)if(n=lfln2)return 1;else return(1);void print.,fibonacci(int
14、 n)inti;第991-5页各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研,试nl)printf(请输入正整数n);如仁丝凶prin贯%dt,f(i);4.下面的结构体Book用来描述一本图书的信息，用name表示图书名，number表示图书数菌date表示图书的出版日期，其中，出版日期也是一个结构体类型，由年(year)、月(month)和日(day)三部分组成，typedeftruct c
15、har ruune20;int n皿ber;struct int y祖r;int month;int day;date;Book;现声明这个结构体的两个变量:Book book,*pbook&book;请分别在横线上方写出相应的语句：，将变量book的图书名(name)设为cprogram的语句：(1).通过指针pbook将出版日期的年份(year)设为2015的语句：一丝L;5.下面的函数word_couht用来统计某个英文文本文件（通过参数fp指定该文件）中单词的个数，每个单词用空格、制表符或换行符分隔。为了使该函数正确、完整，请写出函数的空白处（横线上方）应该填入的内容。int word
16、_ count(FILE*fp)int we,found,i;wc=found=i=O;char ch;while(仁丛.L.)!=EOF)if(ch=)IJ(ch=W)IJ(ch=n)if(found)扫节c;foun,l=O;elsefound=!;if(2)+we;return we;第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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研 六、简答题（本题共20分，每小题各5分）1
17、.如何分别采用for语句和while语句表示一个无限循环？采用什么语句可以退出这种循环？2若某数组定义为inta20;,则a、*a、aO和a+S这四个表达式分别表示什么含义？3.已知带命令行参数的主函数的格式为int皿血(int argc,char*argv ),其中，参数argc和argv分别表示什么含义？对于Lux中的如下命令 团1-ffil.txt,其中的argc和argv的值分别是什么？4.带参数的宏可以实现类似于函数的功能，例如：下面宏定义SQR也可以实现计算x的平方的功能，它类似千中sqr函数的功能。#d efineSQR(x)(x)*(x)然而，在C语言中，这两种方式有着完全不同
18、的实现原理。那么，SQR宏和sqr函数的不同在哪里？七、程序设计题（本题15分）字符串处理函数strcmp(sl,s2)可以比较两个字符串的大小，其字符的大小是以ASCII码表上的顺序决定。该函数首先将sl第一个字符值减去s2的第一个字符值，若差值为0则继续比较对应的下一个字符，若不为0则该差值就是函数的最终结果。请参照该函数的实现原理，写出一个新的字符串比较函数strcmp.:.nc(sl;s2),该函数的功能与strcmp类似，但不区分字符串中的大小写字母，例如，字符a和字符A相等。要求：实现过程中不得使用任何已有的关于字符和字符串处理的库函数。八、程序设计题（本题20分）设存储在D盘根目
19、录下的文本文件score.dat中记录着学生的姓名和成绩，每一行表示一个学生的信息，包括学生姓名（姓名中不存在空格等特殊符号）和成绩，它们之间用制表符(t)分隔，例如：如ne11n84.5 Hsi 78 wangwu 65.5 maliu 90 第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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研夸请针对该文件写一个程序，该程序的功能是计算所有学生的平均成绩，并输出其中成绩最高的3个学生的信息名和成绩）；若学生总人数不足3人，则输出全部学生的信息。第991-8页.各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研