2016年天津大学软件学院数据结构复试笔试最后押题五套卷
● 摘要
一、选择题
1． 假定不采用Cache 和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是（ ）。
A. 每个指令周期中CPU 都至少访问内存一次
B. 每个指令周期一定大于或等于一个CPU 时钟周期
C. 空操作指令的指令周期中任何寄存器的内容都不会被改变
D. 当前程序在每条指令执行结束时都可能被外部中断打断
答:C
【解析】本题涉及的概念比较多。首先，如果不采用Cache 和指令预取技术，每个指令周期中至少要访问内 存一次，即从内存中取指令。其次，指令有的简单有的复杂，每个指令周期总大于或等于一个CPU 时钟周期。第三，即使是空操作指令，在指令周期中程序计数器PC 的内容也会改变为取下一条指令做准备。第四，如果机器处于“开中断”状态，在每条指令执行结束时都可能被新的更高级的中断请求所打断。所以应选择选项C 。
2． 设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。
A.0、1
B.1、0
C.1、2
D.2、0
答:B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源数就只有1个了，由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为0。
3． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
答:B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
4． 5个字符有如下4种编码方案，不是前缀编码的是（ ） A. B. C. D.
答:D
【解析】在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。约定左分支
表示字符
右分支表示字符则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码必是前缀编码。D 选项中，编码110是编码1100的前缀，故不符合前缀编码的定义。
5． 下列选项中，会导致用户进程从态切换到内核的操作是（ ）
I. 整数除以零 II. Sin（ ）函数调用 III. read系统调用
A. 仅 I 、II
B .仅 I 、III
C. 仅II 、III
D. I、II 和III
答:B
【解析】对于I ，系统发生异常，需要进入内核态由操作系统进行处理，而read 系统调用函数也是在内核态执行，sin （ ）就是普通的用户函数，在用户态执行，故答案为C 。
6． 若无向图G= （V , E）中含7个顶点，则保证图G 在任何情况下都是连通的，则需要的边数最少是（ ）。
A.6
B.15
C.16
D.21
答:C
【解析】要保证无向图G 在任何情况下都是连通的，即任意变动图G 中的边，G 始终保持连通。首先需要图G 的任意6
个结点构成完全连通子图然后再添加一条边将第7个结点与需条边，连接起来，共需16条边。本题非常容易错误地选择选项A ，主要原因是对“保证图G 在任何情况下都是连通的”的理解，分析选项A ，在图G 中，具有7个顶点6条边并不能保证其一定是连通图，即有n-1 条边的图不一定是连通图。分析选项D ，图G 有7个顶点21条边，那么图G —定是无向完全图，无向完全图能 保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
7． 主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）
A .10 Mbps
B. 20 Mbps
C.80 Mbps
D.100 Mbps
答:C 【解析】
8． 文件系统中，文件访问控制信息存储的合理位置是（ ）。
A. 文件控制块
B. 文件分配表
C. 用户口令表
D. 系统注册表
答:A
【解析】文件控制块是文件存在的标志，文件的相关信息（基本信息、存取控制信息以及使用信息）都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息。
9． 采用简单选择排序，比较次数与移动次数分别为（ ）。
答:C
【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比 较的次数为
10．下列选项中，降低进程优先级的合理时机是（ ）。
A. 进程的时间片用完
B. 进程刚完成1/0, 进入就绪队列
C. 进程长期处于就绪队列
D. 进程从就绪状态转为运行态
答:A
【解析】进程时间片用完可以降低其优先级，完成的进程应该提升其优先级，处于就绪队列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是
，时间片用完后降低其优独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机）
先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有
相关内容
相关标签