2024年9月2日发(作者：么雅可)
2017 年兰州交通大学电子与信息工程学院 828 数据结构考研
题库
-------------------------------------
一、选择题
1. 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A 其 Next 数组值为（ ）。
【解析】KMP 算法的 next 数组建立的原则
2. 已知三叉树 T 中 6 个叶结点的权分别是 2，3, 4, 5，6，7, T
的带权（外部）路径长度最小是（ ）
A.27
B.46
C.54
D.56
【答案】B
【解析】利用三叉树的 6 个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
3. 某字长为 8 位的计算机中，y 的机器数分别为已知整型变量 x 、
若整型变量
A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
y 右移一位， 【解析】将 x 左移一位，两个数的补码相加的机器数为
1 1000000, 故答案选择 A 。
4．
对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述
中，错误的是（ ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为 1 的结点
C. 树中两个权值最小的结点一定是兄弟结点
则 z 的机器数为（ ）
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
【答案】A
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二
叉树，选项 A 错误；哈夫曼树中没有度为 1 的结点，选项 B 正确；构
造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵
新的二叉树，C 正确；哈夫曼树中任一非叶结点 P 的权值为其左右子
树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结
点 P 的左右子树根结点处于同一层的结点中，若存在权值大于结点 P
权值的结点 Q ，那么结点 Q 与其兄弟结点中权值较小的一个应该与结
点 P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶
结 点的权值一定不小于下一层任一结点的权值。
5. 某网络的 IP 地址空间为采用定长子网划分，子网掩码为则该网络
的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8
B.32, 6
C.8, 32
D.8, 30
【答案】B
【解析】子网号为 5 位，在 CIDR 中可以表示个子网，主机号为 3 位，
除去全 0 和全 1 的情况可以表示 6 个主机地址，答案为 B 。
6. 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，
也可用顺序查找，但前者比后者的查找速度（ ）。
A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减
【答案】C
【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情
况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就
快的多了。这类情况外折半都高于顺序查找。
7. 某系统有 n 台互斥使用的同类设备，3 个并发进程需要 3, 4, 5
台设备，可确保系统不发生死锁的设备数 n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B
【解析】2+3+4+1 = 10
8. 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
9. 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算
量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
10. 对有 2 个顶点 e 条边且使用邻接表存储的有向图进行广度优先遍
历，其算法时间复杂度是（ ）。 A. B. C. D.
【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其
耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵
图的存储结构时，查找每个顶点的邻接点所需时间
2024年9月2日发(作者：么雅可)
2017 年兰州交通大学电子与信息工程学院 828 数据结构考研
题库
-------------------------------------
一、选择题
1. 已知串
A.0123
B.1123
C.1231
D.1211
【答案】A 其 Next 数组值为（ ）。
【解析】KMP 算法的 next 数组建立的原则
2. 已知三叉树 T 中 6 个叶结点的权分别是 2，3, 4, 5，6，7, T
的带权（外部）路径长度最小是（ ）
A.27
B.46
C.54
D.56
【答案】B
【解析】利用三叉树的 6 个叶子结点的权构建最小带权生成树，
最小的带权路径长度为
3. 某字长为 8 位的计算机中，y 的机器数分别为已知整型变量 x 、
若整型变量
A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
y 右移一位， 【解析】将 x 左移一位，两个数的补码相加的机器数为
1 1000000, 故答案选择 A 。
4．
对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述
中，错误的是（ ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为 1 的结点
C. 树中两个权值最小的结点一定是兄弟结点
则 z 的机器数为（ ）
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
【答案】A
【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二
叉树，选项 A 错误；哈夫曼树中没有度为 1 的结点，选项 B 正确；构
造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵
新的二叉树，C 正确；哈夫曼树中任一非叶结点 P 的权值为其左右子
树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结
点 P 的左右子树根结点处于同一层的结点中，若存在权值大于结点 P
权值的结点 Q ，那么结点 Q 与其兄弟结点中权值较小的一个应该与结
点 P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶
结 点的权值一定不小于下一层任一结点的权值。
5. 某网络的 IP 地址空间为采用定长子网划分，子网掩码为则该网络
的最大子网个数、每个子网内的最大可分配地址个数分别是（ ）。
A.32, 8
B.32, 6
C.8, 32
D.8, 30
【答案】B
【解析】子网号为 5 位，在 CIDR 中可以表示个子网，主机号为 3 位，
除去全 0 和全 1 的情况可以表示 6 个主机地址，答案为 B 。
6. 当在一个有序的顺序存储表上查找一个数据时，既可用折半查找，
也可用顺序查找，但前者比后者的查找速度（ ）。
A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减
【答案】C
【解析】对于有序顺序存储表折半查找的效率较高，但是不是所有情
况下都是如此，比如要查找的元素就是第一个时，用顺序查找比它就
快的多了。这类情况外折半都高于顺序查找。
7. 某系统有 n 台互斥使用的同类设备，3 个并发进程需要 3, 4, 5
台设备，可确保系统不发生死锁的设备数 n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B
【解析】2+3+4+1 = 10
8. 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度
B. 减少缺页中断次数
C. 减少页表项所占字节数
D. 减少页表所占的连续内存空间
【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
9. 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算
量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
10. 对有 2 个顶点 e 条边且使用邻接表存储的有向图进行广度优先遍
历，其算法时间复杂度是（ ）。 A. B. C. D.
【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其
耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵
图的存储结构时，查找每个顶点的邻接点所需时间