2017年武汉纺织大学数学与计算机学院848数据结构考研强化模拟题
● 摘要
一、填空题
1． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
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． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
【答案】（1）（2）（3）（4）（5）
4． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。
【答案】n （n-l ）/2
【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。
5． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
6． 建立索引文件的目的是_____。
【答案】提高查找速度
7． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
8． 模式串的next 函数值序列为_____。
【答案】01122312
9． 组成串的数据元素只能是_____。
【答案】字符
10．设有个结点的完全二叉树顺序存放在向量
【答案】
中，其下标值最大的分支结点为_____。
【解析】最大的分支结点是最后一个叶子结点的父结点。
二、算法设计题
11．在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L , 且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。
顺序存储结构的线性表描述为：
【答案】算法如下：