2017年江苏省培养单位苏州生物医学工程技术研究所864程序设计之数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。
A. 串 B. 树 C. 广义表 D. 栈 【答案】C
【解析】串、树、栈中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。
2． 在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps 分组大小为1000B , 其中分组头大小20B , 若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）。
A.80ms
B.80.08ms C.80.16ms D.80.24ms 【答案】C
【解析】由题设可知，分组携带的数据长度为980B , 文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B , 总共需要传送的数据量大小为1MB 。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机。当t ＝1M ×8／100Mbps ＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，
每次转发的时间为
所以，在不考虑分组拆
装时间和传播延时的情况下，当时，H2接受完文件，即所需的时间至少为80.16ms
3． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。
A. 连续结构
B. 索引结构
C. 链式结构且磁盘块定长 D. 链式结构且磁盘块变长 【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展。
4． 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A. 时间片轮转调度算法 B. 短进程优先调度算法 C. 先来先服务调度算法 D. 尚响应比优先调度算法 【答案】D
【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最尚的进程（响应比=1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS ）和短作业优先（SJF ）算法，FCFS 只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF 只考虑执行时间的长短，而未考虑等待时间的长短，HRRN 算法则同时考虑执行时间和等待时间。
5． 若串其子串的数目是（ ）。
A.8 B.37 C.36 D.9
【答案】B
【解析】子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为长为为：
6． 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间 B. 节省内存空间 C. 加快文件的检索速度 D. 加快文件的读/写速度 【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录
长为n 的子串有1个，长为的子串有2个，
的子串有3个，……，长为1的子串有n 个。由于空串是任何串的子串，所以本题的答案
故选B 。
一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度。
7． 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的是（ ）
I. 处理越界错 II. 置换页 III. 分配内存 A. 仅I 、II B .仅II 、III C. 仅I 、III D.I 、II 、和III 【答案】B
【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。
8． 设有数组数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素
【答案】B
【解析】在计算中，可以考虑按照列存放时，址。比如
顺序存放时，它是第
在内存的位置，比较容易计算元素的首地
个元素，由于首地址为BA ，
所以它的存储首地址为
的存储首地址为（ ）。
9． 下列选项中，降低进程优先级的合理时机是（ ）。
A. 进程的时间片用完
B. 进程刚完成1/0, 进入就绪队列 C. 进程长期处于就绪队列 D. 进程从就绪状态转为运行态 【答案】A
【解析】进程时间片用完可以降低其优先级，完成
的进程应该提升其优先级，处于就绪队
列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是，时间片用完后降低其优独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机）先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不优先权）
会随意改变。而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间。
10．图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列