2015年南京航空航天大学922数据结构与操作系统真题

南京航空航天大学2016年硕士研究生招生考试初试试题（A 卷）科目代码: 829科目名称:计算机专业基础满分: 150分注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（50分）1．（10分）求下图中的关键路径，给出算法思想和求解过程每一步的状态。

2．（10分）输入关键字序列（55，12，24, 47,30, 68，19），建立平衡二叉树。

说明算法思想，给出插入和调整的具体过程示意图。

3．（10分）说明基数排序的算法思想和数据结构，对数据序列( 130, 6, 458, 92, 12, 836, 250, 59, 525, 272 )，给出基数排序过程示意图。

4．（10分）设L 为带头结点的单链表，元素值为整型。

编写函数，删除L 中的重复结点（具有相同元素值的结点只保留一个）。

先给出算法思想，再写出程序代码。

5.（10分）已知一棵二叉链表表示的二叉树T，编写函数，判断T 是否是完全二叉树。

先给出算法思想，再写出程序代码。

操作系统部分（50分）6．（10分）回答下列问题：（1）试说明页面置换算法在虚拟存储管理中的重要性。

（2分） （2）FIFO 算法适用于什么场合，又有何缺点 。

（2分）（3）设页面走向为1,2,3,4,1,2,5,1,2,3,4,5，当物理页框数分别是3和4时，试问：采用FIFO、LRU 置换算法产生的缺页中断分别是多少？（这里假设内存开始时都是空的并且只要是第一次用到的页面都产生缺页中断）（6分）7.（10分）A、B 两个程序，程序A 按顺序使用CPU 10秒，使用设备甲5秒，使用CPU 5秒，使用设备乙10秒，最后使用CPU 10秒，程序B 按顺序使用设备甲10秒，使用CPU 10V2V 4V6V5 V 1 V 3a7=6a4=5 a8=1 a2=6a3=2a6=7a5=4a1=8（1）在顺序环境下执行程序A和程序B,CPU的利用率是多少？（3分）（2）在多道程序环境下，CPU的利用率是多少？请画出A、B程序的执行过程。

计算机专业基础综合数据结构（图）历年真题试卷汇编4(总分：58.00，做题时间：90分钟)一、综合题(总题数：7，分数：14.00)1.已知一图如下图所示：(1)写出全部拓扑排序；(2)以V1为源点，以V8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；(3)求V1结点到各点的最短距离。

【北京邮电大学2000五(15分)】__________________________________________________________________________________________正确答案：(正确答案：关键路径有3条，长17。

各事件允许发生的最早时间和最晚时间略。

V1→V2→V6→V8，V1→V3→V5→V7→V8，V1→V7→V8→V1→V4→V5→V8 (3)V1结点到其他各结点的最短距离为：2，3，6，12，10，15，16。

)2.(1)对于有向无环图，叙述求拓扑有序序列的步骤；(2)对于以下的图，写出它的四个不同的拓扑有序序列。

【南开大学1998二(12分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)对有向图，求拓扑序列步骤为： 1)在有向图中选一个没有前驱(即入度为零)的顶点并输出。

2)在图中删除该顶点及所有以它为尾的弧。

3)重复1)和2)，直至全部顶点输出，这时拓扑排序完成；否则，图中存在环，拓扑排序失败。

(2)这里使用形式化描述方法，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉拓扑序列。

这里只画出从顶点1开始的所有可能的拓扑序列，从顶点3开始的拓扑序列可类似画出。

)3.有向图的拓扑排序能否用图的深度搜索模式来查找?若能，请简述方法；若不能，请简述原因。

