2018年燕山大学信息科学与工程学院811数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 顺序栈用
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
2． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。 3． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)
4． 串是一种特殊的线性表，_____；其特殊性表现在_____；串的两种最基本的存储方式是_____、两个串相等的充分必要条件是_____。
【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等
5． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
6． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
二、判断题
7． 对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（ ）
【答案】√
【解析】形状不同的两个二叉排序树(关键字集合相同) ，在中序遍历下是输出排好序的序列，所以顺序是一致的。
8． 由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间更多。（ ）
【答案】×
【解析】希尔排序把序列分成很多小序列，对于直接插入排序，记录少时的效率会大大提高。并且序列在基本有序的情况下，直接插入排序也会提高。
9． 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ）
【答案】 ×
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
10．B-树中所有结点的平衡因子都为零。（ ）
【答案】√
【解析】一棵m 阶的B-树，如果不为空，则所有的叶子结点都出现在同一层次上，所以B-树总的所有结点的平衡因子都为零。
11．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ）
【答案】 ×
【解析】栈只是一种先入后出的存储结构。对于出栈、入栈的元素不进行修改，因此，输入序列的元素不相同，不可能得到相同的输出序列。
12．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。（ ）
【答案】×
【解析】单链表不能使用折半查找方法。折半查找主要用于数据元素有序且存储方式为顺序存储的表。
三、读写算法题
13．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。
【答案】算法如下:
求以双亲表示法作为存储结构的树的深度
深度加1, 并取新的双亲
最大深度更新
返回树的深度
’结束Depth
14．给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。
【答案】算法如下:
建立有向图的十字链表存储结构
假定权值为整型
建立顶点向量
当输入i 、j 、v 之一为0时，结
束算法运行
申请结点
弧结点中权值域
算法结束
15．设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。
【答案】算法如下:
//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称
//i记下结点个数，s 是字符栈
//P是链表的工作指针，指向待处理的当前元素
//链表前一半元素入栈