1、 科目代码：829 科目名称：计算机专业基础 第 1 页 共 6 页 南京航空航天大学南京航空航天大学 2012017 7 年年硕士硕士研究生入学考试初试试题研究生入学考试初试试题（ A A 卷卷 ） 科目代码: 829 满分: 150 分 科目名称: 计算机专业基础 注意: 认真阅读答题纸上的注意事项；认真阅读答题纸上的注意事项；所有答案必须写在所有答案必须写在答题纸答题纸上，写在本试题纸或草稿纸上均无上，写在本试题纸或草稿纸上均无效；效；本试题纸须随答题纸一起装入试题袋中交回！本试题纸须随答题纸一起装入试题袋中交回！ 数据结构部分（数据结构部分（50 分）分） 1 （10 分）为一个家谱管
2、理程序设计一种数据结构，以一个四代人，11 个家庭成员为例，（A 有 3 个孩子 A1、A2、A3；A1 有 2 个孩子 A11、A12；A2 无子，A3 有 3 个孩子 A31、A32、A33；A11 有 1 个孩子 A111；A32 有 1 个孩子 A321；其余尚无子） ，画出家谱示意图，给出所设计的存储结构示意图，并给出在该存储结构上输出第 k 代所有人员的算法思想。 2 （10 分）已知输入数据序列为 (58,68,42,10,88,32,70,52,55,46 )，给出建立 3 阶 B-树示意图，再给出删除 55，70 后的 B-树。 3 （10 分）试用 Dijkstra 算法，
3、求下图中从 V1 到其余各顶点的最短路径，给出实现算法所用的数据结构和求解过程中每一步的状态。 4 （10 分）设 A、B 为递减有序（元素值为整型）的单链表，编写函数，利用原结点将它们合并成一个递增有序的单链表，相同元素值只保留一个结点。先给出算法思想，再写出相应代码。 5.（10 分）设有 n 个学生成绩（0-100 整数）的顺序结构线性表 L，编写函数，将该线性表中调整为成绩及格（大于等于 60）在不及格之前，要求 T(n)=O(n), S(n)=O(1)。先给出算法思想，再写出相应代码。 科目代码：829 科目名称：计算机专业基础 第 2 页 共 6 页 操作系统部分（操作系统部分（5
4、0 分）分） 6. (16 分) 简答（4 分/题） （1） 系统型线程和用户型线程有何区别？ （2）分段式系统和分页式系统有何区别？ （3）引入缓冲的目的是什么，有哪些常见的缓冲模式？ （4）SPOOLING 技术如何实现，在操作系统中起何作用？ 7. （7 分） 设有三道作业，它们的提交时间及执行时间由下表给出: 作业号 提交时间 执行时间 1 8.5 2.0 2 9.2 1.6 3 9.4 0.5 试计算在单道程序环境下，采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间 8. (9 分) 某系统有 A、B、C、D 四类资源可供五个进程 P1、P2、P3、P4、P5 共享。系统
5、共有这四类资源为:A 类 3 个、B 类 14 个、C 类 12 个、D 类 12 个。进程对资源的需求和分配情况如下： 进程 已占有资源 最大需求数 A B C D A B C D P1 0 0 1 2 0 0 1 2 P2 1 0 0 0 1 7 5 0 P3 1 3 5 4 2 3 5 6 P4 0 6 3 2 0 6 5 2 P5 0 0 1 4 0 6 5 6 （1）现在系统是否处于安全状态？（4 分） （2）如果进程 P2 提出需要 A 类资源 0 个、B 类资源 4 个、C 类资源 2 个和 D 类资源 0 个，系统能否去满足它的请求？（5 分） 9.（9 分） 某分页系统，每个
6、页面长为 1KB，某时刻该用户进程的页表如下： 科目代码：829 科目名称：计算机专业基础 第 3 页 共 6 页 页号 物理块号 是否在快表 0 8 是 1 7 是 2 4 否 3 10 否 4 5 否 5 3 是 6 2 是 （1） 请写出分页系统的地址转换过程（3 分） （2）计算两个逻辑地址：0AC5H、1AC5H 对应的物理地址（16 进制表示） 。 （3 分） （3）已知主存的一次存取为 2us，对于快表的查询时间可以忽略，则访问上述两个逻辑地址分别耗费多少时间？（3 分） 10. (9 分) 一家四口人，儿子喜欢吃苹果，由父亲负责购买, 女儿喜欢吃橘子，由母亲负责购买。父亲和母亲
7、购买水果后放到家中的抽屉里，儿子和女儿从抽屉里取出水果。假设抽屉只能容纳 20 个水果，同时只能一人开关, 用纪录型信号量同步父母子女四个进程。 组成原理部分（组成原理部分（50 分）分） 11.（10 分）简答题（5 分/题） （1）计算机内部的指令和数据均以二进制信息的形式存放在存储器中，请问计算机如何从时间和空间上区别它们？ （2）为什么用算逻部件 ALU 和移位器能够实现定点数和浮点数的加减乘除运算？ 12.（10 分） 下面一段 C 程序用于计算数组 a 中各元素之和。当参数 len 为 0 时，返回值应该为 0。但计算机执行该程序时，却发生了存储器访问异常。这是什么原因造成的？应该
8、如何修改？ 1 float sum_elements (float a, unsigned len) 2 3 int i; 4 float result = 0; 5 6 for (i = 0; i = len1; i+) 7 result += ai; 8 return result; 9 科目代码：829 科目名称：计算机专业基础 第 4 页 共 6 页 13 （15 分）高级语言语句“for (i=0;iN;i+) sum=sum+ai;”对应的一段 MIPS 汇编代码如下。其中按字节编址，N 为正整数，存放在$s5 中，sum 初始值为 0，存放在$s2 中，数组 a 的首址在$s3
9、中，最前面的数字是指令序号。 i1 add $t0, $0, $0 # R$t00 i2 add $t1, $0, $0 # R$t10 i3 loop: add $t2, $t1, $s3 # R$t2R$t1+ R$s3 i4 lw $t3, 0($t2) # R$t3MR$t2+0，即 R$t3=ai i5 add $s2, $s2,$t3 # R$s2R$s2+ R$t3 i6 addi $t1, $t1, 8 # R$t1R$t1+8，即 R$t1=8*i i7 addi $t0, $t0, 1 # R$t0R$t0+1，即 i=i+1 i8 bne $t0, $s5, loop #
10、 if R$t0 R$s5 then goto loop 假定这段指令存放在内存 0 x0800 00C0 开始的一段内存中，请回答下列问题。 （1）已知$s2 的编号为 10010，$t3 的编号为 01011，指令 i5 的机器代码是什么？请用 16进制表示。 （提示：add 为 R-型指令，编码如图所示，其字段顺序为 OP、Rs、Rt、Rd、Sh和 Func） op(31:28)=000000 (R-format), func(5:0) 2-0 5-3 000 001 010 011 100 000 shift left shift right sra sllv 001 jump jal
11、r syscall 010 mfhi mthi mflo mlto 011 mult multu div divu 100 add addu sub subu and （2）根据对汇编代码的分析可知数组 a 的每个数组元素占几个字节？ （3）若 N=10，则上述程序段执行过程中共执行了多少条指令？若单周期处理器的时钟频率为 2GHz，则上述程序段（N=10）在该单周期处理器中执行时的 CPU 时间为多少？ 14.（15 分）假定一个计算机系统中有一个 TLB 和一个 L1 data cache。该系统按字节编址，虚拟地址 16 位，物理地址 13 位；页大小为 256B，TLB 为四路组相联，
12、共有 16 个页表项； 科目代码：829 科目名称：计算机专业基础 第 5 页 共 6 页 L1 data cache 采用直接映射方式，块大小为 4B，共 16 行。在系统运行到某一时刻时，TLB、页表和 L1 data cache 中的部分内容（用十六进制表示）如下表(a)，(b)，(c)所示： 组号/标记/页框号/有效位/标记/页框号/有效位/标记/页框号/有效位/标记/页框号/有效位 0 03 0 09 0D 1 00 0 01 02 1 1 03 2D 1 02 0 01 13 1 0A 0 2 02 0 01 19 1 06 0 03 0 3 01 11 1 63 0D 1 0A
13、34 1 72 0 （a） TLB（四路组相联）的四组/16 个页表项 虚页号/页框号/有效位 行索引/ 标记/ 有效位/ 字节 3/ 字节 2/ 字节 1/ 字节 0 00 08 1 0 19 1 12 56 C9 AC 01 03 1 1 15 0 02 14 1 2 1B 1 03 45 12 CD 03 02 1 3 36 0 04 0 4 32 1 23 34 C2 2A 05 16 1 5 0D 1 46 67 23 3D 06 0 6 0 07 07 1 7 16 1 12 54 65 DC 08 13 1 8 24 1 23 62 12 3A 09 17 1 9 2D 0 0A
14、 09 1 A 2D 1 43 62 23 C3 0B 0 B 0 0C 19 1 C 12 1 76 83 21 35 0D 0 D 16 1 A3 F4 23 11 0E 11 1 E 65 1 2D 4A 45 55 0F 0D 1 F 14 0 (b) 部分页表（开始的 16 项） (c) L1 data cache：直接映射，共 16 行，块大小为 4B （1）虚拟地址中哪几位表示虚拟页号？哪几位表示页内偏移量？虚拟页号中哪几位表示TLB 标记？哪几位表示 TLB 索引？ 科目代码：829 科目名称：计算机专业基础 第 6 页 共 6 页 （2）物理地址中哪几位表示物理页号？哪几位表示页内偏移量？ （3）主存（物理）地址如何划分成标记字段、行索引字段和块内地址字段？ （4）CPU 从地址 067AH 中取出的 short 型值（16bit-大端方式）为多少？说明 CPU 读取地址 067AH 中内容的过程。
