1、2014 年东南大学计算机专业考研真题一、 选择题(共 80 分)1.下面关于进程的描述中，不正确的是A 进程是动态的概念 B 进程就是一个独立的程序C 进程可以并发执行 D 进程可由程序、数据和进程控制块描述2.在多对一的线程模型中，一个多线程中的某个线程执行一个需阻塞的系统调用时，下列选项中正确的是A 整个进程都将被阻塞 B 该进程的其他线程仍可继续执行C 该阻塞线程将被撤销 D 该阻塞线程将阻塞直到进程退出3.采用多道程序设计技术能提高整个计算机系统的效率，其基本条件是A 硬盘容量大 B 处理器执行指令速度快C 外围设备多 D 系统具有处理器与外设并行工作的能力4.下列指令中，不是特权指
2、令的是A I/O 指令 B 读取当前时钟C 设置基址寄存器 D 关闭中断5.在存储管理中，外部碎片指的是A 存储分配完成所剩的空闲区 B 没有被使用的存储区C 不能被使用的存储区 D 未被使用，又暂时不能使用的存储区6.进程所请求的一次打印输出结束后，进程状态会发生的变化是A 从运行态变成就绪态 B 从运行态变成等待态C 从等待态变成就绪态 D 从就绪态变成运行态7.关于 Round Robin 调度算法，以下说法正确的是I.同样的情况下，时间片越大，平均周转时间越小II.FCFS 算法是 Round Robin 算法的一种特殊情况III.只有实现了定时的机制，才能实现 Round Robin
3、 算法IV.Round Robin 属于非抢占调度算法A 仅 I 和 II B 仅 II 和 IIIC 仅 III 和 IV D 仅 I 和 IV8.物理内存和虚拟存储空间相比，其大小关系是A 前者比后者大 B 前者比后者小C 两者一样大 D 不一定9.临界区指的是A 一段内存共享区域 B 一个共享变量C 访问临界资源的一段程序 D 一种同步机制10.为使虚拟存储系统有效发挥其预期作用，所运行的程序应具有的特性是A 程序应比较大 B 程序应该具有良好的局部性C 程序应含有多个 I/O 操作 D 程序应含有较多的动态分配内存工作11.下列说法正确的是I.当发现系统中存在抖动(Thrashing)
4、时，应更换一块更大的磁盘用于页面置换II.内存分页管理方式不会产生外部碎片III.磁盘访问时间主要是由旋转时延和传输时延组成IV.FCFS 算法可用于实现磁盘调度A 仅 I 和 II B 仅 III 和 IVC 仅 II 和 IV D 仅 I 和 III12.一个请求分页存储管理系统中，假设分配给某作业的页框(Frame)数为 3，该作业的页引用序列为 0,2,1,3,0,2,4,0,2,1,3,4，所有的页框初始时都为空，分别采用最近最少次数使用(LRU)和最优(OPT)页面置换算法时，产生页面失效(Page Fault)的次数分别是A 10 和 7 B 9 和 8C 9 和 7 D 7 和
5、 413.单处理器系统中有 n(n2)个进程，若进程调度程序当前没有执行，则以下情形不可能发生的是A 有一个运行进程，没有就绪进程，剩下的 n-1 个进程处于等待状态B 有一个运行进程和一个就绪进程，剩下的 n-2 个进程处于等待状态C 没有运行进程，有一个就绪进程，剩下的 n-1 个进程处于等待状态D 有一个运行进程和 n-1 个就绪进程，没有进程处于等待状态14.关于短作业优先(SJF)调度算法，下列说法正确的是I.SJF 算法能得到最优的平均等待时间II.SJF 算法能得到最优的平均响应时间III.SJF 算法可能产生”饥饿”(Starvation)现象IV.SJF 算法是一种实际系统中
6、常用的 CPU 调度算法A 仅 I 和 III B 仅 II 和 IVC 仅 I 和 IV D 仅 II 和 III15.下列选项中，不是文件系统应具备的功能的是A 对文件按名存取 B 实现对文件的各种操作C 提高磁盘的 I/O 速度 D 访问数据时实现从逻辑结构到物理结构的转换16.下列文件的物理结构中，可能带来外部碎片问题的是A 连续结构 B 链接结构C 索引结构 D Hash 结构17.下列选项中，不属于算法的主要特征的是A 有穷性 B 可行性C 确定性 D 可读性18.若一个栈 S 的入栈序列为 0,1,2,3,4,5,6,7,8,9，对于下列序列， S 的可能出栈序列是I.5,6,8
7、,7,2,1,4,3,0,9 II.0,2,1,6,5,8,7,4,3,9III.2,0,1,4,3,7,8,6,5,9 IV.6,5,7,8,4,3,1,2,9,0A 仅 I B 仅 IIC 仅 I 和 III D 仅 II 和 IV19.对任意一个给定的二叉树进行前序、中序和后序遍历可得到三个遍历序列。下列有关这三个遍历序列的叙述中，正确的是I.叶子结点在三个遍历序列中先后次序是一样的II.兄弟结点在三个遍历序列中先后次序是一样的III.父子结点在三个遍历序列中先后次序是一样的IV.祖先和子孙结点在三个遍历序列中先后次序是一样的A 仅 I 和 II B 仅 III 和 IVC 仅 I 和
8、III D 仅 II 和 IV20.下列选项中，不可能是任何二叉搜索树的前序遍历序列的是A 4,2,3,5,6,7 B 4,3,2,7,6,5C 6,5,4,2,3,7 D 6,5,3,4,2,721.用 n(n 大于等于 2)个权值均不相同的字符构成哈夫曼树，下列关于该树的叙述中错误的是A 树中一定没有度为 1 的结点B 该树一定是一棵完全二叉树C 树中两个权值最小的结点一定是兄弟结点D 树中任一非叶子结点的权值一定不小于其任一子节点的权值22.无向图 G 如下图所示，下列选项中，不可能是 G 的广度优先遍历序列的是A 0,1,2,3,4,5B 0,2,1,3,4,5C 0,1,2,3,5,
9、4D 0,3,2,1,5,423.下列关于图的叙述中，正确的是A 强连通有向图的任何顶点到其他所有顶点都有弧B 图与树的区别在于图的边树大于等于顶点数C 有向图的遍历不可采用广度优先遍历方法D 带权无向图 G 中，若所有边的权值均不相同，则 G 的最小生成树是唯一的24.若排序过程中出现这种情况，在最后一遍开始之前，所有元素都不能保证在其最终的位置上，则采用的排序算法是A 冒泡排序 B 堆排序C 快速排序 D 直接插入排序25.若对 15 个元素进行快速排序，则元素的比较次数至少是A 26 B 34 C 52 D 7826.对序列 14,9,7,10,20,1,5 进行排序，若第一趟后的数据排
10、列为 5,9,1,10,20,7,14，则采用的排序算法是A 选择排序 B 归并排序 C 希尔排序 D 冒泡排序27.对一个长度为 16 的有序表，若采用折半查找法查找一个表中不存在的元素，则比较次数最多的是A 7 B 6 C 5 D 428.在一棵初始为空的 AVL 树 T 中依次插入关键码 1,2,3,4,5,6,7 的结点后，T 的根结点的关键码是A 3 B 4 C 5 D 629.冯 诺依曼模型计算机中存放指令地址的寄存器是A PC B IR C MAR D MDR30.某计算机中各种指令的 CPI 平均为 8，CPU 采用 5 级流水方式执行指令，流水线每拍为2 个时钟周期。执行程序
11、 A 时，共执行 2000 条指令，此时流水线的加速比约为A 4.0 B 5.0 C 8.0 D 10.031.下列奇偶校验码中，若有一个存在错误，则它是A 10001001 B 01001101 C 11010110 D 1000010132.某 16 位计算机中，存储器按字节编址，整数用补码表示。数据在存储器中采用小端次序存放，若 X,Y,Z 为整数，且 X=-41，Y=+75，Z=X-Y，Z 存放在地址为 A 和 A+1 存储单元中，则存储单元 A 的内容是A 00H B 74H C 8CH D FFH33.某 CPU 中，若进位/借位标志为 CF，零标志为 ZF，符号标志为 SF(0
12、表示正)，溢出标志为 OF，uA 和 uB 为无符号整数，则判定 uA 小于等于 uB 的条件是A SF=1 B SF+ZF=1 C CF=1 D CF+ZF=134.目前，内存条通常由 DDR2 SDRAM 或 DDR3 SDRAM 芯片组成，该芯片为多体存储器，能够在总线时钟上升沿、下降沿都传送数据。相对基本的 SDRAM 芯片，该类芯片提高性能采用的主要方法是A 增加数据引脚数量 B 减小存储元和 I/O 电路延迟C 交叉编址，并行或交叉存取 D 顺序编址，并行或交叉存取35.下列虚拟存储器的叙述中，错误的是A 虚拟存储器有自己的存储阵列 B 虚拟存储器需按程序逻辑地址访问C 虚拟存储的
13、慢表放在主存中 D 虚拟存储的快表结构类似于 Cache36.下列选项中，与 CPU 主时钟周期相同的是A CPU 周期 B 机器周期 C 节拍周期 D 节拍脉冲37.某同步总线的总线宽度为 16 位，每次数据传输需 2 个总线时钟周期，若希望总线带宽达到 1064MB/s，则总线时钟的频率至少是A 133MHz B 266MHz C 532MHz D 1064MHz38.下列总线仲裁方法中，仲裁过程不需要主设备参与的是A 链式查询 B 独立请求 C 分布式仲裁 D 计数器定时查询39.某磁盘有 1800 个磁道，每个磁道有 120 个扇区，每个扇区可以记录 2KB 的信息，若磁盘机的转速为
14、5400 转/分钟，则该磁盘的最大数据传输率为A 2.73MB/s B 19.33MB/s C 20.60MB/s D 22.12MB/s40.Intel 8086 CPU 采用向量方式处理中断和异常，支持多个可屏蔽中断向量，可以屏蔽中断请求及响应引脚为 INTR 及 ，则 CPU 采用的可屏蔽中断源识别方法是INTAA 软件查询 B 串行判优 C 并行判优 D 无法确定二、 综合应用题(4147 题，共 70 分)41(9 分 )页式内存管理系统中，逻辑地址为 24 位，页面大小为 512B，采用两极页表结构，页表中的每一项占 2B。该系统中访问一次内存的时间为 250ns，不考虑其他环节所
15、用的时间。请回答下列问题：1) 逻辑地址中，用于表示外层页表(outer page table)、页号和页内偏移量的位数分别是多少？2) 简要描述该页式内存管理系统的逻辑地址到物理地址的转换过程3) 访问一个逻辑地址需要多长时间42(9 分 )一个系统中共存在 A、B、C、D 四类资源，有 P0 到 P3 四个进程，系统在某一时刻的资源分配情况如下表所示：Max Allocation AvailableA B C D A B C D A B C DP0 6 0 1 2 4 0 0 1P1 1 7 5 0 1 1 0 0P2 2 3 5 6 1 0 5 4P3 1 6 5 3 0 6 3 33
16、2 1 1请回答下列问题：1) 死锁产生的四个条件分别是什么？2) 需求(Need)矩阵的内容是怎样的？3) 系统是否处于安全状态？为什么？43(10 分)假设缓冲区 buf 最多可存放 n 个数据，进程 P1 往 buf 中写数据，当 buf 中数据多于 m 个时允许进程 P2 从中取数据，m 小于 n，均为正数，试用信号量实现 P1 和 P2 之间的同步44(10 分)设散列表 HT 的存储空间是一个从 0 开始的一位数组，装填( 载)因子为 0.6，散列函数为 H(key)=key MOD 7。现将关键字序列(8,19,12,17,13,20) 散列存储到 HT 中，处理冲突采用线性探测
17、法。回答下列问题：1) 请画出所构造的散列表2) 分别计算等概率的情况下，查找成功和查找不成功的平均查找长度45(11 分)令 A 是具有 n 个元素的一维数组， x 是 A 中的一个元素，若 A 中有一半以上的元素与 x 相同，则称 x 是 A 的主元素。例如：若数组 A 为a ， c， a， b， a， d，a，则存在主元素 a；若数组 A 为a ， d， b， c， b， d， a，则 A 中不存在主元素。试设计算法，判断 A 中是否存在主元素，若存在则给出其主元素。请简要说明算法的设计思想，用 C 或 C+语言给出算法，并请说明算法的时间、空间复杂度46(10 分)某计算机主存按字节编
18、址、地址空间为 32 位；Cache 数据区容量为 1MB，采用 4路组相联映射方式、LRU 替换算法、写回法写策略，块大小为 32B。请回答下列问题：1) Cache 共有多少个组？Cache 行(块) 包含目录表项及块数据区两部分，Cache 行的大小至少为多少位？2) 若 CPU 访存地址为 00463050H，命中时 Cache 的组号是多少？命中时 Cache 行的标记字段的值是多少？(用二进制表示 )3) 某 C 语言程序段为“int i , A512; for (i = 0; i n/2)return mainElement;elsereturn 0;46.（1 ） Cache
19、地址为：组号 13 位、组内块号 2 位、块内地址 5 位。则 Cache 有 2 的 13 次方个组=8192 个组。主存地址为：区号 14 位、区内块号 13 位、块内地址 5 位。Cache 行由目录表项和数据区两部分，目录表项位数为：14+2（LRU 位）+1 （标记位） +1（写回法脏位）=18 位。数据区为 32*8 位=256 位。则 Cache 行大小至少有 18+256=274 位。（2 ） 0000 0000 0100 0110 0011 0000 0101 0000，则 10 0011 0000 010 为命中组号，Cache行标记字段的值为 0000 0000 0100
20、 01（3 ） Ai+=Ai+1等价于 Ai=Ai+Ai+1，则一次循环需要访问主存三次。for(i=0;i512;i+=2)可得循环次数为 512/2=256 次，则该程序段共访存 256*3=768 次。由 sizeof(int)=4，可得存储一个 int 型数据需要 4B。由一个 Cache 块大小为 32B，可得一个 Cache 块可以存放32/4=8 个 int 型数据。int A512定义了 512 个 int 型数据，则存储 A512共需要 512/8=64个 Cache 块。则命中率为 1-64/768=704/768=91.7%。47.（1 ） A8H=1010 1000，1
21、010 对应为 OP2 的存数操作，Rs/Rd=10，则源操作数的寻址方式为寄存器寻址。（2 ） y=y*8，思路：先将 y 所在单元存入 R0，将 R0 左移 3 位，再将 R0 放入 y 所在单元1001 00 00 ；取数操作0010 0011 ；地址 23H，这两步相当于 R023H1000 01 00 ；赋值操作0000 0011 ；3，这两步相当于 R103H001 0 00 01 ；R0 算术左移(R1) 位，相当于 R0(R1)1010 00 00 ；存数操作0010 0011 ；地址 23H，这两步相当于23H(R0)（3 ）R2 MAR，1Read 1TR3 Y， M(MAR)MDR 2TMDRALU ，ADDALU，ALUZ 1TZR3 ， 1End 1T总共需要 5 个时钟周期
