2017年河北大学数学与信息科学学院907数据结构考研冲刺密押题
● 摘要
一、选择题
1． 若一个有向图具有拓扑排序序列，那么它的邻接矩阵必定为（ ）。
A. 对称矩阵 B. 稀疏矩阵 C. 三角矩阵 D. —般矩阵 【答案】C
【解析】在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为改图的一个拓扑排序：①每个顶点出现且出现一次；②若顶点在序列中排在顶点B 的前面，则在 图中不存在从顶点B 到顶点A 的路径。由拓扑排序的性质知，有向图的邻接矩阵必定为三角矩阵。
2． 假定变量i 、f 和d 的数据类型分为int 、float 和double （int 用补码表不，float 和double 分，已知别用IEEE754单精度和双精度浮点数格式表示）
位机器中执行下列关系表达式，则结果为“真”的是（ ）。
A. 仅I 和II B. 仅I 和III C. 仅II 和III D. 仅III 和IV 【答案】B
II 中，f 的数据类型从float 【解析】数据类型不同的数据在运算之前需要进行数据类型的转换。转换为int 时，小数点后面4位会丢失，故II 的结果不为真；IV 中，d+f时需要对阶，对阶后f 的尾数有效位被舍去而变为0, 故d+f仍然为d , 再减去d 后结果为0, 故IV 的结果也不为真。I 和II 进行数据类型的转换的时候并没有改变其值。
3． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。
A. 递归次数与初始数据的排列次序无关
B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数
若在32
D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D
【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）过程的二叉树如下图所示。
在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。
4． 处理外部中断时，应该由操作系统保存的是（ ）。
A. 程序计数器（PC ）的内容 B. 通用寄存器的内容 C. 快表（TLB ）的内容 D.Cache 中的内容 【答案】B
【解析】外部中断处理过程首先要保护现场，使得中断处理完后能够恢复程序的状态继续执；②由中断服务程序保行。保护现场有两个含义：①由中断隐指令保存程序的断点（程序计数器）存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
5． 单链表中，增加一个头结点的目的是为了（ ）。
A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现
D. 说明单链表是线性表的链式存储 【答案】C
【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。
6． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改 B. 查找和索引
C. 索引和修改 D. 建立和删除 【答案】A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
7． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A.24，10，5 和24，10，7 B.24，10，5 和24，12，7 C.24，10，10和24，14，11 D.24，10，10和 24，14，6 【答案】D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B 项错误。同理，通过第三个被访问的节点排除A 项。C 项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C 项错误。D 项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
8． 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
中，则在B 中确定
的位置k 的关系为（ ）。
【答案】B
【解析】将n 阶对称矩阵存人一维数组中，一维数组的大小需为
中，当
时，i 与k 的关系为
对n 阶对称矩阵
A
以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组
9． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ , 每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）（ ） ：
A. B. C. D. 【答案】C
【解析】总线带宽=总线工作频率X （总线宽度/8）, 由于地址线与数据线复用，所以在两次
相关内容
相关标签