2016年东南大学学习科学中心5h1专业综合测试1之数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 假设5个进
程共享三类资
源
题表资源分配情况表
这些资源总数分别
为时刻的资源分配情况如题表所示，此时存在的一个安全序列是（ ）。
答:D 。
【解析】典型的死锁避免算法、银行家算法的应用。本题的题型与2011年的27题相似。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到
，运行是可以的。
本题也可以排除法，时刻可用资源是分别为2, 3, 3, 此时刻，P0需要
分别为2, 3, 7，故排除A , P1需要Rl ，R2, R3分别为1，3, 3, P2还需要资源Rl ，R2, R3分别为0, 0, 6，故C 排除，P3需要Rl ，R2, R3分别为2, 2, 1。所以正确答案在B ，D 之间。看B 选项，P1之后的可用资源Rl ，R2, R3分别变为6, 3，6，而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。
2． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ） A.
B.
C.
D.
答:D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
3． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
答:A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需趟排序，也即时间复杂度仍为而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时
；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，也即间复杂度为0（nlog2n ）
n-1趟，
比较的时间复杂度由 降至
4． 下列指令中，不能在用户态执行的是（ ）
A.trap 指令
B. 跳转指令
C. 后栈指令
D. 关中断指令
答:D
【解析】关中断指令必须在和心态才能执行，trap 指令可以在用户态下执行，执行了就转到和心态，跳转与退栈指令都是可以在用户态下执行的指令。
5． 某计算机的Cache 共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache 组号是（ ）。
A.0
B.2
C.4
D.6
答:C
【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K=ImodQ（K 代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数）来计算Cache 的组号。由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4, Cache 共有16
，故Cache 有8组，按照上面的公式可以计算得到块，采用2路组相联映射方式（即每组2块）
Cache 的组号=4mod8=4。
6． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串
B. 树
C. 广义表
D. 栈
答:C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
7． 下列选项中，在总线的数据线上传输的信息包括（ ）。
I. 接口中的命令字
II. 接口中的状态字III. 中断类型号
A. 仅 I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 、III
答:D 。
【解析】
在
总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。
8． 某计算机存储器按字节编址，主存地址空间大小为64MB ，现用4Mx8位的RAM 芯片组成32MB 的主 存储器，则存储器地址寄存器MAR 的位数至少是（ ）。
A.22 位
B.23 位
C.25 位
D.26 位
答:D
【解析】虽然实际的主存储器（RAM 区）只有32MB , 但不排除还有ROM 区，考虑到存储器扩展的需要， MAR 应保证能访问到整个主存地址空间。因为主存的地址空间大小为64MB , 所以MAR 的位数至少需要26位。
9． 下列关于闪存（FlashMemory ）的叙述中，错误的是（ ）。
A. 信息可读可写，并且读、写速度一样快
B. 存储元由MOS 管组成，是一种半导体存储器
C. 掉电后信息不丢失，是一种非易失性存储器
相关内容
相关标签