【西北大学2000二、8(5分)】__________________________________________________________________________________________ 正确答案：(正确答案：图的深度优先遍历可用于拓扑排序。

2022年南京航空航天大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。

A.插入B.选择C.希尔D.二路归并3、链表不具有的特点是（）。

A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

南京航空航天大学2002年操作系统试题考试科目：操作系统说明：答案一律写在答题纸上一、填空（每小题5分，共20分）（注意：答题时先给出填空内容，再作必要的说明）1、设系统中仅有一个资源类，其中共有3个资源实例，使用此类资源的进程共有3个，每个进程至少请求一个资源，它们所需资源最大量的总和为X，则发生死锁的必要条件是：_________。

2、在一个请求分页系统中，采用先进先出页面置换算时，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5，当分配给该作业的物理块数M分别为3和4时，访问过程中发生的缺页次数为_________和_________。

（假定开始时，物理块中为空）3、设系统中有三种类型的资源（A、B、C）和五个进程（P0，P1，P2，P3，P4），某时刻的状态如下：根据银行家算法可知，该时刻存在着一个安全序列：____________________________________。

4、根据Bernstein 条件（程序能并发执行，且具有可再现性的条件），则如下4条语句中：S1： a:=x+yS2：b:=z+1S3：c:=a-bS4：w:=c+1S1和S2两条语句_________并发执行，S3和S4两条语句_________并发执行。

（本小题填空时考虑：是否可以并发执行）二、回答下列问题（每小题6分，共30分）1、什么要引入设备独立性？如何实现设备独立性？2、举例说明在分页系统中，如何实现内存共享？要求图示说明。

3、从用户角度看，引入线程后有何好处？4、生产者－消费者问题的同步算法中，为什么颠倒生产者进程中的两个P操作的次序，将导致进程死锁？5、Intel 80386在保模式下工作时，为什么对内存有保护作用？三（10分）进程P1和P2通过两个缓冲区给进程P11、P12、P21、P22传递信息，进程P11、P12取进程P1的信息，进程P21、P22取进程P2的信息。

假定这两个缓冲区一样大小，所要传递的信息也与缓冲区一样大，同一时刻只能由一个进程往缓冲区中送信息或取信息。

2015年南京航空航天大学821信号系统与数字信号处理考研专业课真题科目代码：821科目名称：信号系统与数字信号处理第1页共4页南京航空航天大学2015年硕士研究生入学考试初试试题（A 卷）科目代码: 821科目名称: 信号系统与数字信号处理满分: 150分注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无一、填空题（每空1分，共30分）1. 已知某连续时间系统的输入输出关系为()()()de t r t t e t dt=+，其中()r t 为系统响应，()e t 为系统激励，试判断该系统是（线性、非线性）________，（时变、时不变）________，（因果、非因果）________，（稳定、不稳定）________；2. 线性时不变离散时间系统的单位函数响应()()()312k k h k k k εε?=??+，判别系统的因果性、稳定性________，________；3. ()f t 是周期为T 的周期信号，其傅里叶级数展开式可表示为()12jn t n n f t A e ∞?=?∞=∑i ，其中?=________，称为________，n A =i ________；()f t 也可表示为()01()cos 2n n n a f t A n t φ∞==+??∑，其中02a =________，称信号的________分量，n A i 与n A ，n φ的关系为________；4. 若实信号)(t f 的频带宽度为210Hz ，则)43(?t f 的频带宽为________Hz ，(4)cos10003t f t π?的带宽为________Hz ； 5. 线性时不变连续时间因果系统的系统函数213()32s H s s s s +=?++，系统零输入响应的一般形式()zi r t =________，系统是否稳定？（请在稳定、不稳定、临界稳定中选择填空）________，系统转移函数()H j ω=________；6. 设23()252z F z z z =?+为离散信号()f k 的单边Z 变换，则(0)f =________，(1)f =________，()f ∞=________；。

科目代码：922科目名称：数据结构与操作系统(专业学位) 第1页 共3页 南京航空航天大学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）。

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

V4V2V6V3V5 V12 1 5 45 83 6 6 4。

2022年南京航空航天大学计算机科学与技术专业《计算机系统结构》科目期末试卷A（有答案）一、选择题1、计算机系统的层次结构按照由高到低的顺序分别为（）。

A.高级语言机器级，汇编语言机器级，传统机器语言机器级，微程序机器级B.高级语言机器级，应用语言机器级，汇编语言机器级，微程序机器级C.应用语言机器级，传统机器语言机器级，汇编语言机器级，操作系统机器级D.应用语言机器级，操作系统机器级，微程序机器级，传统机器语言机器级2、下列说法中不正确的是（）A.软件设计费用比软件重复生产费用高B.硬件功能只需实现一次，而软件功能可能要多次重复实现C.硬件的生产费用比软件的生产费用高D.硬件的设计费用比软件的设计费用低3、在计算机系统设计中，比较好的方法是( )A.从上向下设计B.从下向上设计C.从两头向中间设计D.从中间开始向上、向下设计4、与全相联映象相比，组相联映象的优点是( )A.目录表小B.块冲突概率低C.命中率高D.主存利用率高5、传统机器语言机器级，是用（）来（）机器指令。

A.硬件，翻译B.编译程序，翻译C.微指令程序，解释D.微指令程序，翻译6、在系统结构设计中，提高软件功能实现的比例会( )。

A.提高解题速度B.减少需要的存贮容量C.提高系统的灵活性D.提高系统的性能价格比7、在流水机器中，全局性相关是指( )。

A.先写后读相关B.先读后写相关C.指令相关D.由转移指令引起的相关8、对汇编语言程序员透明的是（）A.I/O方式中的DMA访问B.浮点数据表示C.访问方式保护D.程序性中断9、"从中间开始"设计的"中间"目前多数是在( )。

A.传统机器语言级与操作系统机器级之间B.传统机器语言级与微程序机器级之间C.微程序机器级与汇编语言机器级之间D.操作系统机器级与汇编语言机器级之间10、下列说法正确的是（）A."一次重叠"是一次解释一条指令B."一次重叠"是同时解释相邻两条指令C.流水方式是同时只能解释两条指令D."一次重叠"是同时可解释很多条指令11、利用时间重叠概念实现并行处理的是( )。