2003-2016年南京航空航天大学829计算机专业基础考研真题及答案解析 汇编

南京航空航天大学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程序的执行过程。

2017版南京航空航天大学《829计算机专业基础》全套考研资料我们是布丁考研网南航考研团队，是在读学长。

我们亲身经历过南航考研，录取后把自己当年考研时用过的资料重新整理，从本校的研招办拿到了最新的真题，同时新添加很多高参考价值的内部复习资料，保证资料的真实性，希望能帮助大家成功考入南航。

此外，我们还提供学长一对一个性化辅导服务，适合二战、在职、基础或本科不好的同学，可在短时间内快速把握重点和考点。

有任何考南航相关的疑问，也可以咨询我们，学长会提供免费的解答。

更多信息，请关注布丁考研网。

以下为本科目的资料清单（有实物图及预览，货真价实）：南京航空航天大学《计算机专业基础》全套考研资料包含：一、南京航空航天大学《计算机专业基础》历年考研真题及答案解析2016年南京航空航天大学《计算机专业基础》考研真题（含答案解析）（11月份统一更新）2015年南京航空航天大学《计算机专业基础》考研真题（含答案解析）2014年南京航空航天大学《计算机专业基础》考研真题（含答案解析）2013年南京航空航天大学《计算机专业基础》考研真题（含答案解析）2007年南京航空航天大学《计算机专业基础》考研真题（含答案解析）2006年南京航空航天大学《计算机专业基础》考研真题（含答案解析）2005年南京航空航天大学《计算机专业基础》考研真题（含答案解析）2004年南京航空航天大学《计算机专业基础》考研真题（含答案解析）2003年南京航空航天大学《计算机专业基础》考研真题（含答案解析）二、南京航空航天大学《计算机专业基础》考研复习笔记1、辅导讲义（含数据结构、操作系统和计算机组成原理）该辅导讲义由2016级高分学长最新编写，适用于2017年参加考试的考生，辅导讲义按章节编写，针对南航的出题特点，编写了考研点睛（历年考题分析）、主要知识点、以及重要题型演练三个部分，是专业课复习具有极高参考价值的一份资料，同学们好好使用一定可以考取一个不错的分数。

2016年全国硕士研究生入学统一考试《计算机学科专业基础综合》真题(总分：150.00，做题时间：180分钟)一、单项选择题(总题数：40，分数：80.00)1.已知表头元素为c的单链表在内存中的存储状态如下表所示现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是（）。

（分数：2.00）A.1010H，1014H，1004HB.1010H，1004H，1014HC.1014H，1010H，1004HD.1014H，1004H，1010H√prev data next结点，正确的语句序列是（）。

（分数：2.00）A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);B.p->next->prev=p->next;p->prey->next=p->next;free(p);C.p->next->prev=p->next;p->prev->next=p->prev;free(p);D.p->next->prey=p->prey;p->prev->next=p->next;fr ee(p);√3.设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。

现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。

若期望驶出的次序依次为1～9，则n至少是（）。

