2018年云南大学软件学院904计算机程序设计[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
2． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为_____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
3． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
4． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。
【答案】4；2
5． 在单链表中设置头结点的作用是_____。
【答案】方便运算
6． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
二、判断题
7． 为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）
【答案】 √
【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。
8． —个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）
【答案】×
【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序， 这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则 称这种排序算法是稳定的；否则称为不稳定的。
9． 若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
10．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
【答案】√
【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。
11．在链队列中，即使不设置尾指针也能进行入队操作。（ ）
【答案】 √
【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。
12．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
【答案】×
【解析】排序的稳定性指:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri 在rj 之前，而在排序后的序列中，ri 仍在ij 之前，则称这种排序算法是稳定的；否则称为不稳定的。
三、单项选择题
13．有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（ ）。
A.543612
B.453126
C.346521
D.234156
【答案】C
【解析】根据栈的后进先出的特点，对于C 选项中前两个元素得出栈顺序可以看出，4在5和6前先出栈，又根据入栈顺序，4在5和6后入栈，因此4出栈时，5和6必定在栈内，且5在6之上，所以出栈时5要比6先出枝。
14．和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现栈满的情况
B. 通常不会出现栈空的情况
C. 插入操作更容易实现
D. 删除操作更容易实现
【答案】A
15．若平衡二叉树的高度为6, 且所有非叶结点的平衡因子均为1, 则该平衡二叉树的结点总数为（ ）。
A.12
B.20
C.32
D.33
【答案】B 。
【解析】本题的实际问题是, 具有6层结点的平衡二叉树含有最少的结点数是多少。
深度为h 的平衡二叉树中含有的最少结点数, 有
由此可得。对应的平衡二叉树如下图所示。
表示
16．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。
17．串是一种特殊的线性表，其特殊性体现在（ ）。
A. 数据元素是一个字符
B. 可以顺序存储
C. 数据元素可以是多个字符
D. 可以链接存储
【答案】A