1、 科目代码：829 科目名称：计算机专业基础 第 1 页 共 4 页 南京航空航天大学南京航空航天大学 2016 年硕士研究生招生考试初试试题（ A 卷 ） 2016 年硕士研究生招生考试初试试题（ A 卷 ） 科目代码: 829 科目名称: 计算机专业基础 满分: 150 分 注意: 认真阅读答题纸上的注意事项；所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无 认真阅读答题纸上的注意事项；所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；本试题纸须随答题纸一起装入试题袋中交回！效；本试题纸须随答题纸一起装入试题袋中交回！ 数据结构部分（50 分） 数据结构部分（50 分） 1 （1
2、0 分）求下图中的关键路径，给出算法思想和求解过程每一步的状态。 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 分）已知一棵二叉链表表示的二叉
3、树 T，编写函数，判断 T 是否是完全二叉树。先给出算法思想，再写出程序代码。 操作系统部分（50 分） 操作系统部分（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 按顺序使用
4、CPU 10 秒，使用设备甲 5 秒，使用 CPU 5秒，使用设备乙 10 秒，最后使用 CPU 10 秒，程序 B 按顺序使用设备甲 10 秒，使用 CPU 10秒，使用设备乙 10 秒，使用 CPU 5 秒，使用设备乙 10 秒。试问： V2 V4 V6 V5 V1 V3 a7=6 a4=5 a8=1 a2=6 a3=2 a6=7 a5=4 a1=8 科目代码：829 科目名称：计算机专业基础 第 2 页 共 4 页 （1）在顺序环境下执行程序 A 和程序 B,CPU 的利用率是多少？（3 分） （2）在多道程序环境下，CPU 的利用率是多少？请画出 A、B 程序的执行过程。 （4 分）
5、（3）多道批处理中，是否系统中并发的进程越多，资源利用率越好，为什么？（3 分） 8.（10 分）考虑 5 个进程 P1、P2、P3、P4、P5，如下表，规定进程的优先级越小，优先级越高，试计算在采用下述几种调度算法时各个进程周转时间和带权周转时间。假设忽略进程的调度时间。 （1）先来先服务调度算法（FCFS） ； （2）时间片轮转调度算法（时间片为 1ms） （RR） ； （3）最短作业优先调度算法（SJF） ； （4）剥夺式优先级调度算法（HPF） 。 进程 提交时刻 需要的 CPU 时间(ms) 优先级 P1 0 3 3 P2 2 6 5 P3 4 4 1 P 4 6 5 2 P5 8
6、2 4 9.（10 分）某系统采用段页式存储管理，有关的数据结构如下图所示。 逻辑地址 8 4 12 段号段号 段内页号段内页号 页内偏移页内偏移 0 1 2 3 001 2 2 3 0 5 1 8 2 9 0 7 1 B 2 A 页表页表0 页表页表1 页表页表2段表0 1 1 4 2 6 页表页表3 (1)说明在段页式系统中动态地址变换过程。 （4 分） (2)计算虚地址 200804（十进制）的物理地址(用十进制表示) （3 分） 。 (3)计算物理地址 32784（十进制）的虚地址(用十进制表示) （3 分） 。 10.(10 分) 某工厂有两个生产车间和一个装配车间，生产车间生产 A
7、、B 两种零件，装备车间把这两种零件装配成产品。生产车间甲把生产的 A 零件放到货架 F1 上，生产车间乙把生产的 B 零件放到货架 F2 上，假设两个货架的容量都是 10 个零件。装配车间每次从货架上取出一个 A 和一个 B 然后进行装配，请用 P、V 操作来进行正确的三个车间管理。 科目代码：829 科目名称：计算机专业基础 第 3 页 共 4 页 组成原理部分（50 分） 组成原理部分（50 分） 一（15 分）选择题（1.5 分/题） 11.以下数据中最大的是（ ） 。 A. 110100010B B. 412D C. 740Q D. 2E2H 12.计算机中最小单位时间为（ ）。 A
8、. 时钟周期 B. 指令周期 C. CPU 周期 D. 执行周期 13.立即寻址是指（ ）。 A指令中直接给出操作数地址 B. 指令中直接给出操作数 C. 指令中间接给出操作数 D. 指令中间接给出操作数地址 14.一般来说，Flash 存储器的功能不包含的操作为（ ）。 A. 编程 B. 读取 C. 擦除 D. 加法运算 15.微程序控制器中，机器指令与微指令的关系是（ ） 。 A. 每一条机器指令由一条微指令来执行 B. 每一个机器指令由一段微指令编程的微程序来解释执行 C. 一段机器指令组成的程序可由一条微指令来执行 D. 一条微指令由若干条机器指令组成 16.TLB, Page, Ca
9、che 这三项的缺失（Miss） 、命中（Hit）组合中可以存在的为（ ） A. TLB hit, Page miss, Cache miss B. TLB hit, Page hit, Cache miss C. TLB hit, Page miss, Cache hit D. TLB miss, Page miss, Cache hit 17.下列叙述中，不能反映 RISC 特征的有（ ） A. 指令长度可变 B. 简单的指令系统 C. 只有 LOAD/STORE 指令访问寄存器 D. 设置大量通用寄存器 18. 浮点数的表示范围和精度取决于（ ） 。 A. 阶码的位数和尾数的机器数形式；
10、 B. 阶码的机器数形式和尾数的位数； C. 阶码的位数和尾数的位数； D. 阶码的机器数形式和尾数的机器数形式 19.设X补=1.x1x2x3x4,当满足（ ）时，X -1/2 成立。 A. x1必须为 1，x2x3x4至少有一个为 1 B. x1必须为 1，x2x3x4任意 C. x1必须为 0，x2x3x4至少有一个为 1 D. x1必须为 0，x2x3x4任意 20.外部总线不包括（ ） 。 A. PCI-E B. AGP C. CAN D. 寄存器与 ALU 间的总线 科目代码：829 科目名称：计算机专业基础 第 4 页 共 4 页 二 （10 分）问答题 21. 指令和数据均以二
11、进制形式存放存储器中，计算机如何区分之？（3 分） 22. 控制器设计的两种方式及其各自特点（4 分） 23. 计算机调用中断服务程序与调用子程序有何区别（3 分） 三 （25 分）综合题 24.（13 分）单总线 CPU 字长 16 位，其结构如下图所示，CPU 和存储器间采用同步通信，按字编址。 每条指令由 2 个字组成，第一个字指明操作码和寻址方式，第二个字包含立即数imm16。每次存储器访问存取一个字，花费 2 个 CPU 时钟。取指阶段第二次访存将 imm16 取到 MDR 中。对于下面问题中列出的 3 个操作，分别完成（a）写出下列每种功能对应指令的RTL 级描述，(b)从寻址的角
12、度说明 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 + ai;” ，其中 N= 100，假定数组 a 中每个元素都是 int 类型，依次连续存放在首地址为 0 x0000 0800 的内存区域中，sizeof(int) = 4。运行上述代码的处理器带有一个数据区容量为 64KB 的 data cache，其主存块大小为 256B，采用直接映射、随机替换和直写（write Through）方式；可寻址的最大主存地址空间为 4GB，配置的主存容量为 2GB，按字节编址。请回答下列问题。(3 分/题)（1）主存地址至少占几位？ （2）data cache 共有多少行？主存地址如何划分？ （3）数组 a 占用几个主存块？所存放的主存块号分别是什么？ （4）在访问数组 a 的过程中数据的缺失率为多少？
