2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研核心题库
● 摘要
目录
2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研核心题库（一） ... 2 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研核心题库（二） . 15 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研核心题库（三） . 28 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研核心题库（四） . 39 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研核心题库（五） . 50
第 1 页，共 61 页
一、单项选择题
1． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。
A. 存在, 且唯一
B. 存在, 且不唯一不唯一
C. 存在, 可能不唯一
D. 无法确定是否存在
【答案】C 。
【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,
如图的邻接矩阵为
在两个拓扑序列。
2． 下列不是设计一个“好”的算法应考虑达到的目标是（ ）。
A. 可行的
B. 健壮的
C. 无二义性的
D. 可读性好的
【答案】A
【解析】设计一个“好”的算法应考虑以下目标:正确性；可读性；健壮性；效率和低存储量需求。可行性是算法的五个基本特征之一，不是一个好的算法该达到的目标。
3． 设有向图G=(V, E) , 顶点集,
边集,
若从顶点V0开始对图进行深度优先遍历, 则可能得到的不同遍历序列个数是（ ）。
A.2
B.3
C.4
D.5
【答案】D
【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索, 所以可能得到的不同遍历序列分别是:
第 2 页，共 61 页 , 则存
①
④
' ; ②; ⑤; ③。
;
4． 设有一棵3阶B 树, 如下图所示。删除关键字78得到一棵新B 树, 其最右叶结点所含的关键字是（ ）。
图 3二叉树图
A.60
B.60, 62
C.62, 65
D.65
【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于
而与该结点相邻的右兄弟(或左兄弟) 结点中的关键字数目大于
(或最大) 的关键字上移至双亲结点中, 而将双亲结点中小于(或大于) 且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下, 其最右叶结点所含的关键字是65。
, , 则需将其兄弟结点中最小
5． 在支持多线程的系统中, 进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段
B. 进程P 中打开的文件
C. 进程P 的全局变量
D. 进程P 中某线程的栈指针
【答案】D
【解析】现代操作系统中, 进程是资源分配的基本单位, 线程是处理机调度的基本单位。因此, 进程是线程运行的容器, 本题中, 进程的代码段, 进程打开的文件, 进程的全局变量等都是进程的资源, 唯有进程中某线程的栈指针是属于线程的, 那么, 属于进程的资源可以共享, 属于线程的栈是独
第 3 页，共 61 页
享的, 不能共享。
6． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
【答案】C
【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标，列标，值) 。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。
7． 某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ）
A.100
B.200
C.400
D.600
【答案】C
【解析】基准程序的
。 , 为1200MHz , 该机器的MIPS 为计算机的主频为
8． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C
【解析】Hanoi 问题总移动次数为:2M 次。
9． 以下说法错误的是（ ）。
(1)算法原地工作的含义是指不需要任何额外的辅助空间
第 4 页，共 61 页 。
相关内容
相关标签