2018年云南大学软件学院842数据结构与程序设计之数据结构考研基础五套测试题
● 摘要
目录
2018年云南大学软件学院842数据结构与程序设计之数据结构考研基础五套测试题（一） ... 2
2018年云南大学软件学院842数据结构与程序设计之数据结构考研基础五套测试题（二） ... 9 2018年云南大学软件学院842数据结构与程序设计之数据结构考研基础五套测试题（三） . 15 2018年云南大学软件学院842数据结构与程序设计之数据结构考研基础五套测试题（四） . 21 2018年云南大学软件学院842数据结构与程序设计之数据结构考研基础五套测试题（五） . 28
一、填空题
1． 二进制地址为011011110000, 大小为【答案】011011110100；011011100000
【解析】011011110000是块的起始地址，大小分别为算公式如下:
当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。
2． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
3． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行
(2)q //将当前结点作为头结点后的第一元素结点插入
4． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构(网状结构)
和其伙伴块的起始地址计和块的伙伴地址分别为:_____
5． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
6． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
二、判断题
7． 如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。
8． 串是一种数据对象和操作都特殊的线性表。（ ）
【答案】 √
【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。
9． 一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了A m*n的转置运算。（ ）
【答案】 ×
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。
10．归并排序辅助存储为O(1)（ ）
【答案】×
【解析】归并排序的辅助存储是O Cn)o
11．对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ ）
【答案】√
【解析】查找成功的情况下，顺序表和无序表的平均查找长度是相同的，对于查找失败，无序表需要查找到表尾，而顺序表不需要查到表尾就能确定，所以顺序表的查找长度小于无序表的查找长度。
12．B-树中所有结点的平衡因子都为零。（ ）
【答案】√
【解析】一棵m 阶的B-树，如果不为空，则所有的叶子结点都出现在同一层次上，所以B-树总的所有结点的平衡因子都为零。
三、单项选择题
13．某容量为256M 的存储器, 由若干4M*8位的DRAM 芯片构成, 该DRAM 芯片的地址引脚和数据引脚总数是:（ ）
A.19
B.22
C.30
D.36
【答案】A
【解析】DREAM 地址线复用, 4M 为2的22次方, 因此除2为11根, 数据线8根。因此地址引脚和数据引脚总数为19根
14．对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
【答案】B
15．要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n －1
B.n
C.n+1
D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n －1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。