2018年南京工业大学828数据结构操作系统考研真题

苏州大学2018年硕士研究生入学考试初试试题（B卷）科目代码：872 科目名称：数据结构与操作系统满分：150分一、数据结构部分1、（15分）判断题，判断下列说法是否正确，如错误，指出错误之处。

（1）对于哈希（散列）查找，若采用线性探测法解决冲突，则装填因子α可以大于1。

（2）在A VL树上进行查找，平均查找长度为。

（3）一棵完全二叉树的高度为h，则该树至少有个结点。

（4）一个线性表，如果在对其进行操作的过程中表的长度经常发生变化，则采用顺序存储结构较合适。

（5）在使用后缀表达式计算表达式值时，应用队列存放操作数和操作符。

2、（15分）若要对一个序列进行排序，且需要对其进行次插入操作，以及次查找最大值的操作。

现有堆和二叉排序树两种数据结构，分别从平均情况和最坏情况下分析各数据结构的时间复杂度。

（1）若考虑平均情况，则应采用哪种数据结构，时间复杂度分别为多少，并进行分析。

（2）若考虑最坏情况，则应采用哪种数据结构，时间复杂度分别为多少，并进行分析。

3、（15分）一个线性表的元素均为正整数，使用带头指针的单链表实现。

编写算法：判断该线性表是否符合：所有奇数在前面，偶数在后面。

4、（15分）一棵用二叉链表实现的二叉树，其每个结点包括以下部分内容：结点值data，左孩子lchild和右孩子rchild，还有一个size存储该结点子树上的结点总数，现size还未赋值。

编写算法：为size赋值。

5、（15分）一棵采用孩子-兄弟表示法的树，编写算法：统计树中度为k的结点的个数。

二、操作系统部分1、（15分）简答题。

（1）什么是物理设备和逻辑设备，说明它们之间的关系。

（2）进程在CPU中执行时，操作系统有哪些操作模式，为什么要区分这些操作模式？（3）死锁解除的方法有哪些？请设计应用于手机操作系统的死锁解除方法。

2、（15分）采用动态优先级调度算法（优先数高的优先级低），根据运行时间和等待时间对优先数进行动态老化，具体老化算法如下：（a）处于等待状态的进程优先数p根据等待时间进行变化，每毫秒减一；（b）处于运行状态的进程优先数p根据运行时间进行变化，每毫秒加二；（c）优先数相同的进程按以下顺序调度：1）运行中的进程；2）先进入就绪队列的进程；（d）优先数p每隔1毫秒重新计算；（e）采用抢占式调度策略。

2018专业考试题及答案一、选择题（每题2分，共20分）1. 在计算机科学中，以下哪个是数据结构的基本概念？A. 算法B. 程序C. 编译器D. 栈答案：D2. 以下哪个不是操作系统的基本功能？A. 文件管理B. 内存管理C. 进程管理D. 数据加密答案：D3. 在数据库管理系统中，以下哪个操作用于查询数据？A. SELECTB. UPDATEC. INSERTD. DELETE答案：A4. 在网络协议中，TCP和UDP分别代表什么？A. 传输控制协议和用户数据报协议B. 传输数据包协议和用户数据报协议C. 传输控制协议和用户数据报协议D. 传输数据包协议和用户数据报协议答案：A5. 在软件开发中，敏捷开发方法的核心是什么？A. 需求分析B. 快速迭代C. 详细设计D. 代码重构答案：B6. 在项目管理中，哪个过程是项目生命周期的开始？A. 项目启动B. 项目规划C. 项目执行D. 项目收尾答案：A7. 在面向对象编程中，封装的主要目的是什么？A. 增加代码的可读性B. 隐藏对象的内部状态C. 提高程序的运行效率D. 减少程序的复杂性答案：B8. 在软件测试中，黑盒测试和白盒测试的区别是什么？A. 黑盒测试关注内部逻辑，白盒测试关注外部功能B. 黑盒测试关注外部功能，白盒测试关注内部逻辑C. 两者都只关注内部逻辑D. 两者都只关注外部功能答案：B9. 在项目管理中，风险矩阵通常用于什么？A. 任务分配B. 风险评估C. 进度跟踪D. 成本估算答案：B10. 在软件开发中，持续集成（CI）的主要优势是什么？A. 减少开发成本B. 降低软件质量C. 提高开发效率D. 减少代码重用答案：C二、简答题（每题10分，共30分）1. 请简述软件开发生命周期（SDLC）的主要阶段。

