2017-2018年北航软件学院软件工程991数据结构与C语言程序设计考研大纲重难点

20XX年“数据结构与C程序设计”(代码991)试题一、单项选择题（本题共20分，每小题各2分）1．对于长度为n的线性表，建立其对应的单链表的时间复杂度为( )。

A．O(1)；B．O(log2n)；．O(n)；D．O(n2)。

2．一般情况下，在一个双向链表中插入一个新的链结点，( )。

A．需要修改4个指针域内的指针；B．需要修改3个指针域内的指针；C．需要修改2个指针域内的指针；D．只需要修改1个指针域内的指针。

3．假设用单个字母表示中缀表达式中的一个运算数(或称运算对象)，并利用堆栈产生中缀表达式对应的后缀表达式。

对于中缀表达式A+B*(C/D-E)，当从左至右扫描到运算数E时，堆栈中的运算符依次是( )。

(注：不包含表达式的分界符)A．+*/-；B．+*(/-；C．+*-；．+*(-。

4．若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70，则后序遍历序列为( )。

A．30,40,20,50,70,60,80；B．30,40,20,70,60,80,50；C．70,60,80,50,30,40,20；D．70,60,80,30,40,20,50。

5．分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼(Huffman) 树的深度为( )。

A．6；B．5；C．4；D．3。

6．下列关于图的叙述中，错误的是( )。

A．根据图的定义，图中至少有一个顶点；B．根据图的定义，图中至少有一个顶点和一条边(弧)；C．具有n个顶点的无向图最多有n(n-1)/2条边；D．具有n个顶点的有向图最多有n(n-1)条边(弧)。

7．若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是( )。

A．G中有弧<vi,vj>；B．G中没有弧<vi,vj>；C．G中有一条从顶点vi到顶点vj的路径；D．G中有一条从顶点vj到顶点vi的路径。

已今， f ., 北京航空航天大学2017年硕士研究生招生考试初试试题科目代码：991 数据结构与C 语言程序设计（共7页）考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的答题一律无效（本题单不参与阅卷）。

一、单项选择题（本题共20分，每小题各2分）1."数据结构”课程研究的内容主要包括＿——°A.数据的逻辑结构与存储结构；B.数据的逻辑结构与对数据进行的操作（即算法）；C.数据的存储结构与对数据进行的操作（即算法）；D.数据的逻辑结构、存储结构以及对数据进行的操作（即算法）。

2. 与单向链表相比，双向链表的优点之一是＿＿＿。

A.可以进行随机访问；B.可以访问链表中的相邻结点；C.链表的插入和删除操作更加简便；D . 可以节省头结点指针。

3.通常情况下，将递归算法转换为等价的非递归算法需要使用一种数据结构来保存中间结果，这种数据结构是A .堆栈； B.队列； c.二叉树； D.图。

4.深度为h的完全二叉树的结点总数不会超过一。

A.2气B.2h 一1;C .2h : D.2h +l 。

5.若某二叉树的前序遍历序列为a,b, e, f, c, d, g, 中序遍历序列为b,f, e, a , d, g, c, 则后序遍历序列为———°A.f, e, b, g, d, c, a;C.b, f , e, a, d , g, c;B.f, g, e , d, b , c, a ;D.f, e, b, a, g, d, c 。

t夕＿＿，一． 6.对千一个具有n 个顶点的有向图，其边数最多为＿＿＿。

A.nX(n -1)/2条；B. n-1条；C.nX(n-1)条；D.n 2条。

第991—1页k'/后计算表达式"1a+28+3吽…+n a"的结果。

需要注意的是，当a或者n小千等千0时，该函数返回0。

提示：可以先编写一个求解旷的辅助函数，再在psum函数中计算累加和。

北京航空航天大学
计算机学院-软件工程专业
专业类别时间总分划
线
专业划线复试总分招生人数录取比例
软件工程2011年
2012年
2013年320 80 320 20 1.2:1
专业考试科目及参考书目
专业类别及方向考试科目参考书目招生情况
软件工程
不区分研究方向初试科目：
政治
英语
数学一
计算机学科专业
基础综合（全国
统考）
复试科目：
C语言上机考试
综合面试初试参考书：
(1)《数据结构》严蔚敏清华大
学出版社。

(2)《计算机组成原理》唐朔飞
高等教育出版社
(3)《计算机操作系统(修订版)》
汤子瀛西安电子科技大学出版社
(4)《计算机网络(第五版)》谢
希仁电子工业出版社
2013年计
算机学院
开设软件
工程专业。

具体招生
人数请看
该年招生
简章。

附：参考书目。

【招生信息】2018年北京航天航空大学软件工程专业考研参考书目、招生人数、考试科目、复习经验021 软件学院研究方向：01 不区分研究方向招生人数:拟招收17人，其中推免10人。

考试科目：①101思想政治理论②201英语一③301数学一④991数据结构与C语言程序设计参考书目：1、北京航空航天大学出版社的《数据结构教程》，唐发根著；2、清华大学出版社的《C程序设计》，谭浩强著。

学制：学制2.5年，全日制学习方式。

006 计算机学院研究方向：01 不区分研究方向招生人数:拟招收30人，其中推免18人。

学制：学制2.5年，全日制学习方式。

考试科目：①101思想政治理论②201英语一③301数学一④961计算机基础综合参考书目：961计算机基础综合共包括三门课程的内容：计算机组成原理、操作系统、计算机网络技术，分别占60分，50分、40分。

所有课程均不指定参考书。

操作系统部分可参考书目：1.操作系统实用教程（第三版），任爱华，清华大学出版社。

2.现代操作系统(ModernOperatingSystem)(The3rdEdition),陈向群,马洪兵等译,AndrewS.Tanenbaum著,机械工业出版社。

计算机网络技术部分可参考书目：1、《计算机网络》(第6版)，谢希仁编著，电子工业出版社，20132、《计算机网络》(第5版)，AndrewS.Tanenbaum，严伟，潘爱民译，清华大学出版社，2012复习经验我的个人计划比较一般，在暑假前先把数学的书先看了一遍，把已经忘了的知识点捡了起来，然后想了想自己哪里的薄弱点，哪里还没有搞清楚。

在暑假的时候买了考研的真题考试做题，大概是做了有两遍左右，平均时长在两个小时左右，平均分数是120左右，在课下压力小一点，还有时间观念不是很强，有时候遇到没有想到的点，偶尔还会看看书还复习一下，这样一共看了两三遍，在暑假期间感觉不错，在后面的一个学期里面，我觉得数学复习还好，就开始重点的复习真题的题，并且还是回过头来看书，书上的，很多的小点，都有可能忘了，总是得时长复习一下，要不然到考试的时候有可能还真忘了。

北航考研复试班-北京航空航天大学软件学院软件工程专硕考研复试经验分享北京航空航天大学（Beihang University）简称北航，是中华人民共和国工业和信息化部直属、中央直管副部级建制的全国重点大学，世界一流大学建设高校，211工程、985工程重点建设高校，入选珠峰计划、2011计划、111计划、卓越工程师教育培养计划、中国政府奖学金来华留学生接收院校、国家建设高水平大学公派研究生项目、国家级新工科研究与实践项目、国家级大学生创新创业训练计划、国家大学生创新性实验计划、全国深化创新创业教育改革示范高校，为国际宇航联合会、中欧精英大学联盟、中国西班牙大学联盟、中俄工科大学联盟成员，是全国第一批16所重点高校之一、80年代恢复学位制度后全国第一批设立研究生院的22所高校之一，也是新中国第一所航空航天高等学府。

北京航空航天大学创建于1952年，时名北京航空学院，由当时的清华大学、北洋大学、厦门大学、四川大学等八所院校的航空系合并组建，1988年4月改名为北京航空航天大学，1989年成为国家八五期间全国14所重点建设的高校之一，首批进入“211工程”，2001年进入“985工程”，2017年入选国家“双一流”建设名单。

启道考研复试班根据历年辅导经验，编辑整理以下关于考研复试相关内容，希望能对广大复试学子有所帮助，提前预祝大家复试金榜题名！专业介绍软件工程硕士(MSE)Master of Software Engineering.2002年，全国35所高校的软件学院成为国家教育部批准成立的首批全国示范性软件学院，授权培养软件工程硕士，其主要目的就是培养从事软件工程各领域工作，如软件开发、项目管理、网络安全等具有较高学历层次的人才，以满足我国软件行业迅猛发展对高层次人才的需求，据启文中国在职研究生网了解到，教育部发出专业硕士学位改革通知，自2014年，已经不再进行34所院校的自主招生，转而进行GCT统一考试。

2016北京航空航天大学软件工程专业考研经验一、深入了解个人价值观，明确考研动机。

一般而言，无论我们要做什么样的选择，都需要对自己有个全面而且客观的了解。

“我为什么要考研?”很多学生会考虑到是否考研的利弊，但是很多同学会忽略非常重要的一点：即利与弊到底孰轻孰重则依赖于个体自身的因素。

对于女生而言，需要了解自己的特点、兴趣爱好、价值观以及个性倾向，这些信息能够帮助自我更加全面地考虑问题。

由于应试教育的原因，很多学生根本就不清楚自己喜欢什么。

研究生的报考是一个人对所学专业的第二次选择，在大学的四年对于自己也有了更多的了解，最好能够明确自己的喜好，比如是愿意学习人文类的内容还是理工类的内容，喜欢与人打交道还是喜欢钻研书籍、实验?性格是内向的还是外向的?愿意参与很多人参加的活动还是喜欢自己一个人独处?这些在不同的专业中都会有所体现，如果你的性格特点与所学的方向差异很大，对以后的研究生学习中和将来的就业都会有很大的影响。

此外，自己对于学业、情感、家庭、事业等因素的重视程度是怎样的?如果读研究生与现在的情感发展有冲突时，你愿意放弃什么?这些都是需要仔细考虑的问题。

对于为什么要考研，一定要有自己足够的分析。

是为了更好地学习专业知识?是为了更高的学历学识?是为了要换一个自己喜欢的城市?为了师从一个自己喜欢的导师?还是感觉别人都在考，自己不好意思被落下?是不是觉得不考研好像很失败?还是因为家人的期望?朋友的督促?不同的动机会带给你不同的结果，当你明确了自己的动机，就能更有针对性地选择自己的学校和方向。

最不好的情况就是不知道自己为什么考、考上以后会怎样，这样即使最后成功，也可能会在新的环境中充满新的困惑。

二、综合考察，做出适合自己的抉择。

孙子兵法云：“知己知彼，百战不殆”。

在了解自己之后，我们需要尽可能地对所要报考的目标有个清晰的了解。

在我接触的学生中，大概有70%的本科生在高考志愿填报时对所学专业不甚了解，以至于进入大学之后发现自己不喜欢或根本不适合所学专业。

考研攻略——北京航空航天大学软件学院考研初试总结本人本科北航软院，2018考研，报考北航软院学硕，总分375，政治56，英语一68，数学一114，专业课137，比起各400分大佬还差了不少，不过考研过程中也算是有点总结，希望分享出来给大家做做参考，如有不妥之处请指出。

闲话不多说，直接进入正题。

数学相信大家都知道数学在考研中的地位，基本上得数学者得高分吧，毕竟150的总分在那里摆着，我就是因为数学只有114才没能得到高分。

数学复习主要有以下几点：尽早开始（大三下期尽可能把第一遍过完，推荐用李永乐）套题很重要！速度很重要！训练后期训练以套题为主。

刷真题！（凡是真题中出现过的知识点，不会的或是记得不清的，一定要去复习清楚）除了李永乐，张宇的教材也建议买（我想很多人报班上万都舍得，多买几本书应该是没有问题的），因为个人感觉张宇的教材在某些知识点有独特的讲解很有收获。

但是张宇那三本不用全刷，在后续的复习过程中，一旦有某块知识有问题，就把张宇和李永乐的对应内容都可以看看，加深印象。

从九月份开始就可以进入刷套题的阶段了，严格控制时间非常有必要，因为考场环境下因为各种因素你的做题速度很可能比不上平时的状态。

平时尽量训练到自己能在两个半小时内完成套题，或者说训练自己在两个半小时内使自己的分数最大化。

这时候可以根据个人能力选择几天一套题，我才开始大概是两天一套，第一天早上做，第二天早上复习做错的知识点。

大概用了一个多月把数一的所有考研真题刷完了。

后面还做了李永乐和张宇的各种模拟题卷试卷的完成顺序也可以根据自己的擅长进行调整，比如我就觉得概率最容易做，其次高数，最后线代，所以我的试卷完成顺序是选题题—–>概率大题—–>高数大题—–>线代大题这个顺序只是提供参考，但是有时候好的顺序真的能帮你多拿分，就比如我高考那一年的理综，我一般做理综先生物后化学最后物理，事实证明是非常正确的，因为14年的四川理综卷，物理题很难，最后一道大题全省只有两三个人得了满分。

2017年硕士研究生入学考试专业课考研大纲一、考试组成961计算机基础综合共包括三门课程的内容：计算机组成原理、操作系统、计算机网络技术，分别占60分，50分、40分。

所有课程均不指定参考书。

二、计算机组成原理部分的考试大纲（60分）<一>、整体要求(一). 理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念；(二).理解计算机系统层次化结构概念，掌握以MIPS为代表的RISC指令集体系结构的基本知识，能对MIPS汇编程序设计语言的相关问题进行分析；(三).理解计算机存储系统的层次化结构，掌握层次化存储系统的设计、分析和性能计算；(四).能根据指令语义进行单周期、多周期或流水线MIPS处理器的数据通路及其控制器的分析和简单设计；(五).理解并掌握输入输出系统的基本知识。

<二>、知识要点(一)、计算机系统概述（1）计算机系统的基本组成与层次结构（2）计算机系统的性能指标：吞吐量、响应时间、带宽、延迟；CPU时钟周期、主频、C PI、CPU执行时间；MIPS、MFLOPS、GFLOPS、TFLOPS、PFLOPS。

(二)、数据的表示和运算（1）数制与编码（2）定点数和浮点数的表示和运算（3）算术逻辑单元ALU串行加法器和并行加法器算术逻辑单元ALU的功能和结构(三)、存储器层次结构（1）存储器的层次化结构（2）主存储器与CPU的连接（3）高速缓冲存储器(Cache)Cache的基本工作原理Cach和主存之间的映射方式Cache中主存块的替换算法与写策略多层次Cache性能计算（4）虚拟存储器虚拟存储器的基本概念页式虚拟存储器TLB(快表)(四)、MIPS指令系统及汇编语言（1）指令系统的基本知识（指令格式、寻址方式）（2）MIPS汇编语言(五)、MIPS处理器（1）CPU的功能和基本结构（2）单周期、多周期MIPS处理器数据通路的功能和基本结构（3）硬布线控制器的功能和工作原理单周期处理器控制器多周期处理器控制器（4）指令流水线指令流水线的基本概念流水线冒险及处理策略指令流水线的基本实现（六）、总线与输入输出(I/O)系统（1）总线的基本概念（2）磁盘存储器（3）I/O控制器I/O控制器的功能和基本结构存储映射I/O编址（4）基本I/O方式程序查询方式程序中断方式：中断的基本概念，中断响应过程，中断处理过程，多重中断和中断屏蔽的概念；DMA方式，DMA控制器组成，DMA传送过程，设备传输性能计算。

2019年北京航天航空大学991《数据结构与C语言程序设计》考试大纲2019年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。

试卷满分为150分。

“数据结构”部分一、概述1．数据的逻辑结构与存储结构的基本概念；2．算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。

二、线性表1．线性关系、线性表的定义，线性表的基本操作；2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。

三、数组1．一维数组和二维数组的存储；2．矩阵的压缩存储的基本概念；3．对称矩阵、对角矩阵以及三角矩阵的压缩存储。

四、堆栈与队列1．堆栈与队列的基本概念与基本操作；2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；4．堆栈和队列在解决实际问题中应用。

五、树与二叉树1．树与二叉树的基本概念，基本特征、名词术语；2．完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用；3．二叉树的顺序存储结构与二叉链表存储结的基本原理；4．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应用；5．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL 的计算。

六、图1．图的基本概念、名词术语；2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；3．图的深度优先搜索与广度优先搜索；4．最小(代价)生成树、最短路径、AOV网与拓扑排序的基本概念。

七、文件及查找1．顺序查找法以及平均查找长度(ASL)的计算；2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造；3．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。

991“数据结构与C语言程序设计”考试大纲（2019版）2019年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C语言程序设计”两门课程的内容，各占比例50%。

试卷满分为150分。

“数据结构”部分一、概述1．数据的逻辑结构与存储结构的基本概念；2．算法的定义、基本性质以及算法分析的基本概念，包括采用大 形式表示时间复杂度和空间复杂度。

二、线性表1．线性关系、线性表的定义，线性表的基本操作；2．线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理；3．在以上两种存储结构的基础上对线性表实施的基本操作，包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。

三、数组1．一维数组和二维数组的存储；2．矩阵的压缩存储的基本概念；3．对称矩阵、对角矩阵以及三角矩阵的压缩存储。

四、堆栈与队列1．堆栈与队列的基本概念与基本操作；2．堆栈与队列的顺序存储结构与链式存储结构的构造原理；3．在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计；4．堆栈和队列在解决实际问题中应用。

五、树与二叉树1．树与二叉树的基本概念，基本特征、名词术语；2．完全二叉树与满二叉树的基本概念，二叉树的基本性质及其应用；3．二叉树的顺序存储结构与二叉链表存储结的基本原理；4．二叉树的前序遍历、中序遍历、后序遍历和按层次遍历，重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应用；5．二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算。

六、图1．图的基本概念、名词术语；2．图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点；3．图的深度优先搜索与广度优先搜索；4．最小(代价)生成树、最短路径、AOV网与拓扑排序的基本概念。

七、文件及查找1．顺序查找法以及平均查找长度(ASL)的计算；2．折半查找法以及平均查找长度(ASL)的计算，包括查找过程对应的“判定树”的构造；3．散列(Hash)表的构造、散列函数的构造，散列冲突的基本概念、处理散列冲突的基本方法以及散列表的查找和平均查找长度的计算。

2016北京航空航天大学软件工程(专业学位)（工程硕士）考研经验我是今年考上了北航计算机的研究生，本科是中山大学的信息与计算科学专业。

初试364分，各科比较平衡，64，64，127，109，没有突出的。

这一年来经过了很多煎熬，现在基本上尘埃落定，写一写自己的经历和感受吧，相应一下版主的号召，也是为后来的同学提供一些经验和教训。

我用时间段分隔一下。

第一阶段，2010.3.1-2011.1.14准备初试我也没什么特别，现在回想起来我当时还是不够努力，上半年基本玩的很多，下半年大部分时候早上7点起床去图书馆占那个我每天都要去坐的位置。

我一零年三月初就买了李永乐的复习全书，大概到九月底我才全部完成，很慢。

主要是自己老是三天打渔两天晒网。

数学时间是在早上，差不多九月份以后每天早上一张数学卷子，时间上基本控制在三小时吧，其实有时候做的也不太好，反正马马虎虎这样也做了一些。

自己觉得总是会做，可是算不对的情况也很多。

127分的我都不太好意思说我是数学学院的。

计算机的课我是之前都学过，当时觉得再一本一本的看教材比较麻烦，就买了文都的辅导讲义，主要的东西总结的还成。

看完这个，又看了100个知识点那本，然后就是做了各路模拟题，我觉得模拟题都不太给力，不如真题那么有内涵。

考完就觉得计算机很难，做的不好，109分我也感觉比较满意了。

暑假上了一个政治强化辅导班，7天讲完了全部要点，实际上，除了给我了几个没压中的押题，我到后来12月份以后对当时讲了什么东西是一点也不记得了。

以为自己是政治素养很高的党员，以致到后来政治提前半小时交卷，64分是对我的惩罚。

英语的话，我复习的也一般，只不过我底子还不算太差，六级550，最后的分数就不算太难看64。

然后我最早用北航出版社的高级词频语境记忆，那本书真的很好，可是背了一百多页就没坚持下去，有点后悔。

其实英语还是要真题，越早看真题越好。

词汇基础要打牢，词汇也是关键。

整个准备复试阶段，其实我买的书是很多的，基本上能买的差不多都买了，不过相当一部分没怎么看，然后我经常是睡午觉睡到下午三四点，鲁能的每场比赛也是回宿舍看，出去玩啊什么的也挺多，自己虽然知道压力大，没办法我神经更大，觉得自己应该能考上，不够努力。