2017年北京市培养单位光电研究院864程序设计之数据结构考研仿真模拟题
● 摘要
一、填空题
1．
设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】
2． 设有个结点的完全二叉树顺序存放在向量中，其下标值最大的分支结点为_____。
【答案】
【解析】最大的分支结点是最后一个叶子结点的父结点。
3． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
4． 在一棵m 阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。
【答案】
【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是最少
5． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测
的次数最小。总次数为
6． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
7． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
8． 串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
9． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为
和
的结点在顺序存储中的下标为
和
。
10．已知如下程序段：
语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。
【答案】（1）n ＋1 （2）n
（3）n （n ＋3）/2 （4）n （n ＋l ）/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4......
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
，
则结点
和
在同一层上的条件是
＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。
二、判断题
11．二叉树中除叶结点外，任一结点点的值大于等于该结点
【答案】×
【解析】二叉排序树按中序遍历的结点序列是从小到大的因为某结点的左子树根结点不一定是它的中序前驱，可能会出现某结点的左子树根结点的右子树上的值大于这个结点；其右子树根结点也不一定是它的中序后继。可能会出现右子树根结点的左子树的值小于这个结点。
12．在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）
【答案】×
【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转
13．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
【答案】√
【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
14．二维以上的数组其实是一种特殊的广义表。（ ）
【答案】√
【解析】广义表是线性表的推广。广义表中的元素还有可能是广义表。对于维数大于二的数组，它在某一维上的元素还是数组。符合广义表的定义，因此二维以上的数组其实是一种特殊的广义表。
15．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
16．顺序存储结构的主要缺点是不利于插入或删除操作。（ ）
【答案】
其左子树根结点的值小于该结点的值；其右子树根结
的值，则此二叉树一定是二叉排序树。（ ）