答案：软件开发生命周期（SDLC）的主要阶段包括需求分析、设计、实现、测试、部署和维护。

2. 解释什么是软件架构，并说明其在软件开发中的重要性。

保罗在1989年初被提升为达拉斯的经营合伙人。他采取了帮助他在 纽约工作时取得显著成效的同种富有进取心的管理方式。他马上更换了 几乎全部的25名专业人员，并制定了短期的和长期的客户开发计划。职 员人数增加的相当快，为的是确保有足够数量的员工来处理预期扩增的 业务。很快，办事处有了约40名专业人员。
但在纽约成功的管理方式并没有在达拉斯取得成效。办事处在一年 时间内就丢掉了最好的两个客户。保罗马上认识到办事处的人员过多 了，因此决定解雇前一年刚招进来的12名员工，以减少开支。
目 录
第一部分 南京工业大学823管理学历年考研真题 2005年南京工业大学管理学原理考研真题 2003年南京工业大学现代企业管理考研真题
第二部分 兄弟院校考研真题 2015年湘潭大学824管理学考研真题 2015年燕山大学812管理学考研真题 2015年暨南大学833管理学[专业硕士]考研真题
第一部分 南京工业大学823管理 学历年考研真题
D．财务成本计划 4．管理学家彼得·德鲁克认为，单纯强调利润会使经理人迷失方向 以至于危及企业的生存，因此他提出，企业目标唯一有效的定义就是 ( )。 A．信誉至上 B．创造顾客 C．技术创新 D．质量优良 5．定量预测是运用数学模型对事物未来的发展趋势作出定量、具 体描述的方法。它需要完整有效的( )作基础。 A．信息 B．数据资料 C．科学技术 D．模拟试验室 6．某企业制造并销售单一成品，固定成本总额为60万元，产品售 价为每件30元，单位变动成本为10元，该企业的盈亏平衡时的产量为 （ ） A.3000 B．2000 C.30000 D．20000 7．企业组织结构的核心内容是( )。 A．权责利关系
他相信挫折只是暂时性的，因而仍继续采取他的策略。在此后的几 个月时间里又增雇了6名专业人员，以适应预期增加的工作量。但预期 中的新业务并没有接来,所以又重新缩减了员工队伍。在1991年夏天的 那个“黑暗的星期二”，13名专业人员被解雇了。

数据结构考研真题与答案解析【数据结构考研真题与答案解析】数据结构是计算机科学与技术中的重要学科，也是考研中不可或缺的一部分。

在考研中，掌握数据结构的相关知识对于顺利通过考试至关重要。

本文将为大家介绍一些历年考研真题，并对答案进行解析，希望对大家备考有所帮助。

一、堆排序相关问题1. 2014年考研真题（题目描述）给定n个整数的序列S，其中$n \leq 10^6$且没有相同元素，并且给定另外的一个元素x，输出S中小于x的最大的数，如果不存在则输出“-1”。

（解析）这是一道关于堆排序的问题。

我们可以利用大顶堆来解决这个问题。

首先建立一个大顶堆，然后依次将序列S中的元素插入到堆中。

在插入的过程中，我们可以通过比较当前元素和x的大小，找到小于x的最大的数。

最后输出即可。

若不存在小于x的元素，则输出“-1”。

二、图的遍历问题2. 2016年考研真题（题目描述）对于一个无向图G，设计一个算法，判断图G是否连通，并给出详细的算法描述和复杂度分析。

（解析）对于这个问题，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

我们可以从图中的任意一个节点开始进行深度或广度遍历，然后标记遍历过的节点。

最后判断所有的节点是否都被遍历到，若是，则图G是连通的，否则不连通。

若使用邻接表表示图，则DFS和BFS的时间复杂度均为O(|V|+|E|)，其中|V|和|E|分别代表图中的节点数和边数。

三、二叉搜索树相关问题3. 2018年考研真题（题目描述）给定一个二叉搜索树，请设计一个算法，找出其中第k大的节点。

（解析）对于这个问题，我们可以利用二叉搜索树的性质。

由于二叉搜索树的中序遍历结果是有序的，我们可以进行中序遍历，并将遍历结果保存到一个有序数组中。

然后根据数组中第k个位置的元素找到对应的节点即可。

算法的时间复杂度为O(n)，其中n为二叉搜索树中节点的个数。

