南京航空航天大学 2014年硕士研究生入学考试初试试题（ 科目代码: 科目名称: 829 计算机专业基础 A卷 ） 分 满分: 150 注意: ①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上，写在本试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！ （一、数据结构部分 50分） 1.（10分）解释哈希表工作原理。将关键字序列（75，54，48，90，18，22，84，63）存储在长度为10的哈希表中，使用哈希函数H(key) = Key % 10 ，并采用二次探测再散列法解决冲突，画出哈希表示意图。 2.（10分）试用Floyd算法，求解下图中各顶点之间的最短路径，写出算法过程中每一步的状态。 3.（10分）设有6个字符，其权值为（12，40，16，8，14，10），给出进行Huffman编码的数据结构和执行过程示意图。 4．（10分）设一个带头结点的单链表L，数据元素为（a1,a2,a3,a4,... ,an）,编写函数，调整该链表，使得数据元素次序为（a1, a3,...,an, ... ,a4,a2）, 要求T(n)=O(n)，先给出算法思想，再写出相应代码。 5.（10分）设有一家谱树T，用二叉链表结构存储（孩子兄弟表示法），树中的结点信息为成员名字。编写函数，输出家谱中共有多少代以及最后一代人数和成员名字。要求先给出算法思想，再写出相应代码。 （二、操作系统部分 50分） 一．填空题(共10小题，每小题1分，共10分) 1．下列关于操作系统的四种陈述中，正确的是：_________。 （A） 批处理操作系统必须在响应时间内处理完一个任务 （B） 实时操作系统必须在规定时间内处理完来自外部的事件 （C） 分时操作系统必须在周转时间内处理完来自外部的事件 （D） 分时操作系统必须在调度时间内处理完来自外部的事件 科目代码：829科目名称：计算机专业基础 第1页 共5页 15 7 V1 3 12 V4 V3V2 2 2.设有两个进程A、B，各按以下顺序使用P,V操作进行同步。 A进程： B进程： a1→ b1→ P(s1) P(s2) a2 → b2→ P(s2) P(s1) a3→ b3→ V(s2) V(s1) a4→ b4→ V(s1) V(s2) a5→ b5→ 试问在下列执行顺序中，哪种情况会发生死锁？_______ （A） a1,a2,a3,a4… （B） b1,b2,b3,b4,b5… （C） a1,a2,b1,b2,a3,b3… （D） a1,b1,a2,b2,a3,b3… 3. 在内存管理中，内存利用率高且保护和共享容易的是_______内存管理方式 （A） 分区管理 （B）分页管理 （C） 分段管理 （D）段页式管理 4．操作系统中，很多事件会引起调度程序的运行，但下列事件中不一定引起操作系统调度程序运行是___________。 （A）当前运行着的进程出错。 （B）当前运行着的进程请求输入/输出。 （C）有新的进程进入就绪状态。 （D）当前运行的进程时间片用完。 5．操作系统中调度算法是核心算法之一，下列关于调度算法的论述中正确的是： _____。 （A）先来先服务调度算法对即对长作业有利也对段作业有利。 （B）时间片轮调度算法转只对长作业有利。 （C）实时调度算法也要考虑作业的长短问题。 （D）高相应比者优先调度算法既有利于短作业又兼顾长作业的作业还实现了先来先服务。 6.操作系统中产生死锁的根本原因是_______。 （A）资源分配不当和CPU太慢 （B）系统资源数量不足 （C）作业调度不当和进程推进顺序不当 （D）用户数太多和CPU太慢 7．内存管理中把作业地址空间中使用的逻辑地址转变为内存中的物理地址称为______。 （A）链接。 （B）装入。 （C）重定位。 （D）虚拟化。 8．I/O设备管理是操作系统的重要功能，那么下列对设备属性的描述正确的是_______。 （A）字符设备的基本特征是可寻址到字节，即能指定输入的源地址或输出的目标地址。 （B）共享设备必须是可寻址的和可随机访问的设备。 （C）共享设备是指同一时间内运行多个进程同时访问的设备。 （D）在分配共享设备和独占设备时都可能引起进程死锁。 9．程序设计时需要调用操作系统提供的系统调用，被调用的系统调用命令经过编译后，形成若干参数和_______ （A）访管指令或软中断 （B）启动I/O指令 （C）屏蔽中断指令（D） 通道指令 10.以时间换空间或者以空间换时间是操作系统的基本技术，以下以空间换时间的机制是_____。 科目代码：829科目名称：计算机专业基础 第2页 共5页 （A）SPOOLING （B） 虚拟存储技术 （C） 通道技术 （D） 覆盖技术 二、简要分析题(共2小题，每小题5分，共10分) 1．从操作系统设计角度谈谈进程控制块的作用。 2．解释静态链接和动态链接是现代操作系统中两种重要的链接方式，试比较同一程序经过静态链接和动态链接后的可执行文件大小，如果有不同分析原因。 三． 综合应用题（共5小题，共30分） 1．（6分）某操作系统采用分页式虚拟存储管理方法，现有一个进程需要访问的地址序列(字节)分别是：115，228，120，88，446，102，321，432，260，167，假设该进程的第0页已经装入内存，并分配给该进程300字节内，页的大小为100字节，试回答以下问题： （1）按LRU调度算法将产生多少次页面置换，依次淘汰的页号是什么？页面置换率为多少？ （2）LRU页面置换算法的基本思想是什么？ 2.（6分）设磁盘的I/O请求队列中的柱面号分别为： 155,158,139,118,190,260,250,138,284，磁头初始位置为200，磁臂方向由小到大。（1）请给出采用SSTF的磁盘调度算法的磁头的柱面移动次数。（2）SSTF的磁盘调度算法有何缺点？ 3.（6分）简述消息缓冲队列通信机制，并用信号量和wait，signal操作实现消息缓冲队列通信机制中的发送和接受原语. 4．（6分）设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2，P3，P4，P5），A的资源的数量为17，B的资源的数量为5，C的资源的数量为20，在T0时刻状态如下： 最大资源需求量 已分配资源需求量 A B C A B C P1 P2 P3 P4 P5 5 5 4 4 4 5 3 0 2 2 9 6 11 5 4 2 4 4 2 3 1 0 0 0 1 2 2 5 4 4 剩A B C 余2 3 3 资源数 系统采用银行家算法实施死锁避免策略。 （1）T0时刻是否为安全状态？若是请给出安全序列。 （2）在T0时刻，若进程P2请求资源（0，3，4），是否能实施资源分配？为什么？ （3）在（2）基础上，若进程P4请求资源（2，0，1），是否能实施资源分配？为什么？ 5. (6分) 一个进程某时刻的页表如下图所示： 页号 标志 内存块号 0 1 2 1 0 2 1 8 科目代码：829科目名称：计算机专业基础 第3页 共5页 3 1 1 4 0 5 1 0 本题中的数字均为十进制，页号、块号都以0开始，页的大小为2K字节，标志为1表示页面在内存，标志为0表示不在内存；请回答下列问题： (1)简述分页式虚拟存储系统中，一个逻辑地址到物理地址的转换过程（并画出地址转换机构图） (2)逻辑地址5188和3199对应的物理地址是什么？ （三、计算机组成原理部分 50分） 1．（10分）关于浮点数的表示和运算，请回答下列问题： （1）简单叙述浮点机器数加减运算所必需的5个步骤。（5分） （2）若某机内部浮点机器数的阶码用移码表示（偏置常数为24），尾数用规格化补码表示，无隐含位，基数为2，格式如下： 数符 1位 阶码 5位 尾数 14位 已知按照该格式表示的浮点机器数[x]浮=56030H，[y]浮=D9F00H，求x+y的和所对应的机器数[x+y]浮（请用16进制表示）。（5分） 2．（10分）关于总线以及通信请回答下列问题： （1）假设N是总线允许接纳的最大设备数，针对总线的判优控制，即链式查询方式、计数器定时查询方式以及独立请求方式，请问这三种方式各需要最少多少根额外的控制线才能完成总线判优控制？（6分） （2）某异步串行传输系统中，若字符格式为1位起始位、7位数据位、1位奇校验位、1位终止位，每分钟最快能够传输12000个字符，则该系统的波特率和比特率分别是多少bps(位/秒)?（4分） 3．（10分）某16位机器所使用的指令格式和寻址方式如下所示，该机有两个20位基址寄存器，四个16位变址寄存器，十六个16位通用寄存器。指令汇编后有三种格式（如下图所示），其中的S(源)、D(目标)都是通用寄存器编码，M是主存单元地址，MOV是传送指令，采用格式1，STA为写数指令，LDA为读数指令，它们都可以采用格式2或格式3。16进制操作码分别为：MOV(OP) =9H，STA(OP)=13H，LDA(OP)=27H。 格式1： 15—10 9—8 7—4 3—0 OP — D S （其中第9—8位未定义，指令中汇编为00，格式3与此类同） 格式2： 15—10 9—8 7—4 3—0 OP 基址 S或D 变址 16位位移量 （其中第9—8位为01或10分别表示选用一个基址寄存器，其它编码无效; 第3—0位16个编码中选用4个编码分别指明1个变址寄存器，其它编码无效） 格式3： 15—10 9—8 7—4 3—0 OP — S或D 20 位内存地址 （其中20位内存地址由第一行的3—0位和第二行构成） 要求：（1）分析三种指令的寻址方式特点。（3分） （2）分析处理机完成每一种格式的指令所花时间的长短，并说明原因. （5分） （3）分析指令(9C268FA5)H的功能。（2分） 科目代码：829科目名称：计算机专业基础 第4页 共5页 4.（10分）某计算机有64KB的主存和1KB的Cache，Cache每组2块，每块64字节，存储系统按组相联方式工作。要求： （1）设计主存地址格式。 （2）若Cache原来是空的，CPU以字节为单位依次从0号地址单元顺序访问到1029号单元，然后再按此顺序重复访问存储器5次，页面替换采用先进先出算法。若访问Cache的时间为20ns，访问主存的时间为200ns，请计算Cache-主存系统的命中率、访问效率和平均访问时间。 5. （10分）某模型机的主机结构如下图所示，其中MEM为主存，AC为累加器，CU为控制单元，STA指令的功能是将AC中的数取出送到主存，如果每个工作周期都是3个节拍，请分别写出取址和执指周期的微操作序列。 科目代码：829科目名称：计算机专业基础 第5页 共5页