2018年杭州电子科技大学数字媒体与艺术设计学院851数据结构考研强化五套模拟题
● 摘要
一、判断题
1． 有n 个数顺序(依次) 入栈，出栈序列有Cn 种，
【答案】 √
2． 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
【答案】 √
【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。
3． 为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对己经排序的子文件进行归并排序。
4． 对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
【答案】√
【解析】形状不同的两个二叉排序树(关键字集合相同) ，在中序遍历下是输出排好序的序列，所以顺序是一致的。
5． 若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）
【答案】×
【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。
6． 倒排文件是对次关键字建立索引。（ ）
【答案】√
【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表) ，将所有具有相同次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
（ ）
二、单项选择题
7． 若用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 则关于该图拓扑序列的结论是（ ）。
A. 存在, 且唯一
B. 存在, 且不唯一不唯一
C. 存在, 可能不唯一
D. 无法确定是否存在
【答案】C 。
【解析】图的基本应用--拓扑排序, 用邻接矩阵存储有向图, 矩阵中主对角线以下的元素均为零, 说明该图为有向无环图, 所以其拓扑序列存在, 但不一定唯一,
如图的邻接矩阵为
在两个拓扑序列。
8． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）.
A. 连续结构
B. 索引结构
C. 链式结构且磁盘块定长
D. 链式结构且磁盘块变长
【答案】B
【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问. 链式结构的优点是文件易于扩展，缺点是不易随机访问. 索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展.
9． 某容量为256M 的存储器, 由若干4M*8位的DRAM 芯片构成, 该DRAM 芯片的地址引脚和数据引脚总数是:（ ）
A.19
B.22
C.30
D.36
【答案】A
【解析】DREAM 地址线复用, 4M 为2的22次方, 因此除2为11根, 数据线8根。因此地址引脚和数据引脚总数为19根
10．假定用若干个位的芯片组成一个8K ×8位的存储器, 则地址0B1FH 所在芯片的最小地址是（ ）。
A.0000H
B.0600H
C.0700H
D.0800H
【答案】D
, 则存
【解析】由若干芯片构成存储器, 采用字和位同时扩展方法。8片
组2个芯片, 各组芯片的地址分配分别为:
第1组,
第3组, ; 第2组, ; 第4组, ; 。 位的芯片分成4组, 每
地址0BIFH 处于第2组内, 其芯片的最小地址为0800H 。
11．数据序列(8，9，10，4，5，6，20，1，2) 只能是下列排序算法中的（ ）的两趟排序后的结果。
A. 选择排序
B. 起泡排序
C. 插入排序
D. 堆排序
【答案】C
【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。
12．4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7 B.
C.15
D.16
【答案】C
【解析】Hanoi 问题总移动次数为:2M 次。
13．float 型数据通常用IEEE754单精度浮点数格式表示。若编译器将float 型变量x 分配在一个32位浮点寄存器FR1中,
且
A.C1040000H
B.C2420000H
C.C1840000H
D.C1C20000H
【答案】A , 则FR1的内容是（ ）。
【解析】首先将十进制数转换为二进制数-1000.01,
接着把它写成规格化形式
IEEE754标准) , 然后计算阶码的移码=偏置值+
阶码真值(按, 最后短浮点数代码:数符位=1, 阶码=10000010, 尾数00001000000000000000000, 写成十六进制为C1040000H 。选项D 是一个很容易被误选的选项, 其错误在于没有考虑IEEE754标准中隐含最高位1的情况, 偏置值是128。
相关内容
相关标签