四、哈夫曼编码问题4. 2017年考研真题（题目描述）给定一段文字，编写一个算法，根据字符出现的频率构建哈夫曼编码。

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

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

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

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

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

A.01112B.01222C.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。

目　录第一部分　历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题第二部分　兄弟院校真题汇编2014年山东科技大学信息科学与工程学院830数据结构与操作系统考研真题2012年山东科技大学信息科学与工程学院838数据结构与操作系统考研真题2011年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题2010年山东科技大学信息科学与工程学院827数据结构与操作系统考研真题第一部分　历年考研真题汇编2006年南京工业大学计算机科学与技术学院828数据结构与操作系统考研真题南京工业大学耍堕年硕士研究生入学考试试卷（A）〈本试题150分、3小时）考试科目：数据埃构与操作系统诸应学科、专业：计算机应用技术（注意：所有答题内容均余写在答鬼地上，在试卷上答题-独无效！）第-部分,数据结构（共90分）一、选择题（每小题2分，共20分）1＞数据的存储结构有廉序、健式、族引和四种疆条形式.丸线性 B.树形C,散列D一图监2、计算机体法必^具备输入、输出和尊5个特性。

A,易读性、稳定性和安全性B可行性、可移植性和可扩充性C,牖定性、有穷性和秘定性可行性、确定性和有穷性3、指出下列时间要杂度最耶的级别是________.A.对数阶Ofhfcn）B.线性阶&n）C,指数阶。

（2"）D,平方阶0（『）4、己知模式串P='ABAABC',其next函数值是*A.011213B.012223C0LH22D,0112215、数组A中，行下标i义卜列下总j从1-10.每个元素的长度为3个字节，从首地址SA开始连续存糖.慢数组核列存放时，元素A”的起始地址为=A.SA+141B.SA+1S0C SA+222 D.SA+226、设无向图的顼点个数为n,聊谖无向图最多有________条辿.A.n;B.tt（n+l）/2C n（n-L）/2D n-17、将序列（50.72.43.85,73.20,35,45.65.30）构造为二叉排序树，杏找元素35重进行________次元素间的比较.A.10B.7C.5D.4一』、除度《设根的层次为L）的完全二又树至少有一^结点.七X尹C i*-T一 D.2W—-—----------------———9、下述几种排序方法中，能完成对突数数绍进行榆定捧序的是_______•,A、归弁样序 B.堆排序 C.快速排虏 D.痿数择序I。

1
(~)
3. 1!J 3 Jfr~~ij,~l:> a> 0, B ,r,7.a<JJj<.lf,fftf$~:
A. f/lJ::O-;
B. fti],ti:,
C.,~'f ~:
C. Mac= 4:rpiJ + Pl/8:
D. Mii(.: = 4i% + Plj8 •
~~,, I ,,,
Hale Waihona Puke .lm3s. ~J.mfB.U!Ff~m~JEtatt.Jat. ~~tniH.a~~1't:Jlt
B. ~~' =tit~~~;
D. =fl=,~;fifjt, ~~~:ff~~o
9. -ff~~ mll1**t¥.lli1iffl~1m, Jt~5*Jh
A. P-oM**;
B. f,¥JM~3't;
~~M*ffl1
~~--A~1*~W~o
liftll3 ~ hrtfi'Hn:N!/.Hll.JB ..
1. 'fi'!~?itE~mmm:
A. :f~MfffJ.E':~f~; B• .Rf!~MMI~'.ii:JatJJ: C• .R1igfpf-mH~U~; D. i'iJ"M{f'.f:~1i"J.
A. 0:
B. k;
C. -xJk;
D. .\'ifk o
i
'l
H
__t!..
,,?,,
I
(a)
6m .1 1m ,I, 3m I 3m ~.2m f
11) 15
ffl':
' IU!UUHIUIUUUtUlUI!,\

2018年南京大学842数据结构、软件工程、操作系统和计算机网络考研真题（回忆版）赞个人品，趁热回忆下真题。

今年的题感觉和17年的难度差不多，数据结构依旧没有算法题（准备了那么多呀），除了软工题型也都是之前见过的题型，唯独操作系统的那个UNIX进程的那个，是期末试卷的一道选择题，当时看时就没懂，也就没印象了。

软工的题型一直很活，很少有原题，两道大题蒙着答的。

总的来讲都是比较基础的，有很多原题，期末试卷中那些难的题都没有考。

