2013年南京航空航天大学829计算机专业基础考研初试真题(A卷)

2017年南京航空航天大学829研究生入学考试真题南京航空航天大学2017年硕士研究生入学考试初试试题（A卷）科目代码:829满分:150 分科目名称:计算机专业基础注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（50分）1．（10分）为一个家谱管理程序设计一种数据结构，以一个四代人，11个家庭成员为例，（A有3个孩子A1、A2、A3；A1有2个孩子A11、A12；A2无子，A3有3个孩子A31、A32、A33；A11有1个孩子A111；A32有1个孩子A321；其余尚无子），画出家谱示意图，给出所设计的存储结构示意图，并给出在该存储结构上输出第k代所有人员的算法思想。

2．（10分）已知输入数据序列为(58,68,42,10,88,32,70,52,55,46 )，给出建立3阶B-树示意图，再给出删除55，70后的B-树。

3．（10分）试用Dijkstra算法，求下图中从V1到其余各顶点的最短路径，给出实现算法所用的数据结构和求解过程中每一步的状态。

4．（10分）设A、B为递减有序（元素值为整型）的单链表，编写函数，利用原结点将它们合并成一个递增有序的单链表，相同元素值只保留一个结点。

先给出算法思想，再写出相应代码。

5.（10分）设有n个学生成绩（0-100整数）的顺序结构线性表L，编写函数，将该线性表中调整为成绩及格（大于等于60）在不及格之前，要求T(n)=O(n), S(n)=O(1)。

先给出算法思想，再写出相应代码。

操作系统部分（50分）6. (16分) 简答（4分/题）（1）系统型线程和用户型线程有何区别？（2）分段式系统和分页式系统有何区别？（3）引入缓冲的目的是什么，有哪些常见的缓冲模式？（4）SPOOLING技术如何实现，在操作系统中起何作用？7. （7分）设有三道作业，它们的提交时间及执行时间由下表给出:作业号提交时间执行时间1 8.5 2.02 9.2 1.63 9.4 0.5试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间8. (9分) 某系统有A、B、C、D四类资源可供五个进程P1、P2、P3、P4、P5共享。

南京航空航天大学2014年硕士研究生入学考试初试试题（A 卷 ）科目代码: 829满分: 150分科目名称:计算机专业基础注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！（一、数据结构部分 50分）1.（10分）解释哈希表工作原理。

将关键字序列（75，54，48，90，18，22，84，63）存储在长度为10的哈希表中，使用哈希函数H(key) = Key % 10 ，并采用二次探测再散列法解决冲突，画出哈希表示意图。

2.（10分）试用Floyd 算法，求解下图中各顶点之间的最短路径，写出算法过程中每一步的状态。

3.（10分）设有6个字符，其权值为（12，40，16，8，14，10），给出进行Huffman 编码的数据结构和执行过程示意图。

4．（10分）设一个带头结点的单链表L，数据元素为（a1,a2,a3,a4,... ,an）,编写函数，调整该链表，使得数据元素次序为（a1, a3,...,an, ... ,a4,a2）, 要求T(n)=O(n)，先给出算法思想，再写出相应代码。

5.（10分）设有一家谱树T，用二叉链表结构存储（孩子兄弟表示法），树中的结点信息为成员名字。

编写函数，输出家谱中共有多少代以及最后一代人数和成员名字。

要求先给出算法思想，再写出相应代码。

（二、操作系统部分 50分）一．填空题(共10小题，每小题1分，共10分)1．下列关于操作系统的四种陈述中，正确的是：_________。

（A） 批处理操作系统必须在响应时间内处理完一个任务 （B） 实时操作系统必须在规定时间内处理完来自外部的事件 （C） 分时操作系统必须在周转时间内处理完来自外部的事件 （D） 分时操作系统必须在调度时间内处理完来自外部的事件V2V 4V 1V 312 237152.设有两个进程A、B，各按以下顺序使用P,V操作进行同步。

