2017年大连大学国家863空间信息技术初试辅导(2016年)之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 线性表
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为
2． 已知如下程序段：
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素
平均需要移动元素的个数是_____。
语句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。 3．
已
知
求REPLACE （S ，V , m ）=_____。
【答案】
4． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
5． 阅读下列程序说明和裎序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。
存放还没有转换过的结点，它的栈顶指针为
。
（1）
{（2）
If （ （3） ）
}
}}
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。
6． 假定查找有序表中每个元素的概率相等，则进行折半查找时的平均查找长度为_____
【答案】37/12
【解析】折半查找时每个的次数如表所示：
表
平均查找次数为
7． 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2；4；3
【解析】二分法查找元素次数列表
查
找100是找到115就停止了。
8． 对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n （n-1）/2
【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n（n-l ）/2。
9． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
10．
设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】
二、算法设计题
11．已知指针P 指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA （P ，q ）, 该算法寻找结点 P 的父亲结点q ，设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG , LLINK , INFO , RL1NK , RTAG ）, 且规定线索树的最左下结点的LLINK 域和最右下结点的RLINKt 域指向表头。
【答案】算法如下：
在中序线索树t 上，求结点p 的双亲结点q
{q=p; //暂存
//找P 的中序最右下的结点
//顺右线索找到q 的后继（P 的袓先结点）
//若后继是头结点，则转到根结点
根结点无双亲
}//找最右结点的过程中回找到
P
12．已知递增有序的单链表A , B 分别存储了一个集合，请设计算法以求出两个集合A 和B 的差，并以同样的形式存储，同时集A-B （即仅由在A 中出现而不在B 中出现的元素所构成的集合）返回该集合的元素个数。
【答案】算法如下：
//准备到左子树中找
P