名词解释感觉重在理解名词的含义，没必要死背，考前各科整理了n多个名词解释，一直因为这个性价比最低的背不下来感到没谱，结果考试要么是比较简单的（如计网的），要么是压根就没整理到的（OS的就没整理到）。

PV算法的话感觉把课件上那几个都掌握了，也就没问题了（注:我是跨考的，有些语言描述可能不规范，望谅解）数据结构（45分）一、填空（3×5）1．一个t叉树，有n个叶子节点，s个非叶子节点，写出n和s的关系2．快速排序最坏情况下时间复杂度3．给出二叉树前序序列和中序序列，写出后序序列4．赫夫曼树，n个叶子节点，求总的节点个数5．一个平衡二叉树，加入一个关键字后，重新调整为平衡二叉树二、大题（10×3）1．对关键码序列{23，17，12，61，26，8，70，75，53}，用堆排序方法进行排序，画出排序过程中所建的初始堆，以及输出前三个关键码过程的示意图。

（要求建立的堆为任一父母结点的关键码都小于其子女结点的关键码）2．请画出往下图的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码100后得到的B-树。

3．按Dijkstra方法计算从顶点1到其它顶点的最短路径。

按路径递增顺序写出先后计算出的最短路径（包括起止点和途径各点）及该路径长度。

软件工程（45分）一、问答题（5×5）1．说明下工程和科学的区别（政治题走错片场了吧？）2．什么是集成测试，什么是单元测试，单元测试用例和集成测试用例有什么区别3．功能性需求和非功能性需求4．写出四个体系结构视角5．质量模型的可用性二、大题（10×2）1．一个购房评估系统，一个类中含有两个功能，一个是输入存款、月工资、月花销、想要购房面积……完后得出可以购房的面积和首付款，另一个功能是根据面积和首都得出一个各小区的的房价列表，供用户参考，问这种设计合理吗？不合理的话画出设计类图并写出类的定义（含属性和方法）2．一个计算税费的问题，根据什么一堆经济的指标什么印花税、公证费、契税、委托办理手续费、房屋买卖手续费啥的，计算出税费，各地的计算方法不同，要求能够灵活扩展，按照一种设计模式设计，画出设计类图并写出关键接口定义。

件工程部分）
2007年南京大学软件基础一考研 真题（操作系统、数据结构部
分）
2007年南京大学软件基础三考研 真题（操作系统、数据结构部
分）
2008年南京大学软件基础一考研 真题（含操作系统、数据结构部
分）
2008年南京大学软件基础二考研 真题（操作系统、数据结构部
二、算法题 1 长度为n的数组a[0…n－1]，编写一个算法在O（n）的时间复杂
度内将数组中所有负数放在非负数前面。
2 已知first为不带表头结点的单链表的表头指针（如下图所 示），链表中存储的都是整型数据，试写出求所有结点的data域平均值 的递归函数。（软院05年数据结构期末题）
3 假设以数组Q[m]存放循环队列中的元素，同时以rear和length分 别指示环形队列中的队尾位置和队列中所含元素的个数，试用C＋＋语 言写出一个程序，给出该循环队列的类声明，给出队空条件和队满条 件，并写出相应的插入元素（Add）和删除（Delete）元素的算法（用 类模板，函数模板形式写）（软院04年考研原题）
目 录
1996年南京大学计算机考研真题（操作系统、数据结构部分） 1997年南京大学计算机考研真题（操作系统、数据结构部分） 1998年南京大学计算机考研真题（操作系统、数据结构部分） 1999年南京大学计算机考研真题（操作系统、数据结构部分） 2000年南京大学计算机考研真题（操作系统、数据结构部分） 2001年南京大学计算机考研真题（操作系统、数据结构部分） 2002年南京大学计算机考研真题（操作系统、数据结构部分） 2003年南京大学计算机考研真题（操作系统、数据结构部分） 2004年南京大学软件基础一考研真题（操作系统、数据结构部分） 2004年南京大学软件基础三考研真题（操作系统、数据结构部分） 2005年南京大学软件基础一考研真题（操作系统、数据结构部分） 2005年南京大学软件基础二考研真题（操作系统、数据结构部分） 2006年南京大学软件基础一考研真题（操作系统、数据结构、软件工程 部分） 2007年南京大学软件基础一考研真题（操作系统、数据结构部分） 2007年南京大学软件基础三考研真题（操作系统、数据结构部分）