2013年南京航空航天大学827经济学考研真题及详解跨考网独家整理最全经济学考研真题资料库，您可以在这里查阅历年经济学考研真题，经济学考研资料，经济学参考书等内容，更有跨考考研历年辅导的经济学学哥学姐的经济学考研经验，从前辈中获得的经验对初学者来说是宝贵的财富，这或许能帮你少走弯路，躲开一些陷阱。

以下内容为跨考网独家整理，如您还需更多考研资料，可选择经济学一对一在线咨询进行解答。

一、名词解释（每题3分，共18分） 1．生产者剩余 答：生产者剩余指厂商在提供一定数量的某种产品时实际接受的总支付和愿意接受的最小总支付之间的差额。

它通常用市场价格线以下、SMC 曲线以上的面积来表示，如图1-1中的阴影部分面积所示。

图1-1生产者剩余也可以用数学公式定义。

令反供给函数为()S P f Q =，且市场均衡价格为0P ，厂商的供给量为0Q ，则生产者剩余为：()0000d Q PS P Q f Q Q =-⎰就单个生产者而言，生产者剩余是生产者所获得的价格超出边际成本的部分。

就整个市场而言，生产者剩余是供给曲线以上、市场价格以下部分。

2．逆向选择 答：逆向选择是指在买卖双方信息非对称的情况下，差的商品总是将好的商品驱逐出市场；或者说拥有信息优势的一方，在交易中总是趋向于作出尽可能地有利于自己而不利于别人的选择。

逆向选择的存在使得市场价格不能真实地反映市场供求关系，导致市场资源配置的低效率。

美国经济学家阿克洛夫在论文《柠檬市场：质量的不确定与市场机制》中提出著名的旧车市场模型，开创了逆向选择理论的研究先河。

他考察了一个次品充斥的旧车市场。

假设有一批旧车，每辆车的好坏只有卖主知道，要让交易做成，最合理的办法是按平均质量水平定价。

这就意味着其中有些好车的价格被低估了，从而卖方就不愿按照平均定价出售，或者卖方“理性”地抽走好车，让买主在剩下的差车中任意挑选。

如果买方明白这一道理，就不会接受卖方的定价，而只愿出较低的价格。

南京航空航天大学2013年硕士研究生入学考试初试试题（A卷）科目代码: 834满分: 150 分科目名称: 数据库原理及应用注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！一、简答题（10题，每题6分，共60分）1、试述数据、数据库、数据库系统、数据库管理系统的概念，并举例说明它们的区别。

