2018年河北师范大学数学与信息科学学院820数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序
B. 起泡排序
C. 基数排序
D. 快速排序
【答案】C
【解析】C 项, 基数排序是采用分配和收集实现的, 不需要进行关键字的比较。ABD 三项都依赖关键字的比较, 不同的初始排列次序下元素移动的次数有很大变化, 最好情况元素正序, 则不用移动, 最坏情况元素反序, 则需要移动次(n为元素个数) 。
2． 在下图所示的采用“存储一转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps ，分组大小为1000B ，其中分组头大小20B ，若主机H1向主机H2发送一个大小为980000B 的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（ ）
.
A.80ms B.
C.
D.
【答案】c
【解析】由题设可知，分组携带的数据长度为980B ，文件长度为980000B ，需拆分为1000个分组，加上头部后，每个分组大小为1000B ，总共需要传送的数据量大小为IMB. 由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过分组交换机. 当t ＝lM ×8/100Mbps＝80ms 时，HI 发送完最后一个比特；到达目的地，最后一个分组，需经过两个分组交换机的转发，每次转发的时间为t 0＝lK ×8/100Mbps＝
装时间和传播延时的情况下，当
，所以，在不考虑分组拆时，H2接受完文件，
即所需的时间至少为
3． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。
A.4
B.5
C.6
D.7
【答案】C
【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为
或》
4． 设文件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.
5． 对线性表进行折半查找时，要求线性表必须（ ）。
A. 以顺序方式存储
B. 以顺序方式存储，且数据元素有序
C. 以链接方式存储
D. 以链接方式存储，且数据元素有序
【答案】B
【解析】二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有
序列表。折半查找方法适用于对以顺序方式存储的有序表的查找，查找效率较高。
6． 哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。
A. 哈希函数
B. 除余法中的质数
C. 冲突处理
D. 哈希函数和冲突处理
【答案】D
【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。
7． 单处理机系统中，可并行的是（ ）.
(1)进程与进程
(2)处理机与设备
(3)处理机与通道
(4)设备与设备
A. (1)、(2)和(3)
B. (1)、(2)和(4)
C. (1)、(3)和(4)
D. (2)、(3)和(4)
【答案】D
【解析】注意区分并发和并行. 在单处理机系统中，进程只能并发. 微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的. 通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行. 显然，设备和设备之间也是可以并行的.
8． 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序
B. 起泡排序
C. 简单选择排序
D. 快速排序
【答案】A
【解析】当待排序列基本有序时，对冒泡排序来说，若最大关键字位于序列首部，则每趟排序仅能使其“下沉”一个位置，要使其下沉到底部仍需n －1趟排序，也即时间复杂度仍为0(n2)。而对简单选择排序来说，其比较次数与待排序列的初始状态无关；归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且