2018年南京航空航天大学829计算机专业基础考研专业课真题硕士研究生入学试题

《2018年南京航空航天大学829计算机专业基础考研专业课真题硕士研究生入学试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、南京航空航天大学2018年硕士研究生入学考试袖试题（A卷）科H代码：829O厶Jrp八—只科目名称：存机脱響：150注意：①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸JU写在1本试题纸或讎I堀效；③本试题纸须随答题纸一起装入试题榮交回数据结构部分（50分）1.CIO分）给定个村庄之间的交通图，边上的值表示这条道路的尷现噪n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最魁村庄到医院的路程最短？试选择或构造一种适当的数据结构并设计一个算法，并应用僚法解答下图所示的实例，给出算法执行过程示意图。2・CIO分）详细解释哈希表的

2、工作原理。以此为例，将关键痂51,3,43,15,62,59，74,61）存储在處10的哈希表中，使用哈希函数H（key）=Key%10，并采用链地址法解决冲突，画出哈希表示意图。亠A3・CIO分）设有一批需实时处理的数据元素绒第S,实时处理开始后，每隔一敕到一个新的数据元素加入So现要求在每次接收一个新元素之前，找出S中现有的最小元素并将其输出（趺中删除）。试选择或构造一种适当的数据结构并设计一个算法，鯛效地完成上述任务。例如：S=（59,31,29,18,78,26,48,10,65,35）,新接受的数据为39,12,46・・・以此为例说明算法执行过程示

3、意图。4.CIO分）设一个带头结点的離表L，数据元素为整数，其中大部分为正数，数为负数，编写函数，采用高效的算法调整链表，实现将负数结点移到链表躍，并瞒链表中的第一个负数结点位置。先给出算法思想，再写相应代码。5.（10分）设二叉樹用二叉链表结构存储，元素值为整数且互不相同编写递豳数，对给的2个整数，若2个都不是T的元素，输出-2；若1个不是T的元素，输出-1；若2个都是T的元素，输出两者所在的层数的间隔数。要求先给出算法思想，再写代码。组成原理部分（50分）6.（8分）如下为一流水和一非流水处理器的参数，请按要谦算:ParameterPipelinedNo

4、n-PipelinedClockRate500MHZ250MHZCPIforALUinstruction11CPIforControlinstruction21CPIforMemoryinstruction2.51若一程序有20%的ALU指令,40%的控制指令和70%的访存指令，上述哪种设计烘？请用合适的指标评估7.（10分）若有一源程序hello.c文件:1）简述如何生成相应的可执行程序;2）简述该可执行程序如何在计算机上执行的程。（10分）对于一n位运算器，通常得到其运算结果的同吋也输出相应的标志信号如ZF（零标志位），SF（符号标志位），CF（进位标志

5、位）和OF（溢出标志位）等：1）请用逻辑表达式表示出上述各标志信号如何根据运算结卿勺相应位产生并做出解2）若需完成两有符号数比大小，请问需采用何种运算且如何利用上述标志位别9.（10分）假定计算机系统主存空间大小为32KX16位，且有一个4K字的4路组相©hche,主存和Cache之间的数据交换块的大小为64字。假定Cache开始为空，处理器顺序地糅储单氐1、…、4351中取数，一共重复10次。设Cache比主存快10倍。采用LRU算法。试分feche的结构和主存地址的划分。说明采用Cache后速度提高了多少？9.（12分）如图所示的单周期数据通路执行如下M

6、IPS32指令Address（Byte）Instruction100beq$R2,$R4,7#TheaddressofregisterRnisn执行上述指令前各寄存器的内容如下表：RegisterValue（10进制）R112R216R38R416Adc>Branch1•绚Control5Unit/ShiftiPCSrcXfemVWiWMemReadMemtoRegALUSrcRegVWmlnsfr(31X)RegDst•11lOMiUmstructionMemoryReaDatatoDataeadAddr1Register.eadAddr2匚心FHeteA

7、ddrV<3.nJielxten

8、进制显示）MemtoRegALUSrcZeroThe