2016年哈尔滨工业大学软件学院数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 下列叙述中，不符合m 阶B 树定义要求的是（ ）。
A. 根结点最多有m 棵子树 B. 所有叶结点都在同一层上 C. 各结点内关键字均升序或降序排列 D. 叶结点之间通过指针链接 【答案】D
【解析】B 树就是指B-树。根据B-树的定义，m 阶B-树中每个结点最多有m 个分支，因此，根结点最多有m 棵子树，A 项正确；B-树中所有叶结点都在最底层，位于同一层，B 项正确；结点内各关键字互不相等且有序排列，C 项正确。但是，所有叶子结点之间通过指针链接，是B+树的定义，而B-树中没有。因此，D 项是错误的。
2． 在文件的索引节点中存放直接索引指针10个，一级二级索引指针各1个，磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中，到把该文件的偏移量（按字节编址）为1234和307400 处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。
A.1, 2 B.1, 3 C.2, 3 D.2, 4
【答案】B
【解析】文件的索引结点的直接索引指针有10个，因此直接索引的偏移量范围是级索引的偏移量范围是
二级索引访问的偏移量范围是
一
偏移量1234
可以通过直接索引得到在磁盘块的地址，因此需要一次访问，307400需要通过二级索引查找其在磁盘的位置，需要分别访问存放二级索引的两个索引块以及对应的数据块。
3． 若某通信链路的数据传输速率为采用4相位调制，则该链路的波特率是（ ）。
A.600波特 B.1200波特 C.4800波特 D.9600波特 【答案】B
【解析】注意无噪声下的码元速率极限值B 与信道带宽H 的关系：B = 2xH （Baud ）, 而奈奎斯特公式一无噪信道传输能力公式是
N 为一个码元所取的离散值个数。从
而可以得到波特率与数据传输速率的关系，即在本题中数据传输速率C = 2400,
N=4，因此波特率是1200, 答案是B 。
4． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。
【答案】C
【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为的时间复杂度为
对于采用归并法，它是一种稳定的排序方法，它
对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，
此时的时间复杂度为
5． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于
中，那么第i 行的对角元素
存放于B 中（ ）处。
【答案】A
【解析】
中列标不大于行标，
又
存放在
中，
所以
存
存放的位置为
6． 下列选项中，操作系统提供的给应用程序的接口是（ ）。
A. 系统调用 B. 中断 C. 库函数 D. 原语 【答案】A
【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口复杂调用（例如多种
，
以及包含在）
自然命令用户接口
等，而系统调用中除了常规的一些传统的系统调用（例如read （ ））以外，还有经过扩展的
库中的各种封装好的过程调用（最终都是通过系统调
用陷入到操作系统中去的）等。
7． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为
8． 将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是（ ）。
I. 父子关系 II. 兄弟关系
III.u 的父结点与v 的父结点是兄弟关系 A. 只有I B.I 和II C.I 和III D.I 、II 和III 【答案】B
【解析】首先，在二叉树中，若结点U 是结点v 的父结点的父结点，那么u*v的关系有如下4种情况：
接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中： ，在原来的森林中U 是V 的父结点的父结点； 情况（1）
，在森林中u 是v 的父结点； 情况（2）
，在森林中u 是v 的父结点的兄弟； 情况（3）
，在森林中u 与v 是兄弟关系。 情况（4）
由此可知，题目中的I 、II 是正确的。
9． 设图的邻接矩阵A 如下所示，各顶点的度依次是（ ）
A.1, 2, 1, 2 B.2, 2, 1, 1 C.3, 4, 2, 3 D.4, 4, 2, 2 【答案】C
【解析】当图用邻接矩阵存储时，各顶点的度是矩阵中此结点对应的横行和纵列非零元素之和。
相关内容
相关标签