2、定义并举例说明以下术语： ( l ）关系（ 2 ）元组 ( 3 ）主码（ 4 ）关系模式。

3、试述关系模型的完整性规则。

在参照完整性中，为什么外部码属性的值也可以为空？什么情况下才可以为空？并举例说明。

4、哪类视图是可以更新的？哪类视图是不可更新的？各举一例说明。

5、什么是数据库中的自主存取控制方法和强制存取控制方法？各举一例说明。

6、什么是数据库的逻辑结构设计？试述其设计步骤。

7、什么是活锁？什么是死锁？举例说明两者的区别。

8、为什么事务非正常结束时会影响数据库数据的正确性？举例说明。

9、什么样的并发调度是正确的调度？举例说明。

10、数据库安全性和计算机系统的安全性有什么关系？并举例说明。

二、应用分析题（2题，共90分）（一）图书馆信息管理系统 （1题共50分）某大学图书馆有两个校区，现设计数据库管理系统。

系统需求如下：1.图书馆有若干管理员librarian，各自有员工号empid、姓名name、身份证号idno、校区campus 等属性。

2.图书馆中备有若干种图书booktype，每种图书有ISBN、名称title、出版社publisher、作者writers、价格price等属性，每种图书有唯一的ISBN号，同种图书可购入多本。

3.每一本图书book有唯一标记bookid和种类booktype。

4.读者reader在办理借书证后方可借阅。

一个读者有唯一的借书证号cardno，还有姓名name、身份证号idno、住址address、注销标记logoff等。

目　录2014年南京航空航天大学829计算机专业基础考研真题2015年南京航空航天大学829计算机专业基础考研真题2016年南京航空航天大学829计算机专业基础考研真题2017年南京航空航天大学829计算机专业基础考研真题2018年南京航空航天大学829计算机专业基础考研真题2014年南京航空航天大学829计算机专业基础考研真题南京航空航天大学2014年硕士研究生入学考试初试试题（A卷）科目代码：829威岳尊料同席称：计算机专业基础‘5地力注意：①认真阅读答飓纸上的注意亭璃；①所有答案必濒写褂瓯制上，写在本试题纸或草稿舐上均无效；③本试题纸须随答趣纸一起装入试题袋中交回!（一、数据结构部分疝分）L（10分）解释哈希表工作原理*将关键字序列（75,54,48,90,18,22,8L S3）存储在长度为1。

的哈希表中，使用哈希函（key）=Key%10t并采用二次探测再散列法解决冲突，画出哈希表示意图*2.（10分）试用Floyd算法，求解下图中各顶点之间的最短路径，写出算法过程中每一步的状态*3.（10分）设有6个字符，其权值为（1L40,16,8,1L10）,始出进行Huffman的数据结构和执行过程示意图.< （10分）设一个带头结点的单链表L,数据元素为（<1,82,43,14,,..,an），编写函数,调整该链表，使得数据元素次序为（al,a3,...,an,...,a4,a2）,要求T（n）=0（n）,先给出算法思想，再写出相应代码.5.（3分）设有一家情树T，用二叉链表结构存健（孩子兄弟表示狭），树中的结点信息为成员洛字.编写函数，输出家谱中共有多少代以及最后一代人数和成员塔字.要求先给出算法思想，再写出相应代码.（二、操作系统部分S0分）一-填空飕（共10小题,每小题1分，共1。

分）1.下列关于操作系统的四种曝述中，正确的是：.........（A）批处理操作系统必须在响应时间内处理完一个任务（B）实时操作系统必须在规定时间内处理完来自外部的事件（C）分时操作系统必须在周转时间内处理完来自外部的事件（D）分时操作系统必须在调度时间内处理完来自外部的事件2.设有两个进程A、B,各按以下顺序使用P,V操作进行同步.A进程：B进程：al-风一P(sl}P(s2)a2-b2-Pis2)P(sl)V(s2)V(sl)a4-*b4V(sl)V(s2)b5-试问在下列执行顺序中，哪神情况会发生死锁？______(A)a】，a2,a*a4“，(B)bl,b2,b3,b4,bS…(C)al,a2,bl f b2,a3T b3...(D)al,bi,h2,b2,a3,b3…3.在内存管理中，内存利用率高且保护和共享容易的是......内存管理方式(AJ分区管理(B)分页管理(以分段管理(D)段页式管理4.操作系统中，很多事件会引起调度程序的逐行，但下列事件中不一定引起操作系统调度程序运行是------------(A)当前运行着的进程出错.(B)当前运行者的进程请求输入/输出*(C)有新的进程进入就绪状态，(D)当前运行的进程时间片用完.5.操作系统中调度算法是核心算法之一，下列关于调度算法的论述中正确的是：-(A)先来为服务调度算法对即对长作业有利也对段作业有利*(B)时间片轮调度算法转只对长作业有利，(C)实时调度算法也要考虑作业的长蕙问题*(D)高相应比者优先调度算法既有利于短作业又兼顾长作业的作业还实现了先来先服务. &操作系统中产生死锁的根本原因是_______(A)资源分配不当和CPU太慢(B)系统资源数量不足(C)作业调度不当利进程推进顺序不当(0)用户数太多和CPU大慢7.内存管理中把作业地址空间中使用的避辑地址转变为内存中的物理地址称为------(A)链接.(B)装入.(。

南京航空航天大学
2013年硕士研究生入学考试初试试题 A
科目代码： 827 科目名称： 经济学 满分： 150 分
注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！
一、名词解释（每题3分，共18分）
1. 生产者剩余
2. 逆向选择
3. 规模报酬
4. 自然失业率
5. 公开市场业务
6. “马歇尔—勒纳”条件
二、单项选择题（每题1分，共20分）
1. 假定商品X和商品Y是互补品，当商品Y的价格下降时，商品X的需求交叉弹性是（ ）。

A. 正值
B. 负值
C. 零
D. 不存在
2. 垄断竞争厂商的短期均衡一定发生在（ ）。

A．P=SMC，且d=D时
B．MR=SMC，且d=D时
C．平均成本降到最低时
D．主观需求曲线与平均成本曲线相切时
3. 折弯需求曲线模型是（ ）。

A．假定一个厂商提高价格，其他厂商就跟着提高价格
B．说明为什么每个厂商要保持现有价格，而不管别的厂商如何行动
C．说明为什么均衡价格是刚性的，而不是说明价格如何决定
D．假定每个厂商认为其需求曲线在价格下降时比上升时更有弹性
827 经济学第 1 页共 5 页。

南京航空航天大学2013年硕士研究生入学考试初试试题A 卷科目代码: 829科目名称:计算机专业基础满分: 150分注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！（一、数据结构部分 50分）1.(1)（2分）推导二叉树的性质3：度为2的结点数与度为0的结点数的关系。

(2)（3分）推导二叉树的性质4：求解N 个结点完全二叉树的高度。

(3)（5分））将关键字序列（75，24， 8，10，28，64，16，35）存储在长度为10的哈希表中，使用哈希函数H(key) = Key % 10，并采用二次探测再散列法解决冲突，说明关键字存储位置的计算方法，画出哈希表示意图。

2.（10分）试用Dijkstra 算法，求下图中从V1到其余各顶点的最短路径，写出算法过程中每一步的状态。

3.（10分）设稀疏矩阵用三元组顺序表存储，用下面例子说明快速转置算法的执行过程。

A 5×6=((1,3,8),(1,5,68),(3,1,12),(3,4,52),(3,5,3),(4,1,45),(5,1,26)) 4．（10分）已知有两个带头结点的单链表A 和B，元素值递增有序，编写函数，调整删减A 链表，使A 链表结点的元素值为A、B 的交集，并成为一个递减有序的单链表。

要求先给出算法思想，再写出相应代码。

5.（10分）编写函数，用非递归方法，求二叉链表表示的二叉树T 的高度。

要求先给出算法思想，再写出相应代码。

（二、操作系统部分 50分）1.简答题（20分，每题5分）（1） 为什么要引入线程，线程和进程有何区别？V2V 4V5V6 V 1V 3123137 7 516（2） 什么是通道，通道经常采用如图所示的交叉连接，为什么？通道1存储器控制器1控制器2通道2I/O设备1 I/O设备2 I/O设备3 I/O设备4（3）简述操作系统引入缓冲的原因？（4）何谓文件的物理结构，可分为哪几类，有何优缺点？2．(10分)假设有个南北向的胡同很窄，仅能容同方向的人顺序走过，相对方向的两个人则无法通过。

南京工业大学2013年硕士研究生入学考试初试试题（A 卷）科目代码：828科目名称：数据结构与操作系统满分：150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分：数据结构（共75分）一、选择题（每小题2分，共10分）1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的()和运算的学科。

A.结构 B.关系 C.算法 D.操作2、指出下列时间复杂度最坏的级别是。

A.对数阶O(log 2n) B.指数阶O(2n ) C.线性阶O(n) D.平方阶O(n 2)3、设S 和队列Q 的初始状态均为空,元素abcdefg 依次进入栈S 。

若每个元出栈后立即进入队列Q,且七个元素出队的顺序bdcfeag ，则栈S 的容量至少是（）。

A.1 B.2 C.3 D.44、已知模式串P=’ABAAB’，其next 函数值是()。

A.01112 B.01222 C.01122D.011235、对基本有序表(21,36,40,54,28,64,69,73)进行排序，使用下列哪种方法最好（）。

A.简单选择排序 B.直接插入排序 C.冒泡排序 D.归并排序二、填空题(每小题2分,共10分)1、线性结构中元素之间存在一对一的关系,图形结构中元素之间存在关系。

2、评价一个算法一般从4个方面进行:正确性、可读性、和。

3、找是具有特点的运算受限的线性表,队列是具有特点的运算变限的线性表。

4、动态查我表与静态查找表的区别是。

5、一组记录的关键字为(45,79,56,38,40,84)则利用堆排序方法建立的初始大根堆为。

三、计算应用题(共35分)1、某电文中使用5个字符:a,b,c,d,e 出现的频率依次:为2、4、5、9、10，试构造一棵对应的哈夫树及哈夫曼编码,并计算其带权路径长度WPL 。

(7分)2、由下列网络的邻接矩阵,画出此带权的图（v1～v6）及BFS 序列，并用Prim 法画出它的最小生成树(从v1出发)(6分)⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡03415012223401900201519011700011060120760172220001703、设关键字序列（10,6,4,10,15,12），插入生成平衡二叉排序树（画出平衡调整的过程并指出每次调整所属的类型）。

2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m +n 的降序链表，则最坏情况下的时间复杂度是（ ）。

A ．()O n B ．()O m n ⨯ C ．(min(,))O m n D ．(max(,))O m n 2．一个栈的入栈序列为1,2,3,,n ，其出栈序列是123,,,,n p p p p 。

若23p =，则3p 可能取值的个数是（ ）。

A ．3n -B ．2n -C ．1n -D ．无法确定3．若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）。

A ．0B ．1C ．2D ．34．已知三叉树T 中6个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。

A ．27B ．46C ．54D ．565．若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）。

A ．X 的父结点B ．以Y 为根的子树的最左下结点C ．X 的左兄弟结点YD ．以Y 为根的子树的最右下结点6．在任意一棵非空二叉排序树T 1中，删除某结点v 之后形成二叉排序树T 2，再将v 插入T 2形成二叉排序树T 3。

下列关于T 1与T 3的叙述中，正确的是（ ）。

I ．若v 是T 1的叶结点，则T 1与T 3不同II ． 若v 是T 1的叶结点，则T 1与T 3相同III ．若v 不是T 1的叶结点，则T 1与T 3不同IV ．若v 不是T 1的叶结点，则T 1与T 3相同A ．仅I 、IIIB ．仅I 、IVC ．仅II 、IIID ．仅II 、IV7．设图的邻接矩阵A 如下所示。

各顶点的度依次是（ ）。

2013 年全国硕士研究生入学统一考试—计算机专业基础综合试题2013 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题（科目代码 408）12013 年全国硕士研究生入学统一考试—计算机专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是int fact(int n){if (n<=1)return 1;return n*fact(n-1);}A. O(log2n)B. O(n)C. (nlog2n)D. O(n2)2．已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。

将中缀表达式a+b-a*((c d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是A. 5B. 7C. 8D. 113.若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点A.只有eB.有e、bC.有e、cD.无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为A. 10B. 20C. 32D. 335．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是A. O(n)B. O(e)C. O(n+e)D. O(n*e)6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是A.存在，且唯一C.存在，可能不唯一B.存在，且不唯一D.无法确定是否存在7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是22013 年全国硕士研究生入学统一考试—计算机专业基础综合试题A.d,e,fB.e,d,fC. f,d,eD.f,e,d8．下列关于最小生成树的说法中，正确的是I.最小生成树树的代价唯一II.权值最小的边一定会出现在所有的最小生成树中III.用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV.普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A.仅IB.仅IIC.仅I、IIID.仅II、IV9．设有一棵3阶B树，如下图所示。