2018年北京联合大学移动商务803软件基础之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 建立索引文件的目的是_____。
【答案】提高查找速度
2． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
3． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
4． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
5． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。
【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)
【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。
二、单项选择题
6． 设文件F1的当前引用计数值为1，先建立F1的符号链接(软链接) 文件F2，再建立F1的硬链接文件F3，然后删除F1. 此时，F2和F3的引用计数值分别是（ ）.
A.0、1
B.1、1
C.1、2
D.2、1
【答案】B
【解析】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目(引用计数值) ，这是共享的一种方法. 当新文件建立时，一般默认引用计数值为1. 硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1. 当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件. 软链接又叫符号链接，在新文件中只包含了被链接文件的路径名，新文件和被链接文件指向不同的节点. 建立软链接文件时，文件的引用计数值不会增加. 在这种方式下，当被链接文件删除时，新文件仍然是存在的，只不过是不能通过新文件的路径访
F1和F2的引用计数值都为1. 当再建立F3时，问被链接文件而已. 因此，在本题中，当建立F2时，
F1和F3的引用计数值就都变成了2. 当后来删除F1时，F3的引用计数值为2﹣1＝1.F2的引用计数值仍然保持不变，所以F2和F3的引用计数值分别是：1，1.
7． 若一个栈以向量 存储，初始栈顶指针top 为n+1，则下面X 入栈的正确操作是（ ）。
A.top :＝top ＋l ；V[top]:＝x
B.V[top]:＝x ；top :＝top ＋l
C.top :＝top ﹣l ；V[top]:＝x
D.V[top]:＝x ；top :＝top ﹣l
【答案】C
【解析】题中初始栈顶指针top 为n ＋1，而栈顶指针又位于最大下标以上，此时入栈应进行先减一操作。
8． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。
A.p ﹣＞llink ＝q ；q ﹣＞Rlink ＝p ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Llink ＝q ；
B.p ﹣＞llink ＝q ；p ﹣＞Llink ﹣＞Rlink ＝q ；q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞Llink ；
C.q ﹣＞Rlink ＝p ；q ﹣＞Llink ＝p ﹣＞L1ink ；p ﹣＞L1ink ﹣＞Rlink ＝q ；p ﹣＞Llink ＝q ；
D.q ﹣＞llink ＝p ﹣>llink；q ﹣＞Rlink ＝q ；p ﹣＞llink ＝q ；p ﹣＞llink ＝q ；
【答案】C
9． 单处理机系统中，可并行的是（ ）.
(1)进程与进程
(2)处理机与设备
(3)处理机与通道
(4)设备与设备
A. (1)、(2)和(3)
B. (1)、(2)和(4)
C. (1)、(3)和(4)
D. (2)、(3)和(4)
【答案】D
【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.
10．某同步总线的时钟频率为100MHz , 宽度为32位, 地址/数据线复用, 每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发) 传输方式, 则一次“主存写”总线事务传输128位数据所需要的时间至少是（ ）。
A.20ns
B.40ns
C.50ns
D.80ns
【答案】C 。
【解析】总线的时钟频率为100MHz , 则时钟周期为10ns 。数据是128位, 总线宽度是32位, 所以需要4个时钟周期, 而传输地址还需要一个周期, 所以传输一个128位的数据至少需要5个时钟周期, 所以至少需要。
11．两台主机之间的数据链路层采用后退N 帧协议(GBN)传输数据, 数据传输速率为16kbps , 单向传播时延为270ms , 数据帧长度范围是字节, 接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高, 帧序号的比特数至少为（ ）。
A.5
B.4
C.3
D.237
【答案】B 。
【解析】GBN 的工作原理如下图所示, 本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧, 要尽可能多发送帧, 应以短的数据帧计算, 注意帧的单位是字节, 因此首先计算出发送一帧的时
间
为
; ,
这段时间总共可以发送, 故发送一帧到收到确认为止的总时间(帧) , 为了保证发送帧序号和确认帧序号在此期间不重复, 因此桢序号的比特数至少为4, 答案为
B