3.设有四道作业，它们进入系统的时间及需要执行的时间如下表所示，并规定第一个作业进入系统后立即 调度，忽略调度的时间开销。
作业号 进入系统时间 需执行时间(分钟) 开始时间 完成时间 周转时间
1
9:00
70
2
9:40
30
3
9:50
10
4
10:10
5
求：(1)采用先来先服务调度算法时的调度次序和平局周转时间。(5 分) (2)采用最短执行时间优先调度算法时的调度次序和平均周转时间。(5 分)
1、写出图中的拓扑排序序列(分别采用栈和队列)(6 分) ①②③④
⑤
⑥
2、某电文中使用 5 个字符:a,b,c,d,e 出现的频率依次:为 2、4、5、9、10，试构造一棵对应的
哈夫树及哈夫曼编码,并计算其带权路径长度 WPL。(6 分)
3、由下列网络的邻接矩阵,画出此带权的图（v1～v6），并用 Kruskal 法画出它的最小生成
南京工业大学
2012 年硕士研究生入学考试初试试题（A 卷）
科目代码： 828 科目名称： 数据结构与操作系统 满分： 150 分 注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；
③本试题纸须随答题纸一起装入试题袋中交回！
第一部分：数据结构（共 90 分）
8、具有 10 个结点的完全二叉树的深度为
。
A.2
B.3
C.4
D.5
9、线性表进行二分查找时,要求线性表必须
。
A.以顺序方式存储
B.以链式方式存储
C.以链接方式存储，且结点按关键字有序 D.以顺序方式存储，且结点按关键字有序
10、对基本有序的表(21，36，40，54,，28，64，69，73)进行排序，下列哪种方法最好

南京工业大学2015年硕士研究生入学考试初试试题（A卷）科目代码：828科目名称：数据结构与操作系统满分：150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分：数据结构（共90分）一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。

每小题2分，共30分）1.下面算法的时间复杂度为。

int f（int n）{if（n==0||n==1）return1;else return n*f（n-1）}A.O（1）B.O（n）C.B.O（n2）D.O（log n）2.在一个长度为n的顺序存储的线性表中按照逐个比较的方法查找值为x的元素时（x在该线性表中），平均查找长度（即x与线性表中的元素平均比较次数，假定查找每个元素的概率都相等）为。

A.nB.n/2C.（n+1）/2D.（n-1）/23.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行的语句是。

A.p=q→next；p→netx=q→next；delete p；B.p=q→next；q→next=p；delete p；C.p=q→next；q→next=p→next；delete p；D.q→next=q→next→next；q→next=q；delete q→next；4.全元素按A，B，C，D顺序进入栈S，执行两次Pop（S，x）运算后，栈顶元素值是。

A.AB.BC.CD.D5.循环队列SQ队满的条件是。

A.SQ→rear==SQ→frontB.（SQ→rear+1）%MAXLEN==SQ→frontC.（SQ→rear+2）%MAXLEN==SQ→frontD.SQ→front==06.若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存两个字符，假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为。

南京工业大学2016年硕士研究生入学考试初试试题（A卷）科目代码：828科目名称：数据结构与操作系统满分：150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！第一部分：数据结构（共90分）一、单项选择题（下列每题给出的四个选项中，只有一项符合试题要求。

每小题2分，共30分）1.下面关于线性表的描述中，错误的是。

A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行的插入和删除操作C.线性表采用链式存储，不必占用一片连续的存储单元D.线性表采用链式存储，便于插入和删除操作2.在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行的语句是。

A.HL=p；p→next=HL；B.p→next=HL；HL=p；C.p→next=HL；p=HL；D.p→next=HL→next；HL→next=p；3.设有一个顺序栈，元素A，B，C，D，E，F依次进栈，如果6个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少为。

A.3B.4C.5D.64.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为。

A.O（m）B.O（n）C.O（m+n）D.O（m×n）5.在按行优先顺序存储的三元组表中，下列陈述错误的是。

A.同一行的非零元素，是按列号递增次序存储的。

B.同一列的非零元素，是按行号递增次序存储的C.三元组表中三元组行号是非递减的D.三元组表中三元组列号是非递减的6.具有10个叶结点的二叉树有个度为2的结点。

A.8B.9C.10D.117.在线索二叉树中，t所指结点没有左子树的充要条件是。

A.t→left=NULLB.t→ltag=TRUEC.t→ltag=TRUE且t→left=NULLD.以上都不对8.在结点数为n的堆中插入一个结点时，复杂度为。