2018南航922数据结构与操作系统考研真题

南京航空航天大学2018年硕士研究生入学考试初试试题（A卷 ）科目代码:834满分:150 分科目名称:数据库原理及应用注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！一、单项选择题（20题，每题2分，共40分）1. 下列关于数据库管理系统的叙述中，哪一条是错误的？（ ）（A）数据库管理系统是用户与操作系统之间的一个接口（B）数据库管理系统便于用户对数据库进行管理和维护（C）数据库管理系统能保证数据库中数据的安全性、完整性（D）数据库管理系统支持多用户对数据的并发使用2. 下列关于概念层模型的叙述中，哪一条是错误的？（ ）（A）概念层模型是现实世界到信息世界的语法抽象（B）概念层模型主要用于数据库设计中的概念设计（C）概念模型是从用户观点对数据和信息建模（D）概念模型独立于具体的逻辑模型3. 下列关于参照完整性约束的参照关系和被参照关系的叙述中，哪一条是错误的？（ ）（A）参照关系是从关系，被参照关系是主关系（B）参照关系与被参照关系之间的联系是1:n联系（C）参照关系与被参照关系通过外码相联系（D）其主码在另一个关系中作为外码的关系称为被参照关系4.下列关于用户定义完整性约束的叙述中，哪一条是错误的？（ ）（A）用户定义完整性约束主要是对属性的取值进行限制（B）域完整性约束是用户定义完整性约束的重要组成部分（C）取值范围可分为静态定义和动态定义两种（D）域完整性约束中含有属性间的多值依赖关系，但没有函数依赖关系5.基于"学生‐选课‐课程"数据库中的三个关系：学生表S（S#，SNAME，SEX，BIRTHYEAR，DEPT），主码为S#课程表C（C#，CNAME，TEACHER），主码为C#选课表SC（S#，C#，GRADE），主码为（S#，C#）查找"选修了C01号课程的全体学生的姓名和所在的系"， 下列SQL语句中哪一个是错误的？ （ ） （A）SELECT SNAME, DEPT FROM S WHERE S# IN (SELECT S# FROM SC WHERE C# ='C01')；（B）SELECT SNAME, DEPT FROM S WHERE S# = (SELECT S# FROM SC WHERE C# ='C01')；（C）SELECT SNAME, DEPT FROM S, SC WHERE C# ='C01' AND S.S# = SC.S#；（D）SELECT SNAME, DEPT FROM (S JOIN SC ON S.S# = SC.S#) WHERE C# ='C01'；6. 如果一门课程只能由一位教师讲授，而一位教师可以讲授若干门课程，则课程与教师这两个实体型之间的联系是 （ ）（A）一对一 （B）多对多（C） 一对多 （D）多对一7. 下列关于关系数据模型的叙述中，哪一条是错误的？（ ）（A）关系模型中数据的物理结构是一张二维表（B）在关系模型中，现实世界的实体以及实体间的各种联系均用关系来表示（C）插入、删除、更新是关系模型中的常用操作（D）关系操作通过关系语言实现，关系语言的特点是高度非过程化8. 在关系代数中，从两个关系的笛卡尔积中选取它们属性间满足一定条件的元组的操作称为（ ） （A）并 （B）选择（C）连接 （D）自然连接9. SQL语言十分简洁，完成数据定义、数据操纵、数据控制的核心功能只用了9个动词。

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. 解释什么是软件架构，并说明其在软件开发中的重要性。