2.00）A.2B.3C.4√D.54.有一个100阶的三对角矩阵M，其元素mi,j(1≤i≤100，1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。

元素m30,30在N中的下标是（）。

（分数：2.00）A.86B.87√C.88D.895.若森林F有15条边、25个结点，则F包含树的个数是（）。

一、计算机组成原理部分【目标】1. 理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式,具有完整的计算机系统的整机概念。

2. 理解计算机系统层次化结构概念,熟悉硬件与软件之间的界面,掌握指令集体系结构的基本知识和基本实现方法。

3. 能够运用计算机组成的基本原理和基本方法,对有关计算机硬件系统中的理论和实际问题进行计算、分析,并能对一些基本部件进行简单设计。

【大纲】1.计算机系统概述(1). 了解计算机的发展历程;(2). 掌握冯?诺依曼计算机结构的特点,计算机硬件的基本组成与功能,计算机系统的组成(硬件+软件)及其层次结构,计算机的工作原理;(3). 掌握计算机的性能指标,具体包括CPU执行时间、CPI、时钟周期、主频、MIPS、MFLOPS、GFLOPS、TFLOPS、PFLOPS等;2.数据的机器级表示(1).掌握数制与编码:包括进位计数制及其相互转换,真值和机器数,BCD编码,字符与字符串,校验码;(2). 熟练掌握定点数的表示与运算:包括无符号数的表示和有符号整数的表示,定点数的移位运算;原码定点数加减运算;补码定点数加减法运算;定点数乘除运算;识记溢出概念和判别方法;(3). 掌握浮点数的表示与运算:包括浮点数的表示,IEEE754标准,浮点数的加减运算及其规格化;(4).理解算术逻辑单元ALU:包括串行加法器和并行加法器,算术逻辑单元ALU 的功能与结构;3.运算方法与运算部件(1).掌握不同层次程序员看到的运算:高级语言以C语言为例,ISA层面则以MIPS为例;(2). 了解串行加法器、并行加法器及先行进位部件,掌握算术逻辑部件ALU 的设计;(3). 掌握定点数运算及运算部件:补码加减运算,无符号数乘法运算,无符号除法运算;掌握补码加减运算器如何实现;(4). 掌握浮点数加减运算及浮点数运算的精度问题;了解相应的运算部件实现思想; 4.存储器分层体系结构(1).了解存储器的分类及其分层结构,半导体存储器随机访问存储器的组织,只读存储器及主存的主要技术指标等;掌握存储器芯片与CPU的连接,多模块存储器的交叉存储;(2).掌握高速缓冲存储器的CPU的基本访存过程,Cache和主存之间的映射方式,程序访问的局部性原理对编程的影响及Cache-friendly的程序,了解Cache替换算法和Cache写策略;(3).掌握虚拟存储器的基本概念,三种实现方案,缺页的处理以及快表的工作原理,注意虚拟地址和物理地址的转换问题,如何查段表和页表;TLB的原理和作用;平均访问时间的计算等。

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

南京航空航天大学计算机考研试卷操作系统部分2000年操作系统考研试卷一、名词术语解释<每小题4分，共20分）1、系统调用与操作系统内核2、进程与线程3、页表与快表4、设备独立性5、文件控制块与索引节点二、填空<每小题2分，共10分）1、如果在设备处理时设置I/O进程，则不需要I/O进程工作时，I/O进程处于__________状态。

2、系统中有3个进程，每个进程需2台打印机，如果系统配有4台打印机，则系统_________ _出现死锁的情况<本题要判断出现死锁的可能性）。

3、设磁盘的I/O请求队列中的磁道号为:98，183，37，122，14，124，65，67，磁头初始位置为50，若采用FCFS<先来先服务）和SSTF<最短寻道时间优先）的磁盘调度算法，磁头分别移动__________、__________磁道。

4、可以被多个进程在任何时刻共享的代码必须是__________。

5、为了实现CPU与外部设备的并行工作，系统引入了__________硬件机制。

三、回答下列问题<每小题8分，共48分）1、在操作系统中，何为虚拟存储器、虚拟设备、虚拟处理机？2、进程具有哪几种基本状态:对于每一种可能有的状态转换。

给出一种状态转换的原因。

<需图示说明）3、何为磁盘高速缓存:说明它为什么会提高磁盘的I/O速度。

4、说明装入时动态链接<Load-time Dynamic Linking ）与运行时动态链接<Run-time Dynamic Linking ）这两种程序链接方法之间差别。

5、试从物理概念上来说明记录型信号量和wait 与 signal 操作？6、简述Intel 80386 实方式寻址和保护方式寻址时，内存地址的形成过程，最大寻址空间各为多少？四、<10分）在测量控制系统中的数据采集任务，把所采集的数据送一单缓冲区:计算任务从该单缓冲区中取出数据进行计算。

科目代码：829科目名称：计算机专业基础第1页共5页南京航空航天大学2018年硕士研究生入学考试初试试题（A 卷）科目代码:829满分:150分科目名称:计算机专业基础注意:①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！数据结构部分（50分）1．（10分）给定n 个村庄之间的交通图，边上的值表示这条道路的长度，现在要从这n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用该算法解答下图所示的实例，给出算法执行过程示意图。

2．（10分）详细解释哈希表的工作原理。

以此为例，将关键字序列（51，83，43，15，62，59，74，61）存储在长度为10的哈希表中，使用哈希函数H(key)=Key %10，并采用链地址法解决冲突，画出哈希表示意图。

3．（10分）设有一批需实时处理的数据元素组成集合S，实时处理开始后，每隔一秒钟收到一个新的数据元素加入S。

现要求在每次接收一个新元素之前，找出S 中现有的最小元素并将其输出（从S 中删除）。

试选择或构造一种适当的数据结构并设计一个算法，尽可能高效地完成上述任务。

例如：S=(59,31,29,18,78,26,48,10,65,35)，新接受的数据为39，12，46….。

以此为例说明算法执行过程示意图。

4．（10分）设一个带头结点的单链表L，数据元素为整数，其中大部分为正数，少数为负数，编写函数，采用高效的算法调整链表，实现将负数结点移到链表尾部，并返回调整后链表中的第一个负数结点位置。

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

5.（10分）设二叉树T，用二叉链表结构存储，元素值为整数且互不相同。

编写非递归函数，对给定的2个整数，若2个都不是T 的元素，输出-2；若1个不是T 的元素，输出-1；若2个都是T 的元素，输出两者所在的层数的间隔数。