搜索
科目代码：829科目名称：计算机专业基础第1页共4页南京航空航天大学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按顺序使用CPU10秒，使用设备甲5秒，使用CPU5秒，使用设备乙10秒，最后使用CPU10秒，程序B按顺序使用设备甲10秒，使用CPU10秒，使用设备乙10秒，使用CPU5秒，使用设备乙10秒。试问：V2V4V6V5V1V3a7=6a4=5a8=1a2=6a3=2a6=7a5=4a1=8科目代码：829科目名称：计算机专业基础第2页共4页（1）在顺序环境下执行程序A和程序B,CPU的利用率是多少？（3分）（2）在多道程序环境下，CPU的利用率是多少？请画出A、B程序的执行过程。（4分）（3）多道批处理中，是否系统中并发的进程越多，资源利用率越好，为什么？（3分）8.（10分）考虑5个进程P1、P2、P3、P4、P5，如下表，规定进程的优先级越小，优先级越高，试计算在采用下述几种调度算法时各个进程周转时间和带权周转时间。假设忽略进程的调度时间。（1）先来先服务调度算法（FCFS）；（2）时间片轮转调度算法（时间片为1ms）（RR）；（3）最短作业优先调度算法（SJF）；（4）剥夺式优先级调度算法（HPF）。进程提交时刻需要的CPU时间(ms)优先级P1033P2265P3441P4652P58249.（10分）某系统采用段页式存储管理，有关的数据结构如下图所示。逻辑地址8412段号段内页号页内偏移0123001223051829071B2A页表0页表1页表2段表011426页表3(1)说明在段页式系统中动态地址变换过程。（4分）(2)计算虚地址200804（十进制）的物理地址(用十进制表示)（3分）。(3)计算物理地址32784（十进制）的虚地址(用十进制表示)（3分）。10.(10分)某工厂有两个生产车间和一个装配车间，生产车间生产A、B两种零件，装备车间把这两种零件装配成产品。生产车间甲把生产的A零件放到货架F1上，生产车间乙把生产的B零件放到货架F2上，假设两个货架的容量都是10个零件。装配车间每次从货架上取出一个A和一个B然后进行装配，请用P、V操作来进行正确的三个车间管理。科目代码：829科目名称：计算机专业基础第3页共4页组成原理部分（50分）一．（15分）选择题（1.5分/题）11.以下数据中最大的是（）。A.110100010BB.412DC.740QD.2E2H12.计算机中最小单位时间为（）。A.时钟周期B.指令周期C.CPU周期D.执行周期13.立即寻址是指（）。A．指令中直接给出操作数地址B.指令中直接给出操作数C.指令中间接给出操作数D.指令中间接给出操作数地址14.一般来说，Flash存储器的功能不包含的操作为（）。A.编程B.读取C.擦除D.加法运算15.微程序控制器中，机器指令与微指令的关系是（）。A.每一条机器指令由一条微指令来执行B.每一个机器指令由一段微指令编程的微程序来解释执行C.一段机器指令组成的程序可由一条微指令来执行D.一条微指令由若干条机器指令组成16.TLB,Page,Cache这三项的缺失（Miss）、命中（Hit）组合中可以存在的为（）A.TLBhit,Pagemiss,CachemissB.TLBhit,Pagehit,CachemissC.TLBhit,Pagemiss,CachehitD.TLBmiss,Pagemiss,Cachehit17.下列叙述中，不能反映RISC特征的有（）A.指令长度可变B.简单的指令系统C.只有LOAD/STORE指令访问寄存器D.设置大量通用寄存器18.浮点数的表示范围和精度取决于（）。A.阶码的位数和尾数的机器数形式；B.阶码的机器数形式和尾数的位数；C.阶码的位数和尾数的位数；D.阶码的机器数形式和尾数的机器数形式19.设［X］补=1.x1x2x3x4,当满足（）时，X-1/2成立。A.x1必须为1，x2x3x4至少有一个为1B.x1必须为1，x2x3x4任意C.x1必须为0，x2x3x4至少有一个为1D.x1必须为0，x2x3x4任意20.外部总线不包括（）。A.PCI-EB.AGPC.CAND.寄存器与ALU间的总线科目代码：829科目名称：计算机专业基础第4页共4页二．（10分）问答题21.指令和数据均以二进制形式存放存储器中，计算机如何区分之？（3分）22.控制器设计的两种方式及其各自特点（4分）23.计算机调用中断服务程序与调用子程序有何区别（3分）三．（25分）综合题24.（13分）单总线CPU字长16位，其结构如下图所示，CPU和存储器间采用同步通信，按字编址。每条指令由2个字组成，第一个字指明操作码和寻址方式，第二个字包含立即数imm16。每次存储器访问存取一个字，花费2个CPU时钟。取指阶段第二次访存将imm16取到MDR中。对于下面问题中列出的3个操作，分别完成（a）写出下列每种功能对应指令的RTL级描述，(b)从寻址的角度说明imm16属于哪种寻址方式，（c）写出下列指令在执行阶段的控制信号序列（1）将地址为imm16的存储单元内容与寄存器R5中的内容相加并将结果存放在R5中（4分）（2）将存储单元imm16的内容作为地址，所指存储单元的内容与寄存器R6中的内容相加并将结果存放在R6中（5分）（3）将imm16直接与寄存器R2中的内容相加，再将结果写入到R3中（4分）25.（12分）某高级语言语句“for(i=0;iN;i++)sum=sum+a[i];”，其中N=100，假定数组a中每个元素都是int类型，依次连续存放在首地址为0x00000800的内存区域中，sizeof(int)=4。运行上述代码的处理器带有一个数据区容量为64KB的datacache，其主存块大小为256B，采用直接映射、随机替换和直写（writeThrough）方式；可寻址的最大主存地址空间为4GB，配置的主存容量为2GB，按字节编址。请回答下列问题。(3分/题)（1）主存地址至少占几位？（2）datacache共有多少行？主存地址如何划分？（3）数组a占用几个主存块？所存放的主存块号分别是什么？（4）在访问数组a的过程中数据的缺失率为多少？