2013专业课真题
一、选择题(1~20题，共40分)
1.在利用栈将中缀表达式A-(B+C/D)×E转化成后缀表达式的过程中，当扫描到符号”)”时，栈中的内容是 A (+/ B -(+ C -(/ D -(+/
2.现有一颗含有25个结点的4叉树T，若T中所有分支(即度不为0的)结点的度均为4，则T的叶子节点数是 A 15 B 17 C 19 D 21
3.下列序列中，不可能是任意二叉搜索树后序遍历序列的个数是
①5,3,4,10,12,8 ②5,4,3,10,12,18 ③3,4,5,12,10,8 ④10,12,5,4,3,8 A 0 B 1 C 2 D 3
4.带权无向图G如下图所示，若分别用Prim算法(从顶点0开始)和Kruskal算法求G的最小生成树，则最后选中的边的权值分别是
A 5,3
B 3,5
C 5,4
D 5,5
5.已知序列25,13,10,12,9,5,6,8是大根堆，在插下新元素20的过程中，共进行比较操作的次数是 A 0 B 1 C 2 D 3
6.若数据元素序列9,10,11,8,5,12,2,4,7是采用下列排序方法之一得到的第二遍排序后的结果，则该排序算法只可能是 A 冒泡排序 B 选择排序 C 插入排序 D 二路归并排序
7.若依次将关键码20,30,50,52,60,68,70插入到初始为空的3阶B树中，则最后得到B树的根结点中所包含的关键码是 A 50 B 52 D 60 D 50,52
8.下列关于机器字长的叙述中，错误的是 A通用寄存器位数等于机器字长 B系统总线宽度等于机器字长 C主存单元长度不大于机器字长 D ALU位数等于机器字长
9.为了使计算机的数据传送和数据处理的功能可以并行实现，下列方法中有效的是 A多种总线互联 B以存储器为中心 C多重存储器共存 D以运算器为中心
10.某计算机存储器按字节编址，主存容量配置为64KB，下列设计方案中，所用芯片的MOS管门电路等基本元件性能相当，则性能最优的方案是 A 4片16KB×8位SRAM芯片 B 4片16KB×8位DRAM芯片 C 4片32KB×4位SRAM芯片 D 8片64KB×1位DRAM芯片
11.下列寻址方式中，只能用于指令寻址的是 A 立即寻址 B 寄存器寻址 C 相对寻址
D 基址寻址
12.下列有关微指令的叙述中，错误的是 A垂直型微指令全部是功能性指令 B垂直型微指令指令长度比较短 C水平型微指令可完成多个微操作 D水平型微指令显示表示顺序控制信息
13.下列有关总线定时的叙述中，错误的是 A异步全互锁定时方式的通信速度最慢 B异步不互锁定时方式的通信可靠性最差
C异步定时方式的握手信息可不通过联络信号产生 D同步定时方式的时钟信号可由设备自行提供
14.下列有关I/O接口的描述中，错误的是 A每个I/O接口中至少包含一个I/O端口 B一个I/O接口可以连接多个I/O设备
C程序控制方式的I/O接口中可以没有状态口 D不同I/O接口的I/O端口之间允许独立编址
15.一个请求分页系统，测得如下利用率：CPU为5%，分页磁盘为97.5%，外设为4%，则下列措施中，可改善CPU利用率的是 A更换速度更快的CPU B更换更大容量的分页磁盘 C挂起内存中的某个用户进程 D增加内存中的用户进程
16.以下关于页式内存管理系统页面大小的叙述中，正确的是 A页越大，页表也越大 B页越大，则I/O开销越大 C页越大，则内部碎片越大 D页越大，则产生缺页中断的可能性越大
17.某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台，为使系统不产生死锁，N的取值最多是 A 4 B 5 C 6 D 7
18.以下关于进程说法正确的是
I.进程从运行状态转换到就绪状态，系统一定会发生CPU调度
II.当I/O完成时，一个进程的状态有可能从等待状态转换为运行状态 III.进程从等待状态转换为就绪状态，系统一定会发生CPU调度 IV.进程进入终止状态，系统一定会发生CPU调度 A I和IV B II和III C III和IV D IV
19.页式内存管理系统中，物理内存地址为16位，逻辑地址为24位，页面大小为512B，采用两级页表结构，外层页表有256页，则以下正确的是 I.一个进程中最多有128个页 II.一个进程中最多有32K个页
III.逻辑地址中表示外层页表、页号和页内偏移量的位数分别为8、7、9 IV. 逻辑地址中表示外层页表、页号和页内偏移量的位数分别为7、8、9
20.系统中四个进程(P1~P4)和三类资源(3个R1，2个R2，2个R3)，进程资源分配和请求状况如下表所示，则正确的是 Allocation Request P1 P2 P3 P4 R1 R2 R3 R1 R2 R3 1 0 1 0 0 2 0 0 0 0 0 2 0 1 0 1 1 0 1 0 0 1 0 0 A由银行家算法知，找不到安全序列，存在死锁
B由银行家算法知，系统处于安全状态，无死锁 C由死锁检测算法知，系统中存在死锁 D由死锁检测算法知，系统中不存在死锁
二、综合应用题(21~32，共110分)
21(8分)归并排序一般从用2路归并，即在两两归并过程中，从两个有序子序列中逐次挑选关键字最小的元素。如果采用K路(K>2)归并，能提高排序效率吗？说明理由
22(8分)连通无向图G=(V,E)采用邻接表存储，其中|V|=n，|E|=e。现需要在G中找到这样一个顶点V，删除V及相关联的边对剩下的图的连通性无影响。试说明解决上述问题的算法思路(不需要写出具体程序)，并估计时间复杂度
23(8分)二叉树T采用二叉链表存储，T中结点结构为(Lchild,data,Rchild)，其中Lchild和Rchild分别是指向左右孩子的指针，data为正整数，编写算法，按后序遍历次序输出T中每个结点data值及所处层次(假定根节点在第一层)
24(12分)设S是n个互不相同的整数组成的序列，试编写一个尽可能高效的算法，判定S是否可能在某棵二叉搜索树查找过程中产生的关键字比较序列，若S可能是，则算法输出为1，否则为0。请说明算法的设计思想，并给出时间复杂度和空间复杂度。
25(8分)某16位计算机的ALU仅实现定点加法/减法运算，如下图所示，其中CF为进位/借位标记。ZF为零标记，SF和OF为符号标记和溢出标记。OP=0时实现加法运算，OP=1时， 减法运算。
请回答下列问题：
1) 若ALU操作时，入端A和B
的数据分别由寄存器R1和R2提供，出端Z的数据存放到寄存器R3中，且R1和R2内容分别为+23及-34，则ALU进行加法及减法后，R3的内容分别是多少？(用十
六进制表示)
2) 简述用同一加法器实现加法和减法运算的方法，画出图中的加法/减法处理电路 3) 根据图中所给信号，写出溢出判断电路OF及CF的信号逻辑
26(11分)某16位计算机存储器按字节编址，主存容量为16MB，Cache容量为32KB，采用4路组相联映射方式。Cache和主存间的块大小为32B，请回答下列问题：
1) 为了实现映射，主存地址应划分为哪几个字段？各字段长度分别为多少位？
2) CPU访问主存单元053070H时，可能命中的Cache组号是多少？所命中的Cache行标记
字段的值是多少？
3) 若int型一维数组A存放在主存单元000050H开始的连续的4KB空间中，CPU依次读出
数组A中的所有元素，此时Cache的命中率是多少？ 4) 相对于全写法写策略，简述回写法写策略的优点
27(11分)某8位计算机存储器地址空间为8位，按字节编址。指令系统包含如下2种指令格式： 3bit 1bit 2bit 2bit 8bit 格式1： OP MS1 Rs Rd
格式2： OP MS2 Rs Rd IMME/Address
其中，格式2为双字长指令格式，操作类型由FUNC指定(OP=000)，IMME/Address存放在第2字中：目标操作数仅支持寄存器寻址方式，即Rd为通用寄存器编号；源操作数支持4种寻址方式，分别为寄存器寻址(MS1=0)、寄存器间接寻址(MS1=1)、立即寻址(MS2=0)、直接寻址(MS2=1)，且约定加法指令采用格式1时，OP=001，采用格式2时，FUNC=01.
设计算机CPU部分如下，R0~R3为通用寄存器(编号0~3)。ALU可实现加法(ALUOP=0时)及减法(ALUOP=1时)操作，其余控制信号为1时表示有效，为0时表示无效。微操作(uOP)控制信号的定时采用联合控制方式(访存操作的等待信号为WMFC)，指令结束信号用End表示。
请回答：
1) 该计算机指令系统最多有多少条指令？
2) 分别写出R1中数据与R2内容所指主存单元中数据相加指令字，以及R2中数据与43H
号主存单元中数据相加指令字，目标操作数均为寄存器寻址方式(十六进制表示) 3) 下表给出了CPU取指和译码每个节拍(时钟周期)的功能及有效信号
时钟 C1 C2 C3 功能 MAR←(PC), Read M MDR←M[(MAR)], PC←PC+1 IR←(MDR)
有效控制信号 PCout, MARin , Read WMFC, PCin MDRout, IRin
C4 指令译码 无
若所取指令为加法指令，源操作数为立即寻址方式，目标操作数在R3中，请按上表格式用表格列出指令执行阶段每个节拍的功能及有效控制信号。
4) 若将该CPU改造成流水线处理器，流水线由取指(IF)、译码(ID)、取数(OF)、执行(EX)和写
结果(WB)组成，简述处理结构相关时须解决的基本问题。
28(6分)某计算机主频为200MHz，CPI为5，存储器总线宽度为32位。准备连接一个数据传输率为20KB/s的字符设备，及1个数据传输率为1MB/s的块设备；字符设备采用中断方式I/O，块设备采用DMA方式I/O，DMA传送方式为周期窃取方式，每次DMA传送数据块大小为4000B。请回答：
1) 若CPU平均每条指令访存1.2次，Cache命中率为0.98，则CPU平均每秒访问主存次数
是多少？
2) 当两个设备均以最大能力工作时，每秒将有多少次DMA请求及中断请求？
3) 若采用I/O总线连接上述设备，且每个总线周期需要4个总线时钟周期，则I/O总线的
总线时钟频率最少是多少？
29(9分)在一个双CPU机器上执行四个进程(P1~P4)，进程到达时刻分别是0,5,10,20，优先级分别是1,2,3,4(值最大者优先级高)，执行时间分别为15,10,25和10个时间单位，系统中有一个就绪队列(ready queue)。可采用下列可抢占调度算法：优先级(Priority)调度，时间片为10个时间单位的轮转(Round Robin)调度，以及最短作业优先(Shortest Job First)调度。请回答下列问题：
1) 分别画出采用上述各种调度算法的甘特图
2) 若上下文切换开销为0，分别计算采用上述各种调度算法的平均等待时间和平均周转时
间
30(8分)一个磁盘有1024个磁道，当前磁头位置在51号磁道，且正向第0号磁道运动。有一个文件分别存储在4个磁盘块中，按顺序其所处的磁道号分别为20，500，10，900，该文件的目录项存储在第50号磁道的某块中。请回答下列问题：
1) 假定磁盘调度采用LOOK策略，文件结构采用链接分配方式，给出读取整个文件的磁盘
访问序列，计算所需的总寻道距离。
2) 假定磁盘调度策略采用C-SCAN策略，文件结构采用FAT分配方式，FAT表位于0磁道，
若执行append操作(在文件末添加内容)，添加的数据存储于600号磁道上的某块中。给出append操作的磁盘访问序列，计算相应的寻道距离。
31(12分)车间有甲乙丙三个工人，甲生产零件A，乙生产零件B，甲和乙每生产出一个零件都放入到同一个周转箱中，丙每次从该箱中取出一件A和一件B组装成成品。周转箱每次只能有一个人放入或者取出零件，能放入的零件总数为n，规定A和B均不能连续放入，且放入一件A后才能放入B，使用信号量实现甲乙丙之间的同步。
2013年东南大学计算机专业考研真题