《数据结构》复习提纲第一章数据结构的概念及基本结构，数据结构在计算机中的表示方法及其存储结构算法的特性，会计算时间复杂度第二章线性表的顺序存储表示，掌握插入和删除操作，线性表的链式存储表示，掌握单链表的插入和删除操作第三章栈的定义及特点，栈的顺序存储表示队列的定义及特点，链队列的插入和删除，循环队列的判空判满条件第四章串的概念及常用操作，掌握模式串next函数的求法第五章特殊矩阵的存储表示，稀疏矩阵的三元组表示，会求广义表的头部和尾部第六章树的定义和基本概念，二叉树的性质，二叉树的链式存储结构――二叉链表二叉树的先序，中序，后序, 层次遍历操作会对二叉树进行先序，中序，后序线索化操作树的存储结构――－孩子兄弟表示法树，森林，二叉树三者之间的转换方法，以及它们遍历的对应关系掌握哈夫曼树的构造，会求树的带权路径长度WPL第七章图的定义和术语，图的邻接矩阵表示法，邻接表，逆邻接表掌握图的深度优先搜索算法，广度优先搜索算法最小生成树――普里姆算法和克鲁斯卡尔算法，会对AOV网进行拓扑排序会求AOE网的关键路径，关键活动第九章顺序查找表，有序表的折半查找，索引查找表及其平均查找长度ASL二叉排序树的建立和删除操作，会计算其平均查找长度ASL掌握将二叉排序树转换成平衡二叉树的旋转处理方法，哈希表的概念，掌握哈希函数的构造方法――除留余数法掌握处理冲突的方法――线性探测再散列及平均查找长度ASL――二次探测再散列及平均查找长度ASL第十章直接插入排序，希尔排序，快速排序，简单选择排序，堆排序，归并排序会写上述排序算法每趟排序的结果，并对其进行排序性能分析（稳定性，时间复杂度等）期末考试题型：选择题，填空题，综合题练习题一、单选题1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（c）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，12.下列排序方法中，关键字的比较次数与记录的初始排列状态无关？（ c ）A. 直接插入排序B. 起泡排序C. 快速排序D. 直接选择排序3.对n个记录的文件进行二路归并排序，总的时间代价为（ d）A. O（nlogn）B. O（n2）C. O（logn）D. O（n）4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（b ）A. 9B. 11C. 12D. 不确定5．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（d）A．q一>next＝p一>next；p一>next＝q；B．p一>next＝q一>next；q＝p；C．q一>next＝p一>next；p一>next＝q；D．p一>next＝q一>next； q一>next＝p；6.广义表A=（a,b,(c,d),(e,(f,g))）,则式子Head(Tail(Head(Tail(Tail(A)))))的值为 d ；A．（g） B.(d) C.c D.d7. 直接插入排序在最好情况下的时间复杂度为（d）。

南京航空航天大学
2012年硕士研究生入学考试初试试题 A
科目代码： 922 科目名称： 数据结构与操作系统(专业学位) 满分： 150 分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！
图第题图
分）已知输入数据序列为{38, 66, 18, 80, 58, 52, 26, 42, 28, 16}，给出建立B-树示意图，再给出删除28，52B-树。

分）已知序列{108, 170, 503, 87, 512, 161, 175, 53, 897, 462}，写出采用堆
排序法对该序列作降序排序时的每一趟结果。

为带头结点的单链表，元素值为整数。

设计一个算法，调整结点的位置，
将所有元素值为负数的结点移动到元素值为正数的结点之前，要求时间复杂度
要求先给出算法思想，再写出相应代码。

分）设树采用孩子兄弟链表结构进行存储，设计一个算法，求树的宽度（即具有结。

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

922数据结构与操作系统（专业学位）第 1 页共4页。

南京航空航天大学2015年硕士研究生入学考试初试试题A 卷科目代码: 922科目名称:数据结构与操作系统(专业学位)满分: 150分注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（75分）1．（5分）已知一棵完全二叉树共有999个结点，试求以下问题，并给出求解过程。

(1) 树的高度 (2) 叶子结点数2．（10分）应用栈操作求解算术表达式：(28+10*2)/(11-5),画出栈的变化过程。

3．（10分）已知带权图如下所示，用Prim 算法从顶点2开始产生最小生成树，说明算法思想，并给出求解所需的数据结构和每一步执行过程的相关数据变化。

4．（10分）已知输入数据序列为 (68, 40, 25, 21, 33, 12, 58, 51, 16,36)，给出建立3阶B-树示意图，再给出删除51，16后的B-树。

5．（10分））解释希尔排序的算法思想。

对以下的数据序列，给出希尔排序过程的示意图。

(46,8,36,50,6,24,18,78,12,10)6．（10分）设一个带头结点的单链表L，数据元素为整数，编写函数，通过调整该链表的结点指针，对该链表进行简单选择排序（元素值从小到大）。

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

7.（10分）设二叉树T，用二叉链表结构存储。

编写函数，输出最长一枝（根到叶子）上的所有结点值。

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

8．（10分）基于图的广度优先搜索策略，编写函数，判别以邻接表存储的有向图G 中，是否存在由顶点Vi 到顶点Vj 的路径（i≠j）。

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

V4V2V6V3V5V1 2 15458 3664操作系统部分（75分）1.（30分）文件系统是操作系统的主要功能之一，请设计一个文件系统，需给出以下信息：（1）给出描述文件的数据结构（即文件控制块）和目录结构；（5分）（2）以索引节点为文件系统的物理文件组织结构，图示索引节点结构，说明其优点；（5分）（3）以线性检索法作为此文件系统的文件检索方法，以实例方式给出检索一个文件的过程（例如查找／usr／ast／mbox）；（10分）（4）为该文件系统设计几个必要的系统调用，选其中一个为例，详细说明实现该系统调用的方法和过程（注意要使用以上设计中的数据结构）。

2018江苏南京航空航天大学数据库原理及应用考研真题一、单项选择题（20 题，每题 2 分，共 40 分）1. 下列关于数据库管理系统的叙述中，哪一条是错误的？（）（A）数据库管理系统是用户与操作系统之间的一个接口（B）数据库管理系统便于用户对数据库进行管理和维护（C）数据库管理系统能保证数据库中数据的安全性、完整性（D）数据库管理系统支持多用户对数据的并发使用2. 下列关于概念层模型的叙述中，哪一条是错误的？（）（A）概念层模型是现实世界到信息世界的语法抽象（B）概念层模型主要用于数据库设计中的概念设计（C）概念模型是从用户观点对数据和信息建模（D）概念模型独立于具体的逻辑模型3. 下列关于参照完整性约束的参照关系和被参照关系的叙述中，哪一条是错误的？（）（A）参照关系是从关系，被参照关系是主关系（B）参照关系与被参照关系之间的联系是 1:n 联系（C）参照关系与被参照关系通过外码相联系（D）其主码在另一个关系中作为外码的关系称为被参照关系4. 下列关于用户定义完整性约束的叙述中，哪一条是错误的？（）（A）用户定义完整性约束主要是对属性的取值进行限制（B）域完整性约束是用户定义完整性约束的重要组成部分（C）取值范围可分为静态定义和动态定义两种（D）域完整性约束中含有属性间的多值依赖关系，但没有函数依赖关系5. 基于"学生‐选课‐课程"数据库中的三个关系：学生表 S（S#，SNAME，SEX，BIRTHYEAR，DEPT），主码为 S#课程表 C（C#，CNAME，TEACHER），主码为 C#选课表 SC（S#，C#，GRADE），主码为（S#，C#）查找"选修了 C01 号课程的全体学生的姓名和所在的系"，下列 SQL 语句中哪一个是错误的？（）（A）SELECT SNAME, DEPT FROM S WHERE S# IN (SELECT S# FROM SC WHERE C# ='C01')；（B）SELECT SNAME, DEPT FROM S WHERE S# = (SELECT S# FROM SC WHERE C# ='C01')；（C）SELECT SNAME, DEPT FROM S, SC WHERE C# ='C01' AND S.S# = SC.S#；（D）SELECT SNAME, DEPT FROM (S JOIN SC ON S.S# = SC.S#) WHERE C# ='C01'；6. 如果一门课程只能由一位教师讲授，而一位教师可以讲授若干门课程，则课程与教师这两个实体型之间的联系是（）（A）一对一（B）多对多（C）一对多（D）多对一7. 下列关于关系数据模型的叙述中，哪一条是错误的？（）（A）关系模型中数据的物理结构是一张二维表（B）在关系模型中，现实世界的实体以及实体间的各种联系均用关系来表示（C）插入、删除、更新是关系模型中的常用操作（D）关系操作通过关系语言实现，关系语言的特点是高度非过程化8.在关系代数中，从两个关系的笛卡尔积中选取它们属性间满足一定条件的元组的操作称为（）（A）并（B）选择（C）连接（D）自然连接9. SQL 语言十分简洁，完成数据定义、数据操纵、数据控制的核心功能只用了 9 个动词。

目　录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)装入.(。

2019年南京航空航天大学922初试真题
2019南航922初试：
数据结构
1平衡二叉树的建立与调整
2广义表的两种表示
3堆的建立与调整
4哈夫曼树的建立与调整+哈夫曼树的数据结构定义
5最小生成树
6链表（删除a链表在b中有的结点）
7二叉树（求繁茂度（高度乘以宽度）
8判断所有结点能到其余个结点，如果能则输出
操作系统
1概念（进程控制快dma 临界区和进程控制原则文件物理和逻辑2进程调度（（1）fcfs sjf平均周转时间（2）抢占式sjf）
3磁盘调度
4虚拟存储器（页面置换算法）
5分页存储管理
6pv操作。